hgm wrote:He doesn't use the hash table. Just the hash key. Most engines store a small array of hash keys since the last irreversible move, through which they then do a linear search. You could make a small dedicated hash table for this too (which for games without irreversiblemoves is probably advisable)..
Some have used a hash table for repetitions. Bruce Moreland was the first I had heard this from. Idea is that when you enter a position, you look for a repetition match. If present, increment the included rep counter and do what you want (most call 2 reps a draw, but you can be more careful and only allow 3 reps near the root if you want (I do not like the idea, but some have used it.) If you do the probe and find nothing, you enter the signature and a count of one. When you return from this ply, you decrement the counter and if zero, remove the entry. I think he used a table of 2K entries.
I didn't like the idea because one has to copy all of that stuff in a parallel search so that each thread has its own repetition hash,... but it seems to work just fine. It eliminates the loop to look for repetitions, but it means that for each node you do a "probe" and a "delete" (Bruce called them "open" and "close" operations.) I don't think there is any difference in terms of speed.
I did it exactly like that in Joker. It could make a difference in games without irreversible moves, like Crazyhouse, where you would always have to search back to the beginning of the game.
hgm wrote:I did it exactly like that in Joker. It could make a difference in games without irreversible moves, like Crazyhouse, where you would always have to search back to the beginning of the game.
As a human player that has played thousands of bughouse/crazyhouse games, I just realized that we never even thought about the 50 move rule, although some games did end in perpetuals. Never even occurred to me, in fact. Ditto for repetitions except for those that are simply 3 straight repetitions. Is there actually a rule for this? After a drop and capture I suppose you can repeat with a previous position where the capturing piece moved to that same square when it was empty or contained another piece?
Not particularly important, but I had never even though about it as I played, and Bert Gower and I were pretty damned good at this game as communication is as important as chess skill (what do you need? or "give me a knight whatever it costs")
bob wrote:
Some have used a hash table for repetitions.
Actually I just use a C++ std::vector object to hold the hash keys from previous positions. When looking for 3-fold rep draws I simply search the vector and count how many times the current position has occurred. Note that my test program is a not a chess engine, just something that lets two engines plays chess and has to adjudicate game endings as they cannot do such things themselves.
bob wrote:Some have used a hash table for repetitions. Bruce Moreland was the first I had heard this from. Idea is that when you enter a position, you look for a repetition match. If present, increment the included rep counter and do what you want (most call 2 reps a draw, but you can be more careful and only allow 3 reps near the root if you want (I do not like the idea, but some have used it.) If you do the probe and find nothing, you enter the signature and a count of one. When you return from this ply, you decrement the counter and if zero, remove the entry. I think he used a table of 2K entries.
If I recall correctly, Ken Thompson long ago used the main and only transposition table in Belle to recognize repeated positions in the search. Upon entering a node for the first time, it was stored in the transposition table with a flag saying "current variation position". Upon exiting the node, the flag was reset. Upon entering the same node a second time by a deeper path the flag was checked and if set, the node was scored as a draw. The controlling program in the attached pdp-11 had the logic for detecting threefold at ply one. It all worked, although there was a slight risk that a table element overwrite could cause a false negative and a repetition would be missed.
trojanfoe wrote:Actually I just use a C++ std::vector object to hold the hash keys from previous positions. When looking for 3-fold rep draws I simply search the vector and count how many times the current position has occurred. Note that my test program is a not a chess engine, just something that lets two engines plays chess and has to adjudicate game endings as they cannot do such things themselves.
Well, as long as you flawlessly incorporate all rights in the key, (e.g. no phantom e.p. rights) this should work. But that is of course exactly what you should test. Assuming things work properly because they were designed to work properly is no substitute for testing.
function PosCalcRepCount(var pos: postype; limit: Integer): Integer;
var
myresult: Integer;
count: hmvctype;
spevptr: spevptrtype;
begin
with pos do
begin
myresult := 0;
count := 0;
spevptr := usedspevlist.tail;
while (myresult < limit) and (count < hmvc) and (spevptr <> nil) do
begin
if Odd(count) then
if HashEq(spevptr^.spevmphc, mphc) then
Inc(myresult);
Inc(count);
spevptr := spevptr^.prev
end
end;
PosCalcRepCount := myresult
end; { PosCalcRepCount }
function PosIsRepeated(var pos: postype): Boolean; inline;
var
myresult: Boolean;
begin
if pos.hmvc < 4 then
myresult := False
else
myresult := PosCalcRepCount(pos, 1) = 1;
PosIsRepeated := myresult
end; { PosIsRepeated }
function PosIsDrawByRepetition(var pos: postype): Boolean; inline;
var
myresult: Boolean;
begin
if pos.hmvc < 8 then
myresult := False
else
myresult := PosCalcRepCount(pos, 2) = 2;
PosIsDrawByRepetition := myresult
end; { PosIsDrawByRepetition }
hgm wrote:Well, as long as you flawlessly incorporate all rights in the key, (e.g. no phantom e.p. rights) this should work. But that is of course exactly what you should test. Assuming things work properly because they were designed to work properly is no substitute for testing.
I played a 100-game tourney between komodo and stockfish and 22 of the games were adjudicated as draws by 3-fold repetition, which seems quite high to me!
I'm just about to go through the games to see if there is anything suspicious.
hgm wrote:Well, as long as you flawlessly incorporate all rights in the key, (e.g. no phantom e.p. rights) this should work. But that is of course exactly what you should test. Assuming things work properly because they were designed to work properly is no substitute for testing.
I played a 100-game tourney between komodo and stockfish and 22 of the games were adjudicated as draws by 3-fold repetition, which seems quite high to me!
I'm just about to go through the games to see if there is anything suspicious.
hgm wrote:Well, as long as you flawlessly incorporate all rights in the key, (e.g. no phantom e.p. rights) this should work. But that is of course exactly what you should test. Assuming things work properly because they were designed to work properly is no substitute for testing.
I played a 100-game tourney between komodo and stockfish and 22 of the games were adjudicated as draws by 3-fold repetition, which seems quite high to me!
I'm just about to go through the games to see if there is anything suspicious.
