Take my Philosophy and Logic of Games final exam!
Can you pass the exam for my games course?
We just finished up the Philosophy and Logic of Games, my new course here at Notre Dame exploring all things games. What a lot of fun it was—many students told me how much they enjoyed the class.
I am sharing here the questions from which the final exams were drawn.
About the class
First let me say a little about the class. We began with some elementary game theory and decision theory, and some philosophical accounts of what is a game in the first place, before getting into the fundamental theorem of finite games, game trees, the hypergame paradox, and many examples of finite games and their strategies, such as Nim, 21, tic-tac-toe, including 3D tic-tac-toe, and many other games. Eventually we discussed determinacy issues and connections with the philosophy of mathematics, such as supertasks. A final highlight of the class was to cover the analysis of various infinite games, including infinite chess, infinite draughts, infinite Hex, infinite Wordle, infinite Sudoku, and more.
In addition to regular course work with quizzes and so forth, the students had to pass various games challenges with me during the semester, playing me one-on-one in Nim, 21, Gold-coin game, chess, Hex, draughts, Go, Connect 4, Othello, and also to solve the Rubik’s cube.
The course was open to all students, with no prerequisites, and fulfilled the university 2nd philosophy requirement.
Final exam questions
The final exam questions were drawn from the following. Please post your answers in the comments!
Suppose that an evil king hauls up two innocent prisoners from his dungeon to play chess against each other, with the instructions that the winner will be set free, while the loser will be executed. The prisoners meekly begin playing. According to the criterion of Bernard Suits in his essay on what is a game, are the prisoners playing a game? Please defend your answer with detailed reference to the Suits criterion, explaining why this situation does or does not meet it.
Explain why the penny partition paradox is also known as the “Centipede game.” Give a fully self-contained explanation of the paradox and why it might deserve this title.
Give an example of a finite-play game that is not a finite game, if possible (or explain why it is not possible), and similarly for a finite game that is not a finite-play game. As a part of your answer, explain the precise meanings and differences between these notions.
During the leisure time at a certain fire station, the fire fighters like to play a certain finite-play two-player game of perfect information, called Fireout! The game is a little dangerous, however, in that some moves cause the game itself to catch fire. Indeed, every single move made on the game when not on fire will cause it to burst into flames. But whenever the game is on fire, then thankfully there is some move in the game that will immediately extinguish the fire (even if some other moves leave the game fully alight).
The game will inevitably come to an end, for complicated reasons involving the details of game play. The player making the final move will lose if the end state of the game is that it is on fire, but if it is not on fire, then they win. Without knowing any further details about the game, can you describe a winning strategy for this game? If so, provide full details for how exactly the player should play, covering all contingencies, and provide an argument for why your strategy is a winning strategy. From which sort of positions will your strategy be winning? If the game starts without fire, should you rather go first or second?
Give a careful explanation of the hypergame paradox and explain how you think it can be resolved or why it cannot be resolved.
Explain, as fully and precisely as possible, in the context of a two-player game of perfect information: what is a strategy? what is a game tree? what is a winning strategy? what is a drawing strategy?
State the fundamental theorem of finite games, and provide a proof of it using the back-propagation method for the case of games with no draws.
Explain how we can use the fundamental theorem of finite games without draws to prove the theorem for the case of games with draws. That is, how might we argue for the fully general version of the theorem, if we have already established the theorem for games without draws?
What are the main things to say about 3D tic tac toe in terms of winning strategies and the possibility of draws?
Consider the game of Hex played with the swap rule, meaning that on the very first move only, the first player places a tile on the board, and then the second player at his option can choose to accept that move and play continues or instead to take that move as his own (so the player roles and colors swap). Using the fundamental theorem, show that the second player has a winning strategy in the swap rule variation of Hex.
Suppose you work as a waiter at Cafe Infinity, which features infinitely many tables—table 0, table 1, table 2, and so forth, each with infinitely many seats, seat 0, seat 1, and so forth. The restaurant is empty at the start of the shift. At each ring of the bell, however, the manager sends in infinitely many new hungry customers, exactly one additional for each table. But alas, you are able to serve only one customer in each time interval. The bell rings get faster and faster as the evening progresses, so that by close there will be infinitely many intervals. Ordinarily, each table has its own waiter, and the customers are easily served. But tonight it turns out that there is only you on duty, and you must serve all the tables. Can you do it? Will you be able to serve all the customers? If so, explain how, or if not, explain why.
How well did you do on the exam? Post your solutions in the comments. Please post one solution per comment, so we can have a discussion about the details of each separately.
See all the other games posts here: Infinite Games.
What’s coming
Stay tuned for more logic of games posts continuing through the summer. I plan to continue posting on determinacy issues, including nondetermined games, and several more explicitly mathematical issues arising in the philosophy and logic of games. I also plan eventually to have introductory essays on the various infinite games, including infinite chess, infinite draughts, infinite Hex, and so forth.
In addition, I will soon begin posting again on various topics in mathematical logic.
11. Can be done by an argument similar to the countability of the rationals. Every customer is assigned a pair (a, b), where a is the time they were seated, and b is their table number. Then we serve customer (a, b) at time T(a, b) = (a+b)(a+b+1)/2 + a. Every customer is served, and at every time only one customer is served (this can be shown as follows - if (a, b) and (p,q) are two customers, and if a+b < p+q, then T(a, b) < (a+b+1)(a+b+2)/2 <= T(p, q). If a+b = p+q, then if a < p, then also T(a, b) < T(p, q). All other cases are similar.).
Sounds like a fun class! Is there any course material that is available online?
4. Basically there are two states, on fire and not. From the on fire state, there is always a transition to being not on fire. From the not on fire state, there is only the transition to being on fire.
So at best, que of your moves should be to put the fire out, leaving your opponent no choice but to light it again, alternating states. So if it starts not on fire, you should go second.
11. Sounds like a job for a diagonal argument.