When you say "transposition tables" I assume you mean structuring the tree as a hash table instead of a tree with pointers.
I have done both, but currently Lazarus does the tree for several reasons. I do not claim it's better either way. Here are the problems with hash tables as a tree: 1. Time - it is more expensive - you must gather the children together when making decisions about which node to expand (which generally involves re-generating the keys by making all the legal moves.) There are ways around this that trade space for time but in either case it is more expensive. 2. GHI - you must take special care to deal with Graph History Interaction - primarly recognizing that ko situations are different. You can get by with relatively simple solutions that don't fully address this issue but it's still imperfect. 3. UCT - I have to think about this more - but I'm not sure how UCT interacts with different nodes growing outside the normal context of a direct parent/child node relationship. In other words a particular node may be over-represented when it is approached from a different path. Will this hurt the search? I don't know. Going along with this, the numbers won't add up (although I don't know if that is important.) In other words, if you do 10,000 simulations at the root, all grandchildren will add up to more (due to transpositions.) If you propogate this up the tree you might come up with many more than 10,000 simulations at the root. Hash table have the obvious advantage of taking advantage of redundant calculations. In my opinon (currently) that might be a big advantage with UCT trees since they are highly selective. I would expect there to be rich transpositions. I've done it both ways, but I've never taken the time to really study the advantages nor have I noticed a remarkable difference in one over the other. A hash table implementation will be slower but this is likely to be offset with the advantages. I think it's well worth the time to further investigate. - Don On Fri, 2007-05-11 at 09:07 -0400, Jason House wrote: > While I can't talk specifically about UCT, I believe that > transposition tables are one of the easiest and most profound speed > ups you can do for a program. The answer really depends on the depth > you're searching. > > At two moves ahead, all results are unique. At 4 moves ahead, it's a > 75% savings. At 6, the savings is over 99%. > > I was thinking recently about the "sum your children's move count" > thing recently and realized that with transposition tables, that's > really the only way to implement UCT. > > On 5/11/07, Chris Fant <[EMAIL PROTECTED]> wrote: > How much improvement should one see in a UCT program after > adding a > transposition table? > > _______________________________________________ > computer-go mailing list > computer-go@computer-go.org > http://www.computer-go.org/mailman/listinfo/computer-go/ _______________________________________________ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
