Deadly Chess Programming
Artificial Intelligence
For those who don't know, transposition tables can cause massive headaches. It vastly increases the search depth in all positions, especially in the endgame. However, due to the nature of it, incorrect search results can occur. This happens when an entry in the hashtable is overwritten. What are the effects of instability? Well first, the search isn't so nice or elegant any more. Second, it will sometimes report mates in 4 when in reality there is no mate in sight. This could be disastrous because the computer might throw material away for free.
Solutions? I decided to put a depth constraint in each transposition entry (Now it includes the depth, the board position and whose turn to move). This means it will always return the exact value; it won't return a more "accurate" result from a greater depth. (Of course, you will never return a transposition entry from a smaller depth. A search to the appropriate depth is required). Unfortunately, the downside of this is that more entries need to be stored, but suprisingly, it doesn't increase memory consumption by much. Since the transposition table now contains the best move found from ply 1 to 6 search, I have many more best moves to scan through which actually speeds up alpha beta in the end. (I ran a ply 6 benchmark to compare the speeds of the iterations of this program). So far, search instability has been completely elimanted.