算法合集之由感性認(rèn)識(shí)到理性認(rèn)識(shí)——透析一類搏弈游戲的解答過程(存儲(chǔ)版)
【正文】 B 中，若 m=4，則 $(9)={(8), (7), (6), (5)}， $(2)={(1), (0)}。（充要） (5) (1, 4) (2, 3) (7) $(7)={(5), (1, 4), (2, 3)} g(7)={(5), (1, 4), (2, 3)} 由感性認(rèn)識(shí)到理性認(rèn)識(shí) —— 透析一類搏弈游戲的解答過程 張一飛 14 ? ? 若 S≠ 0，則先行者必然存在一種取子方法 S→T ，且 T=0。 ? 設(shè)局面 S=(a1, a2, … , an)， S=f(a1)+f(a2)+…+f(a n)，采用二進(jìn)制數(shù)的加法。 ? 令非負(fù)整數(shù)集為全集，集合 G(x)表示集合 g(x)的補(bǔ)集。 ? 有了前面的結(jié)論，這個(gè)游戲就難不倒我們了。于是，我們改用集合來表示一個(gè)局面。 2. 從算法構(gòu)造的角度 人們認(rèn) 識(shí)事物的過程中，開始只是看到了各個(gè)事物的現(xiàn)象。那么，我們究竟是如何 由淺入深 的呢？ 兩堆數(shù)目相等的石子 —— 這是個(gè)很簡(jiǎn)單 的局面。 在解游戲 A 和 B 的過程中，我們積累了很多經(jīng)驗(yàn)。 “ 由此及彼、由表及里 、 去粗取精、去偽存真 ” ，這就是由感性認(rèn)識(shí)上升到理性認(rèn)識(shí)的關(guān)鍵。在解游戲 C 時(shí)，我們并不在意它與游戲 A 的規(guī)則有多大的區(qū)別，而是注意到它與游戲 A 有著相似的性質(zhì)，從而想到用類似的方法解游戲 C。具體到解這類游戲，就是要 從簡(jiǎn)單入手 。 “相同局面”的定義，必須能夠反映游戲的性質(zhì)。因?yàn)槲覀冎魂P(guān)心局面的勝負(fù)，于是得到了第一個(gè)性質(zhì)：這個(gè) n 元組是無序的。誰(shuí)不能取了，誰(shuí)就是輸家。 ? 用符號(hào) $(x)，表示局面 (x)的下一步所有可能出現(xiàn)的局面的集合。 ? 令 N 為全集，集合 G(x)表示集合 g(x)的補(bǔ)集。 ? ? 若 S=0，則無論先行者如何取子 S→T ，都有 T≠ 0。 由感性認(rèn)識(shí)到理性認(rèn)識(shí) —— 透析一類搏弈游戲的解答過程 張一飛 13 ? 用符號(hào) $(x)，表示局面 (x)的下一步所有可能出現(xiàn)的局面的集合。若 S≠ 0，則先行者（甲）有必勝策略；否則 S=0，這時(shí)后行者（乙）有必勝策略。 第一排， a1=7 第二排， a2=3 第三排， a3=3 1 2 3 4 5 6 7 由感性認(rèn)識(shí)到理性認(rèn)識(shí) —— 透析一類搏弈游戲的解答過程 張一飛 12 我們只關(guān)心，對(duì)于一個(gè)初始局面，究竟是先行者（甲）有必勝策略，還是后行者（乙）有必勝策略。 ? 類似游戲 A 的證明。 ? (1, 2, 3, 4)=001+010+011+100=100，故局面 (1, 2, 3, 4)勝。 ? 因?yàn)?p≠ 0，所以 p 的最高位是 1； ? 設(shè) p 的最高位是 第 q 位； ? 至少存在一個(gè) k，使得 ak的第 q 位也是 1； ? ak+p 的第 q 位為 0，所以 ak+pak。 ? 對(duì)于游戲 A 來說， f(x)就是 x 所對(duì)應(yīng)的二進(jìn)制數(shù)。 ? 能否用一個(gè)二進(jìn)制數(shù)，來表示一個(gè)局面呢？ ? 用符號(hào) S，表示局面 S 所對(duì)應(yīng)的二進(jìn)制數(shù)。 由感性認(rèn)識(shí)到理性認(rèn)識(shí) —— 透析一類搏弈游戲的解答過程 張一飛 6 如果用搜索（搏弈樹）的方法來解這個(gè)游戲，則采用集合來表示一個(gè)局面，比采用多元組來表示一個(gè)局面，搜索量將有所減少，但時(shí)間復(fù)雜度仍然很高。 ? 一個(gè)局面的勝負(fù)情況，與其簡(jiǎn)化后的局面相同。 ? 令 B=C+C，則 S=A+B 且 B 負(fù)，故 S 的勝負(fù)情況與 A 相同。 ? 設(shè)初始局面 S 可以分解成兩個(gè)子局面 A 和 B（分解理論） 。 ? 設(shè)初始局面 S=A+A，想象有兩個(gè)桌子，每個(gè)桌子上放一個(gè) A 局面； ? 若甲在一個(gè)桌子中取石子，則乙在另一個(gè)桌子中對(duì)稱的取石子； ? 根據(jù)對(duì)稱性，在甲取了石子之后，乙總有石子可?。? ? 石子總數(shù)一直在減少，最后必定是甲無石子可取。 ? 如果初始局面有兩堆石子，而且這兩堆石子的數(shù)目相等，則乙有必勝策略。 我們關(guān)心的是，對(duì)于一個(gè)初始局面，究竟是先行者（甲）有必勝策略，還是后行者（乙）有必勝策略。 圖 1 游戲的一個(gè)初始局面 ? 游戲 B： ? 甲乙雙方事先約定一個(gè)數(shù) m，并且每次取石子的數(shù)目不能超過 m 個(gè)； ? 其余規(guī)則同游戲 A。 ? 甲可以一次把這一堆石子全部取完，這樣乙就無石子可取了。 ? 如果初始局面可以分成兩個(gè)相同的“子局面”，則乙 有必勝策略。 ? 如果局面 S 負(fù)，則對(duì)于任意取子方法 S→T ，有 T 勝。 由感性認(rèn)識(shí)到理性認(rèn)識(shí) —— 透析一類搏弈游戲的解答過程 張一飛 5 ? 如果 S=A+C+C，則 S 的勝負(fù)情況與 A 相同。 ? 局面 (2, 2, 2, 7, 9, 9)可以簡(jiǎn)化為 (2, 2, 2, 7)，還可以進(jìn)一步簡(jiǎn)化為 (2, 7)。 ? 圖 1 所示的局面 (3, 3, 1)，可以用集合 {1}來描述。 ? 二進(jìn)制數(shù)的加法 VS 局面的加法 ? 大寫字母 AB 表示局面，小寫字母 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 來表示一個(gè)局面 S 的勝或負(fù)， S 勝則 s≠ 0， S 負(fù)則 s=0 ? 局面的加法，與二進(jìn)制數(shù)的加法，性質(zhì)完全相同。 ? 對(duì)于游戲 A 來說， (5)=101，所以 f(5)=101。 ? 1011 + 1011 0000 1011 + 1001 0010 0011 + 1010 1001 1001 + 1010 0011 由感性認(rèn)識(shí)到
試題試卷相關(guān)推薦
鄂ICP備17016276號(hào)-1