Thank you, Greg!

Greg Restall is way more dedicated and wired than I am. He already has two posts about what’s happening at the Logic Colloquium, and I just made it up the hill in the midday sun. I am so glad I didn’t pack my computer. So thank you, Greg, for blogging from the Logic Colloquium, so I don’t have to. Greg’s slides for his course are up, so you can follow along even if you’re not here with us in Athens.

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.