Game theory

Fair combination game ICG

• Two players alternate
• At any time of the game , The legal actions that can be performed have nothing to do with which player's turn
• The same state in the game cannot be reached multiple times , The game ends with the player unable to act , And it will end in a non draw after a limited step

Digraph game （ Game diagram ）

Given a directed acyclic graph , Have a unique starting point , There is a chess piece on it , Two players alternate to move the pieces along the opposite side , One step at a time , Those who can't move will be judged negative .

Any fair combination game can be transformed into a directed graph game .

• It's a must win situation ： It can make the other party go to a certain state of failure
• If you start, you'll lose ： The other party can't go to any state of failure

Theorem ：

1. A state without a successor state is a must fail state
2. A state is a winning state if and only if there is at least one losing state as its successor State
3. A state is a must lose state if and only if all its subsequent states are a must win state

Thus , You can use O(N + M) Time to get each state is a winning state or a losing state .（N Is the number of states , M Number of sides ）

• Must lose point （P spot ）： The point that the previous player will win
• Pizza Hut （N spot ）： The next player will win

1. All endpoints are fail points
2. Operate from any winning point , There is at least one way to get into the fail point
3. Whatever you do , You can only enter the winning point from the losing point

Internal fixation ： In the directed graph , aggregate X There is no boundary between any two points in .
External fixation ： In the directed graph , Any not in the set X There is a point that points to the set X The edge of .
nucleus ： In the directed graph , aggregate X It is an external fixed set , It is also internal fixation .
The nucleus is the set of all necessary States .

Theorem ： In a two person game , Agree to take the last step to win , If there are nuclei , Then one of them has an invincible strategy .
The initial state of the forehand is not in the core , Then the first hand must take some strategy to move the state to the core , turn B when ,B No matter what strategy is adopted , Will go out of the nuclear , So again and again ,A Will make B Always face the nuclear state . There is no way out of the core , Because the outside of the core can always go to the inside ,A Can maintain unbeaten .

Theorem ： A acyclic digraph with finite nodes has a unique kernel .

Nimm Game Nim Game

Given N Heap items , The first i Stack items Ai individual . Two players take turns , You can choose one pile at a time , Remove any number of items , You can take out a bunch of them , But we can't do without . Whoever takes the last item wins . Both take the best strategy , Ask if the first hand is sure to win .
There is no draw .

Conclusion ：
Definition Nim and by a1 ^ a2 ^ …… ^ an
If and only if Nim And for 0 when , This state is that the first hand will lose , On the contrary, the first hand will win .

Bash Game Bash Game

Yes 1 Rubble , The total number is n, Two players take turns to take stones in the stone pile , Take at least 1 individual , At most m individual . The player who takes the last stone is the winner , Decide who wins first and second .

Conclusion ：
if （m + 1）% n = 0 You will lose first , On the contrary, first hand wins .

Weizov game Wythoff Game

There are two piles of stones , The number of stones can be different . The two take turns taking stones , You can take... From a pile at a time , Or take the same number of stones from two piles , Any amounts , The man who took the last stone won . Determine whether the first hand is bound to win .

Conclusion ：
Suppose two piles of stones are （a,b） among a < b
Then you will lose first , If and only if （b - a）* （5 ^ (1 / 2) + 1） / 2 = a

Fibonacci game Fibonacci Game

There's a pile of numbers for n (n >= 2) The stone of the stone , Both sides of the game take turns taking stones , The following rules ：

1. You can't take all the stones the first time , At least 1 star .
2. After that, the number of stones that can be taken each time is at least 1 , It's at most the number of stones the opponent just took 2 times .

The person who agreed to take the last stone was the winner , Seeking is bound to fail .

Conclusion ：
If you start, you'll lose , If and only if the number of stones is Fibonacci number .

SG function Sprague - Grundy

set up S Represents a set of nonnegative integers .
mex(S) Find out that it does not belong to the set S The operation of the smallest nonnegative integer of .
namely mex(S) = min{x},x Belongs to natural number , And x Do not belong to S.

SG function It is an evaluation function for each node in the game graph .
Defining the end of the game SG Function value is 0, namely SG( End ) = 0.

For each node x ( The situation ), Set from x There are k The strip has a directed edge ( Legal operation ), Arrive at the node respectively y1, y2,……, yk( The next situation ), Definition SG(x) by x The successor node of .
y1, y2,……, yk Of SG Reexecution of a set of function values mex(S) Result of operation , namely ：
SG(x) = mex({SG(y1), SG(y2), …… , SG(yk)})

Special , The whole directed graph game G Of SG The function value is defined as the starting point of the directed graph game s Of SG Function value .

if SG(x) = 0, It is a state of inevitable failure , if SG(x) != 0, It is a winning state .
（ If it is not zero, it means that this point points directly to 0, That is, you can reach the state of failure , To win ）

nature ：

• For any situation , If it's SG The value is 0 , Then any subsequent situation of it SG Values are not for 0
• For any situation , If it's SG Values are not for 0, Then it must have a successor situation SG The value is 0

SG Theorem ：
All fair combination games under general victory can be transformed into Nim Count Express Nim pile game , A game Nim value Defined as the equivalence of this game Nim Count .
namely ： For the current game X, It can be divided into several sub Games x1, x2, ……, xn, that SG(X) = SG(x1) ^ SG(x2) ^ …… ^ SG(xn)

For the n A composition game consisting of a directed graph game , Let them start from s1, s2, ……, sn, If and only if SG(s1) ^ SG(s2) ^ …… ^ SG(sn) != 0 when , This game is the first to win .

Originally, all points of the game graph should be considered , High complexity , But now through SG function , Just consider the starting point .