Theory 3: Sequential Games I: Perfect Information and no Randomness
Erich Prisner · American Mathematical Society eBooks · 2014
“Life can only be understood backwards, but it must be lived forwards.” —Soren Kierkegaard Example 1 NIM(6) Six stones lie on the board. Black and White alternate to remove either one or two stones from the board, beginning with White. Whoever first faces an empty board when having to move loses. The winner gets $1, the loser loses $1. What are the best strategies for the players? Student Activity Try your luck in applet AppletNim7 against a friend (hit the “Start new with 6” button before you start). Or play the game against the computer in AppletNim7c . Play ten rounds where you start with seven stones. Then play ten rounds where you start with nine stones. Then play ten rounds where you start with eight stones. Discuss your observations. In this chapter we look at a class of simple games, namely sequential games. They are games where the players move one after another. Among them we concentrate on games of perfect information, where players know all previous decisions when they move. Randomness will be included after the next chapter. We will learn a little terminology, see how to display the games either as a game tree or a game digraph, and how to analyze them using “backward induction” provided the game is finite. We conclude by discussing whether the solution found by backward induction would be what real players would play, by discussing another approach for sequential games, by discussing the special roles two-person zero-sum games play here, and by discussing briefly the well-known sequential games chess, checkers, and tic-tac-toe.