Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Draw Detection by Move Repetition Procedure -- Comments

Author: Rémi Coulom

Date: 11:19:21 08/01/04

Go up one level in this thread


On August 01, 2004 at 13:51:47, vladan wrote:

>
>
>
>
>Hi Remi,
>
>
>"Extender" is Alfa-Beta procedure we use in terminal nodes instead of static
>evaluator. Only a fraction of all generated moves are computed (captures, some
>checks and promotion moves). It is very important to optimize this procedure as
>much as possible.
>
>
>Hash system used in Axon is simple:
>
>6 bytes (48 bit):
>
>
>24 bit - fractional position key,
>16 bit - best move,
>8 bit - other flags.
>
>
>Using this compressed hash system we have tested Axon with 32 million
>positions/best moves memory. All nodes (included ones generated by the extender)
>could be supplied with best moves efficiently.
>
>
>Of course, 24-bit is not enough to determine positions exactly (like Zobrist
>64-bit hash); different positions could generate the same 24-bit hash key. But
>those cases (hash failure) are not fatal for searcher - they only could decrease
>quality of move ordering. But if the best move is found, Alfa-Beta, Null-Move
>and Extender procedures could make a great number of cutoffs.
>
>This is the main reason why our hash could be used for searcher and not for
>draw-detector.
>
>
>Best regards,
>
>Vladan      (Axon programmer)

If I understand correctly, this means that you do not store an evaluation in the
hash table, and perform no pruning in case of a transposition. I agree that in
this case, hash collisions should be no problem. But this seems to be a very bad
idea, especially in the endgame. You may gain a little node rate, but you lose a
lot by not pruning transpositions.

The numbers of nodes reported on your paper on this WAC position demonstrate
this:
[D]R7/P4k2/8/8/8/8/r7/6K1 w - -

Here is the output of TCB (P4 @ 1.7 GHz):
00:00:00,00         0 ------ Depth = 1
00:00:00,00         1   +147 1. Kh1
00:00:00,00         2   +153 1. Kf1
00:00:00,00         3   +153 1. Kf1
00:00:00,00        23 ------ Depth = 2
00:00:00,00        48   +150 1. Kf1 Ke6
00:00:00,00        81 ------ Depth = 3
00:00:00,00       311   +154 1. Kf1 Ke7 2. Ke1
00:00:00,00       503 ------ Depth = 4
00:00:00,01       773   +153 1. Kf1 Ke7 2. Ke1 Ke6
00:00:00,01      1054 ------ Depth = 5
00:00:00,01      2627   +154 1. Kf1 Ke7 2. Ke1 Kd7 3. Kd1
00:00:00,01      3101 ------ Depth = 6
00:00:00,02      6313   +153 1. Kf1 Ke7 2. Ke1 Kd7 3. Kd1 Kd6
00:00:00,02      6877 ------ Depth = 7
00:00:00,02     10687   +151 1. Kf1 Ke7 2. Ke1 Kd7 3. Kd1 Ke7
00:00:00,03     14380   +152 1. Rh8
00:00:00,04     26340   +490 1. Rh8 Ra1+ 2. Kf2 Ke6 3. a8=Q Rxa8 4. Rxa8 Ke5
00:00:00,04     27152 ------ Depth = 8
00:00:00,06     42439   +495 1. Rh8 Ra1+ 2. Kf2 Ra2+ 3. Ke3 Ra3+ 4. Kd4 Ra4+
                             5. Kc5 Ra5+ 6. Kb6 Ra4 7. a8=R
00:00:00,06     44042 ------ Depth = 9
00:00:00,10     72411   +495 1. Rh8 Ra1+ 2. Kf2 Ra2+ 3. Ke3 Ra3+ 4. Kd4 Ra4+
                             5. Kc5 Ra5+ 6. Kb6 Ra4 7. a8=R Rxa8
00:00:00,10     74134 ------ Depth = 10
00:00:00,14    113237   +495 1. Rh8 Ra1+ 2. Kf2 Ra2+ 3. Ke3 Ra3+ 4. Kd4 Ra4+
                             5. Kc5 Ra5+ 6. Kc6
00:00:00,15    118113 ------ Depth = 11
00:00:00,21    165614   +495 1. Rh8 Ra1+ 2. Kf2 Ra2+ 3. Ke3 Ra3+ 4. Kd4 Ra4+
                             5. Kc5 Ra5+ 6. Kc6 Ra6+ 7. Kb7 Ra5 8. a8=Q Rxa8
                             9. Rxa8
00:00:00,22    167809 ------ Depth = 12
00:00:00,37    329252   +501 1. Rh8 Ra1+ 2. Kf2 Ra2+ 3. Ke3 Ra3+ 4. Kd4 Ra4+
                             5. Kc5 Ra5+ 6. Kb6 Rxa7
00:00:00,39    357057 ------ Depth = 13

So, TCB needs 357057 nodes to complete ply 12, while your programs needs
8524217! Also note that the right move is found at depth 7, with the right
evaluation.

Rémi



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.