[Computer-go] effectiveness of transposition tables for go

Greg Schmidt gschmidt958 at yahoo.com
Sun May 9 15:52:08 PDT 2010

>> Yes, that' how it's typically done, but I don't see how that leads to finding *all* parents of a given node.  The situation I'm referring to is when you're propagating the UCT value back up the tree following a simulation.  If you also want to update *all* parents of that node (not just the single parent within the simulated line of play), how would you find *all* of them?  The parent nodes will have different hash codes (and be in different chained lists) in your representation.  Therefore I don't see how this representation is able answer the question "give me the list of all parent nodes which point to this TT entry" (unless I'm missing something).

>I think you're missing something. If I reach a node, I look up what other nodes have the same transposition value. Each of those nodes knows its single parent. Nodes do not have multiple parents stored explicitly.
I see, so in a sense duplicate nodes are not merged, they remain distinct (or at least a ortion of them do) in order to point back to the parent.  Where I was headed with my initial post is that I wonder if the main advantage of using a TT appears when all parents are updated.  It seems like most implementations don't do that.  Based on your representation, It sounds like yours does perform multiple updates, but that you are not seeing a gain.  Is that correct?
-- Greg


-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://computer-go.org/pipermail/computer-go/attachments/20100509/feaa0583/attachment.html>

More information about the Computer-go mailing list