Mathematical knowledge -- ideas and examples of game theory (bash game, Nim game, wizov game)

Fundamentals of game theory

    Game theory is also called Game theory (Game Theory), It's a new branch of modern mathematics , It's also an important subject of operational research . Game theory mainly studies formulaic Interaction between incentive structures , It is a mathematical theory and method to study the phenomenon of struggle or competition . Game theory considers... In the game Individual's predicted behavior and actual behavior , And study Their optimization strategy .

introduce ： Prisoner's dilemma

    The story of the prisoner's dilemma is , Two suspects are small A、 Small B He was caught by the police after committing the crime , They were kept in different rooms for interrogation . The police knew they were guilty , But there is not enough evidence . The police told everyone : If both deny , Each was sentenced to one year ; If both of them confess , Five years for each ; If one of them confesses and the other denies , Let go frankly , Those who deny will be sentenced to ten years .

therefore , Every prisoner faces two choices : To confess or deny .

    In discord B Under the condition of negotiation , As a little A You chose to confess and go to jail 5 Years or 0 year , Will still choose to deny imprisonment 10 Years or 1 Years? ？

                                        

The average person would choose to be a little safer To confess Well .

    In contrast, small B, Will certainly make the same choice , That is to confess . let me put it another way , As long as both prisoners are selfish and rational , Then both sides will choose to confess at the same time , The result is that both sides decide 5 year .

    In this scenario , Neither side can One sided Change your game strategy （ Unilateral change will only make you suffer losses ）, The situation has entered a delicate and stable balance , This balance is called Nash equilibrium .

    In reality , There are many similar phenomena , For example, parents sign up for more and more extra-curricular classes for their children , For example, senior three candidates prepare for the college entrance examination , volume Get up . From an outsider's point of view , A lot of competition is obviously a lose lose lose situation , But we can't , Because we are all involved in the game “ Prisoner ”.

ICG game

The game problem discussed satisfies the following conditions ：

    The player There are only two people , take turns Make a decision .

    Game The state set is finite , Make sure the game ends after a limited number of steps , This is bound to The production cannot be operated , Lose .

    For any situation , Winner and loser It depends on the situation itself , It doesn't matter which player's turn .

Stone game ： The game of taking stones is an old game , Originated in China , It is a classical problem in combinatorial mathematics . It has many different ways to play , Basically two players , The form of play is Take turns grabbing stones , The standard of victory is Grab the last stone . Player settings ：  The player who takes the stones first A（ First of all A）, The player who takes the stone later B（ Later stage B）.

Three classic ways to play

One 、 Bash Game (Bash Game)

Two 、 Nim game (Nimm Game)

3、 ... and 、 Wizov game (Wythoff Game)

（ One ） Bash Game

1 Pile up n A stone Every time Most take m individual 、 At least 1 individual

Case 1: If n=m+1, that Because you can only take m individual , therefore , No matter how many the first to take away , The latter can take away the remaining items at one time , The latter won .

Case 2:n=(m+1)*r+s,(r For any natural number ,s≤m), Then the first to take away s Items , If the latter takes away k(1≤k≤m) individual , Then take it first m+1-k individual , The result is (m+1)(r-1) individual , Keep this method later , that The first mover is sure to win .

Case 3:n=r*(m+1), Take it first k(1≤k≤m) individual , Then the back hand will take it away m+1-k individual , The result is (m+1)(r-1) individual , Keep this method later , Then the backhand wins , If you start, you'll lose .

All in all , Stay with your opponent （m+1） Multiple , You can win in the end .

The term : A serious person (m+1) The situation is strange

Disguised play

Two people report in turn , At least one at a time , Ten at most , Who can report 100 The winner .（ Equivalent to from a pile of 100 Take a stone from a stone , The last winner ）

Example ：2368 -- Buttons (poj.org)

Topic ：

      The meaning of the question is ： There is a pile of k A stone , Everyone takes turns 1,2,..L A stone , The data range is 3 <= K <= 100 000 000 ,2 <= L < K. Input k Value , Minimum output required L, Make the latter win .

After understanding the bash game, we can see that the idea of this problem is relatively clear , First I want my backhand to win , You have to put （1+L） The situation is left to the first hand . This question doesn't ask us who will win , The question is The backhand is the least likely to win L What's the value . Then we'll find a way to By k The minimum of an integral division is greater than 2 The factor of , after reduce 1 Output is the answer .

So with the following code, notice （poj You can't use a universal header file , Compiler requirements are a bit strict .）：

//#include<bits/stdc++.h>
#include<iostream>
using namespace std;
typedef long long ll;
const int N=100005;
ll n;// Number of stones 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    ll i;
    for(i=2;i<n;i++)// Find the smallest factor in turn 
    {
        if(n%(i+1)==0)
        {
            cout<<i<<endl;
            break;
        }
    }
    if(i==n) cout<<0<<endl;// Output if not found 0
    return 0;
}

  That is, the data range 1e8, Just be happy ,TEL Ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha . Because of the cycle 2~n, The time complexity is O(n).

    Another new idea is , Go through all the n The factor of , Save up , The minimum output is greater than or equal to 3 The factor of minus one . The time complexity of the following code is O(log n).AC happy .

