On May 7, 2010, at 2:43 AM, [email protected] wrote:
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.
You have to be very careful when trying to translate your
transposition table data to theoretical tree savings. A transposition
node not only prevents duplication of that node, but also all of its
children. This can apply recursively for additional savings. Your 3%
savings, if uniformly spread through a 10 ply tree would really be
1-0.97^10 = 26%.
Of course, in the leaves of the search tree, new transpositions are
less common because of the low branching factor. Transpositions near
the root are actually more valuable. What follows is a complete swag
to illustrate the point. An 8 ply tree with a branching factor of 4
would have 65536 nodes in it. If 3 out of 4 nodes at ply 3 are
transpositions, and 2 out of 4 of the remaining nodes at ply 4 are
transpositions, that would be only 80 transposition nodes, yet the
final tree would be only 8192 nodes. That's a savings of 87.5% or the
equivalent of running 8x faster!
(ply 3 is the first ply where transpositions can occur in a 2 player
game)
_______________________________________________
Computer-go mailing list
[email protected]
http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
