Author: Christophe Theron
Date: 10:51:46 08/02/04
Go up one level in this thread
On August 01, 2004 at 17:40:31, vladan wrote:
>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!).
In Chess Tiger the size of the main hash table entries is 12 bytes. I store much
information than you do and use it to produce direct cutoffs (by transposition
detection).
As doubling the size of the hash table typically speed up the engine by 6%, I
think that using 12 bytes instead of 6 and using the information to produce
direct cutoffs is more efficient.
>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.
I have found that using the hash table during QSearch was still the most
efficient approach, but this could change for a program with a faster QSearch
than mine.
Ultimately, and depending how many non-capture moves your QSearch generates, the
best approach could be to have a very FAST QSearch that computes less positional
information and that does not use hashing at all.
>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)
I would not use your variant strings approach because I believe that the
algorithm I have recently published here is more efficient.
However I must admit that it is by reading your paper that I found this "piece
vector sum" algorithm. So thank you very much for publishing it.
Christophe
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.