Valkyria uses a transposition table to turn the MCTS tree into a
graph. For example I just searched a early middle game position on a
9x9 board.
There was 14515 new nodes created and instead of creating a new node
the search found 524 transpositions. I have no memory if this actually
improved the program. I think for some reason I cannot easily disable
the transposition without having to rewrite a lot of code so I never
tested it.
My feeling is that the improvement is minor. The move ordering is
probably improved for each of these transpositions but since it
applies to an extremely small number of nodes overall I do not think
it has a measurable impact on the playing strength.
I have been tempted to remove the transposition table in order to
simplify the code. Having a graph causes bad bugs because of
circularity and it is hard to make changes that do not introduce bugs.
Also it although the transpositions speed up the search in theory the
table lookup might in practice even slow down the the search.
-Magnus Persson
Quoting Mark Boon <[email protected]>:
During my brief stint in playing with MCTS I also tried to implement
transpositions. I read somewhere (about MoGo I think) that it would
gain about 100 ELO points. But I didn't see any gain at all. David
Fotland told me he used it and it did work for him.
Possibly my idea how to do it were plain wrong. I never had time to
look into it very carefully. What I tried to do was creating a
hash-table next to the tree. The hash-table contained lists of
positions that were identical but with different positions in the
tree. So a hash-table of lists. When updating the win-rate in the
tree, I wouldn't just go up the one path, but up multiple paths when
there were transpositions (taking care of loops). Basically the tree
had become a graph.
What I saw was a small gain for small number of nodes ( a few K), and
worse results the larger the number of nodes became to the point it
was a negative contribution.
Mark
_______________________________________________
Computer-go mailing list
[email protected]
http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
_______________________________________________
Computer-go mailing list
[email protected]
http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
