算法合集之《由感性認(rèn)識(shí)到理性認(rèn)識(shí)-透析一類搏弈游戲的解答過程》

1、由感性認(rèn)識(shí)到理性認(rèn)識(shí)透析一類搏弈游戲的解答過程 TOC h z t 集訓(xùn)作業(yè)次標(biāo)題,1 HYPERLINK l _Toc536545499 一、游戲 PAGEREF _Toc536545499 h 2 HYPERLINK l _Toc536545500 二、從簡(jiǎn)單入手 PAGEREF _Toc536545500 h 2 HYPERLINK l _Toc536545501 三、類比與聯(lián)想 PAGEREF _Toc536545501 h 6 HYPERLINK l _Toc536545502 四、證明 PAGEREF _Toc536545502 h 8 HYPERLINK l _Toc536545

2、503 五、推廣 PAGEREF _Toc536545503 h 11 HYPERLINK l _Toc536545504 六、精華 PAGEREF _Toc536545504 h 12 HYPERLINK l _Toc536545505 七、結(jié)論 PAGEREF _Toc536545505 h 16 HYPERLINK l _Toc536545506 八、總結(jié) PAGEREF _Toc536545506 h 17游戲游戲A：甲乙兩人面對(duì)若干堆石子，其中每一堆石子的數(shù)目可以任意確定。例如圖1所示的初始局面：共n=3堆，其中第一堆的石子數(shù)a1=3，第二堆石子數(shù)a2=3，第三堆石子數(shù)a3=1。兩人

3、輪流按下列規(guī)則取走一些石子，游戲的規(guī)則如下：每一步應(yīng)取走至少一枚石子；每一步只能從某一堆中取走部分或全部石子；如果誰無法按規(guī)則取子，誰就是輸家。第一堆：a1=3第二堆：a2=3第三堆：a3=1圖 SEQ 圖 * ARABIC 1 游戲的一個(gè)初始局面游戲B：甲乙雙方事先約定一個(gè)數(shù)m，并且每次取石子的數(shù)目不能超過m個(gè)；其余規(guī)則同游戲A。我們關(guān)心的是，對(duì)于一個(gè)初始局面，究竟是先行者（甲）有必勝策略，還是后行者（乙）有必勝策略。下面，我們從簡(jiǎn)單入手，先來研究研究這個(gè)游戲的一些性質(zhì)。從簡(jiǎn)單入手 用一個(gè)n元組(a1, a2, , an)，來描述游戲過程中的一個(gè)局面?？梢杂?元組(3, 3, 1)來描述圖1

4、所示的局面。改變這個(gè)n元組中數(shù)的順序，仍然代表同一個(gè)局面。(3, 3, 1)和(1, 3, 3)，可以看作是同一個(gè)局面。如果初始局面只有一堆石子，則甲有必勝策略。甲可以一次把這一堆石子全部取完，這樣乙就無石子可取了。如果初始局面有兩堆石子，而且這兩堆石子的數(shù)目相等，則乙有必勝策略。因?yàn)橛袃啥咽樱约谉o法一次取完；如果甲在一堆中取若干石子，乙便在另一堆中取同樣數(shù)目的石子；根據(jù)對(duì)稱性，在甲取了石子之后，乙總有石子可?。皇涌倲?shù)一直在減少，最后必定是甲無石子可取。對(duì)于初始局面(1)，甲有必勝策略，而初始局面(3, 3)，乙有必勝策略。局面的加法：(a1, a2, , an) + (b1, b2,

5、 , bm) = (a1, a2, , an, b1, b2, , bm)。(3) + (3) + (1) = (3, 3) + (1) = (3, 3, 1)。對(duì)于局面A, B, S，若S=A+B，則稱局面S可以分解為“子局面”A和B。局面(3, 3, 1)可以分解為(3, 3)和(1)。如果初始局面可以分成兩個(gè)相同的“子局面”，則乙有必勝策略。設(shè)初始局面S=A+A，想象有兩個(gè)桌子，每個(gè)桌子上放一個(gè)A局面；若甲在一個(gè)桌子中取石子，則乙在另一個(gè)桌子中對(duì)稱的取石子；根據(jù)對(duì)稱性，在甲取了石子之后，乙總有石子可?。皇涌倲?shù)一直在減少，最后必定是甲無石子可取。初始局面(2, 2, 5, 5, 5, 5

6、, 7, 7)，可以分成兩個(gè)(2, 5, 5, 7)，故乙有必勝策略。對(duì)于局面S，若先行者有必勝策略，則稱“S勝”。對(duì)于局面S，若后行者有必勝策略，則稱“S負(fù)”。若A=(1)，B=(3, 3)，C=(2, 2, 5, 5, 5, 5, 7, 7)，則A勝，B負(fù)，C負(fù)。我們所關(guān)心的，就是如何判斷局面的勝負(fù)。如果局面S勝，則必存在取子的方法ST，且T負(fù)。如果局面S負(fù)，則對(duì)于任意取子方法ST，有T勝。設(shè)初始局面S可以分解成兩個(gè)子局面A和B（分解理論）。若A和B一勝一負(fù)，則S勝。不妨設(shè)A勝B負(fù)；想象有兩個(gè)桌子A和B，桌子上分別放著A局面和B局面；因?yàn)锳勝，所以甲可以保證取桌子A上的最后一個(gè)石子；與此同

