Computer Chess Club Archives




Subject: Re: Detecting Draws using a Small Hash Table?

Author: Vincent Diepeveen

Date: 16:18:51 02/20/02

Go up one level in this thread

On February 20, 2002 at 16:39:58, Uri Blass wrote:

>On February 20, 2002 at 13:10:01, Vincent Diepeveen wrote:
>>On February 20, 2002 at 09:19:20, Uri Blass wrote:
>>sounds very buggy to me.
>>easier is storing an array with hashcodes. goes very fast.
>>you can even skip step 2.
>>what you do is pretty hard and not very smart IMHO.
>I agree it was not easy and I agree that hash tables are probably better but I
>wanted to get my program to participate in the 5th division of the winboard
>engines and one of the conditions was repetition detection.

no no i do not mean hashtable. i mean ARRAY with hashcodes

all you have to do is:

  for f=current move to 1   f = f -2;
    if( hashcode[f] == currenthash )

of course bugfix the above for captures and such (though
there is no need there actually) and for simplicity i'm
using an array here instead of a pointer. Also note that
the above thing is hell slower than a solution where you
do f += 2; because then one cache line is all you  might need,
now you might need more than one cache line (not sure though).

now if you make a move all you have to do is:

  *hashcur++ = currenthash;

undoing a move add:


I always WONDER why such fast and simple solutions are hardly
posted to CCC. Well i'll shut up about move generation and other
stuff. Simpler is usually faster LOSSLESS!

Hopefully this gives ideas though for other terrains to improve
too. The above thing it's impossible to get bugs in, except
the 50 move rule needs checking. imagine how many bugs a
hashtable can have!

>I did not want to copy from other programmers.
>I may change it later after I learn about using hash tables in chess programs
>but I guess that the speed difference relative to hash tables is not big and I
>believe that my program does not waste more than 1% of it's time in repetition
>detections(in most of the cases there is a conversion in the last 4 plies so I
>can detect no repetition with no problem).
>The main advantage of hash tables should be different then detection of

>some more details about my program:

>It generates only legal moves and for that purpose it builds attack tables that
>tells it for every square the directions that it is attacked and a pin array
>that tells it for every piece if it is pinned.
>Today it extends only positions when there is a single legal move or positions
>when the king is in check.
>It practically does not use today the fact that it generates only legal moves
>except the single reply extension but I may use my attack tables for the
>evaluation and for better search rules in the future.
>>in the next line please tell me whether there is repetition:
>>Ra1-a2 Rh7xh6 Ra2-c2 Kg7-h8 Kh1-h2 Kh8-g8 Rc2-a2 Rh6-h7 Kh2-h1 Rh7-h6 Ra2-c2
>No repetition:
>taking back one ply every time sho that the last position did not repeat:
>Ra2-c2                                    white a2c2
>Rh7-h6 Ra2-c2                             white a2c2      black h7h6
>Kh2-h1 Rh7-h6 Ra2-c2                      white h2h1,a2c2 black h7h6
>Rh6-h7 Kh2-h1 Rh7-h6 Ra2-c2               white h2h1,a2c2
>Rc2-a2 Rh6-h7 Kh2-h1 Rh7-h6 Ra2-c2        white h2h1
>Kh8-g8 Rc2-a2 Rh6-h7 Kh2-h1 Rh7-h6 Ra2-c2 white h2h1      black h8g8
>Kh1-h2 Kh8-g8 Rc2-a2 Rh6-h7 Kh2-h1 Rh7-h6 Ra2-c2          black h8g8
>Kg7-h8 Kh1-h2 Kh8-g8 Rc2-a2 Rh6-h7 Kh2-h1 Rh7-h6 Ra2-c2   black g7g8
>Ra2-c2 Kg7-h8 Kh1-h2 Kh8-g8 Rc2-a2 Rh6-h7 Kh2-h1 Rh7-h6 Ra2-c2
>white a2c2 black g7g8

This page took 0.01 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.