Your generalized version is interesting to me... The original version already looks unbelievable. The theorem could be proved a bit more clearly I think; the crucial paragraph (very short) clearly shows the result for a random variable on subsets with each location black or white with probability 50%, but the fact that it's independent over locations is not so clear at first reading. I agree that the result is nonetheless ok.
Incidentally, the result can be understood as a proof of the classical sentence "your good moves are the good moves of your opponent"... even if the theorem does not apply to go. Olivier 2011/11/15 "Ingo Althöfer" <[email protected]> > 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 > -- ========================================================= Olivier Teytaud -- [email protected] TAO, LRI, UMR 8623(CNRS - Universite Paris-Sud), bat 490 Universite Paris-Sud F-91405 Orsay Cedex France http://0z.fr/EJm0g (one of the 56.5 % of french who did not vote for Sarkozy in 2007)
_______________________________________________ Computer-go mailing list [email protected] http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
