+- Ludii Forum (https://ludii.games/forums)
+-- Forum: Suggestions (https://ludii.games/forums/forumdisplay.php?fid=10)
+--- Forum: Submit Your Games (https://ludii.games/forums/forumdisplay.php?fid=23)
+--- Thread: Goats Wintering - new game submission (/showthread.php?tid=429)
Pages:
1
2
RE: Goats Wintering - new game submission - DennisSoemers - 02-13-2021
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.
RE: Goats Wintering - new game submission - dale walton - 02-14-2021
OK, I get that you are backing down on saying that a search is exhaustive on every level before reaching a deeper level, because you can grab already searched sub-trees. That good, the numbers can drop faster than expected.
However this cannot explain a proven win ceasing to be a proven win. Which was in my example. So I take it you mean that you also already fixed that bug as well... If not please look deeper.
Could there be any issue in improperly grabbing a sub-tree because of a change to the passing state?
RE: Goats Wintering - new game submission - DennisSoemers - 02-14-2021
(02-14-2021, 05:29 AM)dale walton Wrote: Could there be any issue in improperly grabbing a sub-tree because of a change to the passing state?
With the current live code, yes, because the Zobrist hash used to index into the transposition table would ignore whether or not the last move was already a pass. And this is important information in your game, because if the previous move was already a pass, passing again will end the game -- whereas if the previous move was not a pass, passing will not yet end the game. That should be addressed in our next version.