23dfcca431 2011-02-23 kinaba: // SRM338 Div1 LV3 23dfcca431 2011-02-23 kinaba: 42f877f59c 2012-12-21 kinaba: ------------------------------------------------------------------------------------------- 42f877f59c 2012-12-21 kinaba: 対象となるゲーム 42f877f59c 2012-12-21 kinaba: - 二人ゲーム 42f877f59c 2012-12-21 kinaba: - 二人とも動かせる手の集合は同じ 42f877f59c 2012-12-21 kinaba: - 動かせなくなった方が負け 42f877f59c 2012-12-21 kinaba: - 無限ループしない 42f877f59c 2012-12-21 kinaba: 42f877f59c 2012-12-21 kinaba: nim 42f877f59c 2012-12-21 kinaba: - n 個の石の山がある 42f877f59c 2012-12-21 kinaba: - 一手で 1 ～ n 個取っていい 339e20815a 2014-10-24 kinaba: - 石がなくなって打つ手が無くなった方が負け（最後の石を取った方が勝ち） 42f877f59c 2012-12-21 kinaba: 42f877f59c 2012-12-21 kinaba: *n をサイズ n の山が1個だけの nim とする 42f877f59c 2012-12-21 kinaba: - *0 は負け 42f877f59c 2012-12-21 kinaba: - *n は勝ち n>=1 42f877f59c 2012-12-21 kinaba: 42f877f59c 2012-12-21 kinaba: ------------------------------------------------------------------------------------------- 42f877f59c 2012-12-21 kinaba: ゲーム 42f877f59c 2012-12-21 kinaba: - 状態 G から打てる手で遷移する先を G1, ..., Gk とする 42f877f59c 2012-12-21 kinaba: G = {G1, ..., Gk} と書く 42f877f59c 2012-12-21 kinaba: 42f877f59c 2012-12-21 kinaba: ゲームの和 42f877f59c 2012-12-21 kinaba: - G1 + G2 を、G1 と G2 の二つのゲームがあって、どちらかを選んで一手進められるゲームとする。 42f877f59c 2012-12-21 kinaba: すなわち G1 + G2 = {(v,G2) | v∈G1} ∪ {(G1,u) | u∈G2} 42f877f59c 2012-12-21 kinaba: 42f877f59c 2012-12-21 kinaba: 等価 42f877f59c 2012-12-21 kinaba: - 二つのゲームG, Fが等価なことを G ≡ F と書く 339e20815a 2014-10-24 kinaba: 等価というのは勝ち負け一致よりもっと強い。二つのゲームの和 G+F が必敗になることと定義する。 42f877f59c 2012-12-21 kinaba: たとえば *n と *n は同サイズの山2つのnimは必敗なので等価。同サイズでなければ必勝なので等価でない 42f877f59c 2012-12-21 kinaba: 等価というのは可能な動きの構造がisomorphic/bisimilarというよりは弱い。 42f877f59c 2012-12-21 kinaba: たとえば以下で示すように *1 + *3 ≡ *2 だが初手のパターン数など違う。 42f877f59c 2012-12-21 kinaba: 42f877f59c 2012-12-21 kinaba: ------------------------------------------------------------------------------------------- 339e20815a 2014-10-24 kinaba: 補題：必敗 + 必敗 = 必敗 339e20815a 2014-10-24 kinaba: - どう動かしてもと必勝+必敗になるので必敗+必敗に戻されて負ける 339e20815a 2014-10-24 kinaba: 339e20815a 2014-10-24 kinaba: 補題：必勝 + 必敗 = 必勝 339e20815a 2014-10-24 kinaba: - 必敗+必敗 に動かせばよい 339e20815a 2014-10-24 kinaba: 339e20815a 2014-10-24 kinaba: 定理：【等価(和を取ると必敗) => 勝ち負け一致】 339e20815a 2014-10-24 kinaba: - 勝ち負け不一致=>必勝が上の補題で言えているので証明終了 42f877f59c 2012-12-21 kinaba: 42f877f59c 2012-12-21 kinaba: 注意： 42f877f59c 2012-12-21 kinaba: 必勝 + 必勝 = 必敗 42f877f59c 2012-12-21 kinaba: は成り立たない！ *2 + *1 は 初手で *1 + *1 に行けるのでこれは勝てる 42f877f59c 2012-12-21 kinaba: 42f877f59c 2012-12-21 kinaba: 補題：G+G は必敗 42f877f59c 2012-12-21 kinaba: - まねっこmoveをされると負けるしかない 42f877f59c 2012-12-21 kinaba: 0366fb35b4 2014-10-24 kinaba: ------------------------------------------------------------------------------------------- 339e20815a 2014-10-24 kinaba: 補題：A≡A', B≡B' ならば A+B≡A'+B' 339e20815a 2014-10-24 kinaba: - A+B+A'+B' = (A+A')+(B+B') = 必敗+必敗 = 必敗 339e20815a 2014-10-24 kinaba: 42f877f59c 2012-12-21 kinaba: 定理【ゲームの和はxor】 42f877f59c 2012-12-21 kinaba: - *n1 + *n2 = *(n1 xor n2) 42f877f59c 2012-12-21 kinaba: - より一般的に G1≡*n1, G2≡*n2 ならば、G1 + G2 ≡ *(n1 xor n2) 42f877f59c 2012-12-21 kinaba: 42f877f59c 2012-12-21 kinaba: 証明 42f877f59c 2012-12-21 kinaba: - *n1 + *n2 + *(n1 xor n2) が必敗であることを言えば良い。 257929a5e9 2013-01-21 kinaba: - (n1 xor n2 xor (n1 xor n2)) は 0 である 257929a5e9 2013-01-21 kinaba: - 一手動かすと 0 じゃなくなる 257929a5e9 2013-01-21 kinaba: >> n1 と n2 と n1^n2 のどれか一個だけビットが変わるので絶対xorが変わるから 257929a5e9 2013-01-21 kinaba: - 相手は一手動かして 0 に戻せる 339e20815a 2014-10-24 kinaba: >> a^b^c = x が非ゼロの場合 a=>a^x か b=>b^x か c=>c^x と動かせばよい 339e20815a 2014-10-24 kinaba: >> つまりa,b,cのどれかは^xすると減ることを言えばよい。 339e20815a 2014-10-24 kinaba: >> a,b,cのうち最上位ビットが立っているものが奇数個ならxも立つのでxorすれば減る 339e20815a 2014-10-24 kinaba: >> 偶数個(2個)なら、その最上位ビットを無視した残りをa',b',c'とするとこれも 339e20815a 2014-10-24 kinaba: >> xorがxなので数学的帰納法的にやることにより巧い減らし方が見つかる。 257929a5e9 2013-01-21 kinaba: - よって最終局面"全部 0"になるのは絶対に自分のターン 42f877f59c 2012-12-21 kinaba: 42f877f59c 2012-12-21 kinaba: ------------------------------------------------------------------------------------------- 0366fb35b4 2014-10-24 kinaba: 補題：Ai≡Ai' ならば {A0,A1,A2,...}≡{A0',A1',A2',...} 0366fb35b4 2014-10-24 kinaba: - {A0,A1,A2,...}+{A0',A1',A2',...} は必敗。なぜならこちらがどう動かしても 0366fb35b4 2014-10-24 kinaba: A0+A0', A1+A1', A2+A2', ... のいずれかの必敗状態に遷移させられるから。 0366fb35b4 2014-10-24 kinaba: 42f877f59c 2012-12-21 kinaba: 定理【ゲームの状態遷移はmex】 42f877f59c 2012-12-21 kinaba: - {*n1, ..., *nk} ≡ *mex(n1,...,nk) 42f877f59c 2012-12-21 kinaba: where mex(S) = min(nat \setminus S) 42f877f59c 2012-12-21 kinaba: 42f877f59c 2012-12-21 kinaba: - より一般的に G1≡*n1, ..., Gk≡*nk ならば、G={G1, ..., Gk} ≡ *mex(n1,...,nk) 42f877f59c 2012-12-21 kinaba: 帰納的に、全てのゲームはなんらかの *n と等価 42f877f59c 2012-12-21 kinaba: 42f877f59c 2012-12-21 kinaba: 証明 42f877f59c 2012-12-21 kinaba: - {*n1, ..., *nk} は *mex(n1,...,nk) と等価。 42f877f59c 2012-12-21 kinaba: つまり和を取ると必敗。 42f877f59c 2012-12-21 kinaba: *mex(n1,...,nk) 側を動かした場合、相手は対応する ni に遷移する。 42f877f59c 2012-12-21 kinaba: {*ni} 側を mex(n1,...,nk) より小さいゲームに動かした場合、mex側を対応する値に変える。 42f877f59c 2012-12-21 kinaba: {*ni} 側を mex より大きいゲームに動かした場合、その大きいゲームをmexに下げる。 42f877f59c 2012-12-21 kinaba: で両側等価を保ててしまう。 42f877f59c 2012-12-21 kinaba: 42f877f59c 2012-12-21 kinaba: 42f877f59c 2012-12-21 kinaba: ------------------------------------------------------------------------------------------- 42f877f59c 2012-12-21 kinaba: まとめ 42f877f59c 2012-12-21 kinaba: 42f877f59c 2012-12-21 kinaba: ・一手動かした次の局面が *n1 または *n2 または ... なゲーム 0366fb35b4 2014-10-24 kinaba: {*n1, ..., *nk} ≡ *mex(n1, ..., nk) 0366fb35b4 2014-10-24 kinaba: 42f877f59c 2012-12-21 kinaba: ・ゲーム *n1 と *n2 とどちらかを選んで一手進められるゲーム 0366fb35b4 2014-10-24 kinaba: *n1 + *n2 ≡ *(n1 xor n2) 0366fb35b4 2014-10-24 kinaba: 0366fb35b4 2014-10-24 kinaba: 0366fb35b4 2014-10-24 kinaba: ------------------------------------------------------------------------------------------- 0366fb35b4 2014-10-24 kinaba: その他のゲームの組み合わせ（証明があやしい） 0366fb35b4 2014-10-24 kinaba: 0366fb35b4 2014-10-24 kinaba: 定理： ゲーム *n1 と *n2 とどちらか一方または両方一気に進められるゲーム 0366fb35b4 2014-10-24 kinaba: *n1 <+> *n2 ≡ *(n1 + n2) 0366fb35b4 2014-10-24 kinaba: 証明： 単に１個の山なのとかわらないので勝敗一致どころか同型 0366fb35b4 2014-10-24 kinaba: 0366fb35b4 2014-10-24 kinaba: 補題：A≡A' かつ B≡B' ならば (A<+>B)≡(A'<+>B')。 0366fb35b4 2014-10-24 kinaba: ゆえに一般に G1≡*n1, G2≡*n2 ならば G1<+>G2 ≡ *(n1+n2) 0366fb35b4 2014-10-24 kinaba: 証明：(A<+>B)+(A'<+>B')が必敗であることを言えばよい。 0366fb35b4 2014-10-24 kinaba: 相手がどう動かしても A<+>B ==> a<+>b 0366fb35b4 2014-10-24 kinaba: a+a'、b+b'が必敗であるように (a<+>b)+(a'<+>b') と動かせる。 0366fb35b4 2014-10-24 kinaba: いずれ相手は死ぬ 0366fb35b4 2014-10-24 kinaba: 0366fb35b4 2014-10-24 kinaba: 0366fb35b4 2014-10-24 kinaba: 定理： 先手はゲーム *n1、後手はゲーム *n2 を交互に一手ずつ進めるゲーム 0366fb35b4 2014-10-24 kinaba: *n1 X *n2 ≡ *(n1<=n2 ? 0 : n2+1) 0366fb35b4 2014-10-24 kinaba: 後手 0366fb35b4 2014-10-24 kinaba: 0 1 2 3 4 0366fb35b4 2014-10-24 kinaba: ------+---------- 0366fb35b4 2014-10-24 kinaba: 先手 0|0 0 0 0 0 0366fb35b4 2014-10-24 kinaba: 1|1 0 0 0 0 0366fb35b4 2014-10-24 kinaba: 2|1 2 0 0 0 0366fb35b4 2014-10-24 kinaba: 3|1 2 3 0 0 0366fb35b4 2014-10-24 kinaba: 4|1 2 3 4 0 0366fb35b4 2014-10-24 kinaba: 左辺のゲームのmex計算してみるとこうなる。 0366fb35b4 2014-10-24 kinaba: 0366fb35b4 2014-10-24 kinaba: 補題：A≡A' かつ B≡B' ならば (A X B)≡(A' X B')。 0366fb35b4 2014-10-24 kinaba: ゆえに一般に G1≡*n1, G2≡*n2 ならば G1 X G2 ≡ *(n1<=n2 ? 0 : n2+1) 0366fb35b4 2014-10-24 kinaba: 証明：AxB + A'xB' を Bxa + A'xB' と動かされたら Bxa + B'xa' に動かせて≡が 0366fb35b4 2014-10-24 kinaba: 保てるのでいずれ相手は死ぬ