Game theory 1. Introduction (basic concepts of combination games, confrontation search, bash games, Nim games)

1. game

Game theory is a mathematical theory and method for studying phenomena with the nature of struggle or competition .

Every player has one Preference ,A Usually hope A win , If not, they tend to It ends in a draw ,B General tendency B win , If you can't reach it, you tend to draw . their Each step constitutes a “ function ”, Or rather, “ mapping ”, That is, each operation will correspond to a result , And every step is not fixed , It is generated according to the previous step ......

 “ The general game is very complicated , Generally, I can't work out the answer , Therefore, in the algorithm test, it is generally not tested , The ones who got a lot in the exam were the following ‘ Combination game ’”

2. Combination game （combinatorial game）

  Combination game Give it to Limit , Give the question simplify

“ The transfer of state ” -> “ Directed acyclic graph ”

 Bash game

 0 Stones are in the end state ,0 Can be 1 Come to , Can be 2 Come to , from 3 Come to ...4 It can reach 3,2,1......21 As a starting point , This can end in limited steps .

Bash The game is a combination game

Discuss the best strategy of the game , And who will win under the optimal strategy

P N state

Pay attention to the “ nature ”, And Bash The game has nothing to do with , All combination games are applicable .

 

  Shallow explanation ： For the picture above , The player A arrive 0 After the player B You can't take any more , Game over (A - ), therefore 0 by P state （A Go to the 0,A - ）; arrive 1 The player , Take this stone and the next player will arrive 0, Then the player who takes the next step wins The player lost ,1 by N state ;…… Can I get to P All States are N state , We call “ Current player ” by Players who go down from the current state , be P state ： The current player loses ,N state ： The current player wins . about P state , No matter how you walk, you will lose , So it's the optimal strategy , and N state To arrive P state , Make yourself win .

P N state We analyze game problems A basic tool .【 It's usually Push backward 】

Determine the final state ： Normal rules and abnormal rules

 Bash The game is a normal rule , So abnormal rules Bash What about the game ？（ Still upside down “ Recurrence ”）

  Example

1.【hdu 1404】Digital Diletions

 2.【hdu 1079】Calendar Game

  So a very important " universal " The way is ： The meter （ Learned to play a watch , The game problem is basically half solved ）

Let's go back to the first question , He is not satisfied Definition of combination game （ There will be no draw in the combined game ）, But it can still be solved with its ideas , Here you can. dp、 Recurrence , We only care about those “ Number pair ”（ The number of pairs corresponding to the beginning and end of palindrome determination ） The number of , We don't care where they are ,“1-1” You don't have to worry about it , Below f, We need to record “0-0” For the number of ,“0-1” For the number of ,0 The number of , And whether the flip operation was carried out in the previous step ....

3.【cf 1527 B2】Paindrome Game

 

 4. Mavericks fight again

analysis ：

（ Here it's manual “ The meter ” First ）N=0 when ,P state （ Normal rule ）;N=1 when , You can take them all ,N state ;

    N=2 when , Set these two piles ：x1>=x2>0; First , obviously （emogg Yes , Injured, I ）,x1==x2 by P state , Because we get x1 Take a part and go ( Put it or not x2 Are all the same ) become y, x2 , If y=0, Then enter. N=1 Of N State -> here x1==x2 by P state ; if y!=0, The second player can always turn it into two equal piles ： stay x2 Take that pile away （x2-y） A stone .... That is, always with the last player “ Against ”, such x1>x2 Namely N state .N=3 when , yes N state , set up x1>=x2>=x3>0 , So from x1 take （x2-x3） A gift x3( Throw away more ), obtain 0,x2, x2（P state ）; We can guarantee x1>(x2-x3) Of （ because x1>=x2, x2>x2-x3 ah ） therefore N=3 by N state ;

  Conclusion ：

1.N Is odd ->N state ;

2.N yes even numbers when , Pairing Just yes P, It is N;

 

prove ：

Put it all in order first ：x1>=x2>=x3>=...>=xn;

N When it's an odd number , Take the biggest one , Assign to the back （ All =x2）x1 >( x2-x3）+（x4-x5）+（x6-x7）.....+(X[n-1] - X[n]) As long as you change the order of the parentheses behind it, you can see ：x1 > x2 (- x3+x4) (-x5+x6) (-x7..)...( +X[n-1] ) - Xn; All included are less than 0 Of , also x1>=x2 ....

N When it's even , In pairs P state , If you are not paired, you can become paired in one step P state -> by N state , See the figure below ..

5.【cf 1537 D】Deleting Divisors