So maybe another way to measure the benefit is to look at how it reduces the effective branching factor? Does anyone have data on the typical length of the PV with and without a transposition table? People are surprised sometimes at MFGO's large PV length.
David > -----Original Message----- > From: [email protected] [mailto:[email protected]] > On Behalf Of Jason House > > 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 _______________________________________________ Computer-go mailing list [email protected] http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
