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 個取っていい
42f877f59c 2012-12-21        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 と書く
42f877f59c 2012-12-21        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: -------------------------------------------------------------------------------------------
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:       必勝 + 必勝 = 必敗
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: 
42f877f59c 2012-12-21        kinaba: 補題：A≡B ならば A+C≡B+C
42f877f59c 2012-12-21        kinaba:   - A+C+B+C = (A+B)+(C+C) = 必敗+必敗 = 必敗
42f877f59c 2012-12-21        kinaba: 
42f877f59c 2012-12-21        kinaba: 補題：A≡B ならば {A,G1,G2,...}≡{B,G1,G2,...}
42f877f59c 2012-12-21        kinaba: 　- {A,G1,G2,...}+{B,G1,G2,...} は必敗。なぜならこちらがどう動かしても
42f877f59c 2012-12-21        kinaba:     A+B, G1+G1, G2+G2, ... のいずれかの必敗状態に遷移させられるから。
42f877f59c 2012-12-21        kinaba: 
42f877f59c 2012-12-21        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 に戻せる
257929a5e9 2013-01-21        kinaba:         >> 常に
257929a5e9 2013-01-21        kinaba:     - よって最終局面"全部 0"になるのは絶対に自分のターン
42f877f59c 2012-12-21        kinaba: 
42f877f59c 2012-12-21        kinaba: 
42f877f59c 2012-12-21        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)
23dfcca431 2011-02-23        kinaba: 
42f877f59c 2012-12-21        kinaba:   - より一般的に G1≡*n1, ..., Gk≡*nk ならば、G={G1, ..., Gk} ≡ *mex(n1,...,nk)
42f877f59c 2012-12-21        kinaba:     帰納的に、全てのゲームはなんらかの *n と等価
23dfcca431 2011-02-23        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: 
23dfcca431 2011-02-23        kinaba: 
42f877f59c 2012-12-21        kinaba: -------------------------------------------------------------------------------------------
42f877f59c 2012-12-21        kinaba: まとめ
23dfcca431 2011-02-23        kinaba: 
42f877f59c 2012-12-21        kinaba: ・一手動かした次の局面が *n1 または *n2 または ... なゲーム
42f877f59c 2012-12-21        kinaba: 　　{*n1, ..., *nk} = *mex(n1, ..., nk)
42f877f59c 2012-12-21        kinaba: ・ゲーム *n1 と *n2 とどちらかを選んで一手進められるゲーム
42f877f59c 2012-12-21        kinaba: 　　*n1 + *n2 = *(n1 xor n2)
42f877f59c 2012-12-21        kinaba: ・ゲーム *n1 と *n2 とどちらか一方または両方一気に進められるゲーム
42f877f59c 2012-12-21        kinaba: 　　*n1 <+> *n2 = *(n1 + n2)     //単に１個の山なのとかわらない
42f877f59c 2012-12-21        kinaba: ・両方一手ずつ進めるゲーム？
42f877f59c 2012-12-21        kinaba: 　　*n1 X *n2 = ?