Hi, > http://arxiv.org/PS_cache/math/pdf/0508/0508580v2.pdf > The top of page 4 in this paper is very clear - yes, pure Monte-Carlo (no > tree search!) is optimal for these random-turn games. > > Impressive... The proof is simple, but it is > so unexpected that one can work 20 years on such games without observing > this I guess :-)
Right. When I first read the result, I could not believe it. I tried to find a hole in the proof for several hours. But there is none. Some time later I generalized the result and wrote a paper on it. It came to a referee who also could not believe it - and made very negative comments. The theorem allows statements for very strange games: Consider a polynomial P(x)= a_n*x^n + a_(n-1)*x1(n-1) + ... + a_1*x^1 + a_0, where the coefficients a_i are not fixed yet. In each move a fair coin is flipped, and the winner is allowed to fix one free coefficient a_i either to +1 or -1. At the end (after n+1 moves) all coefficients are fixed. For the resulting polynomial the number of real roots is determined. Player Max wants to maximize this number, Player Min wants to keep it as small as possible. The theorem says: In each possible state of this game pure Monte Carlo converges to the best move. Hopefully, someone is willing to play this game with me in Tilburg. (We can use http://www.wolframalpha.com/ as a referee on the number of real roots.) Regards, 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
