[Computer-go] undecidability of phantom-go ? partially observable games are undecidable, even with finite state space and deterministic transitions

Olivier Teytaud olivier.teytaud at lri.fr
Tue Nov 29 22:55:37 PST 2011


Hi;

we had a discussion some time ago on this mailing list around decidability
of partially observable games
(finite state space, deterministic transitions), with a natural focus on
phantom-go and phantom-rengo.

There's no undecidability result for Go,
but:

- as Bob Hearn explained in the past, the decision problem "is there a
strategy for winning with probability
     1 whatever maybe the strategy of the opponent" is decidable for all
such 2Player games, but
     is undecidable for some team games; this is not shown for the special
case of phantom-rengo,
     but shows that there is a question: is phantom-rengo decidable ?

- however, for a PO game, the question "is there a strategy for winning
with probability 1 whatever maybe
   the strategy of the opponent" is not relevant. In fact, we want to find
the optimal move, even if a move
  with probability 100% of winning does not exist. The question should be
   "is there a strategy for winning with probability C%" ?
  We show in http://www.lri.fr/~teytaud/sparta2.pdf that this is
undecidable for partially observable games,
  even with finite state space, and with deterministic transitions (the
result was already known for stochastic
  transitions). This is not for phantom-Go; it is for the general case of
partially observable games with
  finite state space and deterministic transitions.

So an open problem: is phantom-go decidable ? with Chinese rules obviously
yes, but for japanese rules
the question is unclear to me.

The paper is recently accepted at IJFCS.

Best regards,
Olivier
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://computer-go.org/pipermail/computer-go/attachments/20111130/7331a004/attachment.html>


More information about the Computer-go mailing list