[Computer-go] David Wilson's "All Critical Moves As First"

Olivier Teytaud olivier.teytaud at lri.fr
Tue Nov 15 02:23:46 PST 2011

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
"your good moves are the good moves of your opponent"... even if the
theorem does not
apply to go.

2011/11/15 "Ingo Althöfer" <3-Hirn-Verlag at gmx.de>

> 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
> Computer-go at dvandva.org
> http://dvandva.org/cgi-bin/mailman/listinfo/computer-go

Olivier Teytaud -- olivier.teytaud at inria.fr
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)
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://computer-go.org/pipermail/computer-go/attachments/20111115/c1476434/attachment.html>

More information about the Computer-go mailing list