sje wrote:
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.
This is also how super-connie does it.
I think that the Super Constellation with only 8 KB RAM did not have a transposition table but did have a ply indexed stack of position hash signatures. I do not know the bit length used for a hash signature, but I have shown by experiment that a 12 bit hash is sufficient for repetition detection in all practical cases.
I remember my early chess programming days of more than thirty years ago when I hadn't yet learned of Zobrist hash generation. For each move played on the board but not during search, I stored a packed representation of the entire position on a stack. This was used for repetition detection at the root; I think I didn't bother with detection at lower levels in the tree.
If the model used a 100 ply history stack with each element containing a two byte move and a two byte hash, then nearly ten percent of the RAM was used just for move retraction and repetition detection. Assuming that the search also accessed the stack and could reach a depth of 16 ply, then the total storage would have been (100 + 16) * (2 + 2) = 464 bytes, about 11.3% of all RAM.
In Usurpator I just detected if the last 4 ply where going back and forth (in game as well as in tree). That solved 90% of the problem, and who cares about the other 10%...
sje wrote:
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.
This is also how super-connie does it.
I think that the Super Constellation with only 8 KB RAM did not have a transposition table but did have a ply indexed stack of position hash signatures. I do not know the bit length used for a hash signature, but I have shown by experiment that a 12 bit hash is sufficient for repetition detection in all practical cases.
I remember my early chess programming days of more than thirty years ago when I hadn't yet learned of Zobrist hash generation. For each move played on the board but not during search, I stored a packed representation of the entire position on a stack. This was used for repetition detection at the root; I think I didn't bother with detection at lower levels in the tree.
That is correct, my mistake. I knew David and his later programs did repetition that way, the ones that had Transposition tables.
