Editing Game theory
Warning: You are not logged in. Your IP address will be publicly visible if you make any edits. If you log in or create an account, your edits will be attributed to your username, along with other benefits.
The edit can be undone.
Please check the comparison below to verify that this is what you want to do, and then save the changes below to finish undoing the edit.
Latest revision | Your text | ||
Line 11: | Line 11: | ||
===Availability of information=== | ===Availability of information=== | ||
− | When all players know the entire state of a game at any given time, the game is said to be ''perfect information''. Perfect information games include chess, Go, and tic-tac-toe. Most games of interest in mathematics and computer science are perfect information games | + | When all players know the entire state of a game at any given time, the game is said to be ''perfect information''. Perfect information games include chess, Go, and tic-tac-toe. Most games of interest in mathematics and computer science are perfect information games. Imperfect information games include most card games, as each player usually hides cards from opponents. |
===Partiality=== | ===Partiality=== | ||
Line 22: | Line 22: | ||
An important class of games consists of those between two players in which there are only two possible outcomes: victory and loss. If the winner is the last player who is able to make a legal move, the game is said to follow the ''normal play'' convention. Otherwise, it is said to follow the ''misère play'' convention. Dominoes is an example of a normal play game. | An important class of games consists of those between two players in which there are only two possible outcomes: victory and loss. If the winner is the last player who is able to make a legal move, the game is said to follow the ''normal play'' convention. Otherwise, it is said to follow the ''misère play'' convention. Dominoes is an example of a normal play game. | ||
− | ==N-positions and P-positions== | + | ===N-positions and P-positions=== |
In a two-player, deterministic, impartial game which is guaranteed to end in a finite number of moves, an ''N-position'' is a configuration such that the '''n'''ext player to make a move can force victory, and a ''P-position'' is a configuration such that the '''p'''revious player who moved can force victory. In a normal-play game, a configuration in which no further moves are possible is a P-position, since the player who is supposed to move next cannot do so and loses; in a misère-play game, it is an N-position, since the player who moved last made the last move and hence lost. | In a two-player, deterministic, impartial game which is guaranteed to end in a finite number of moves, an ''N-position'' is a configuration such that the '''n'''ext player to make a move can force victory, and a ''P-position'' is a configuration such that the '''p'''revious player who moved can force victory. In a normal-play game, a configuration in which no further moves are possible is a P-position, since the player who is supposed to move next cannot do so and loses; in a misère-play game, it is an N-position, since the player who moved last made the last move and hence lost. | ||
Line 29: | Line 29: | ||
* Otherwise (at least one P-position is reachable from <math>C</math>) <math>C</math> is an N-position, and a winning strategy necessarily entails leaving behind one of these P-positions for the next player. | * Otherwise (at least one P-position is reachable from <math>C</math>) <math>C</math> is an N-position, and a winning strategy necessarily entails leaving behind one of these P-positions for the next player. | ||
− | == | + | ==Nimbers== |
− | + | A game which is | |
+ | * deterministic, | ||
+ | * impartial, | ||
+ | * normal play, and | ||
+ | * guaranteed to end in a finite number of moves | ||
+ | can be analyzed using the '''Sprague-Grundy theorem'''. We shall denote such games as ''Nim-like''. (Note that this term is not in use in the academic literature.) | ||
− | === | + | ===Nim=== |
− | + | ||
− | + | ||
− | + | ||
The name ''nimber'' alludes to what is perhaps the simplest interesting example of such a game: Nim. The rules of the game are as follows: | The name ''nimber'' alludes to what is perhaps the simplest interesting example of such a game: Nim. The rules of the game are as follows: | ||
# The game board consists of one or more piles of sticks. | # The game board consists of one or more piles of sticks. | ||
Line 42: | Line 44: | ||
It is deterministic because the outcome of the game depends entirely upon the players' decisions and not upon any element of chance, it is perfect-information because we assume that both players know the sizes of all piles at any time, it is impartial because any move available to one player is available to the other and because both players have the same goal, it is normal play because the last to move wins, and it is guaranteed to end in a finite number of moves because each move removes at least one stick from the total count of sticks in play. | It is deterministic because the outcome of the game depends entirely upon the players' decisions and not upon any element of chance, it is perfect-information because we assume that both players know the sizes of all piles at any time, it is impartial because any move available to one player is available to the other and because both players have the same goal, it is normal play because the last to move wins, and it is guaranteed to end in a finite number of moves because each move removes at least one stick from the total count of sticks in play. | ||
− | + | ====Winning strategy==== | |
We state here the solution to Nim, a well-known result, and show later how it fits into the framework of Nim-like games in general. Simply compute the bitwise XOR of the sizes of all piles gives the ''nim-sum'' of a configuration of Nim. If this is zero, then the configuration is a P-position; otherwise it is an N-position. For example, if there are three piles containing one, two, and three sticks, respectively, the nim-sum is 1 XOR 2 XOR 3 = 0, and the configuration is a P-position; however, if instead of a three-stick pile we had a four-stick pile, the nim-sum would be instead 1 XOR 2 XOR 4 = 7, and the configuration would be a N-position. | We state here the solution to Nim, a well-known result, and show later how it fits into the framework of Nim-like games in general. Simply compute the bitwise XOR of the sizes of all piles gives the ''nim-sum'' of a configuration of Nim. If this is zero, then the configuration is a P-position; otherwise it is an N-position. For example, if there are three piles containing one, two, and three sticks, respectively, the nim-sum is 1 XOR 2 XOR 3 = 0, and the configuration is a P-position; however, if instead of a three-stick pile we had a four-stick pile, the nim-sum would be instead 1 XOR 2 XOR 4 = 7, and the configuration would be a N-position. | ||
If, on your turn, you are faced with a P-position, it doesn't matter what you do; your opponent can force you to lose. If, on the other hand, you are faced with an N-position, you want to leave a P-position for your opponent. In the example with one, two, and four sticks, you would want to take one stick from the four-stick pile, leaving behind one, two, and three sticks for your opponent: a P-position. Repeatedly applying this strategy guarantees victory. | If, on your turn, you are faced with a P-position, it doesn't matter what you do; your opponent can force you to lose. If, on the other hand, you are faced with an N-position, you want to leave a P-position for your opponent. In the example with one, two, and four sticks, you would want to take one stick from the four-stick pile, leaving behind one, two, and three sticks for your opponent: a P-position. Repeatedly applying this strategy guarantees victory. | ||
− | + | ====Nimbers in Nim==== | |
The '''nimber''' of a position in Nim is equal to its nim-sum, as defined above: the nimber of a single pile of sticks is simply the number of sticks in it, and the nimber of a collection of piles is the bitwise XOR of the nimbers of the individual piles. | The '''nimber''' of a position in Nim is equal to its nim-sum, as defined above: the nimber of a single pile of sticks is simply the number of sticks in it, and the nimber of a collection of piles is the bitwise XOR of the nimbers of the individual piles. | ||
− | + | ===Disjunctive sum of games=== | |
− | In some cases, a position in a game may be analyzed as the '''disjunctive sum''' of two or more sub-positions of the same game. This means that a player chooses exactly one of those sub-positions and makes exactly one valid move in it. | + | In some cases, a position in a game may be analyzed as the '''disjunctive sum''' of two or more sub-positions of the same game. This means that a player chooses exactly one of those sub-positions and makes exactly one valid move in it. For example, if a Ni |
− | + | ===Statement of the theorem=== | |
The Sprague-Grundy theorem is the remarkable result that '''a nimber can be assigned to any configuration of any Nim-like game'''. This means that nimbers are useful in the analysis of not only Nim itself but of any Nim-like game. There are only a few simple rules for assigning nimbers: | The Sprague-Grundy theorem is the remarkable result that '''a nimber can be assigned to any configuration of any Nim-like game'''. This means that nimbers are useful in the analysis of not only Nim itself but of any Nim-like game. There are only a few simple rules for assigning nimbers: | ||
− | # A nimber is a non-negative integer. | + | # A nimber is a non-negative integer. |
− | # The nimber of a position is the smallest possible value that does not appear among the nimbers of positions reachable from it in a single move | + | # The nimber of a position is the smallest possible value that does not appear among the nimbers of positions reachable from it in a single move. For example, if no moves are possible from a given configuration, the nimber is zero. If moves possible from a given configuration lead to other configurations with nimbers of 3, 0, 5, and 2, then the nimber for the given configuration is 1: the smallest non-negative integer that doesn't appear among these. |
− | # | + | # Suppose that a |
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + |