[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