7、時(shí)，甲還可以保證在桌子B中走第一步的是乙；因?yàn)锽負(fù)，所以甲還可以保證取桌子B中的最后一個(gè)石子；綜上所述，甲可以保證兩個(gè)桌子上的最后一個(gè)石子都由自己取得。若A負(fù)B負(fù)，則S負(fù)。無論甲先從A中取，還是先從B中取，都會(huì)變成一勝一負(fù)的局面；因此，乙面臨的局面總是“勝”局面，故甲面臨的S是“負(fù)”局面。若B負(fù)，則S的勝負(fù)情況與A的勝負(fù)情況相同。若A勝B勝，則有時(shí)S勝，有時(shí)S負(fù)。如果S=A+C+C，則S的勝負(fù)情況與A相同。令B=C+C，則S=A+B且B負(fù)，故S的勝負(fù)情況與A相同。圖1所示的初始局面(3, 3, 1) = (3) + (3) + (1)，與局面(1)的勝負(fù)情況相同。圖1中所示的初始局面(3, 3

8、, 1)是“勝”局面，甲有必勝策略。稱一個(gè)石子也沒有的局面為“空局面”?？站置媸恰柏?fù)”局面。如果局面S中，存在兩堆石子，它們的數(shù)目相等。用T表示從S中把這兩堆石子拿掉之后的局面，則稱“S可以簡(jiǎn)化為T”。局面(2, 2, 2, 7, 9, 9)可以簡(jiǎn)化為(2, 2, 2, 7)，還可以進(jìn)一步簡(jiǎn)化為(2, 7)。一個(gè)局面的勝負(fù)情況，與其簡(jiǎn)化后的局面相同。三個(gè)局面(2, 2, 2, 7, 9, 9)、(2, 2, 2, 7)和(2, 7)，勝負(fù)情況都相同。不能簡(jiǎn)化的局面稱為“最簡(jiǎn)局面”。局面 (2, 7)是最簡(jiǎn)局面。最簡(jiǎn)局面中不會(huì)有兩堆相同的石子，故可以用一個(gè)集合來表示最簡(jiǎn)局面。最簡(jiǎn)局面(2, 7)

9、可以用集合2, 7來表示。如果只關(guān)心局面的勝負(fù)，則一個(gè)局面可以用一個(gè)集合來描述。圖1所示的局面(3, 3, 1)，可以用集合1來描述。如果用搜索（搏弈樹）的方法來解這個(gè)游戲，則采用集合來表示一個(gè)局面，比采用多元組來表示一個(gè)局面，搜索量將有所減少，但時(shí)間復(fù)雜度仍然很高。能不能進(jìn)一步簡(jiǎn)化一個(gè)局面的表示呢？類比與聯(lián)想二進(jìn)制加法 本文的“二進(jìn)制加法”，是指不進(jìn)位的二進(jìn)制加法，也可以理解為邏輯里的“異或”操作。1 + 0 = 1；0 + 1 = 1；0 + 0 = 0；1 + 1 = 0。二進(jìn)制的加法 VS 局面的加法大寫字母AB表示局面，小寫字母ab表示二進(jìn)制若A和B相同，則A+B負(fù)；若a和b相等，則

