Author: Vincent Diepeveen
Date: 12:34:26 12/21/99
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, 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.