Logic and Finite Games

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 WM1, …, Mn, where each Mi is a finite set. Mi is the set of possible moves at step 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 m1M1, then B moves by picking m2M2, etc. The game ends after n moves (that’s why it’s finite). A wins if the sequence m1, … mnW, otherwise B wins (there are no draws).

This framework is pretty general. For instance, this is how tic-tac-toe fints the definition: each Mi = {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 m1, what to pick for m3 (depending on what B picked for m2), what to pick for m5 (depending on what B picked for m2 and m4), etc., so that m1, …, mnW. Similarly, a winning strategy for B is a prescription which tells B what to pick for m2 (depending on what A picked for m1), what to pick for m4 (depending on what A picked for m1 and m3), etc., so that m1, …, mnW. 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.

4 thoughts on “Logic and Finite Games

  1. 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

  2. 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

  3. 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

Leave a Reply to Anonymous Cancel reply

Your email address will not be published. Required fields are marked *