10、a+b=0若A勝B負(fù)，則A+B勝；若a=1且b=0，則a+b=1若B勝A負(fù)，則A+B勝；若b=1且a=0，則a+b=1若A負(fù)B負(fù)，則A+B負(fù)；若a=0且b=0，則a+b=0如果用二進(jìn)制1和0，分別表示一個(gè)局面的勝或負(fù)局面的加法，與二進(jìn)制的加法有很多類似之處。若A勝B勝，則A+B有時(shí)勝，有時(shí)負(fù)；若a=1且b=1，則a+b=0。二進(jìn)制數(shù)的加法：對(duì)二進(jìn)制數(shù)的每一位，都采用二進(jìn)制的加法。0011+10101001，1010+10100000。二進(jìn)制數(shù)的加法 VS 局面的加法大寫字母AB表示局面，小寫字母ab表示二進(jìn)制數(shù)若A和B相同，則A+B負(fù)；若a和b相等，則a+b為0若A勝B負(fù)，則A+B勝；若a0且

11、b=0，則a+b0若B勝A負(fù)，則A+B勝；若b0且a=0，則a+b0若A負(fù)B負(fù)，則A+B負(fù)；若a=0且b=0，則a+b=0若A勝B勝，則A+B有時(shí)勝，有時(shí)負(fù)若a0且b0，則有時(shí)a+b0，有時(shí)a+b=0如果用二進(jìn)制數(shù)s來表示一個(gè)局面S的勝或負(fù)，S勝則s0，S負(fù)則s=0局面的加法，與二進(jìn)制數(shù)的加法，性質(zhì)完全相同。能否用一個(gè)二進(jìn)制數(shù)，來表示一個(gè)局面呢？ 用符號(hào)#S，表示局面S所對(duì)應(yīng)的二進(jìn)制數(shù)。如果局面S只有一堆石子，則用這一堆石子數(shù)目所對(duì)應(yīng)的二進(jìn)制數(shù)來表示S。#(5)=5=101。若局面S=A+B，則#S=#A+#B。局面(3, 3)=(3)+(3)，所以#(3, 3)=#(3)+#(3)=11+1

12、1=0。局面(3, 3, 1)=(3, 3)+(1)，所以#(3, 3, 1)=#(3, 3)+#(1)=0+1=1。函數(shù)f：若局面S只有一堆石子，設(shè)S=a1，則f(a1)=#S，即f(a1)=#(a1)。對(duì)于游戲A來說，#(5)=101，所以f(5)=101。對(duì)于游戲A來說，f(x)就是x所對(duì)應(yīng)的二進(jìn)制數(shù)。換句話說，f(x)=x。設(shè)局面S=(a1, a2, , an)，即S=(a1)+(a2)+(an)，則#S=f(a1)+f(a2)+f(an)。#(3, 3, 1)=#(3)+(3)+(1)=#(3)+#(3)+#(1)=f(3)+f(3)+f(1)=11+11+1=1。 對(duì)于局面S，若#

13、S=0，則S負(fù)；若#S0，則S勝。證明二進(jìn)制數(shù)a, b，若a + b = 0，當(dāng)且僅當(dāng)a = b。1011+101100001011+10010010二進(jìn)制數(shù)a, b, s，若a + b = s，則a = b + s。0011+101010011001+10100011二進(jìn)制數(shù)a1+a2+an=p0，則必存在k，使得ak+pak。因?yàn)閜0，所以p的最高位是1；設(shè)p的最高位是第q位；至少存在一個(gè)k，使得ak的第q位也是1；ak+p的第q位為0，所以ak+p0f(a1)f(a1x)f(a1)+f(a1x)0#T0。00101a110011a210111a3+00001a400000p=000101

14、a100101a2+a3+a4=a1+00000p=0 xa1a1+p0若#S0，則先行者必然存在一種取子方法ST，且#T=0。設(shè)S=(a1, a2, , an)，p=#S=f(a1)+f(a2)+f(an)；因?yàn)閜0，所以必然存在k，使得f(ak)+pf(ak)，不妨設(shè)k=1，f(a1)+p=x；先行者將第1堆的石子的數(shù)目從a1變成x，用T表示這個(gè)局面；p=#S=f(a1)+#(a2, , an)，故#(a2, , an)=f(a1)+p=x；#T=f(x)+#(a2, , an)=f(x)+x=0。00101a110011a200111a3+10111a400110p000101a1000

