Tic‐Tac‐Toe and Other Sequential Games of Perfect Information

The sequential games are fundamentally different from the simultaneous games because players can account for the moves previously made by their opponent when making their own decisions. This chapter focuses on sequential games of perfect information, in which outcomes are not randomly determined. It considers three sequential games, including the centipede game, tic-tac-toe, and the game of Nim. In all the three examples, it was possible to find optimal strategies for the games using backward induction and, once those strategies were obtained, the outcome of the game was predetermined. Sequential games can be solved by recursively deciding what is the best decision faced by the last player to move and then moving up the decision tree. This procedure for solving sequential games is known as backward induction, and it can be used to solve any finite, two-person sequential game of perfect information.