1
博弈論簡介
2
博弈論基礎(chǔ)知識(shí)
3
4
(一)巴什博奕(Bash Game):
5
6
只有一堆n個(gè)物品,兩個(gè)人輪流從這堆物品中取物,規(guī)定每次至少取一個(gè),最多取m個(gè).最后取光者得勝.
7
8
若(m+
1
) |
n，則先手必?cái)?，否則先手必勝。
9
10
顯然,如果n=m+
1
,那么由于一次最多只能取m個(gè),所以,無論先取者拿走多少個(gè),后取者都能夠一次拿走剩余的物品,后者取勝.因此我們發(fā)現(xiàn)了如何取勝的法則：如果n=(m+
1
)r+s,(r為任意自然數(shù),s≤m),那么先取者要拿走s個(gè)物品,如果后取者拿走k(≤m)個(gè),那么先取者再拿走m+
1
-k個(gè),結(jié)果剩下(m+
1
)(r-
1
)個(gè),以后保持這樣的取法,那么先取者肯定獲勝.總之,要保持給對手留下(m+
1
)的倍數(shù),就能最后獲勝.
11
12
13
14
(二)威佐夫博奕(Wythoff Game):
15
16
有兩堆各若干個(gè)物品,兩個(gè)人輪流從某一堆或同時(shí)從兩堆中取同樣多的物品,規(guī)定每次至少取一個(gè),多者不限,最后取光者得勝.
17
18
奇異局勢下先手必?cái)。瞧娈惥謩菹孪仁直貏佟?
19
20
這種情況下是頗為復(fù)雜的.我們用(ak,bk)(ak ≤bk ,k=
0
,
1
,
2
,...,n)表示兩堆物品的數(shù)量并稱其為局勢,如果甲面對(
0
,
0
),那么甲已經(jīng)輸了,這種局勢我們稱為奇異局勢.前幾個(gè)奇異局勢是：(
0
,
0
)、(
1
,
2
)、(
3
,
5
)、(
4
,
7
)、(
6
,
10
)、(
8
,
13
)、(
9
,
15
)、(
11
,
18
)、(
12
,
20
).
21
22
可以看出,a0=b0=
0
,ak是未在前面出現(xiàn)過的最小自然數(shù),而bk= ak +
k,奇異局勢有如下三條性質(zhì)：
23
24
1
、任何自然數(shù)都包含在一個(gè)且僅有一個(gè)奇異局勢中.
25
26
由于ak是未在前面出現(xiàn)過的最小自然數(shù),所以有ak > ak-
1
,而bk= ak + k > ak-
1
+ k-
1
= bk-
1
> ak-
1
.所以性質(zhì)1.成立.
27
28
2
、任意操作都可將奇異局勢變?yōu)榉瞧娈惥謩?
29
30
事實(shí)上,若只改變奇異局勢(ak,bk)的某一個(gè)分量,那么另一個(gè)分量不可能在其他奇異局勢中,所以必然是非奇異局勢.如果使(ak,bk)的兩個(gè)分量同時(shí)減少,則由于其差不變,且不可能是其他奇異局勢的差,因此也是非奇異局勢.
31
32
3
、采用適當(dāng)?shù)姆椒?可以將非奇異局勢變?yōu)槠娈惥謩?
33
34
假設(shè)面對的局勢是(a,b),若b = a,則同時(shí)從兩堆中取走a 個(gè)物體,就變?yōu)榱似娈惥謩?
0
,
0
)；如果a = ak ,b > bk,那么,取走b - bk個(gè)物體,即變?yōu)槠娈惥謩?；如果a = ak , b < bk ,則同時(shí)從兩堆中拿走ak - ab - ak個(gè)物體,變?yōu)槠娈惥謩? ab - ak , ab - ak+ b - ak)；如果a > ak ,b= ak + k,則從第一堆中拿走多余的數(shù)量a - ak 即可；如果a < ak ,b= ak + k,分兩種情況,第一種,a=aj (j < k),從第二堆里面拿走b - bj 即可；第二種,a=bj (j < k),從第二堆里面拿走b -
aj 即可.
35
36
從如上性質(zhì)可知,兩個(gè)人如果都采用正確操作,那么面對非奇異局勢,先拿者必勝；反之,則后拿者取勝.
37
38
那么任給一個(gè)局勢(a,b),怎樣判斷它是不是奇異局勢呢？我們有如下公式：
39
40
ak =[k(
1
+√
5
)/
2
](下取整), bk= ak +
k (k∈N)
41
42
奇妙的是其中出現(xiàn)了有關(guān)黃金分割數(shù)的式子：(
1
+√
5
)/
2
=
1.618
...,若兩堆物品個(gè)數(shù)分別為x,y(x<y)，則k=y-x，再判斷x是否等于[(y-x)*( √
5
+
1
)/
2
] 即可得知是否是奇異局勢。
43
44
參考例題：POJ1067取石子游戲
45
46
參考代碼：
47
48
var
49
a,b:longint;
50
begin
51
repeat
52
readln(a,b);
53
if
a>
b then
54
begin a:=a xor b; b:=a xor b; a:=
a xor b; end;
55
if
a=trunc((b-a)*(sqrt(
5
)+
1
)/
2
) then writeln(
0
)
else
writeln(
1
);
56
until seekeof;
57
end.
58
59
60
61
(三)尼姆博奕(Nimm Game):
62
63
有三堆各若干個(gè)物品,兩個(gè)人輪流從某一堆取任意多的物品,規(guī)定每次至少取一個(gè),多者不限,最后取光者得勝.
64
65
這種情況最有意思,它與二進(jìn)制有密切關(guān)系,我們用(a,b,c)表示某種局勢,首先(
0
,
0
,
0
)顯然是奇異局勢,無論誰面對奇異局勢,都必然失敗.第二種奇異局勢是(
0
,n,n),只要與對手拿走一樣多的物品,最后都將導(dǎo)致(
0
,
0
,
0
).仔細(xì)分析一下,(
1
,
2
,
3
)也是奇異局勢,無論對手如何拿,接下來都可以變?yōu)?
0
,n,n)的情形.
66
67
計(jì)算機(jī)算法里面有一種叫做按位模2加,也叫做異或的運(yùn)算,我們用符號(hào)xor表示這種運(yùn)算.這種運(yùn)算和一般加法不同的一點(diǎn)是1+
1
=
0
.先看(
1
,
2
,
3
)的按位模2加的結(jié)果：
68
69
1
=
二進(jìn)制01
70
71
Xor
2
=
二進(jìn)制10
72
73
Xor
3
=
二進(jìn)制11
74
75
———————
76
77
0
=
二進(jìn)制00
78
79
對于奇異局勢(
0
,n,n)也一樣,結(jié)果也是0.
80
81
任何奇異局勢(a,b,c)都有a xor b xor c =
0
。該結(jié)論可以推廣至若干堆，都是成立的。
82
83
如果我們面對的是一個(gè)非奇異局勢(a,b,c),要如何變?yōu)槠娈惥謩菽?？假設(shè)a < b< c,我們只要將c 變?yōu)閍 xor b,即可,因?yàn)橛腥缦碌倪\(yùn)算結(jié)果: a xor b xor (a xor b)=(a xor a) xor (b xor b)=
0
xor
0
=
0
.要將c 變?yōu)閍 xor b,只要從c中減去c-
(a xor b)即可.
84
85
86
87
(四)Nim Staircase博奕:
88
89
這個(gè)問題是尼姆博弈的拓展：游戲開始時(shí)有許多硬幣任意分布在樓梯上，共n階樓梯從地面由下向上編號(hào)為0到n。游戲者在每次操作時(shí)可以將樓梯j(
1
<=j<=n)上的任意多但至少一個(gè)硬幣移動(dòng)到樓梯j-
1上。游戲者輪流操作，將最后一枚硬幣移至地上（0號(hào)）的人獲勝。
90
91
算法：將奇數(shù)樓層的狀態(tài)異或，和為0則先手必?cái)?，否則先手必勝。證明略。
92
93
例題：Poj1704
94
這道題可以把兩個(gè)棋子中間間隔的空格子個(gè)數(shù)作為一堆石子，則原題轉(zhuǎn)化為每次可以把左邊的一堆石子移到相鄰的右邊的一堆中。也就是階梯尼姆博弈，注意對輸入數(shù)據(jù)先排序，然后倒著往前數(shù)（a[n]-a[n-
1
]-1為第一個(gè)），奇數(shù)個(gè)數(shù)到的就做一下xor，其中最前面的看做a[
1
]-
0
-
1
，參考程序：
95
var
96
t,n,b,i,j:longint;
97
a:array[
0
..
1000
]of longint;
98
begin
99
readln(t);
100
repeat
101
dec(t);
102
readln(n);
103
for
i:=
1
to n
do
read(a[i]);
104
qsort(
1
,n);
//
快排略
105
j:=
0
;
106
b:=
0
;
107
for
i:=n downto
1
do
108
begin
109
inc(j);
110
if
odd(j) then b:=b xor (a[i]-a[i-
1
]-
1
);
111
end;
112
if
b=
0
then writeln(
'
Bob will win
'
)
else
writeln(
'
Georgia will win
'
);
113
until t=
0
;
114
end.
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號(hào)聯(lián)系： 360901061
您的支持是博主寫作最大的動(dòng)力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點(diǎn)擊下面給點(diǎn)支持吧，站長非常感激您！手機(jī)微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點(diǎn)擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
