1. Fibonacci Game#
Description#
The basic Fibonacci Game is described as follows:
There is a pile of stones, and two extremely intelligent people are playing a game. The first player can take any number of stones, but cannot take all of them. After that, each player can take a number of stones that is at least 1 and at most twice the number of stones taken by the opponent. The person who takes the last stone is the winner. Find the losing state.
Conclusion#
The first player will lose if and only if the total number of stones is a Fibonacci number.
Proof#
The proof is as follows, taken from a great proof.
Zeckendorf's theorem is used (also known as the Zeckendorf representation): any positive integer can be represented as the sum of several non-consecutive Fibonacci numbers.
2. Bash Game#
Description#
The basic Bash Game is described as follows:
There is a pile of n items, and two players take turns taking items. Each player can take at least one and at most m items. The player who takes the last item wins.
Conclusion#
If n % (m+1) == 0, then the first player will lose.
bool FirstWin(int n, int m) { // Returns true if the first player wins
return n % (m+1) != 0;
}
Proof#
The game process is as follows: Proof
Here is a brief explanation:
Congruence theorem: if n%(m+1) = r, if the first player takes r items, no matter how many items the second player takes from 1 to m, the first player can take enough items to make the total number of items (m+1), so the first player will win. On the contrary, the first player will lose. When n<m, the first player can take all the items at once, and still win.
Variation of Bash Game#
There is a pile of n items, and two players take turns taking items. Each player can take at least p and at most q items. When there are less than p items remaining, the player can take all of them. The player who takes the last item wins.
If n%(p+q) = r, then the first player will win if r != 0 && r < p, otherwise the first player will lose.
3. Wythoff Game#
Description#
The basic Wythoff Game is described as follows:
There are two piles of items, each with a certain number of items. Two players take turns taking the same number of items from one pile or from both piles. Each player can take at least one item, and there is no limit to the maximum number of items taken. The player who takes the last item wins.
Conclusion#
For two piles of items with a and b items respectively, calculate the difference between ab and multiply it by the golden ratio. Check if the result is equal to the minimum value in ab. If it is, then the first player will lose.
bool FirstWin(int a, int b) { // Returns true if the first player wins
double G = (sqrt(5.0)+1) / 2; // Golden ratio
int t = abs(a-b) * G;
return t != min(a,b);
}
Proof#
The proof is quite complex... Here is a placeholder for the code, and you can check the proof here.
4. Nim Game#
Description#
The basic Nim Game is described as follows:
There are several piles of items, each with a certain number of items. Two players take turns taking any number of items from one pile. Each player can take at least one item, and there is no limit to the maximum number of items taken. The player who takes the last item wins.
Conclusion#
XOR all the numbers of items in each pile. If the result is 0, then the first player will lose; otherwise, the first player will win.
bool FirstWin(int a, int b) { // Returns true if the first player wins
int ans = 0;
for(int i = 0; i < N; ++i) ans ^= a[i]; // a[i] represents the number of items
return ans != 0;
}
Proof#
The proof is also quite complex... You can check the proof here.
Later, we will introduce the SG function, and generally set the SG value of the final state to 0.
SG Theorem: The SG value of the sum of games is the XOR of the SG values of each subgame.
Knowing the above conclusions, we can see that the Nim game can actually be divided into n Bash games. If the subgame can be played infinitely, the current state of the remaining stones is the state, and SG(x)=x. Therefore, the answer to this problem is the XOR value of the number of stones in each pile. If the value is 0, the first player will lose; otherwise, the first player will always have a strategy to make the XOR value of the next state 0, and the second player will lose.
Variation#
Refer to the blog Nim Game and Its Variations
Misere Nim Game#
As the name suggests, in the Misere Nim Game,
There are several piles of items, each with a certain number of items. Two players take turns taking any number of items from one pile. Each player can take at least one item, and there is no limit to the maximum number of items taken. The player who takes the last item loses.
Example Problem E - Misere Nim
The first player can only win in two cases: 1) when all piles have 1 item and the XOR sum is 0, or 2) when there is a pile with more than 1 item and the XOR sum is not 0.
5. SG Function#
Refer to the blog: SG Function, Combinatorial Game - SG Function and SG Theorem
1. Introduction#
Impartial Combinatorial Game (ICG)#
The conditions are as follows: The description of the problem usually involves two players, A and B.
- A and B take turns making moves.
- After each move, the player can choose any valid move from a set of possible moves.
- For any possible game state, the set of valid moves depends only on that state and is independent of other factors (not related to the player or previous moves).
- If a player cannot make a valid move, they lose.
In the above-mentioned Bash Game background, there is a pile of n items, and two players take turns taking items. Each player can take at least one and at most m items. The player who takes the last item wins.
A fair game can be abstractly represented by a directed acyclic graph, where each point corresponds to a state, and each directed edge represents a valid move from one state to another.
Winning and Losing States#
- Losing state (P-position): The previous player (the player who just made a move) is in a winning position. Whoever faces this state will lose.
- Winning state (N-position): The next player (the player who is about to make a move) is in a winning position. Whoever faces this state will win.
Properties:
- All terminal nodes are losing states.
- From any winning state, there is at least one way to enter a losing state.
- No matter how you move, you can only enter a winning state from a losing state.
2. SG Function#
Definition of mex operation#
First, define the mex (minimal excludant) operation, which is applied to a set and represents the smallest non-negative integer that does not belong to the set.
- For example, mex{2,3,5}=0, mex{0,1,2,4}=3, mex{}=0.
For any state x, define SG(x)=mex(S), where S is the set of SG function values of the successor states of x. For example, if x has three successor states a, b, and c, then SG(x)=mex{SG(a), SG(b), SG(c)}. In this way, the set S will eventually become an empty set, so SG(x)=0 if and only if x is a losing point P.
Using the SG function, every ICG can be transformed into a Nim game. The domain of the SG function is all nodes on the decision tree of the ICG, which is specifically defined as: SG(x)=mex{SG(y)|y is a node of x}. For a node u on the decision tree of the ICG, we can imagine it as a Nim game with only one pile of stones, with a number of stones equal to the SG value of u. The calculation method of the SG function is understood through this blog: Combinatorial Game - SG Function and SG Theorem.
3. SG Theorem#
- The SG function of the sum of games is the XOR of the SG functions of each subgame, where all subgames are independent of each other.
- Therefore, the first player will win if and only if the XOR sum of the SG functions of each pile of stones is not 0.
6. Green Hackenbush (Tree Removal Game)#
I got stuck on the first problem and found out that it was a game I hadn't learned before, Green Hackenbush.
Refer to the blog: Game-Green Hackenbush, the following content is from there.
1. Overview of Hackenbush Game#
The Hackenbush game is played by removing certain edges from a rooted graph until there are no edges connected to the ground. The ground is represented by dashed lines, and when removing an edge, all edges connected above that edge will also be removed, just like cutting branches, where the parts above the branches will also be removed. Here, we discuss the fair version of this game, where each player can remove any edge on their turn. This version is called Green Hackenbush, and we will refer to it as the GH game. There is also an unfair version called Blue-Red Hackenbush, where some edges are blue and some are red, and player one can only remove blue edges, while player two can only remove red edges. In general, the Hackenbush game may have blue edges that only player one can remove, red edges that only player two can remove, and green edges that both players can remove.
2. Sprague-Grundy Theorem (Colon Principle)#
For a point on a tree, its branches can be transformed into a bamboo with this point as the root, and the length of this bamboo is the XOR sum of the number of edges in its branches.
When all edge weights are 1, it is a naked green game, and the sg function of each point is equal to the XOR sum of the sg functions of its child nodes plus 1.
When the edge weights are different, if the weights of A and B are both 1, sg[A]=sg[B]+1.
If the weights of A and B are even, sg[A]=sg[B].
If the weights of A and B are odd, sg[A]=sg[B]^1.