Using a hashing scheme works perfectly if you can encode all relevant situational properties. Whether that's practical depends on the rules. I found that for the traditional rules it is generally feasible to encode all relevant situational properties.
In my experience iterative deepening alpha-beta (when combined with an incomplete hash) has much more problems with graph-history-interaction than the usual MCTS implementations. This is because MCTS always plays out the sequence and therefore will discover any rule violation along the path, while alpha beta might make cutoffs that depend on unverified continuations. Once you start to update along multiple paths, propagating back to more than one parent, this may change of course. However, there are more fundamental problems with that idea anyway. E.g., if you update along some virtual path the statistics no longer necessarily conform to you your selection policy. Also, you have to avoid double counting when paths merge back. Erik On Sat, Jul 9, 2011 at 10:21 AM, <[email protected]> wrote: > 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 <[email protected]>: > >> 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, <[email protected]> wrote: >> >>> Quoting Michael Williams <[email protected]>: >>> >>> >>>>> 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 >>> [email protected] >>> >>> http://dvandva.org/cgi-bin/**mailman/listinfo/computer-go<http://dvandva.org/cgi-bin/mailman/listinfo/computer-go> >>> >> > > > _______________________________________________ > 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
