開頭先啰嗦一句:想學好博弈,必然要花費很多的時間,深入學習,不要存在一知半解,應該是一看到題目,就想到博弈的類型。
以及,想不斷重復不斷重復,做大量各大oj網站的題目,最后吃透它。
博弈:
博弈論又被稱為對策論(Game Theory),既是現代數學的一個新分支,也是運籌學的一個重要學科。
博弈,具體的例子就是下棋,雙方都考慮最有利于自已的步驟,但是最終必有一方輸,一方贏。
博弈的策略:參與者在行動之前所準備好的一套完整的行動方案,就是想好下完這步棋,對方會如何下,
以及接下來該如何下,最終得出結果。
常見的博弈有以下:
1.博弈:合作博弈和非合作博弈
?? 合作博弈:指參與者能夠達成一種具有約束力的協議,在協議范圍內選擇有利于雙方的策略
?? 非合作博弈:指參與者無法達成這樣一種協議
2.博弈:靜態博弈和動態博弈
?? 靜態博弈:指在博弈中,參與者同時選擇,或雖非同時選擇,但是在邏輯時間
?????????????????? 上是同時的。(期末老師評分與同學給老師評分)
?? 動態博弈:指在博弈中,參與者的行動有先后順序,且后行動者能夠觀察
?????????????????? 到先行動者的行動。(下棋)
3.博弈:完全信息博弈與不完全信息博弈
?? 完全信息博弈:指在博弈中,每個參與者對其他參與者的類型,策略空間及損益函數都有準確的信息。(賣家與買家)
?? 不完全信息博弈:總有一些信息不是所有參與者都知道的
4.博弈:零和博弈與非零和博弈
?? 零和博弈:指博弈前的損益總和與博弈后的損益總和相等
?? 非零和博弈:指博弈后的損益大于(小于)博弈前的損益總和(正和或負和 )
下面我主要講一些關于算法比賽中用到的博弈類型:
首先你要理解必勝狀態和必敗狀態:
對下先手來說,
一個狀態是必敗狀態當且僅當它的所有后繼都是必敗狀態。
一個狀態是必勝狀態當且僅當它至少有一個后繼是必敗狀態。
就是說,博弈者,一旦捉住了勝利的把柄,必然最后勝利。
博弈中常常用到的:
兩個數,不用中間變量實現交換。
a b;
a = a^b;
b = a^b;
a = a^b;
巴什博弈:
百度百科:
巴什博弈:只有一堆n個物品,兩個人輪流從這堆物品中取物, 規定每次至少取一個,最多取m個。最后取光者得勝。
顯然,如果n=m+1,那么由于一次最多只能取m個,所以,無論先取者拿走多少個,后取者都能夠一次拿走剩余的物品,后者取勝。因此我們發現了如何取勝的法則:如果n=(m+1)r+s,(r為任意自然數,s≤m),那么先取者要拿走s個物品,如果后取者拿走k(≤m)個,那么先取者再拿走m+1-k個,結果剩下(m+1)(r-1)個,以后保持這樣的取法,那么先取者肯定獲勝。總之,要保持給對手留下(m+1)的倍數,就能最后獲勝。這個游戲還可以有一種變相的玩法:兩個人輪流報數,每次至少報一個,最多報十個,誰能報到100者勝。對于巴什博弈,那么我們規定,如果最后取光者輸,那么又會如何呢?(n-1)%(m+1)==0則后手勝利
請去刷下面的題目,均是巴什博弈
???? 算博弈題目時,一定要算到一個周期結束,防止出錯,很有可能像HDU2897那樣。中途錯的猝不及防 ? ?
package Combat.com;import java.util.Arrays; import java.util.Scanner;public class Main {public static void main(String []args){Scanner cin = new Scanner(System.in);while(cin.hasNext()){int n = cin.nextInt();PLG(n);}}static void PLG(int n){if(n%3 == 0){System.out.println("Cici");}else{System.out.println("Kiki");}} }
?
import java.util.Arrays; import java.util.Scanner;public class Main {public static void main(String []args){Scanner cin = new Scanner(System.in);while(cin.hasNext()){int n = cin.nextInt();int m = cin.nextInt();if(n == 0 && m == 0){return;}PLG(n,m);}}static void PLG(int n,int m){if(n%2 == 0 || m % 2 == 0){System.out.println("Wonderful!");}else{System.out.println("What a pity!");}} }
?
package Combat.com;import java.util.Arrays; import java.util.Scanner;public class Main {public static void main(String []args){Scanner cin = new Scanner(System.in);while(cin.hasNext()){int m = cin.nextInt();int n = cin.nextInt();PLG(m,n);}}static void PLG(int m,int n){if(m % (n+1) == 0){System.out.println("none");}else{if(m <= n){for(int i = m; i <= n; i++){if(i!= m){System.out.print(" ");}System.out.print(i);}System.out.println();}else{int flag = 0;for(int i = 1; i <= n; i++){if((m-i)%(n+1) == 0){if(flag == 0){System.out.print(i);}else{System.out.print(" " + i);}flag++;}}System.out.println();}}} }
?
package Combat.com;import java.util.Arrays; import java.util.Scanner;public class Main {public static void main(String []args){Scanner cin = new Scanner(System.in);int C = cin.nextInt();while(C != 0){int n = cin.nextInt();int m = cin.nextInt();PLG(n,m);C--;}}static void PLG(int n,int m){if(n <= m){System.out.println("Grass");}else{if(n % (m+1) == 0){System.out.println("Rabbit");}else{System.out.println("Grass");}}} }
package Combat.com;import java.util.Arrays; import java.util.Scanner;public class Main {public static void main(String []args){Scanner cin = new Scanner(System.in);while(cin.hasNext()){int n = cin.nextInt();int p = cin.nextInt();int q = cin.nextInt();PLG(n,p,q);}}static void PLG(int n,int p,int q){if(n < p+q){if(n <= p){System.out.println("LOST");}else{System.out.println("WIN");}}else if(n%(p+q) == 0){System.out.println("WIN");}else//有坑 {if(n % (p+q) > p)System.out.println("WIN");elseSystem.out.println("LOST");}} }
?
威佐夫博弈:
一定要去百度百科上面,先理解透意思。
下面是一些威佐夫博弈的總結:
設當前局勢為(a,b); a <= b
①a==b:同時從兩堆取走a個石子,轉化為(0,0)
②a==a[k]&&b>b[k]:從第二堆取走b?b[k]個石子,轉化為(a,b[k])
③a==a[k]&&b<b[k]:同時從兩堆取走a?a[b?a]個石子,轉化為(a[b?a],b?a+a[b?a])
④a>a[k]&&b==b[k]:從第一堆取走a?a[k]個石子,轉化為(a[k],b)
⑤a<a[k]&&b==b[k]:若a==a[j] (j<k),則從第二堆取走b?b[j]個石子,轉化為(a,b[j]);
否則必有a==b[j](j<k)a==b[j](j<k),則從第二堆取走b?a[j]b?a[j]個石子,轉化為(a[j],a)
例如5 ?8 ,5>a(8-5)=a3=4 ?8>b(8-5)=b3=7 從兩堆中取走a-a(b-a)=5-4=1個,變成奇異局勢(4,7)。
例如4 6 ,4>a(6-4)=a2=3 ?6>b(6-4)=b2=5 從兩堆中取走a-a(b-a)=4-3=1個,變成奇異局勢(3,5)。
可以理解成變成差為b-a的奇異局勢。
如果a=bk并且b-a!=k,則從b堆中取走b-ak個,變成奇異局勢(ak,bk).
例如,5 10 ,5=b2 10-5=5!=2 則從10中取走10-a2=10-3=7個,變成奇異局勢(3,5)。
為什么要b-a!=k呢?例如7 10 , 7=a3,10-7=3=k 也可以變成奇異局勢(4,7)。但這已經在4)判斷過了。
package Combat.com;import java.util.Arrays; import java.util.Scanner;public class Main {static final double mid = (Math.sqrt(5)+1)/2;public static void main(String []args){Scanner cin = new Scanner(System.in);while(cin.hasNext()){int a = cin.nextInt();int b = cin.nextInt();int MAX = Math.max(a, b);int MIN = Math.min(a, b);int temp = (int) ((MAX-MIN)*mid);if(temp == MIN){System.out.println("0");}else{System.out.println("1");}}} }
HDU2177的代碼實現如下:巧妙暴力,分情況太麻煩了。
package Combat.com;
import java.util.Arrays;
import java.util.Scanner;
public class Main
{
?? ?static final double MID = (Math.sqrt(5)+1)/2;
?? ?public static void main(String []args)
?? ?{
?? ??? ?Scanner cin = new Scanner(System.in);
?? ??? ?while(cin.hasNext())
?? ??? ?{
?? ??? ??? ?int a = cin.nextInt();
?? ??? ??? ?int b = cin.nextInt();
?? ??? ??? ?if(a == 0 && b == 0)
?? ??? ??? ?{
?? ??? ??? ??? ?return;
?? ??? ??? ?}
?? ??? ??? ?WTFGame(a,b);
?? ??? ?}
?? ?}
?? ?static void WTFGame(int a,int b)
?? ?{
?? ??? ?int temp = (int) ((b-a)*MID);
?? ??? ?if(temp == a)
?? ??? ?{
?? ??? ??? ?System.out.println("0");
?? ??? ?}
?? ??? ?else
?? ??? ?{
?? ??? ??? ?System.out.println("1");
?? ??? ??? ?for(int i = 1; i <= a; i++)//先取同樣石子
?? ??? ??? ?{
?? ??? ??? ??? ?int n = a-i;
?? ??? ??? ??? ?int m = b-i;
?? ??? ??? ??? ?temp = (int) ((m-n)*MID);
?? ??? ??? ??? ?if(temp == n)
?? ??? ??? ??? ?{
?? ??? ??? ??? ??? ?System.out.println(n + " " + m);
?? ??? ??? ??? ?}
?? ??? ??? ?}
?? ??? ??? ?for(int i = a-1; i >=0; i--)//從最小堆單取;
?? ??? ??? ?{
?? ??? ??? ??? ?temp = (int) ((b-i)*MID);
?? ??? ??? ??? ?if(temp > i)//因為a越小,temp就越大,永遠不可能等。
?? ??? ??? ??? ?{
?? ??? ??? ??? ??? ?break;
?? ??? ??? ??? ?}
?? ??? ??? ?}
?? ??? ??? ?for(int i = b-1; i >= 0; i--)//從最大堆單取
?? ??? ??? ?{
?? ??? ??? ??? ?int n = a;
?? ??? ??? ??? ?int m = i;
?? ??? ??? ??? ?if(n > m)
?? ??? ??? ??? ?{
?? ??? ??? ??? ??? ?int t = a;
?? ??? ??? ??? ??? ?n = m;
?? ??? ??? ??? ??? ?m = t;
?? ??? ??? ??? ??? ?temp = (int)((m-n)*MID);
?? ??? ??? ??? ??? ?if(temp > n)//這里充當優先,當條件滿足,無需進行下去了。
?? ??? ??? ??? ??? ?{
?? ??? ??? ??? ??? ??? ?break;
?? ??? ??? ??? ??? ?}
?? ??? ??? ??? ?}
?? ??? ??? ??? ?temp = (int) ((m-n)*MID);
?? ??? ??? ??? ?if(temp == n)
?? ??? ??? ??? ?{
?? ??? ??? ??? ??? ?System.out.println(n + " " + m);
?? ??? ??? ??? ?}
?? ??? ??? ?}
?? ??? ?}
?? ?}
}
?
尼姆博弈(Nimm Game):
尼姆博弈指的是這樣一個博弈游戲: ?有任意堆物品,每堆物品的個數是任意的,雙方輪流從中取物品,每一次只能從一堆物品中取部分或全部物品,最少取一件, ?取到最后一件物品的人獲勝。
百度百科:
結論就是:把每堆物品數全部異或起來,如果得到的值為0,那么先手必敗,否則先手必勝。
HDU2176
代碼實現如下;
package Combat.com;import java.util.Arrays; import java.util.Scanner;public class Main {static final int MAX = 200005;static int array[] = new int[MAX];public static void main(String []args){Scanner cin = new Scanner(System.in);while(cin.hasNext()){int m = cin.nextInt();if(m == 0){return;}int sum = 0;//異或的結果for(int i = 0; i < m; i++){array[i] = cin.nextInt();sum = sum^array[i];}NIMGame(sum,m);}}static void NIMGame(int sum,int k){if(sum == 0)//代表面臨奇異情況,必輸 {System.out.println("No");return;}else{System.out.println("Yes");for(int i = 0; i < k; i++)//勝的第一次取法, {int s = sum^array[i];//結果s相當于,sum沒與array[i]異或。if(s < array[i]){System.out.println(array[i] + " " + s);}}}} }
HDU1850? 也是一道尼姆博弈題目,解法和上面相同。
HDU1907也是同樣的做法
?
?階梯博弈:
具體意思,參照下面網址:https://www.cnblogs.com/jiangjing/p/3849284.html
?