15、11x=a2+a3+a4=a1+pa1+00110pxx+p=0若S是空局面，則#S=0。若#S=0，則S負(fù)；若#S0，則S勝。#(1, 2, 3)=01+10+11=0，故局面(1, 2, 3)負(fù)。#(1, 2, 3, 4)=001+010+011+100=100，故局面(1, 2, 3, 4)勝。對(duì)于游戲A來說，任意的一個(gè)初始局面S=(a1, a2, , an)，我們把這里的ai都看成是二進(jìn)制數(shù)。令#S=a1+a2+an。若#S0，則先行者（甲）有必勝策略；否則#S=0，這時(shí)后行者（乙）有必勝策略。下面把這個(gè)結(jié)論推廣到游戲B。函數(shù)f：f(x)=x mod (m+1)；把函數(shù)f的值看作是二進(jìn)

16、制數(shù)。對(duì)于任意初始局面S=(a1, a2, , an)，令#S=f(a1)+f(a2)+f(an)。若#S0，則先行者（甲）有必勝策略；否則后行者（乙）有必勝策略。類似游戲A的證明。游戲B的解法與游戲A十分類似。這是因?yàn)閮蓚€(gè)游戲的規(guī)則相當(dāng)類似。推廣游戲C：甲乙兩人面對(duì)若干排石子，其中每一排石子的數(shù)目可以任意確定。例如圖2所示的初始局面：共n=3排，其中第一排的石子數(shù)a1=7，第二排石子數(shù)a2=3，第三排石子數(shù)a3=3。兩人輪流按下列規(guī)則取走一些石子，游戲的規(guī)則如下：每一步必須從某一排中取走兩枚石子；這兩枚石子必須是緊緊挨著的；如果誰無法按規(guī)則取子，誰就是輸家。第一排，a1=7第二排，a2=3第

17、三排，a3=31 2 3 4 5 6 7圖 SEQ 圖 * ARABIC 2 游戲的一個(gè)初始局面如果甲第一步選擇取第一排34這兩枚石子，之后無論是甲還是乙，都不能一次取走25這兩枚石子。換句話說，如果取了34這兩枚石子，等價(jià)于將第一排分成了兩排，這兩排分別有2個(gè)和3個(gè)石子。我們只關(guān)心，對(duì)于一個(gè)初始局面，究竟是先行者（甲）有必勝策略，還是后行者（乙）有必勝策略。游戲C的規(guī)則和游戲A并不那么相似。但是，前面所列出的，游戲A的關(guān)鍵性質(zhì)，游戲C卻都具有。比如說，圖2所示的初始局面可以用三元組(7, 3, 3)來表示，它的勝負(fù)情況與初始局面(7)相同。游戲A的解答是由它的性質(zhì)得出來的。因此，我們猜想游戲

18、C是否也能用類似的方法來解。精華回憶游戲A的結(jié)論，以及它在游戲B上的推廣，對(duì)于游戲C，我們的想法是設(shè)計(jì)一個(gè)函數(shù)f，把函數(shù)f的值看作是二進(jìn)制數(shù)。對(duì)于任意一個(gè)初始局面S，設(shè)S=(a1, a2, , an)，令#S=f(a1)+f(a2)+f(an)。若#S0，則先行者（甲）有必勝策略；否則#S=0，這時(shí)后行者（乙）有必勝策略。游戲A中，f(x) = x。游戲B中，f(x) = x mod (m + 1)。游戲C中，f(x) = ?。關(guān)鍵就在于如何構(gòu)造一個(gè)滿足要求的函數(shù)f?；貞涥P(guān)于游戲A、B的結(jié)論的證明過程函數(shù)f是否滿足要求，關(guān)鍵在于#S是否滿足下面的條件。若#S=0，則無論先行者如何取子ST，都有

