How complex is your game ?
A usual tool for answering such a question is computational complexity.
It consists in finding where the problem is, in the following scale:
The classes on the right are more difficult.
For the most important classes:
- PL is the class of problems solvable in poly-logarithmic time;
- P is the class of problems solvable in polynomial time
- PSPACE is the class of problems solvable with polynomial memory
- EXP is the class or problems solvable in exponential time
- EXPSPACE is the class of problems solvable in exponential space.
Given a position, how "powerful" should be your computer, if you want it to find if this situation, in case of perfect play,
is a win for the player to play.
We will here consider only deterministic (i.e. non randomized - this is not "determinism" in the sense of P vs NP) games.
Zero-sum two-player games, existence of strategies winning with proba > c:
the surprising thing is that, in the partially observable case, even on a finite board (finite state space), the problem is undecidable. If c<1 and c>0, then the problem is undecidable. How is it possible ? The trick is that usually people consider this case as decidable, because they consider the problem of the existence of a winning strategy independently of what is played by the opponent. This makes the problem much simpler, as in particular the opponent does not have to be clever; he can just play randomly, independently of observations, as it is sufficient for him to win with proba >0.
Importantly, this questions is probably the most natural one. We now consider the easier cases in which we look for a forced win. But keep in mind that the natural case is probably more the case above.
Remark: the undecidability certainly not holds in the fully observable case, which is immediately downgraded to the same case as the existence of winning strategies whatever may be the choice of the opponents, below.
Zero-sum two-player games: the existence of winning strategies whatever may be the choice of the opponents
Consider a game which is encoded in succinct form; this means that the game is given as a simple automaton,
updating variables depending on some rules.
Then, the complexities are as follows:
- deciding whether the situation is a forced win, if everything is observable, is EXPTIME-complete;
- deciding whether the situation is a forced win, if nothing is observable (you have no info!) is EXPSPACE-complete;
- deciding whether the situation is a forced win, if the situation is partially observable, is 2EXP-complete.
==> Rintanen's paper is the main reference in this case.
The game of Go with japanese rules is fully observable; it is EXPTIME-complete. It is therefore as complicated as it is possible for a fully observable game that can be described in succinct form. This is proved in Robson's impressive paper which exhibits a complicated ko-fights whose results decides the issue of a connection problem.
And what if the game is limited in length, to an exponential length ? still the existence of winning strategies, whatever may be the choice of the opponents
Things are much easier in this case:
- the fully observable case is EXPTIME in the fully observable case (no change!);
- the no-observability case is NEXPTIME (much easier);
- the partially observable case is EXPSPACE, which is easier than 2EXP.
This was shown in papers by Mundhenk et al.
And what if the game is limited in length, e.g. an acyclic graph is given and the game is played on the graph, i.e. at most a linear number of possible states ?
The fully observable case then becomes linear (solving by minimax).
I'm not aware of results in the partially or unobservable case, please tell me if you know (olivier.teytaud@gmail.com).
