02-13-2021, 12:45 PM
You're right, some of those proven wins or losses seem incorrect.
The tree search itself seems fine though. If I internally in the code disable use of the Transposition Table, everything appears to be correct. So, likely, something in our Zobrist hashing is incomplete, causing the AI to think that certain states are equal to ones stored in the transposition table when in fact they aren't.
I'm seeing two things so far that appear to be important in your game which weren't being properly tracked yet specifically in the zobrist hash. The first thing is keeping track of the number of consecutive pass moves that have been made in the game. This is necessary due to the use of (was Pass). That's easy, I've added that in our code just now.
I'm more worried about the use of repetition rules though (which actually is definitely not just unique to your game, but also present in common games like Go). The use of such rules essentially means that really the entire history of all game states that have been encountered so far is an important aspect that must be factored into the current game state. For games like Go that have been widely studied in AI research, there are some techniques that mitigate most cases of incorrect hashes in practice, while still being computationally efficient (but not 100% theoretically correct). I don't think we can afford to rely on any of that for our much more general game system with hundreds of games though... I'm thinking I'll probably just make Alpha-Beta not use a transposition table anymore in any game that involves any kind of state repetition checks in our next release.
The tree search itself seems fine though. If I internally in the code disable use of the Transposition Table, everything appears to be correct. So, likely, something in our Zobrist hashing is incomplete, causing the AI to think that certain states are equal to ones stored in the transposition table when in fact they aren't.
I'm seeing two things so far that appear to be important in your game which weren't being properly tracked yet specifically in the zobrist hash. The first thing is keeping track of the number of consecutive pass moves that have been made in the game. This is necessary due to the use of (was Pass). That's easy, I've added that in our code just now.
I'm more worried about the use of repetition rules though (which actually is definitely not just unique to your game, but also present in common games like Go). The use of such rules essentially means that really the entire history of all game states that have been encountered so far is an important aspect that must be factored into the current game state. For games like Go that have been widely studied in AI research, there are some techniques that mitigate most cases of incorrect hashes in practice, while still being computationally efficient (but not 100% theoretically correct). I don't think we can afford to rely on any of that for our much more general game system with hundreds of games though... I'm thinking I'll probably just make Alpha-Beta not use a transposition table anymore in any game that involves any kind of state repetition checks in our next release.