Author: Frederik Tack
Date: 13:11:29 12/21/05
Go up one level in this thread
On December 20, 2005 at 19:26:47, Stuart Cracraft wrote:
>On December 20, 2005 at 17:11:41, Frederik Tack wrote:
>
>>I'm looking for the best way to implement a repetition detection in the search
>>tree for my engine without loosing performance.
>>
>>I've found some articles on the internet suggesting to create a repetition table
>>using zobristkeys. I have now implemented this and it works fine, but i've lost
>>about 10% performance.
>>
>>I have now come up with a new idea that should have no impact on performance.
>>However, i'm not sure if what i'm about to do is completely correct. Here's the
>>idea. Before starting the analysis, i store every position i've had on the board
>>from the move history in the transposition table with an evaluation of 0 and a
>>depth of maxdepth + 1. During the analysis, i use a replacement scheme in the
>>transposition table that will not replace the position if the depth in the tree
>>is smaller than depth in the table. Since i've stored the historic positions
>>with maxdepth + 1, they will never get replaced. This should score every
>>position that has been on the board before with a draw score.
>>
>>The fact is i haven't found any article on the internet discussing this way of
>>working, so i fear it may have some drawbacks i'm not aware of. Has any1 tried
>>implementing repetition detection this way or has any1 an idea why this wouldn't
>>work?
>
>10% is too much. Something is wrong.
>
>As moves as are made, the Zobrist value for the current
>board position is updated or downdated incrementally by
>the makemove and unmakemove routines. I hope you do that
>and don't recalculate it by a full board scan.
Yes, i do this. I have already implemented an incremental zobristkey for use in
the transposition table, so no performance is lost here.
>
>My draw repetition code is:
>
>// 50 or more moves since last pawn move?
>int pawndrawn()
>{
> int h;
> for (h = histptr; h >= 0; h--)
> if (ABS(hist[h].pc) == WP)
> if (histptr-h >= 50)
> return(1);
> else
> return(0);
> return(0);
>}
>// how many times the current position has been repeated in the past
>int reps()
>{
> int r, h;
> r = 0;
> for (h = 0; h <= histptr; h++)
> if (hist[h].key == hashkey)
> r++;
> return r;
>}
>
>Then this code is placed near the top of my quiescence and
>tree search routines:
>
> if (reps()==3 || pawndrawn()) return(DRAW);
>
That is also what i do now at the top of my negamax function, except i think
your method of counting the repetions in every node will be even more time
consuming than using a repetition table like i do. Robert Hyatt suggested in
another post to do the test for repetition just after making the move. This
might be better for performance, since i save a call to negamax in case of a
repetition, so i'm gonna try this out. If i still have a significant performance
loss, i think i'll just go for the idea of using the transposition table without
detecting repetitions that occur only in the principal variation. This has a
cost of zero, performance and storage wise. Only drawback i see is that i will
only detect perpetual checks after the first check has been given, which is too
late.
>Someone once suggested the above 3 should be a 2 since if it
>could be forced once (be at 2) it should be forced again. I think it
>was Tom K. of TSCP fame. But I did some tests with both and
>preferred 3. Perhaps I should make it 2 after all.
>
>--Stuart
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.