1 1 // SRM338 Div1 LV3 2 2 3 -定理のステートメント 3 +------------------------------------------------------------------------------------------- 4 +対象となるゲーム 5 + - 二人ゲーム 6 + - 二人とも動かせる手の集合は同じ 7 + - 動かせなくなった方が負け 8 + - 無限ループしない 9 + 10 +nim 11 + - n 個の石の山がある 12 + - 一手で 1 ～ n 個取っていい 13 + - 最後の石を取った方が勝ち（石がなくなって打つ手が無くなった方が負け） 14 + 15 +*n をサイズ n の山が1個だけの nim とする 16 + - *0 は負け 17 + - *n は勝ち n>=1 18 + 19 +------------------------------------------------------------------------------------------- 20 +ゲーム 21 + - 状態 G から打てる手で遷移する先を G1, ..., Gk とする 22 + G = {G1, ..., Gk} と書く 23 + 24 +ゲームの和 25 + - G1 + G2 を、G1 と G2 の二つのゲームがあって、どちらかを選んで一手進められるゲームとする。 26 + すなわち G1 + G2 = {(v,G2) | v∈G1} ∪ {(G1,u) | u∈G2} 27 + 28 +等価 29 + - 二つのゲームG, Fが等価なことを G ≡ F と書く 30 + 等価というのは勝ち負け一致よりもっと強い。二つのゲームの和 G+F が必敗になること。 31 + たとえば *n と *n は同サイズの山2つのnimは必敗なので等価。同サイズでなければ必勝なので等価でない 32 + 等価というのは可能な動きの構造がisomorphic/bisimilarというよりは弱い。 33 + たとえば以下で示すように *1 + *3 ≡ *2 だが初手のパターン数など違う。 34 + 35 +------------------------------------------------------------------------------------------- 36 +定理：等価(和を取ると必敗) => 勝ち負け一致 37 + - 必勝ゲーム+必敗ゲーム なら初手で必勝を必敗に変えて常にその状態を保てば勝てる。 38 + ゆえに勝ち負けが一致しないなら和をとったゲームは必勝。 39 + 必敗 + 必敗 = 必敗 40 + 必勝 + 必敗 = 必勝 41 + 42 + 注意： 43 + 必勝 + 必勝 = 必敗 44 + は成り立たない！ *2 + *1 は 初手で *1 + *1 に行けるのでこれは勝てる 45 + 46 +補題：G+G は必敗 47 +　- まねっこmoveをされると負けるしかない 48 + 49 +補題：A≡B ならば A+C≡B+C 50 + - A+C+B+C = (A+B)+(C+C) = 必敗+必敗 = 必敗 51 + 52 +補題：A≡B ならば {A,G1,G2,...}≡{B,G1,G2,...} 53 +　- {A,G1,G2,...}+{B,G1,G2,...} は必敗。なぜならこちらがどう動かしても 54 + A+B, G1+G1, G2+G2, ... のいずれかの必敗状態に遷移させられるから。 55 + 56 +------------------------------------------------------------------------------------------- 57 +定理【ゲームの和はxor】 58 + - *n1 + *n2 = *(n1 xor n2) 59 + - より一般的に G1≡*n1, G2≡*n2 ならば、G1 + G2 ≡ *(n1 xor n2) 60 + 61 + 証明 62 + - *n1 + *n2 + *(n1 xor n2) が必敗であることを言えば良い。 4 63 5 - 対象となるゲーム 6 - - 二人ゲーム 7 - - 二人とも動かせる手の集合は同じ 8 - - 動かせなくなった方が負け 9 - - 無限ループしない 64 + 10 65 11 - nim 12 - - サイズ s1, s2, .., sk の山がある 13 - - どれか一つ山を選んで 1 ～ 山サイズ の任意個取り除ける 14 - - 最後の山を取った方が勝ち（山がなくなって打つ手が無くなった方が負け） 66 +------------------------------------------------------------------------------------------- 67 +定理【ゲームの状態遷移はmex】 68 + - {*n1, ..., *nk} ≡ *mex(n1,...,nk) 69 + where mex(S) = min(nat \setminus S) 15 70 16 - *n をサイズ n の山が1個だけの nim とする 17 - - *0 は負け 18 - - *n は勝ち n>=1 19 - 20 - ゲーム 21 - - 状態 G から打てる手で遷移する先を G1, ..., Gk とする 22 - G = {G1, ..., Gk} と書く 71 + - より一般的に G1≡*n1, ..., Gk≡*nk ならば、G={G1, ..., Gk} ≡ *mex(n1,...,nk) 72 + 帰納的に、全てのゲームはなんらかの *n と等価 23 73 24 - 等価 25 - - 二つのゲームG, Fが等価なことを G ≡ F と書く 26 - 等価というのは勝ち負け一致よりもっと強い。二つのゲームの和を取ると必敗になること 27 - *n と *n は同サイズの山2つのnimは必敗なので等価。同サイズでなければ必勝なので等価でない 74 + 証明 75 + - {*n1, ..., *nk} は *mex(n1,...,nk) と等価。 76 + つまり和を取ると必敗。 77 + *mex(n1,...,nk) 側を動かした場合、相手は対応する ni に遷移する。 78 + {*ni} 側を mex(n1,...,nk) より小さいゲームに動かした場合、mex側を対応する値に変える。 79 + {*ni} 側を mex より大きいゲームに動かした場合、その大きいゲームをmexに下げる。 80 + で両側等価を保ててしまう。 81 + 28 82 29 - 定理 30 - - G1≡*n1, ..., Gk≡*nk ならば、G={G1, ..., Gk} ≡ *mex(n1,...,nk) 31 - where mex(S) = min(nat \setminus S) 32 - 帰納的に、全てのゲームはなんらかの *n と等価 33 - 34 - 定理の証明 35 - - {G1, ..., Gk} は *mex(n1,...,nk) と等価。 36 - つまり和を取ると必敗。 37 - *mex(n1,...,nk) 側を動かした場合、相手は対応する Gi に遷移する。 38 - {G} 側を mex(n1,...,nk) より小さいゲームに動かした場合、mex側を対応する値に変える。 39 - {G} 側を mex より大きいゲームに動かした場合、その大きいゲームをmexに下げる。 40 - で両側等価を保ててしまう。 41 - 42 - 等価(和を取ると必敗) => 勝ち負け一致 の証明 43 - - 偶奇を考えれば良い。必勝ゲーム+必敗ゲーム なら初手で必勝を必敗に変えて常にその状態を 44 - 保てば勝てる。ゆえに一致しないなら和をとったゲームは必勝。 83 +------------------------------------------------------------------------------------------- 84 +まとめ 45 85 46 - 47 -おまけ 48 - @G を G のnim値とする。つまりG≡*@G 49 - G = X + Y ならば @G = @X xor @Y 50 - 山が複数のnimの勝敗は全部xorとった1つ山のnimに等しいのと同じ原理。 86 +・一手動かした次の局面が *n1 または *n2 または ... なゲーム 87 +　　{*n1, ..., *nk} = *mex(n1, ..., nk) 88 +・ゲーム *n1 と *n2 とどちらかを選んで一手進められるゲーム 89 +　　*n1 + *n2 = *(n1 xor n2) 90 +・ゲーム *n1 と *n2 とどちらか一方または両方一気に進められるゲーム 91 +　　*n1 <+> *n2 = *(n1 + n2) //単に１個の山なのとかわらない 92 +・両方一手ずつ進めるゲーム？ 93 +　　*n1 X *n2 = ?