+- Ludii Forum (https://ludii.games/forums)
+-- Forum: Problems (https://ludii.games/forums/forumdisplay.php?fid=5)
+--- Forum: AI Problems (https://ludii.games/forums/forumdisplay.php?fid=7)
+--- Thread: Tree Reuse problem for Amazons (/showthread.php?tid=1314)
Tree Reuse problem for Amazons - Victor Putrich - 10-14-2022
Hello o/
I'm trying to implement a MCTS using tree reuse in Ludii. My first attempt was literally understand how tree reuse is done in MCTS source code from Ludii's repo. Basically it recreates the movements made in game and searches across the old root.
something like:
gameHistory = context.trial().generateCompleteMovesList()
...
while (offset>0)
Move m = gameHistory.get(gameHistory.size - offset).
root=findChild(m, root)
offset--
For my surprise, when I was testing the percentage of nodes actually reused, I found that it never finds the target node (new root) for some games.
To give one example, in Amazons the first element in gameHistory is:
[[Move:typeFrom=Cell, from=1, typeTo=Cell, to=34, decision=true], [SetNextPlayer:player=1]]
the 'findChild' method returns 'null', but inside the root, one of the children is:
[Move:typeFrom=Cell, from=1, typeTo=Cell, to=34, decision=true][]
I can see why it is not considering the same movement, because the movement actually made is composed by two actions (including a similar, but not equal, data structure).
I wonder why the child node doesn't have the same format as the move got from gameHistory (with the SetNextPlayer part), if in the last search the move computed was actually the same.
RE: Tree Reuse problem for Amazons - DennisSoemers - 10-15-2022
For our built-in MCTS, this issue is now fixed in this commit to our dev branch: https://github.com/Ludeme/Ludii/commit/366a1ac30fc420aa67d1ce3a4893d989e947c030
The core tree reuse code that you've probably seen close to the start of the selectAction() method (approx around lines 477-540ish) was already correct. However, at the end of the method, I also already did a little bit of traversing (of just the action that we're planning to take, but not opponents' actions yet since they didn't move yet) to be able to clean up a small amount of memory (around lines 799-818). There, I was using the "returnMove" instead of a Move object extracted from a Trial (because we are traversing the move that we are planning to play, rather than one already played), and that one was in a different format (with consequents still in Ludeme-rule-format instead of having been converted into concrete Actions).
RE: Tree Reuse problem for Amazons - Victor Putrich - 10-15-2022
(10-15-2022, 01:23 PM)DennisSoemers Wrote: For our built-in MCTS, this issue is now fixed in this commit to our dev branch: https://github.com/Ludeme/Ludii/commit/366a1ac30fc420aa67d1ce3a4893d989e947c030
The core tree reuse code that you've probably seen close to the start of the selectAction() method (approx around lines 477-540ish) was already correct. However, at the end of the method, I also already did a little bit of traversing (of just the action that we're planning to take, but not opponents' actions yet since they didn't move yet) to be able to clean up a small amount of memory (around lines 799-818). There, I was using the "returnMove" instead of a Move object extracted from a Trial (because we are traversing the move that we are planning to play, rather than one already played), and that one was in a different format (with consequents still in Ludeme-rule-format instead of having been converted into concrete Actions).
Thank you for your reply.
I finally understood the problem :)
I found very cleaver your solution for clear memory and also move the root for the next known step. (which is the one that the agent actually selected to do).
I'm not sure if I'm right or wrong but, it seems that the move format divergence can be avoided only for situations where the agent knows the subsequent action.
To give one example where I think it should not work: when the opponent made a move, with the same situation where the concrete move is different than the Ludeme-rule-format ([move ...], [setPlayer...]]), the agent still won't find the opponent step in the traversed nodes, because the only way to actually search the move is using the actionHistory list.
Let me know if it works on these situation. (I tested in Amazons and it looks like it is not working).
> I want to share a temporary solution (which is terrible and I'm not proud of it) but it seems to work in the situation mentioned before:
In the findChildForMove method, inside the children iteration, instead of comparing the 'move' parameter with child.parentMove (line 124 from DeterministicNode), create a copy of the node.context and apply the child.parentMove in the copied context,
something like: copyContext.game().apply(cpyContext, child.moveFromParent).
The 'concrete action' returned from copyContext.trial().lastMove() should have the same format as the one got from the actionHistory list.
The if condition should now be: concreteAction.equals(move)
It looks like it is working, but a different approach should be made for the clean memory situation. The 'returnMove' should be transformed into a concrete action (the same way previously shown) before passing it in the findChildForMove, in order to find the right child node.
RE: Tree Reuse problem for Amazons - DennisSoemers - 10-16-2022
With that "trick" where you copy the context and apply the action to it, you indeed transform it into the fully-resolved format where consequents have been converted from Ludeme-rules-format to concrete-actions-format.
However, this should not be necessary here: the "parentMove" member of the MCTS node classes already is in this format too (and I actually store the other format as well, in a different member named something like "parentMoveWithoutCons").
If I test with my implementation in Amazons (using the code in dev branch with yesterday's commit, so not the master branch or any current public .jar releases), the tree reuse works fine.