6 - 二人とも動かせる手の集合は同じ 6 - 二人とも動かせる手の集合は同じ 7 - 動かせなくなった方が負け 7 - 動かせなくなった方が負け 8 - 無限ループしない 8 - 無限ループしない 9 9 10 nim 10 nim 11 - n 個の石の山がある 11 - n 個の石の山がある 12 - 一手で 1 ～ n 個取っていい 12 - 一手で 1 ～ n 個取っていい 13 - 最後の石を取った方が勝ち（石がなくなって打つ手が無くなった方が負け） | 13 - 石がなくなって打つ手が無くなった方が負け（最後の石を取った方が勝ち） 14 14 15 *n をサイズ n の山が1個だけの nim とする 15 *n をサイズ n の山が1個だけの nim とする 16 - *0 は負け 16 - *0 は負け 17 - *n は勝ち n>=1 17 - *n は勝ち n>=1 18 18 19 -------------------------------------------------------------------------------- 19 -------------------------------------------------------------------------------- 20 ゲーム 20 ゲーム ................................................................................................................................................................................ 23 23 24 ゲームの和 24 ゲームの和 25 - G1 + G2 を、G1 と G2 の二つのゲームがあって、どちらかを選んで一手進められるゲームとする。 25 - G1 + G2 を、G1 と G2 の二つのゲームがあって、どちらかを選んで一手進められるゲームとする。 26 すなわち G1 + G2 = {(v,G2) | v∈G1} ∪ {(G1,u) | u∈G2} 26 すなわち G1 + G2 = {(v,G2) | v∈G1} ∪ {(G1,u) | u∈G2} 27 27 28 等価 28 等価 29 - 二つのゲームG, Fが等価なことを G ≡ F と書く 29 - 二つのゲームG, Fが等価なことを G ≡ F と書く 30 等価というのは勝ち負け一致よりもっと強い。二つのゲームの和 G+F が必敗になること。 | 30 等価というのは勝ち負け一致よりもっと強い。二つのゲームの和 G+F が必敗になること���定義する��� 31 たとえば *n と *n は同サイズの山2つのnimは必敗なので等価。同サイズでなければ必勝なので等価でない 31 たとえば *n と *n は同サイズの山2つのnimは必敗なので等価。同サイズでなければ必勝なので等価でない 32 等価というのは可能な動きの構造がisomorphic/bisimilarというよりは弱い。 32 等価というのは可能な動きの構造がisomorphic/bisimilarというよりは弱い。 33 たとえば以下で示すように *1 + *3 ≡ *2 だが初手のパターン数など違う。 33 たとえば以下で示すように *1 + *3 ≡ *2 だが初手のパターン数など違う。 34 34 35 -------------------------------------------------------------------------------- 35 -------------------------------------------------------------------------------- 36 定理：等価(和を取ると必敗) => 勝ち負け一致 < 37 - 必勝ゲーム+必敗ゲーム なら初手で必勝を必敗に変えて��にその状態を保てば勝てる。 < 38 ゆえに勝ち負けが一致しないなら和をとったゲームは必���。 < 39 必敗 + 必敗 = 必敗 | 36 補題：必敗 + 必敗 = 必敗 > 37 　- どう動かしてもと必勝+必敗になるので必敗+必敗に戻さ���て負ける > 38 40 必勝 + 必敗 = 必勝 | 39 補題：必勝 + 必敗 = 必勝 > 40 　- 必敗+必敗 に動かせばよい > 41 > 42 定理：【等価(和を取ると必敗) => 勝ち負け一致】 > 43 - 勝ち負け不一致=>必勝が上の補題で言えているので証明��了 41 44 42 注意： 45 注意： 43 必勝 + 必勝 = 必敗 46 必勝 + 必勝 = 必敗 44 は成り立たない！ *2 + *1 は 初手で *1 + *1 に行けるのでこれは勝てる 47 は成り立たない！ *2 + *1 は 初手で *1 + *1 に行けるのでこれは勝てる 45 48 46 補題：G+G は必敗 49 補題：G+G は必敗 47 　- まねっこmoveをされると負けるしかない 50 　- まねっこmoveをされると負けるしかない 48 51 49 補題：A≡B ならば A+C≡B+C | 52 補題：A≡A', B≡B' ならば A+B≡A'+B' 50 - A+C+B+C = (A+B)+(C+C) = 必敗+必敗 = 必敗 | 53 - A+B+A'+B' = (A+A')+(B+B') = 必敗+必敗 = 必敗 51 54 52 補題：A≡B ならば {A,G1,G2,...}≡{B,G1,G2,...} | 55 補題：Ai≡Ai' ならば {A0,A1,A2,...}≡{A0',A1',A2',...} 53 　- {A,G1,G2,...}+{B,G1,G2,...} は必敗。なぜならこちらがどう動かしても | 56 　- {A0,A1,A2,...}+{A0',A1',A2',...} は必敗。なぜならこちらがどう動かしても 54 A+B, G1+G1, G2+G2, ... のいずれかの必敗状態に遷移させられるから。 | 57 A0+A0', A1+A1', A2+A2', ... のいずれかの必敗状態に遷移させられるから。 55 58 56 -------------------------------------------------------------------------------- 59 -------------------------------------------------------------------------------- 57 定理【ゲームの和はxor】 60 定理【ゲームの和はxor】 58 - *n1 + *n2 = *(n1 xor n2) 61 - *n1 + *n2 = *(n1 xor n2) 59 - より一般的に G1≡*n1, G2≡*n2 ならば、G1 + G2 ≡ *(n1 xor n2) 62 - より一般的に G1≡*n1, G2≡*n2 ならば、G1 + G2 ≡ *(n1 xor n2) 60 63 61 証明 64 証明 62 - *n1 + *n2 + *(n1 xor n2) が必敗であることを言えば良い。 65 - *n1 + *n2 + *(n1 xor n2) が必敗であることを言えば良い。 63 - (n1 xor n2 xor (n1 xor n2)) は 0 である 66 - (n1 xor n2 xor (n1 xor n2)) は 0 である 64 - 一手動かすと 0 じゃなくなる 67 - 一手動かすと 0 じゃなくなる 65 >> n1 と n2 と n1^n2 のどれか一個だけビットが変わるので絶対xorが変わるから 68 >> n1 と n2 と n1^n2 のどれか一個だけビットが変わるので絶対xorが変わるから 66 - 相手は一手動かして 0 に戻せる 69 - 相手は一手動かして 0 に戻せる 67 >> 常に | 70 >> a^b^c = x が非ゼロの場合 a=>a^x か b=>b^x か c=>c^x と動かせばよい > 71 >> つまりa,b,cのどれかは^xすると減ることを言えばよ��。 > 72 >> a,b,cのうち最上位ビットが立っているものが奇数個���らxも立つのでxorすれば減る > 73 >> 偶数個(2個)なら、その最上位ビットを無視した残りをa',b',c'とするとこれも > 74 >> xorがxなので数学的帰納法的にやることにより巧い��らし方が見つかる。 68 - よって最終局面"全部 0"になるのは絶対に自分のターン 75 - よって最終局面"全部 0"になるのは絶対に自分のターン 69 < 70 76 71 -------------------------------------------------------------------------------- 77 -------------------------------------------------------------------------------- 72 定理【ゲームの状態遷移はmex】 78 定理【ゲームの状態遷移はmex】 73 - {*n1, ..., *nk} ≡ *mex(n1,...,nk) 79 - {*n1, ..., *nk} ≡ *mex(n1,...,nk) 74 where mex(S) = min(nat \setminus S) 80 where mex(S) = min(nat \setminus S) 75 81 76 - より一般的に G1≡*n1, ..., Gk≡*nk ならば、G={G1, ..., Gk} ≡ *mex(n1,...,nk) 82 - より一般的に G1≡*n1, ..., Gk≡*nk ならば、G={G1, ..., Gk} ≡ *mex(n1,...,nk) ................................................................................................................................................................................ 90 96 91 ・一手動かした次の局面が *n1 または *n2 または ... なゲーム 97 ・一手動かした次の局面が *n1 または *n2 または ... なゲーム 92 　　{*n1, ..., *nk} = *mex(n1, ..., nk) 98 　　{*n1, ..., *nk} = *mex(n1, ..., nk) 93 ・ゲーム *n1 と *n2 とどちらかを選んで一手進められるゲーム 99 ・ゲーム *n1 と *n2 とどちらかを選んで一手進められるゲーム 94 　　*n1 + *n2 = *(n1 xor n2) 100 　　*n1 + *n2 = *(n1 xor n2) 95 ・ゲーム *n1 と *n2 とどちらか一方または両方一気に進められるゲーム 101 ・ゲーム *n1 と *n2 とどちらか一方または両方一気に進められるゲーム 96 　　*n1 <+> *n2 = *(n1 + n2) //単に１個の山なのとかわらない 102 　　*n1 <+> *n2 = *(n1 + n2) //単に１個の山なのとかわらない 97 ・両方一手ずつ進めるゲーム？ | 103 ・両方一手ずつ進めるゲーム？？？？？ 98 　　*n1 X *n2 = ? 104 　　*n1 X *n2 = ?