Author: Albert Silver
Date: 13:18:27 12/21/99
Go up one level in this thread
On December 21, 1999 at 15:34:26, Vincent Diepeveen wrote:
>How efficient was the search of Deep Blue?
>Let's compare Diep searching FULLWIDTH (so no pruning at all!)
>with Deep Blue fullwidth.
>
>There are not many log files from Deep Blue available.
>
>
>----------------------
>Played 36. axb5 with 4 moves and 40:28 minutes remaining.
>Evaluating based on expected reply 36... axb5
>Starting at iteration 8.
>Ply 8: 0:01 eval >30 (fail high): Qb6 Rxa2 Rxa2 Bc7 Qe6 Kh8
> Be4 Rb8 Ra6 Qd8 d6 Bb6
>Ply 8: 0:04 eval 53: Qb6 Rxa2 Rxa2 Bc7 Qe6 Kh8
> Be4 Rb8 Ra6 Qd8 d6 Bb6
>Ply 9: 0:09 eval 53: Qb6 Rxa2 Rxa2 Bc7 Qe6 Kh8
> Be4 Ra8 Kh2 Rb8 g3 Qf8
>Ply 10: 0:33 eval 55: Qb6 Rxa2 Rxa2 Bc7 Qe6 Kh8
> Be4 Qf8 Kh1 Bd6 Ra6 Rd8 Ra7
>Ply 11:
>36... axb5 played by Black (correct guess). Continuing to think on my clock...
>Set planned thinking time to 199 sec. Maximum time ("panic time") to 709 sec.
>Ply 11: 1:24 eval 32: Qb6 (no principal variation given)
>Ply 11: 3:02 eval 37: Be4 Rcb8 g3 Qd8 Ra6 Rxa6 Rxa6 Bc7 Rxf6
>(Amir Ban: This PV is ridiculous. I don't know what it means).
>Ply 12:
>Timeout occured after 199 sec.
>Ply 12: 3:19 eval 37: Be4 Rcb8 g3 Qd8 Kg2 Rxa2 Rxa2 Bc7
> Qa7 Bb6 Qa6 Qd7
>(Amir Ban: Since the search was timed out, I don't know where this new PV
>comes from. The eval did not change.).
>37. Be4 played.
>--------------------------
>
>I guess the PV comes from the hashtable at 12 ply, after getting a timeout.
>So this means that Deep Blue is still busy searching at 12 ply. The PV
>at 11 ply is probably easily explainable as a bound. It's perhaps a PV that's
>just quoted as it saw Be4 was better than Qb6 (searching with window
>[32;33]?)
>
>Hsu writes in a paper that Deep Blue searched near 1 billion nodes a second
>but never came over that number.
>
>Below is the full log of DIEP searching fullwidth
>at this position. Note that DIEP doesn't have singular extensions turned on,
>and gets all moves out of the hashtable.
>
>To finish ply 11 DIEP gets roughly 18.5k nodes a second
>needing 49,957,263 positions and 2701.11 seconds.
>
>At a machine never getting 1 billion but getting over it, let's say
>800 million nodes a second, which just starts with 12 ply after more
>than 3 minutes, we talk about next estimation:
> 3 minutes * 800 M/s = 180 * 800,000,000 = 144 billion nodes
> Diep needs 49957263 nodes. Let's see how many more nodes Deep Blue
> needed:
> 144 B / 50M = 144000 / 50 = 2880 times more nodes needed by Deep Blue.
>
>In the same article Hsu writes that in the hardware deep blue isn't doing
>forced moves extensions,
That's correct, he says it was done through software: "During the 1997 match,
the software search extended the search to about 40 plies along the forcing
lines, even though the nonextended search reached only about 12 plies." He also
mentions that "The software portion of the search can be arbitrarily selective
without slowing down the system."
Albert Silver
so that means that this search of DIEP picks up
>a lot of more tactics there, where i'm doing ESPECIALLY near my leafs
>extensions.
>
>In the fullwidth version there is no threat score, so i only extend some on
>passed pawns, which are plenty there the last 4 ply especially...
>
>Search is done at a parallel version of DIEP running at a single PII450
>processor (hence the '(0)' )
>Hashtable size: 80mb.
>
> 00:00 6 (0) 1 0.12 Ra2xa8 Rc8xa8
> 00:00 10 (0) 1 0.20 Qf2-g3 Ra8xa2 Ra1xa2
> 00:00 13 (0) 1 0.23 Qf2-b6
> 00:00 17 (0) 1 0.45 Ra2-a7 Ra8xa7 Ra1xa7
> 1 49 0.03
> 00:00 121 (0) 2 0.27 Ra2-a7 Qe8-d8
> 2 354 0.06
> 00:00 542 (0) 3 0.38 Ra2-a7 Qe8-d8 Bc2-e4 Ra8xa7 Ra1xa7
> 3 2526 0.21
> 00:00 4702 (0) 4 0.25 Ra2-a7 Ra8xa7 Ra1xa7 Qe8-d8
> 4 8648 0.61
> 00:00 12777 (0) 5 0.23 Ra2-a7 Ra8xa7 Ra1xa7 Rc8-a8 Ra7-b7
> 5 32646 1.94
> 00:04 72860 (0) 6 -0.01 Ra2-a7 Qe8-d8 Ra7-a6 Ra8xa6 Ra1xa6
> Rc8-a8 Ra6xa8 Qd8xa8 Qf2-b6
> 00:06 100417 (0) 6 0.33 Qf2-b6 Ra8xa2 Ra1xa2 Qe8-d7 Ra2-a7
> Rc8-c7 Ra7-a8 Kg8-h7
> 6 140127 8.54
> 00:11 199896 (0) 7 0.33 Qf2-b6 Ra8xa2 Ra1xa2 Qe8-d7 Ra2-a7
> Rc8-c7 Ra7-a8 Kg8-h7
> 7 435591 23.26
> 00:35 650814 (0) 8 0.51 Qf2-b6 Ra8xa2 Ra1xa2 Bd6-c7 Qb6-e6
> Qe8xe6 f5xe6 Bc7-d6
> 8 1181720 64.34
> 01:32 1686387 (0) 9 0.44 Qf2-b6 Ra8xa2 Ra1xa2 Bd6-c7 Qb6-c5
> Bc7-b8 Qc5-e3 Qe8-f7 Bc2-e4
> 9 4312903 210.31
> 04:56 5919532 (0) 10 0.37 Qf2-b6 Ra8xa2 Ra1xa2 Bd6-c7 Qb6-e6
> Kg8-f8 Kg1-f1 Rc8-d8 Ra2-a7 Qe8-d7 Bc2-e4
>10 11792234 642.73
> 14:45 15717139 (0) 11 0.32 Qf2-b6 Ra8xa2 Ra1xa2 Bd6-c7 Qb6-e6 Kg8-h8
> Kg1-h1 Rc8-b8 Ra2-a6 Qe8-d8 d5-d6
>11 49957263 2701.11
> 59:11 63799298 (0) 12 0.41 Qf2-b6 Ra8xa2 Ra1xa2 Bd6-c7 Qb6-e6 Kg8-f8
> Kg1-h1 Qe8xe6 f5xe6 Kf8-e7 Ra2-a6 Bc7-d6
>12 136729687 8367.18
> 02:56:30 171055530 (0) 13 0.31 Qf2-b6 Ra8xa2 Ra1xa2 Bd6-c7 Qb6-e6
> Kg8-f8 Kg1-f1 Qe8xe6 f5xe6 Kf8-e7
> Ra2-a6
>13 521919372 29234.39
> 10:13:04 645188658 (0) 14 0.51 Qf2-b6 Ra8xa2 Ra1xa2 Bd6-c7 Qb6-e6
> Kg8-f8 Kg1-f1 Qe8xe6 f5xe6 Kf8-e7
> Ra2-a6
>
>So branching factor is about 3 of DIEP in this position (obviously
>because most lines lead to an endgame).
>
>
>To finish 13 ply DIEP needs roughly 520M nodes.
>To finish 11 ply Deep Blue needed 144 billion nodes roughly.
>
>Let's now see how deep DIEP would search with bf=3 with 144 billion nodes.
> extra depth = log( 144000/520 ) / log ( 3 ) = 5.12 ply
>
>So 13 ply + 5 ply = 18 ply.
>
>Diep would finish 18 ply here fullwidth, starting with 19.
>Compare that with Deep Blue getting 11 ply here fullwidth, this considering
>that in the leafs DIEP sees a lot more than Deep Blue.
>
>Now you might cry about DIEP not having singular extensions?
>Well that's no problem. In the 11 ply search deep blue got, it could
>only extend 11 - 5 = 6 ply (not extending in root i suppose and for sure
>not extending last 4 ply in hardware). Secondly i remember some work
>done on extensions that prevents it from keeping extending the same move.
>So Deep Blue would see (not counting checks of course as those get
>extended anyway in both programs): 11 + 6 = 17 ply at maximum.
>
>Now DIEP searches without singular extensions with the same number of nodes
>another ply deeper, not to mention that interesting lines don't have too
>much singular extensions!
>
>Vincent
This page took 0.02 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.