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