Hi;<br><br>we had a discussion some time ago on this mailing list around decidability of partially observable games<br>(finite state space, deterministic transitions), with a natural focus on phantom-go and phantom-rengo.<br>
<br>There's no undecidability result for Go,<br>but:<br><br>- as Bob Hearn explained in the past, the decision problem "is there a strategy for winning with probability<br>     1 whatever maybe the strategy of the opponent" is decidable for all such 2Player games, but<br>
     is undecidable for some team games; this is not shown for the special case of phantom-rengo,<br>     but shows that there is a question: is phantom-rengo decidable ?<br><br>- however, for a PO game, the question "is there a strategy for winning with probability 1 whatever maybe<br>
   the strategy of the opponent" is not relevant. In fact, we want to find the optimal move, even if a move<br>  with probability 100% of winning does not exist. The question should be<br>   "is there a strategy for winning with probability C%" ?<br>
  We show in <a href="http://www.lri.fr/~teytaud/sparta2.pdf">http://www.lri.fr/~teytaud/sparta2.pdf</a> that this is undecidable for partially observable games,<br>  even with finite state space, and with deterministic transitions (the result was already known for stochastic<br>
  transitions). This is not for phantom-Go; it is for the general case of partially observable games with<br>  finite state space and deterministic transitions.<br><br>So an open problem: is phantom-go decidable ? with Chinese rules obviously yes, but for japanese rules<br>
the question is unclear to me.<br><br>The paper is recently accepted at IJFCS.<br><br>Best regards,<br>Olivier<br><br>