It looks like an interesting problem. Just to be sure I understand correctly : In the genreral case of unbounded games, the question is undecidable. But you wonder if it is still the case for phantom go ? What prevents a brute force approach is the fact that a strategy cannot be described finitely because of the unboundedness ?
________________________________ De : Olivier Teytaud <[email protected]> À : computer-go <[email protected]> Envoyé le : Lun 13 septembre 2010, 13h 38min 53s Objet : [Computer-go] phantom go, MCTS & decidability Thanks Steve for your answer. 1) One-player randomized games (paper by Madani et al) For the paper by Madani et al, they work on unobservable problems; there is a graph, some transitions are labelled with actions (e.g. just binary actions), and some others are labelled with probabilities (rational probabilities are ok, so there's no problem for encoding this). The instance also contains a rational number c, and the question is "is there a sequence of actions leading to acceptance with probability at least c". The undecidability result is then a classical undecidability result, by reduction to the halting problem for Turing machines. 2) Two-player games For the extension to two players non-stochastic games, there's no more randomness. Unobservability is still ok. The point is that in non-fully observable games, even when they are deterministic, there is a probability c of winning for an optimal stochastic strategy S at the worst case on the opponent's stochastic strategies S'. This is well defined, and so the question "given graph G (equipped with decision nodes for player 1 and decision nodes for player 2), is c bigger than d ?" makes sense, and is undecidable. Importantly, approximate answers are also undecidable. (nb: my email address is [email protected], [email protected], [email protected], all of them leading to the same email account) could you be a bit more precise with your definition of the language you'd like to show is undecidable? try to phrase it as a decision question that results in a language of strings over some finite alphabet, and then maybe you can get somewhere, with a reduction, for instance. > > >i'm not sure how you intend to define undecidability in the face of >randomness, >or even what your question is really asking. > > >a natural way to use computability to include the flavor of randomness is to >bound the number of bad cases. i.e., to imagine that something is happening >either uniformly at random or with a particular distribution, and to bound the >probability in the uniform case is just to bound the number of bad cases in >the >deterministic case. but you have to be careful about how you state this. > > >it could be a fairly straightforward undecidability result, but it depends >upon >the question that you're asking. > > >PS i tried to email you directly instead, but apparently your return email >address is invalid... > > >s. >_______________________________________________ >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) -- ========================================================= 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
