02-13-2021, 07:04 PM
On repetition rule being used in your game: you're right, indeed I saw that unused define and just assumed that that would be a reason for transposition table issues in your game, but after writing that post and looking into fixing it, I noticed it wasn't relevant to your game. Still important for other games though :)
For your game specifically... I've spent most of my Saturday looking into it now, and believe that actually there's not really a bug in the AI at all. Maybe there was / is a small one in the current live version still (because number of consecutive pass moves wasn't being tracked in the Zobrist hash), but not anymore in our dev code. Still, there are some of these inconsistencies in the reported search depths for proven wins/losses, but I believe that may be more an issue in the search depth being reported than actually a bug in the AI.
The search depth reported in the Analysis tab is the depth to which the current iteration of iterative deepening is searching. But, with a transposition table, it's possible to prove a win at a greater depth than the depth being searched. For example, suppose that after some sequence of moves A-->B-->C, we prove a large subtree below C to be a win, and store this in the transposition table. But after playing move A, our opponent also has a better move available than B, which prevents us from winning, so we didn't fully prove a win for our root state yet. Later on, we may discover a winning line of moves from the root state which looks like D-->E-->F-->G-->H-->C, where we no longer have to prove that C is a winning subtree because it's in our table already. We may report this as having proven a win at depth 5 because that's the search depth we need to reach C, but the actual win may be much deeper because there's still a larger subtree below C.
This also implies that we may not always go for the shortest winning line; instead, we go for the winning line that requires the lowest effort to prove that it is a win. Intuitively I feel that this should never be deeper than twice as deep as the closest win (worst case), and I... think it would still be a decreasing function, in the sense that we won't keep infinitely going around in circles and keep changing our minds on which winning line to pursue, but not 100% sure on that yet.
For your game specifically... I've spent most of my Saturday looking into it now, and believe that actually there's not really a bug in the AI at all. Maybe there was / is a small one in the current live version still (because number of consecutive pass moves wasn't being tracked in the Zobrist hash), but not anymore in our dev code. Still, there are some of these inconsistencies in the reported search depths for proven wins/losses, but I believe that may be more an issue in the search depth being reported than actually a bug in the AI.
The search depth reported in the Analysis tab is the depth to which the current iteration of iterative deepening is searching. But, with a transposition table, it's possible to prove a win at a greater depth than the depth being searched. For example, suppose that after some sequence of moves A-->B-->C, we prove a large subtree below C to be a win, and store this in the transposition table. But after playing move A, our opponent also has a better move available than B, which prevents us from winning, so we didn't fully prove a win for our root state yet. Later on, we may discover a winning line of moves from the root state which looks like D-->E-->F-->G-->H-->C, where we no longer have to prove that C is a winning subtree because it's in our table already. We may report this as having proven a win at depth 5 because that's the search depth we need to reach C, but the actual win may be much deeper because there's still a larger subtree below C.
This also implies that we may not always go for the shortest winning line; instead, we go for the winning line that requires the lowest effort to prove that it is a win. Intuitively I feel that this should never be deeper than twice as deep as the closest win (worst case), and I... think it would still be a decreasing function, in the sense that we won't keep infinitely going around in circles and keep changing our minds on which winning line to pursue, but not 100% sure on that yet.