The following may be interesting mainly for MCTS programmers of Hex, but perhaps also for those of other "board filling games" like Havannah or even Go.
Several years ago, during 2004 and 2005, David B. Wilson wrote a very nice computer program which plays the games "Random-turn Hex" and "Random-turn Y" almost perfectly. Here "random-turn" means that in each move a fair coin flip decides which player makes the next move. For such random- turn games it has been proved that pure Monte Carlo converges to perfect play. Wilson's Windows program, named "Hexamania", can be downloaded from http://dbwilson.com/hex/ Hexamania is based on a clever version of AMAF: In a current position, the board is randomly filled, and the winner is determined. But also all CRITICAL cells are determined. Here "critical" means that switching the value of this cell would result in another outcome of the game. All critical cells - and only those - get a bonus in their counters. (In "normal" AMAF all cells occupied by the winning side gets a bonus in the counter.) This procedure converges more quickly to an optimal move (one with the highest counter) than normal AMAF. My intuition: This ACMAF (standing for "All Critical Moves As First") may also be helpful in normal MCTS programs for Hex. The approach of Wilson is theoretically backed by the paper "Random-turn Hex and other selection games", by Yuval Peres, Oded Schramm, Scott Sheffield, and David B. Wilson. American Mathematical Monthly, 114:373--387, May 2007. http://arxiv.org/PS_cache/math/pdf/0508/0508580v2.pdf ************************ Of course, in final positions of Go games it is not so easy to tell which stones are critical. Especially, in situations where the stronger side has a large lead there may not be any critical stones. But perhaps, there is a way to make use of Wilson's idea also in Go MCTS. Ingo. -- Empfehlen Sie GMX DSL Ihren Freunden und Bekannten und wir belohnen Sie mit bis zu 50,- Euro! https://freundschaftswerbung.gmx.de _______________________________________________ Computer-go mailing list [email protected] http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
