[Computer-go] Congratulations to Zen!
valkyria at phmp.se
valkyria at phmp.se
Sat Jul 9 01:21:32 PDT 2011
Yes it is tricky I think my main idea (and I think similar ideas can
been found in a couple of papers) is to check for unexpected super ko
violations and then one has to mark the path that led to that
violations as "dirty" and create a new line in the collision node so
that dirty variations has there own node linked to the original
transposition node in a linked list, and there is a parent pointer
that is used to identify the right node in the linked list. This is
what I remember but details were hairy because of the many ways this
But most of the problems goes away if one uses a good hashing scheme
that also makes different capture histories different. I think Erik
vand Der Werf has written some good stuff on this issue because it
becomes extremely import when you try to solve game on small boards.
Quoting Michael Williams <michaelwilliams75 at gmail.com>:
> Keeping a real tree is of course tivial. I guess you mean a way to preserve
> the benefits of transposition while also maintaining admisibility. That
> does seem like it would be tricky.
> On Fri, Jul 8, 2011 at 9:24 PM, <valkyria at phmp.se> wrote:
>> Quoting Michael Williams <michaelwilliams75 at gmail.com>:
>>>> The Valkyria tree is not a pure tree, because a node can have several
>>>> parents if more than one sequence leads to a position.
>>> I think this is common, but inadmissable in the strictest sense,
>>> right? Because the optimal action for a node depends on it's history of
>>> positions thanks to the super ko rule.
>>> What was the word Don used for techniques like this? I mean techniques
>>> are not going to lead to perfect play given infinite time and memory.
>> Yes, you are right. For the next rewrite of Valkyria I actually think i
>> rediscovered some algorithm to solve this but it is painfully complicated to
>> Luckily it is extremely rare that affect play (I think).
>> Computer-go mailing list
>> Computer-go at dvandva.org
More information about the Computer-go