算法合集之《由感性認(rèn)識(shí)到理性認(rèn)識(shí)——透析一類(lèi)搏弈游戲的解答過(guò)程》-文庫(kù)吧
2024-12-25 09:23 本頁(yè)面
【正文】 ? 因?yàn)?B 負(fù)，所以甲還可以保證取桌子 B 中的最后一個(gè)石子； ? 綜上所述，甲可以保證 兩個(gè)桌子上的最后一個(gè)石子都由自己取得。 ? 若 A 負(fù) B 負(fù)，則 S 負(fù)。 ? 無(wú)論甲先從 A 中取，還是先從 B 中取，都會(huì)變成一勝一負(fù)的局面； ? 因此，乙面臨的局面總是“勝”局面，故甲面臨的 S 是“負(fù)”局面。 ? 若 B 負(fù)，則 S 的勝負(fù)情況與 A 的勝負(fù)情況相同。 ? 若 A 勝 B 勝，則有時(shí) S 勝，有時(shí) S 負(fù)。 由感性認(rèn)識(shí)到理性認(rèn)識(shí) —— 透析一類(lèi)搏弈游戲的解答過(guò)程 張一飛 5 ? 如果 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, 1)是“勝”局面，甲有必勝策略。 ? 稱(chēng)一個(gè)石子也沒(méi)有的局面為“空局面”。 ? 空局面是“負(fù)”局面。 ? 如果局面 S 中，存在兩堆石子，它們的數(shù)目相等。用 T 表示從 S 中把這兩堆石子拿掉之后的局面，則稱(chēng)“ 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)化的局面稱(chēng)為“最簡(jiǎn)局面”。 ? 局面 (2, 7)是最簡(jiǎn)局面。 ? 最簡(jiǎn)局面中不會(huì)有兩堆相同的石子，故可以用一個(gè)集合來(lái)表示最簡(jiǎn)局面。 ? 最簡(jiǎn)局面 (2, 7)可以用集合 {2, 7}來(lái)表示。 ? 如果只關(guān)心局面的勝負(fù)，則一個(gè)局面可以用一個(gè)集合來(lái)描述。 ? 圖 1 所示的局面 (3, 3, 1)，可以用集合 {1}來(lái)描述。 由感性認(rèn)識(shí)到理性認(rèn)識(shí) —— 透析一類(lèi)搏弈游戲的解答過(guò)程 張一飛 6 如果用搜索（搏弈樹(shù)）的方法來(lái)解這個(gè)游戲，則采用集合來(lái)表示一個(gè)局面，比采用多元組來(lái)表示一個(gè)局面，搜索量將有所減少，但時(shí)間復(fù)雜度仍然很高。 能不能進(jìn)一步簡(jiǎn)化一個(gè)局面的表示呢？ 三、 類(lèi)比與聯(lián)想 ? 二進(jìn)制加法 1 ? 1 + 0 = 1； ? 0 + 1 = 1； ? 0 + 0 = 0； ? 1 + 1 = 0。 ? 二進(jìn)制的加法 VS 局面的加法 ? 大寫(xiě)字母 AB 表示局面，小寫(xiě)字母 ab 表示二進(jìn)制 ? 若 A 和 B 相同，則 A+B 負(fù)；若 a 和 b 相等，則 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)制的加法有很多類(lèi)似之處。 ? 若 A 勝 B 勝，則 A+B 有時(shí)勝，有時(shí)負(fù)；若 a=1 且 b=1，則 a+b=0。 1 本文的“二進(jìn)制加法”，是指不進(jìn)位的二進(jìn)制加法，也可以理解為邏輯里的“異或”操 作。 由感性認(rèn)識(shí)到理性認(rèn)識(shí) —— 透析一類(lèi)搏弈游戲的解答過(guò)程 張一飛 7 ? 二進(jìn)制數(shù)的加法：對(duì)二進(jìn)制數(shù)的每一位，都采用二進(jìn)制的加法。 ? ， 。 ? 二進(jìn)制數(shù)的加法 VS 局面的加法 ? 大寫(xiě)字母 AB 表示局面，小寫(xiě)字母 ab 表示二進(jìn)制數(shù) ? 若 A 和 B 相同，則 A+B 負(fù)；若 a 和 b 相等，則 a+b 為 0 ? 若 A 勝 B 負(fù)，則 A+B 勝；若 a≠ 0 且 b=0，則 a+b≠ 0 ? 若 B 勝 A 負(fù)，則 A+B 勝；若 b≠ 0 且 a=0，則 a+b≠ 0 ? 若 A 負(fù) B 負(fù)，則 A+B 負(fù)；若 a=0 且 b=0，則 a+b=0 ? 若 A 勝 B 勝，則 A+B 有時(shí)勝，有時(shí)負(fù) ? 若 a≠ 0 且 b≠ 0，則有時(shí) a+b≠ 0，有時(shí) a+b=0 ? ?? ? 如果用二進(jìn)制數(shù) s 來(lái)表示一個(gè)局面 S 的勝或負(fù)， S 勝則 s≠ 0， S 負(fù)則 s=0 ? 局面的加法，與二進(jìn)制數(shù)的加法，性質(zhì)完全相同。 ? 能否用一個(gè)二進(jìn)制數(shù)，來(lái)表示一個(gè)局面呢？ ? 用符號(hào) S，表示局面 S 所對(duì)應(yīng)的二進(jìn)制數(shù)。 ? 如果局面 S 只有一堆石子，則用這一堆石子數(shù)目所對(duì)應(yīng)的二進(jìn)制數(shù)來(lái)表示 S。 ? (5)=5=101。 1010 + 1010 0000 0011 + 1010 1001 由感性認(rèn)識(shí)到理性認(rèn)識(shí) —— 透析一類(lèi)搏弈游戲的解答過(guò)程 張一飛 8 ? 若局面 S=A+B，則 S=A+B。 ? 局面 (3, 3)=(3)+(3)，所以 (3, 3)=(3)+(3)=11+11=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 來(lái)說(shuō)， (5)=101，所以 f(5)=101。 ? 對(duì)于游戲 A 來(lái)說(shuō)， f(x)就是 x 所對(duì)應(yīng)的二進(jìn)制數(shù)。換句話說(shuō)， 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，若 S=0，則 S 負(fù)；若 S≠ 0，則 S 勝。 四、 證明 ? 二進(jìn)制數(shù) a, b，若 a
試題試卷相關(guān)推薦
鄂ICP備17016276號(hào)-1