19、#T0。若#S0，則先行者必然存在一種取子方法ST，且#T=0。用符號(hào)$(x)，表示局面(x)的下一步所有可能出現(xiàn)的局面的集合。在游戲A中，$(3)=(2), (1), (0)。在游戲B中，若m=4，則$(9)=(8), (7), (6), (5)，$(2)=(1), (0)。在游戲C中，$(7)=(5), (1, 4), (2, 3)。定義集合g(x)：設(shè)$(x)=S1, S2, , Sk，則g(x)=#S1, #S2, , #Sk。在游戲A中，$(3)=(2), (1), (0)，故g(3)=#(2), #(1), #(0)=10, 01, 00。在游戲B中，若m=4，則g(9)=#(8)

20、, #(7), #(6), #(5)，g(2)=#(1), #(0)。在游戲C中，g(7)=#(5), #(1, 4), #(2, 3)。(5)(1, 4)(2, 3)(7)$(7)=(5), (1, 4), (2, 3)g(7)=#(5), #(1, 4), #(2, 3)若#S=0，則無論先行者如何取子ST，都有#T0。設(shè)S=(a1, a2, , an)，由于先行者只能選擇一堆石子，不妨設(shè)選擇了a1；因?yàn)?S=f(a1)+#(a2, , an)=0，所以f(a1)=#(a2, , an)；先行者可能將局面(a1)變?yōu)榫置?b1, , bm)，#(b1, , bm)屬于集合g(a1)；設(shè)這時(shí)

21、的局面為T，我們有T=(b1, , bm)+(a2, , an)；#T=#(b1, , bm)+#(a2, , an)=#(b1, , bm)+f(a1)；如果要求#T0，則必然有#(b1, , bm)f(a1)；因此，函數(shù)f(a1)的值，不屬于集合g(a1)。（充要）00101f(a1)10011f(a2)10111f(a3)+00001f(a4)00000p=000101f(a1)00101f(a1)+00000p=0#(b1, b2, , bm)g(a1)f(a1)+p0若#S0，則先行者必然存在一種取子方法ST，且#T=0。設(shè)S=(a1, a2, , an)，p=#S=f(a1)+f(

22、a2)+f(an)；因?yàn)閜0，所以必然存在k，使得f(ak)+pf(ak)，不妨設(shè)k=1，f(a1)+p=x；因?yàn)閜=#S=f(a1)+#(a2, , an)，故(a2, , an)=p+f(a1)=x；如果先行者把局面(a1)變?yōu)榫置?b1, , bm)，#(b1, , bm)屬于集合g(a1)；設(shè)這時(shí)的局面為T，我們有T=(b1, , bm)+(a2, , an)；#T=#(b1, , bm)+#(a2, , an)=#(b1, , bm)+x；如果要使#T=0，相當(dāng)于要找到(b1, , bm)，使得#(b1, , bm)等于x；如果可以保證x屬于集合g(a1)，則肯定可以找到相應(yīng)的的(b

23、1, , bm)；因?yàn)閤f(a1)，所以，x屬于集合0, 1, , f(a1)1；如果集合g(a1)包含集合0, 1, , f(a1)1，則x一定屬于g(a1)。（充分）00101f(a1)10011f(a2)00111f(a3)+10111f(a4)00110p000101f(a1)00011x=f(a1)+pf(a1)+00110p#(b1, b2, , bm)=xx如果xg(a1)+p=0函數(shù)f滿足要求的一個(gè)充分條件f(a1)不屬于集合g(a1)。集合g(a1)包含集合0, 1, , f(a1)1。如果g(a1)=0, 1, 2, 5, 7, 8, 9，則f(a1)=3，滿足要求。用大寫

24、字母N表示非負(fù)整數(shù)集，即N=0, 1, 2, 。令N為全集，集合G(x)表示集合g(x)的補(bǔ)集。定義函數(shù)f(n)：f(n)=minG(n)，即f(n)等于集合G(n)中的最小數(shù)。設(shè)局面S=(a1, a2, , an)，#S=f(a1)+f(a2)+f(an)，采用二進(jìn)制數(shù)的加法。若#S=0，則S負(fù)；若#S0，則S勝。游戲C的f值：g(0)=，G(0)=0, 1, ，f(0)=0；g(1)=，G(1)=0, 1, ，f(1)=0；g(2)=#(0)=f(0)=0，G(2)=1, 2, ，f(2)=1；g(3)=#(1)=f(1)=0，G(2)=1, 2, ，f(3)=1；g(4)=#(2), #

