10-14-2022, 11:22 PM
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.
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.