Games in logic are incredibly fashionable, and there’s lots of exciting work that I could write about. But I won’t. Instead, I’ll give you an exercise that can be solved with just the very basics of logic.

A finite game is a subset *W* ⊆ *M*_{1}, …, *M*_{n}, where each *M _{i}* is a finite set.

*M*is the set of possible moves at step

_{i}*i*, and

*W*is the set of winning play for player

*A*. You have two players,

*A*and

*B*.

*A*begins by making a move

*m*

_{1}∈

*M*

_{1}, then

*B*moves by picking

*m*

_{2}∈

*M*

_{2}, etc. The game ends after

*n*moves (that’s why it’s finite).

*A*wins if the sequence

*m*

_{1}, …

*m*

_{n}∈

*W*, otherwise

*B*wins (there are no draws).

This framework is pretty general. For instance, this is how tic-tac-toe fints the definition: each *M _{i}* = {1, …, 9}, where 1, …, 9 are the numbers assigned to the 9 squares on the tic-tac-toe board, say, like this:

1 | 2 | 3 |

4 | 5 | 6 |

7 | 8 | 9 |

Players *A* and *B* alternate in picking squares. The game ends after 9 moves (n = 9). *W* is the set of those sequences of 9 numbers in which (a) at the end, *A* has picked 3 squares in a row, column, or a diagonal, and (b) every move by *A* was legal, i.e., *A* didn’t pick a square that *B* had picked previously.

A winning strategy for *A* is a method by which *A* can force a win every time, i.e., a prescription which tells *A* what to pick for *m*_{1}, what to pick for *m*_{3} (depending on what *B* picked for *m*_{2}), what to pick for *m*_{5} (depending on what *B* picked for *m*_{2} and *m*_{4}), etc., so that *m*_{1}, …, *m*_{n} ∈ *W*. Similarly, a winning strategy for *B* is a prescription which tells *B* what to pick for *m*_{2} (depending on what *A* picked for *m*_{1}), what to pick for *m*_{4} (depending on what *A* picked for *m*_{1} and *m*_{3}), etc., so that *m*_{1}, …, *m*_{n} ∉ *W*. A game is determined if there’s either a winning strategy for player *A* or for player *B*.

Exercise: Show using only principles of ordinary predicate logic that every finite game is determined.

so, is go a finite game? Posted by Jonas!

Since every game is finite and each mi is a first-order statement satisfiable in a finite domain (since there are only finite possible moves in any finite game), the problem reduces to the n-satisfiability problem for first-order sentences, which is decidable. Therefore every finite game is determined (i.e. decidable).Is that what you mean? Posted by lumpy pea coat

That proves more than required, namely that finite games aren’t only determined, but that it is decidable which player has the winning strategy.I understand that the ko rule prohibits the same board configuration to repeat, so Go is a finite game. Posted by Richard Zach

I don’t have an answer. But I’d like to make a small point of clarification. It seems implicit in your definitions of winning strategies that every “play” of the game must result in either a win to player A or a win to player B. In this respect, Tic Tac Toe is not a good example of the kind of game you have in mind, since it allows for draws, where neither player wins. (At least, that’s the way I used to play it: if neither player made three in a row, the game was called a draw.)Another very minor point: when you write “W ⊆ M1, …, Mn”, I think you mean to write “W ⊆ M1xM2x … xMn”. (Or maybe that’s just a variation in notation). Posted by Campbell Brown