Computer Chess Club Archives


Search

Terms

Messages

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

Author: vladan

Date: 14:40:31 08/01/04

Go up one level in this thread


On August 01, 2004 at 14:12:23, Christophe Theron wrote:

>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.
>
>
>
>We call this a "quiescence search" or "QSearch". This term has been used for the
>last 50 years I think.
>
>When you publish papers, it is a good idea to use terms that are commonly used
>in your field of research.
>
>Or maybe I do not understand what you extender does?
>
>
>
>
>>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.
>
>
>
>If I understand correctly, you use your hash table only for move ordering. You
>do not use it to produce direct cut-offs. Correct?
>
>
>
>    Christophe
>
>
>
>
>>
>>
>>Best regards,
>>
>>Vladan      (Axon programmer)




Hi Christophe,


You have understood everything, thanks for the very competent previous comments.


"Extender" is the name of our Qsearch procedure   (sorry, I always think like a
programmer :)



Our current strongest version of Axon engine (about 2470-2500 ELO) use 6-byte
hash with no direct cutoffs. It is very fast but not selective enough. Best-move
hash is able to increase only number of Alfa-Beta cutoffs. But, as the
compensation, this extra-compressed hash system could store millions of
positions in operating memory - our record is 32 millions using Windows 98 on
256 DDR Ram machine. (not 2000 or XP, they use too much memory for their
needs!).


Now, we try to find new optimal hash solutions for our program. In my opinion
the right combination is probably:

1. Zobrist 64-bit in normal search, where all techniques (direct hash pruning of
course) will be used. Draw detection in that case will be performed using
standard approaches.

2.   Our new approach using variant strings could be performed in Qsearch, in
the nodes where Zobrist key is not calculated.


Next versions of Axon will have this hybrid hash architecture; we'll test it.


The main intention of the paper is to explain the new solution for the
draw-detection problem when it is not possible to use hash keys. This is the
first implementation of the new class of algorithms; of course some improvements
could be included.

We hope that new Chess Tiger will have benefits from the variant string
approach, if you decide to use it.



best regards,

Vladan

(Axon programmer)




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.