Is it possible to prove that a game(ex. chess or othello...) is solvable and will eventually halt at some point. I wonder as the halting problem is undecidable, will it be possible to prove that a particular game will end after a finite number of moves

  • $\begingroup$ This site is for research-level questions in theoretical computer science, that are likely to have short well-defined answers. "Research-level" means, roughly, questions that might be discussed between two professors, or between graduate students working on Ph.D.'s, but not usually between a professor and the typical undergraduate student. It does not include questions at the level of difficulty of typical undergraduate homework/textbook exercises. You may want to try Math.SE. $\endgroup$ – Kaveh Mar 24 '11 at 21:53

You can make games that will halt and those that won't. Othello will always halt because it cannot continue for more than 60 moves based on the rules. Chess ends only because there are rules to prevent infinite-move games (repetition rule, 50-move rule, etc). You can certainly construct games that never end... a silly example is "whoever names the highest integer wins".

Then there are games that lead to a paradox when you try and ask if they will end or not. A famous example is the game called CHOICE. The first move of CHOICE is to choose a game that does eventually end. The 2nd move of CHOICE is to play the first move of the chosen game, etc.

Now we ask, "does CHOICE end or not?" If you say it does, then the first move of CHOICE could be to choose CHOICE, and continuing this way leads to a never-ending game. So suppose we say CHOICE does not end, thereby disqualifying it as a possibility for the first move. Then clearly it DOES end.

| cite | improve this answer | |
  • $\begingroup$ For instance is it possible to show that the tile game will halt. (i.e 15 of the 16 positions in a 4*4 matrix are filled by tiles, leaving one unfilled hole. Tiles adjoining the hole can be shifted into the hole, the object being to form some particular permutation of the tiles (typically forming a picture out of fragments printed on the tiles). There are certainly many combinations involved here and only one combination is the halting state $\endgroup$ – user4376 Mar 24 '11 at 21:33
  • $\begingroup$ @Harry: it will depend on the rules of such a game. If you invoke a rule saying that repeating a pattern ends the game, then yes, it will halt. This is because there are a finite number of configurations. To know whether a winning state is reachable, we could just use DFS. To know the shortest sequence of moves to a win, use BFS. To make your question more interesting, you could parameterize to an $n \times n$ matrix and make it a two-player game. Then under most "natural" rulesets the game will be PSPACE-Complete, but still solvable. $\endgroup$ – Fixee Mar 24 '11 at 21:41