# Is it possible to prove that a game(ex. chess or othello...) will eventually halt at some point. [closed]

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

• 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. Mar 24 '11 at 21:53

• @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. Mar 24 '11 at 21:41