//#include<bits/stdc++.h>
#include<algorithm>
#include<math.h>
#include<iostream>
#include<stdio.h>
using namespace std;
typedef long long ll;
const int N=100005;
ll n,a[N];//n Is the total number of stones ,a[i] save n The factor of 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    int temp=0;
    for(int i=1;i*i<=n;i++)
    {
        if(n%i==0&&i*i!=n) a[temp++]=i,a[temp++]=n/i;
        // Be careful to distinguish between similar n=4 when , The factor is 1,2,4. instead of 1,2,2,4 The situation of 
        else if(n%i==0&&i*i==n) a[temp++]=i;
    }
    sort(a,a+temp);// Sort from small to large 
    for(int i=0;i<temp;i++)
    {
        if(a[i]>=3)// Find the minimum greater than or equal to 3 The factor of , Minus one output 
        {
            cout<<a[i]-1<<endl;
            break;
        }
    }
    return 0;
}

（ Two ） Nimm Game

Yes n Rubble , The number of stones in each pile is a1,a2,a3……, Two people in turn from these Take any stone from a pile of stones , At least one , The last man to take the stone won

n=1: Take it all first , The first step is to win .

n=2: There are two situations , One possibility is the same , One pile is less than the other in one case （ many ）

        (m,m) according to “ There is a learning one , Draw the cat according to the cat ” Law , First you lose .

        (m,M) Get out of the pile first (M-m) individual , At this time, the back hand faces (m,m) The first hand is sure to win .

The term : A serious person (m,m) The situation is strange

n=3:(m,m,M) The first hand must win the game , You can take it first M, Then it became (m,m,0) The situation of , Is that familiar ~

 (a1,a2,a3) Words , for instance (1,2,3), The possible situation after taking it first is (0,2,3),(1,1,3),(1,0,3),(1,2,2),(1,2,1),(1,2,0) It's all what I said before , The situation is as follows ：

 

Our predecessors told us that the law is ： The result of XOR is 0

A discussion of the winning situation

The result of facing XOR is 0 All players must lose .

The result is not 0, Then the player has a way to win .

Example ：891. Nim game - AcWing Question bank

  Topic ：

Understand Nim game , This topic is minutes AC Slightly .

Code up ：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100005;
ll n,a[N];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>a[i];
    int ans=a[0];
    for(int i=1;i<n;i++) ans^=a[i];//^ Is to do XOR operations 
    if(ans==0) cout<<"No"<<endl;
    else cout<<"Yes"<<endl;
    return 0;
}

( 3、 ... and ) Weizov game

There are two piles of several items , Two people take turns from At least one in any heap or Take as many items from both stacks at the same time , Regulations Take at least one at a time , Unlimited in number , The last winner wins .

For example : The situation is (1,2), There are four ways to get started , Use your smart brain and you will find that no matter how you take it first , The backhand can win , in other words (1,2) It's a strange situation .

People without brains come to see the analysis ：

Take it from the first pile first 1 individual , The latter takes all the back 2 individual , The latter wins .

Take it from the first pile and the second pile at the same time 1 individual , The latter can only take away the rest of the second pile 1 individual , The latter wins .

Take it from the second pile first 2 individual , The second hand took away the first pile 1 individual , The latter wins .

Take it from the second pile first 1 individual , The second hand is taken from the first pile and the second pile at the same time 1 individual , The latter wins .

Suppose the current situation is （3,5)：

（1） First in “3” To take 1 individual , The back hand can be in “5” Take it from me 4 individual , So this becomes （1,2） The situation of

（2） First in “3” To take 2 individual , The back hand can be in “5” Take it from me 3 individual , This also becomes （1,2） The situation of

（3） First in “5” To take 1 individual , The back hand is “3” and “5” Take them away 2 individual , This becomes （1,2） The situation of

（4） First in ”5” To take 2 individual , The back hand is “3” and ”5” Take them away 3 individual , This becomes (0,0) The situation of , Lose first

（5） First in “5” To take 3 individual , The back hand is “3” and “5” Take them away 1 individual , Also became （1,2） The situation of

（6） First in “5” To take 4 individual , The backhand is “3” Take it from me 1 individual , still （1,2） The situation of

We can look for the rules of those situations where the first hand will lose （ Strange situation ）

• The first one is （0,0）
• The second kind （1,2）
• The third kind of （3,5）
• A fourth   (4 ,7）
• The fifth （6,10）
• 6 kinds of   (8,13）              
• Seventh kinds   (9 ,15）
• Eighth   (11 ,18）
• The first n Kind of （a,b）

We'll find them The difference is increasing Of , Namely 0,1,2,3,4,5,6,7......n

There is another rule ( Normal people can't find it ):a=(b-a)*1.618 Rounding down

  Namely ：a = int(b - a)*1.618

notes ： there int Is a cast , Note that this is not a simple rounding , If the following value is 3.9, What you get after conversion is not 4 It is 3, That is to say, force int The result of type conversion is The largest integer not greater than this number .

Some topics require high accuracy , We can express this value by the following formula :

1.618 = (sqrt(5.0) + 1) / 2   

The header file ：include<math.h>

Example ：1067 -- Stone game (poj.org)

Topic ：

  Code ：

//#include<bits/stdc++.h>
#include<algorithm>
#include<math.h>
#include<iostream>
#include<stdio.h>
using namespace std;
typedef long long ll;
const int N=100005;
ll a,b;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    while(cin>>a>>b)// Multi group input ！！！
    {
        double flag= (sqrt(5.0) + 1) / 2.0;// The precision is higher double Come and save 1.618
        if(a>b) swap(a,b);// Guarantee b than a Big , It's useful to b-a
        if(a==int((b-a)*flag))cout<<0<<endl;// In the face of strange situations, you will lose 
        else cout<<1<<endl;
    }

    return 0;
}