1 // SRM338 Div1 LV3 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 < > 66 -------------------------------------------------------------------------------- 12 - サイズ s1, s2, .., sk の山がある | 67 定理【ゲームの状態遷移はmex】 13 - どれか一つ山を選んで 1 ～ 山サイズ の任意個取り除ける | 68 - {*n1, ..., *nk} ≡ *mex(n1,...,nk) 14 - 最後の山を取った方が勝ち（山がなくなって打つ手が無くなった方が負け） | 69 where mex(S) = min(nat \setminus S) 15 70 16 *n をサイズ n の山が1個だけの nim とする | 71 - より一般的に G1≡*n1, ..., Gk≡*nk ならば、G={G1, ..., Gk} ≡ *mex(n1,...,nk) 17 - *0 は負け | 72 帰納的に、全てのゲームはなんらかの *n と等価 18 - *n は勝ち n>=1 < 19 < 20 ゲーム < 21 - 状態 G から打てる手で遷移する先を G1, ..., Gk とする < 22 G = {G1, ..., Gk} と書く < 23 73 24 等価 < > 74 証明 25 - 二つのゲームG, Fが等価なことを G ≡ F と書く | 75 - {*n1, ..., *nk} は *mex(n1,...,nk) と等価。 26 等価というのは勝ち負け一致よりもっと強い。二つのゲームの和を取ると必敗���なること | 76 つまり和を取ると必敗��� 27 *n と *n は同サイズの山2つのnimは必敗なので等価。同サイズでなければ必勝なので等価でない | 77 *mex(n1,...,nk) 側を動かした場合、相手は対応する ni に遷移する。 > 78 {*ni} 側を mex(n1,...,nk) より小さいゲームに動かした場合���mex側を対応する値に変える。 > 79 {*ni} 側を mex より大きいゲームに動かした場合、その大きいゲームをmexに下げる。 > 80 で両側等価を保ててしまう。 > 81 28 82 29 定理 < > 83 -------------------------------------------------------------------------------- 30 - G1≡*n1, ..., Gk≡*nk ならば、G={G1, ..., Gk} ≡ *mex(n1,...,nk) | 84 まとめ 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 保てば勝てる。ゆえに一致しないなら和をとったゲームは必勝。 < 45 85 46 < > 86 ・一手動かした次の局面が *n1 または *n2 または ... なゲー�� 47 ���まけ | 87 ���　{*n1, ..., *nk} = *mex(n1, ..., nk) 48 @G を G のnim値とする。つまりG≡*@G | 88 ・ゲーム *n1 と *n2 とどちらかを選んで一手進められるゲーム 49 G = X + Y ならば @G = @X xor @Y | 89 　　*n1 + *n2 = *(n1 xor n2) 50 山が複数のnimの勝敗は全部xorとった1つ山のnimに等しいのと同じ原理。 | 90 ・ゲーム *n1 と *n2 とどちらか一方または両方一気に進められるゲーム > 91 　　*n1 <+> *n2 = *(n1 + n2) //単に１個の山なのとかわらない > 92 ・両方一手ずつ進めるゲーム？ > 93 　　*n1 X *n2 = ?