I think there are three ways the tree is stored,
As a tree, with pointers As a tree (with pointers), and with a separate transposition table - I think Fuego does this As a hash table only, with no pointers between nodes. This is what Many Faces does. I never implemented a tree structure, so I can't compare the strength of the tree to the strength of a table only. For me, the hash table structure seems easier to code, since there are no pointers. It's far easier to garbage collect. David From: [email protected] [mailto:[email protected]] On Behalf Of Don Dailey Sent: Thursday, May 06, 2010 11:07 AM To: [email protected] Subject: Re: [Computer-go] effectiveness of transposition tables for go When you say transposition table I'm not sure what you mean. Most programs do not do a typical alpha/beta search where transposition tables are used. In MCTS there seems to be 2 different ways the "tree" is stored in memory, via a transposition table or via a tree structure (where transposition would not be noticed.) Is that what you are talking about? In the old Lazarus program, which is pretty weak by todays standards, I used a tree because it seemed a bit easier to implement and I like easy. I did not want to deal with how to handle transpositions such as how to identify the parent node when there might be many and how to reconcile different hit counts and success rates. It's probably not a difficult thing, but I wanted to keep it real straightforward. But I think many excellent programs use the hash table structure which I would call a transposition table. Is that what you mean? My intuition is that a transposition table should be superior. Don On Thu, May 6, 2010 at 1:45 PM, Jean-loup Gailly <[email protected]> wrote: Petr Baudis and I have a debate about the effectiveness of transposition tables for go. My guess is that, compared to a simple tree, a transposition table should make the program stronger, particularly for long games and many cores. Petr thinks that transposition tables are much less effective in go than in chess. For those of you using a transposition table, did you observe a strength increase? If so do you have even a vague estimate of how many elo points this can bring? Is it more effective in 19x19 or 9x9? Thanks. Jean-loup _______________________________________________ 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
