Author: Guido Schimmels
Date: 07:47:17 05/12/98
Go up one level in this thread
On May 11, 1998 at 15:11:14, Vincent Diepeveen wrote:
>
>On May 11, 1998 at 11:47:08, Robert Hyatt wrote:
>
>>On May 11, 1998 at 10:20:27, Vincent Diepeveen wrote:
>>
>>>
>>>On May 11, 1998 at 09:06:05, Guido Schimmels wrote:
>>>
>>>>>The only addition I would make to this report is a remark on the odd
>>>>>nature of the PV for Qb6 at ply 10. GM Ronen Har-Zvi pointed out to me
>>>>>that the move Qa7 in this PV is a simple blunder. How such a move can
>>>>>appear in a PV is just one more mystery.
>>>>
>>>>The DB outputs of game 2 you've presented here, have already been
>>>>discussed
>>>>in an issue of the german magazine "CSS" quite some time ago.
>>>>The author says, DB does not propagate the PV from the leaves to
>>>>the root, as most PC-programs do. In order to save time, DB simply
>>>>looks up the PV in the hashtable, which he thinks explains for some
>>>>weird PV's.
>>>
>>>I'm doing this to: i only look in the hashtable. You get exactly
>>>the same PV. the 2 advantages are:
>>> -it is faster
>>> - sometimes you get a little longer PV because of transpositions that
>>> extend your PV.
>>>>Guido
>>
>>
>>No you don't get "exactly the same PV". Often you get one *much
>>shorter*
>>because a critical PV node was overwritten by something that was
>>searched
>>later.
>> That is *the* problem with using the TT for PV moves... Unless
>>you
>>either search very slowly or have a huge TT so you never have to replace
>>anything...
>
>>Backing it up from the tips is much more reliable, but DB can't do this
>>because the hardware doesn't have a way to pass back a variable amount
>>of
>>information.. just best move and best score... The software search can
>>back up a PV, but when they hit the hardware part, it stops...
>
>Correct when they hit the hardware then it stops.
>So assuming 32 processors which each search 4 ply, then
>how much nodes do we get when we search say 14 ply?
>
>I think you can store these tuples quite easily in few gigabyte RAM.
>You might even want to hand count them.
>
>So there loading factor is very low. If they additional have a say 8
>probe or more,
>then they're doing much better than my program.
>
>Because after few hours of search with 8 probe i still get a long PV
>which
>is at least as long as the pv backed up by arrays would be. In fact it
>sometimes is longer.
>
>If you DON'T get the same PV because of TT overwrite then there is a
>bug in your 8 probe. Perhaps there are even more bugs in your program
>then.
>
>Because the depth of the PV is always as big or bigger than the tuple
>that would replace it.
>
>The chance that it gets replaced is so terrible little.
>
>It can happen when you use nullmove that you get the same position
>at a lower depth and cannot give a cutoff. This can take care that if
>there is
>a bug in your hashtable which causes an overwrite that a stupid move
>gets stored, because it was a nullmove, so the scores you got back
>indicate that the most stupid move was in fact good as the opponent
>ply after it nullmoved also.
>However DB doesn't use nullmove, so the only scenario which can
>disturb PV's doesn't work for them.
>
>Now in Diep i do use nullmove, and the better my search is beyond the
>PV the better the PV.
>
>When we look to DB out put, then we see clearly some stupid moves
>near the leafs.
>
>This means that after that move their search was kind of silly causing
>that
>move to come into the hashtable.
>
>Vincent.
Vincent, I agree with you, if DB was a single-CPU system, reconstructing
the PV from hash as not beeing critical. I do this as well. I do not
even
have any problems with part of the PV getting overwritten, which you
have
been discussing with Bob. I use an enhanced version of the Belle/Crafty
hashing approach, where I have three kind of tables:
1. depth-priority-replacement (8 byte/entry)
2. always-replace (8 byte/entry)
3. PV-table (16 byte/entry)
The 8-byte record works this way:
32-bit key
9-bit move
15-bit score
6-bit depth
1-bit flag (upper_bound/lower_bound)
1-bit age
At the beginning of the search I do as follows:
CopyPVTableToTT();
ClearPVTable();
pv_count = 0;
Storing of TRUE-nodes into the depth-priority-table:
table->key = key; /* 32-bit */
table->depth = 63 /* 63 == max_depth+3 */
table->score = pv_count;
pvtable[pv_count]->address = hash_address; /* 32-bit */
pvtable[pv_count]->key = hash_key; /* 32-bit */
pvtable[pv_count]->score = score;
pvtable[pv_count]->mv = bestmove;
pvtable[pv_count]->depth = depth;
++pv_count;
Retrievial:
if(table->key == key) {
if(table->depth == 63) { /* true */}
else {
if(table->flag) {/* upper_bound */}
else {/* lower_bound */}
}
}
(My real code looks a lot different than this of course, but for
the sake of simplicity I didn't show all the shifting and masking here)
As I use PVS, the PV-table can be very very small.
This method has some more advantages. The PV-table does hold
every position that was 'true' at least one time during the search.
Normally when you revisit a true-node and it fails high/low then, you
loose this information. But this information is of high value, you
can do a lot of things with it.
Ok Vincent, but now back to Deep Blue.
DB's search/hashing is much different. The 512 ASICs are distributed to
32
boards, each containing 16 of them plus an additional RISC-CPU at 120
mhz.
(AFAIK)
I don't know, how the boards/RISC-CPU's manage the hashing (one big
table
or 32 small tables), I have no kind of experience at parallel computing
anyway, but the complexity of DB might explain a lot of things that look
strange to us PC-programers.
PS:
I'm not defending IBM here.
I'm not very happy about the circumstances of the match - to say the
least.
Nor I'm happy about the way IBM has behaved since then.
I don't want to be naive, but the way IBM is exploiting their success
upsets
me a lot.
When I read in computer-magazines:
'Deep Blue is currently doing some molecular engineering',
I don't know how I should call this. They are fooling the public.
What is the sence of life, the universe and all the rest ?
Deep Thought: 42 !
What is the sequence of a protein katalyzing the synthesis of alcohol ?
Deep Blue: e4 !
'You may call this cheating, but I can impossibly comment on that'
(Francis Urquart, 'House of Cards' (freely citated))
Guido
This page took 0 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.