Game Theory and the Sprague-Grande Function
Good day, dear Habrasoobschestvo.
Recently, olympiad programming has become more and more widespread, an integral part of which is the knowledge of algorithms (and, of course, the ability to use them).
I want to tell you the basics of the theory of the Games, prove the function of Sprag-Grande, analyze several classic impartial-problems and illustrate them with python code.
')
Search on Habrakhabr showed that about a function of Shprag-Grande already wrote . Unfortunately, very little and not very understandable for a person who has not come across the theory of the Games before. I will try to open this topic wider.
We should start with the fact that the theory developed by Roland Shprag and Patrick Grandi in the middle of the last century extends to games that can be called “equal” (impartial). This category includes games in which the following conditions are met:
As examples of such games you can cite the game Nim , Bash and other games. We will talk about them a bit later, but for now we will discuss what follows from the conditions.
The main point, of course, is the finiteness of the game, from which it follows that the process itself can be represented as a movement along an acyclic oriented graph, the vertices of which are the game states, and the edges are transitions between them as a result of the player's turn.
From the fact that the game is impossible to draw, it follows that the state of the game can be divided into winning and losing. The first are those from which you can go to a losing state, and the second - from which you can not go anywhere, or you can, but only in a winning state.
Thus, the solution of problems on the theory of Games related to “equal rights” games can be reduced to studying the state graph of the game and determining the final result.
Consider an example of finding a winning strategy on the example of the game Nimes. Why? Because later it will be possible to prove that the conditions of all "equal" games can be reduced to the conditions of the game by Him.
So, we have N heaps, each of which has a positive amount of stones. Players take turns picking up a positive amount of stones. When all the heaps become empty, the game ends with the defeat of the player who cannot make a move. Consequently, the state of the game can be described by a set of Npositive positive 0 numbers, and the game ends when the sum of these numbers becomes zero.
Let's prove it.
Suppose we have two arrays of values ​​(before [], after []), in one of which (before []) the sizes of the heaps are stored before the player’s turn, and in the other (after []) - after the player’s move.
We will store in variables bf and af xor-sums before and after the player’s turn (where “^” is operation xor):
bf = before [0] ^ before [1] ^ ... ^ before [N - 1] ^ before [N]
af = after [0] ^ after [1] ^ ... ^ after [N - 1] ^ after [N]
Then, using the corollary of the properties xor, we can write:
af = bf ^ before [i] ^ after [i], where "i" is the number of the pile from which the player who made the move took the stones.
Based on the above, we prove Theorem # 1 by induction (consider two cases: bf == 0 and bf! = 0):
If bf == 0, then the current state is either losing (and so there are no transitions from it), or there are transitions, but for them the equality af == bf [i] ^ af [i] holds, but since before [i]! = after [i], then af! = 0, which means the transition leads to a winning state by induction.
If bf! = 0, then you need to determine which move will lead to the losing state (ie, af == 0):
Consider the bit record of the number bf. Take the leading nonzero bit, denoting its number by q. Let k be the number of that before [] number, in which the qth bit is nonzero (in other words, the number of the required handful).
Suppose that after [k] = before [k] ^ bf (it is assumed that this is the desired move). Why is it correct? Because after [k] <before [k]. This follows from the fact that all bits higher than the qth of the after [k] and before [k] are the same, and the qth bit of the before [k] contains a one, and that of the after [k] is zero.
Then we calculate:
af = bf ^ before [k] ^ after [k] = bf ^ before [k] ^ (bf ^ before [k]) = 0
Since during this move the xor-sum is zero, the theorem is proved.
What follows from Theorem 1? It follows from it that any state of a nim-like (“equal”) game can be replaced by an equivalent, but consisting of a single pile, the size of which is equal to the XOR-sum of the sizes of the piles in the old state.
The state of any "equal" game can be depicted in the form of it-heaps. If the heap size is zero, then the state is losing. If not equal - winning.
Suppose we have a certain state G [], equivalent to a certain heap of size X. This number can be found by induction. If we know that the state G [i] corresponds to m [i], then m [] will be as follows:
m = mex {m [1], ..., m [k]} 2 .
This is precisely the function of the Spraga-Grandey: if we need to determine the winner of an “equal” game, then we reduce it to them — groups, consider G () for each of the heaps and find their xor sum.
In other words, G (k, n, m) = G (k) ^ G (n) ^ G (m).
Now let us analyze the Spraga-Grandi function by the example of the olympiad problem that I encountered in the qualifying round of the Summer Computer School. The conditions of the problem were as follows:
It is necessary to determine who in the optimal game will pay a fine for the robot. Obviously, this game is similar to him: it is finite, a draw is impossible in it, and both players see information about the opponent’s progress.
What does it boil down to? That's right, to the definition of the G-function from the city with the number 1.
Consider the example code. We assume that we have an adjacency matrix with removed edges (we will delete the edge a -> b if city b burns before city a).
Then the Spray-Grande function for this problem will be calculated as follows:
If the function returns “1”, then at the optimal game Vladimir will win.
Now consider the situation with him-like game, but with many conditions. Let there be a bunch of stones, the number of which is odd. At a time, you can take no more than four stones from the pile. The game continues until the stones run out. The one who took an even amount of stones does not win.
At first glance, the game is no longer analyzed using the Sprag-Grande function. Why? Because the state of the game determines not only the number of stones in the pile - the stones of the players are also important. But it's easy to take into account, if you take as a game state
G () of the numbers n, m and p, where n is the number of stones in the pile, and m and p are the parity of the stones of the players (0 is an odd number, 1 is an even number).
There are two possible game end situations in which n == 0:
G (0, 0, 1) and G (0, 1, 0).
The first situation is a bit uncharacteristic for ordinary him-games - the player cannot make a move, but since the number of his stones is even, he did not lose. To depict this on the graph, add a transition:
(0, 0, 1) -> (0, 1, 0)
If we now draw the graph, we can note the following frequency:
G (n, m, p) = G (a, m, p),
where a = n mod 6
What does this give us? Let the stones in the handful 27. Then G (27, 0, 0) = G (3, 0, 0) = 3. The beginner wins, and the move that creates a winning position must translate (3, 0, 0) -> ( 100). Therefore, to win a beginner need to take two stones.
The Spraga-Grandi function is an integral part of the like-like (“equal”) games and the theory of the Games as a whole. Solving problems with it is reduced to determining the function G () from each state of the game and finding their xor sum (this is also called the “sum of the game”).
For games in which the number of states is so large that it is considered resource intensive, it is possible to find certain patterns. In addition, quite often the function Spraga-Grande is periodic.
0 despite the controversial nature of this issue , zero will also be considered a natural number.
1 xor-sum of a [N] is the expression a [1] ^ a [2] ^ ... ^ a [N].
2 mex from the set of numbers is the smallest non-negative number not found in this set (from English minimum excludant).
For a more detailed study of this topic I recommend books:
E. Berlekamp, ​​JH Conway, R. Guy. Winning Ways for your Mathematical Plays
JH Conway. On Numbers And Games.
And quite an interesting course of lectures .
Unfortunately, all this is in English.
If you want to solve tasks on this topic, then I recommend this and other similar tasks .
Successes!
UPD : moved to "Sport Programming".
Recently, olympiad programming has become more and more widespread, an integral part of which is the knowledge of algorithms (and, of course, the ability to use them).
I want to tell you the basics of the theory of the Games, prove the function of Sprag-Grande, analyze several classic impartial-problems and illustrate them with python code.
')
Instead of the preface
Search on Habrakhabr showed that about a function of Shprag-Grande already wrote . Unfortunately, very little and not very understandable for a person who has not come across the theory of the Games before. I will try to open this topic wider.
We should start with the fact that the theory developed by Roland Shprag and Patrick Grandi in the middle of the last century extends to games that can be called “equal” (impartial). This category includes games in which the following conditions are met:
- the game is finite
- no draw is possible in the game
- players see all information about the state of the opponent
As examples of such games you can cite the game Nim , Bash and other games. We will talk about them a bit later, but for now we will discuss what follows from the conditions.
The main point, of course, is the finiteness of the game, from which it follows that the process itself can be represented as a movement along an acyclic oriented graph, the vertices of which are the game states, and the edges are transitions between them as a result of the player's turn.
From the fact that the game is impossible to draw, it follows that the state of the game can be divided into winning and losing. The first are those from which you can go to a losing state, and the second - from which you can not go anywhere, or you can, but only in a winning state.
Thus, the solution of problems on the theory of Games related to “equal rights” games can be reduced to studying the state graph of the game and determining the final result.
Game Nim
Consider an example of finding a winning strategy on the example of the game Nimes. Why? Because later it will be possible to prove that the conditions of all "equal" games can be reduced to the conditions of the game by Him.
So, we have N heaps, each of which has a positive amount of stones. Players take turns picking up a positive amount of stones. When all the heaps become empty, the game ends with the defeat of the player who cannot make a move. Consequently, the state of the game can be described by a set of N
Theorem # 1:
For the current player, the strategy is winning if and only if the xor sum of 1 heap sizes is positive.
Let's prove it.
Suppose we have two arrays of values ​​(before [], after []), in one of which (before []) the sizes of the heaps are stored before the player’s turn, and in the other (after []) - after the player’s move.
We will store in variables bf and af xor-sums before and after the player’s turn (where “^” is operation xor):
bf = before [0] ^ before [1] ^ ... ^ before [N - 1] ^ before [N]
af = after [0] ^ after [1] ^ ... ^ after [N - 1] ^ after [N]
Then, using the corollary of the properties xor, we can write:
af = bf ^ before [i] ^ after [i], where "i" is the number of the pile from which the player who made the move took the stones.
Based on the above, we prove Theorem # 1 by induction (consider two cases: bf == 0 and bf! = 0):
If bf == 0, then the current state is either losing (and so there are no transitions from it), or there are transitions, but for them the equality af == bf [i] ^ af [i] holds, but since before [i]! = after [i], then af! = 0, which means the transition leads to a winning state by induction.
If bf! = 0, then you need to determine which move will lead to the losing state (ie, af == 0):
Consider the bit record of the number bf. Take the leading nonzero bit, denoting its number by q. Let k be the number of that before [] number, in which the qth bit is nonzero (in other words, the number of the required handful).
Suppose that after [k] = before [k] ^ bf (it is assumed that this is the desired move). Why is it correct? Because after [k] <before [k]. This follows from the fact that all bits higher than the qth of the after [k] and before [k] are the same, and the qth bit of the before [k] contains a one, and that of the after [k] is zero.
Then we calculate:
af = bf ^ before [k] ^ after [k] = bf ^ before [k] ^ (bf ^ before [k]) = 0
Since during this move the xor-sum is zero, the theorem is proved.
What follows from Theorem 1? It follows from it that any state of a nim-like (“equal”) game can be replaced by an equivalent, but consisting of a single pile, the size of which is equal to the XOR-sum of the sizes of the piles in the old state.
Spraga Grande function
The state of any "equal" game can be depicted in the form of it-heaps. If the heap size is zero, then the state is losing. If not equal - winning.
Suppose we have a certain state G [], equivalent to a certain heap of size X. This number can be found by induction. If we know that the state G [i] corresponds to m [i], then m [] will be as follows:
m = mex {m [1], ..., m [k]} 2 .
This is precisely the function of the Spraga-Grandey: if we need to determine the winner of an “equal” game, then we reduce it to them — groups, consider G () for each of the heaps and find their xor sum.
In other words, G (k, n, m) = G (k) ^ G (n) ^ G (m).
Tasks
Now let us analyze the Spraga-Grandi function by the example of the olympiad problem that I encountered in the qualifying round of the Summer Computer School. The conditions of the problem were as follows:
On a certain island fires are raging. The robot was able to extinguish all the cities except one.
The flame spreads very quickly, so every day the fire consumes all the cities,
connected by road with already burning cities. Robot can not put out anything
the only thing left for him is to escape from the fire. The speed of the robot coincides with
fire speed, so one day the robot can move to a nearby city.
The robot is shifted by two pilots Nikolai and Vladimir, who are on
natural satellite of the Earth. Despite the fact that the robot is no longer save and benefit from it
there is no, the pilots are very interested that it should not be destroyed in their shift. Behind
the loss of the robot relies a decent wage deduction.
On the first day, the robot is in the capital (city number 1). Nikolai controls the robot
on the first day and can send it to an arbitrary city connected to 1. Then the pilots
alternate. Thus, every day the only thing that a robot can do is
move to any city adjacent to its current location.
On the first day only the capital burns. Every next day
all cities connected by roads with already burning light up.
If the pilot leaves the robot in a burning city or sends it to an already burning one
city, the robot does not hold up fire and is destroyed.
It is necessary to determine who in the optimal game will pay a fine for the robot. Obviously, this game is similar to him: it is finite, a draw is impossible in it, and both players see information about the opponent’s progress.
What does it boil down to? That's right, to the definition of the G-function from the city with the number 1.
Consider the example code. We assume that we have an adjacency matrix with removed edges (we will delete the edge a -> b if city b burns before city a).
Then the Spray-Grande function for this problem will be calculated as follows:
def Grundy(): for i in range(N): if matrix[v][i] == 1: if Grundy(i) == 0: return 1 exit return 0 If the function returns “1”, then at the optimal game Vladimir will win.
Now consider the situation with him-like game, but with many conditions. Let there be a bunch of stones, the number of which is odd. At a time, you can take no more than four stones from the pile. The game continues until the stones run out. The one who took an even amount of stones does not win.
At first glance, the game is no longer analyzed using the Sprag-Grande function. Why? Because the state of the game determines not only the number of stones in the pile - the stones of the players are also important. But it's easy to take into account, if you take as a game state
G () of the numbers n, m and p, where n is the number of stones in the pile, and m and p are the parity of the stones of the players (0 is an odd number, 1 is an even number).
There are two possible game end situations in which n == 0:
G (0, 0, 1) and G (0, 1, 0).
The first situation is a bit uncharacteristic for ordinary him-games - the player cannot make a move, but since the number of his stones is even, he did not lose. To depict this on the graph, add a transition:
(0, 0, 1) -> (0, 1, 0)
If we now draw the graph, we can note the following frequency:
G (n, m, p) = G (a, m, p),
where a = n mod 6
What does this give us? Let the stones in the handful 27. Then G (27, 0, 0) = G (3, 0, 0) = 3. The beginner wins, and the move that creates a winning position must translate (3, 0, 0) -> ( 100). Therefore, to win a beginner need to take two stones.
Let's sum up
The Spraga-Grandi function is an integral part of the like-like (“equal”) games and the theory of the Games as a whole. Solving problems with it is reduced to determining the function G () from each state of the game and finding their xor sum (this is also called the “sum of the game”).
For games in which the number of states is so large that it is considered resource intensive, it is possible to find certain patterns. In addition, quite often the function Spraga-Grande is periodic.
Notes
0 despite the controversial nature of this issue , zero will also be considered a natural number.
1 xor-sum of a [N] is the expression a [1] ^ a [2] ^ ... ^ a [N].
2 mex from the set of numbers is the smallest non-negative number not found in this set (from English minimum excludant).
Literature
For a more detailed study of this topic I recommend books:
E. Berlekamp, ​​JH Conway, R. Guy. Winning Ways for your Mathematical Plays
JH Conway. On Numbers And Games.
And quite an interesting course of lectures .
Unfortunately, all this is in English.
Tasks for self-study
If you want to solve tasks on this topic, then I recommend this and other similar tasks .
Successes!
UPD : moved to "Sport Programming".
Source: https://habr.com/ru/post/124856/
All Articles