25、(1, 1)=f(2), f(1)+f(1)=1, 0，G(4)=2, 3, ，f(4)=2；g(5)=#(3), #(1, 2)=f(3), f(1)+f(2)=1, 1，G(5)=0, 2, 3, ，f(5)=0；g(6)=#(4), #(1, 4), #(2, 2)=2, 1, 0，G(6)=3, 4, ，f(6)=3；g(7)=#(4), #(1, 4), #(2, 3)=2, 2, 0，G(7)=1, 3, 4, ，f(7)=1；圖2所示的局面S=(7, 3, 3)，有#S=f(7)+f(3)+f(3)=1+1+1=1，故S勝。游戲C的初始局面S=(3, 4, 6)，有#S=1+2+

26、3=01+10+11=0，故S負(fù)。結(jié)論此類搏弈游戲的一般性解法：用一個(gè)n元組(a1, a2, , an)，來描述游戲過程中的一個(gè)局面。用符號(hào)#S，表示局面S所對(duì)應(yīng)的二進(jìn)制數(shù)。用符號(hào)$(x)，表示局面(x)的下一步所有可能出現(xiàn)的局面的集合。定義集合g(x)：設(shè)$(x)=S1, S2, , Sk，則g(x)=#S1, #S2, , #Sk。令非負(fù)整數(shù)集為全集，集合G(x)表示集合g(x)的補(bǔ)集。定義函數(shù)f(n)：f(n)=minG(n)，即f(n)等于集合G(n)中的最小數(shù)。設(shè)局面S=(a1, a2, , an)，#S=f(a1)+f(a2)+f(an)，采用二進(jìn)制數(shù)的加法。若#S0，則先行者有必

27、勝策略；若#S=0，則后行者有必勝策略。適用范圍和限制條件：甲乙兩人取石子游戲及其類似的游戲；每一步只能對(duì)某一堆石子進(jìn)行操作；每一步操作的限制，只與這堆石子的數(shù)目或一些常數(shù)有關(guān)；操作在有限步內(nèi)終止，并不會(huì)出現(xiàn)循環(huán)；誰無法繼續(xù)操作，誰就是輸家。游戲D（POI2000，Stripes）：一排石子有L個(gè)，甲乙兩人輪流從中取“緊緊挨著的”A或B或C枚石子。誰不能取了，誰就是輸家。已知A, B, C, L，問甲乙二人誰有必勝策略。有了前面的結(jié)論，這個(gè)游戲就難不倒我們了?？偨Y(jié)從算法優(yōu)化的角度取石子游戲?qū)儆谝活惖湫偷牟挠螒?。窮舉所有的局面，理論上可以求得最優(yōu)策略。但窮舉的時(shí)空復(fù)雜度太高，本文所提出的解法，

28、有效的控制了算法的時(shí)空復(fù)雜度，可以看作是對(duì)窮舉法的一個(gè)優(yōu)化。優(yōu)化算法的過程，可以看作是在優(yōu)化局面的表示。首先，我們用一個(gè)n元組表示一個(gè)局面，這是很直觀很容易想到的。因?yàn)槲覀冎魂P(guān)心局面的勝負(fù)，于是得到了第一個(gè)性質(zhì)：這個(gè)n元組是無序的。進(jìn)一步分析發(fā)現(xiàn)，n元組中如果出現(xiàn)兩個(gè)相同的數(shù)字，則把它們消去，不影響局面的勝負(fù)。于是，我們改用集合來表示一個(gè)局面。最后，通過與二進(jìn)制數(shù)的對(duì)比，又簡(jiǎn)化到用一個(gè)數(shù)來表示一個(gè)局面。優(yōu)化局面的表示，使得搜索量大大減少。那么，減少的搜索量都到哪里去了呢？舉個(gè)例子，對(duì)于游戲A中的5個(gè)局面：(3, 3, 1), (1, 3, 3), (5, 5, 1), (2, 3)：采用n元組：這5個(gè)局面互不相同；采用無序