[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  
could happen.

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.

-Magnus

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.
>>>>
>>>> Best
>>>> Magnus
>>>>
>>>>
>>>>
>>> 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
>>> that
>>> 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
>> implement.
>>
>> Luckily it is extremely rare that affect play (I think).
>>
>> ______________________________**_________________
>> Computer-go mailing list
>> Computer-go at dvandva.org
>> http://dvandva.org/cgi-bin/**mailman/listinfo/computer-go<http://dvandva.org/cgi-bin/mailman/listinfo/computer-go>
>>
>





More information about the Computer-go mailing list