Hoofdstuk 10:
We can distinguish between different kinds of games:
- Games of chance – like roulette – where there is no good strategy for winning.
- Games of no chance – like tic-tac-toe or chess – where some moves are clearly better than
others.
10.1 Strategies for Games-of-No-Change
We are interested in two-player games of no chance with perfect information. This means that both
platers know what moves have been made up to that point in time, as well as what moves their
opponent can make in response to any move that they themselves make. Chess is a game of perfect
information, poker is not – as players only know the cards in their own hand. And we will only study
finite games that are guaranteed to end after some finite number of moves.
A strategy for a player in a game is a rule which tells that player what move to make each time it is
their turn to move. A position in a game is a winning position, if the player whose turn it is has a
winning strategy from this point. It is a losing strategy if the other player (whose turn it is not) has a
winning strategy from this position.
From a winning position must be a move to a losing position, while every move from a losing
position must lead to a winning position. From a drawing position there must be some move to a
drawing position, perhaps some moves to winning positions, but no moves to losing positions.
Example game “21”:
Two players count, starting from one. They take turns in saying one, two or three numbers. The
player that says “twenty-one” wins. How can player A always beat player B?:
- If it’s player A’s turn to say 21 he has won.
- If it’s player A’s turn, and the current count is 17 – he is in a losing position. Regardless of
player B’s move, he can always reach 21 and player A cannot win.
- By the same argument, 13 is also a winning position;
- As are 9, 5 and 1.
So the first player has a winning strategy: always finish on a number that is 1 modulo 4.
Reminder:
- A strategy is a rule that computes the best move a player can make at any given point in the
game.
- A winning strategy is one that guarantees the player will win the game.
- A drawing strategy is one that guarantees the player will win the game or draw (but not
lose).
- A position in a game is called a winning position if the current player has a winning strategy
(such as 19 in the game Twenty-one).
- If the other player has a winning strategy in the current position, this is known as a losing
position (such as 17 in the game Twenty-one).
, Example game “10 coins”:
There are 10 coins on a table. Players take turns by removing two or three coins. The player that
takes the last coin wins; if one coin remains, the game has ended in a draw.
If it is your turn and:
- there are no coins left, you are in a losing position;
- there is one coin left, you are in a drawing position;
- there are two coins left, you are in a winning position;
- there are three coins left, you are in a winning position;
We can tabulate the different kinds of positions for each number of coins:
We can also visualize this game by drawing a game tree describing the possible moves and
associated positions for each possible game state.
Each node contains a number, corresponding to the current game state; each node has two
subtrees, corresponding to the state after removing 2 or 3 coins. Furthermore, each node has been
decorated with a circle if it is a winning position and square if it is a losing position; the double
arrows indicate the best move to make at any given position.
We can distinguish between different kinds of games:
- Games of chance – like roulette – where there is no good strategy for winning.
- Games of no chance – like tic-tac-toe or chess – where some moves are clearly better than
others.
10.1 Strategies for Games-of-No-Change
We are interested in two-player games of no chance with perfect information. This means that both
platers know what moves have been made up to that point in time, as well as what moves their
opponent can make in response to any move that they themselves make. Chess is a game of perfect
information, poker is not – as players only know the cards in their own hand. And we will only study
finite games that are guaranteed to end after some finite number of moves.
A strategy for a player in a game is a rule which tells that player what move to make each time it is
their turn to move. A position in a game is a winning position, if the player whose turn it is has a
winning strategy from this point. It is a losing strategy if the other player (whose turn it is not) has a
winning strategy from this position.
From a winning position must be a move to a losing position, while every move from a losing
position must lead to a winning position. From a drawing position there must be some move to a
drawing position, perhaps some moves to winning positions, but no moves to losing positions.
Example game “21”:
Two players count, starting from one. They take turns in saying one, two or three numbers. The
player that says “twenty-one” wins. How can player A always beat player B?:
- If it’s player A’s turn to say 21 he has won.
- If it’s player A’s turn, and the current count is 17 – he is in a losing position. Regardless of
player B’s move, he can always reach 21 and player A cannot win.
- By the same argument, 13 is also a winning position;
- As are 9, 5 and 1.
So the first player has a winning strategy: always finish on a number that is 1 modulo 4.
Reminder:
- A strategy is a rule that computes the best move a player can make at any given point in the
game.
- A winning strategy is one that guarantees the player will win the game.
- A drawing strategy is one that guarantees the player will win the game or draw (but not
lose).
- A position in a game is called a winning position if the current player has a winning strategy
(such as 19 in the game Twenty-one).
- If the other player has a winning strategy in the current position, this is known as a losing
position (such as 17 in the game Twenty-one).
, Example game “10 coins”:
There are 10 coins on a table. Players take turns by removing two or three coins. The player that
takes the last coin wins; if one coin remains, the game has ended in a draw.
If it is your turn and:
- there are no coins left, you are in a losing position;
- there is one coin left, you are in a drawing position;
- there are two coins left, you are in a winning position;
- there are three coins left, you are in a winning position;
We can tabulate the different kinds of positions for each number of coins:
We can also visualize this game by drawing a game tree describing the possible moves and
associated positions for each possible game state.
Each node contains a number, corresponding to the current game state; each node has two
subtrees, corresponding to the state after removing 2 or 3 coins. Furthermore, each node has been
decorated with a circle if it is a winning position and square if it is a losing position; the double
arrows indicate the best move to make at any given position.
