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.
Month: July 2005
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 W ⊆ M1, …, 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 m1 ∈ M1, then B moves by picking m2 ∈ M2, etc. The game ends after n moves (that’s why it’s finite). A wins if the sequence m1, … mn ∈ 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 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, …, mn ∈ W. 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, …, mn ∉ 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.