Artifact Content
Not logged in

Artifact b75bd46f8bc82eec374d14159b21ec0f425c51a5


// SRM338 Div1 LV3

-------------------------------------------------------------------------------------------
対象となるゲーム
  - 二人ゲーム
  - 二人とも動かせる手の集合は同じ
  - 動かせなくなった方が負け
  - 無限ループしない

nim
  - n 個の石の山がある
  - 一手で 1 ~ n 個取っていい
  - 石がなくなって打つ手が無くなった方が負け(最後の石を取った方が勝ち)

*n をサイズ n の山が1個だけの nim とする
  - *0 は負け
  - *n は勝ち n>=1

-------------------------------------------------------------------------------------------
ゲーム
  - 状態 G から打てる手で遷移する先を G1, ..., Gk とする
    G = {G1, ..., Gk} と書く

ゲームの和
  - G1 + G2 を、G1 と G2 の二つのゲームがあって、どちらかを選んで一手進められるゲームとする。
    すなわち G1 + G2 = {(v,G2) | v∈G1} ∪ {(G1,u) | u∈G2} 

等価
  - 二つのゲームG, Fが等価なことを G ≡ F と書く
    等価というのは勝ち負け一致よりもっと強い。二つのゲームの和 G+F が必敗になることと定義する。
    たとえば *n と *n は同サイズの山2つのnimは必敗なので等価。同サイズでなければ必勝なので等価でない
    等価というのは可能な動きの構造がisomorphic/bisimilarというよりは弱い。
    たとえば以下で示すように *1 + *3 ≡ *2 だが初手のパターン数など違う。

-------------------------------------------------------------------------------------------
補題:必敗 + 必敗 = 必敗
 - どう動かしてもと必勝+必敗になるので必敗+必敗に戻されて負ける

補題:必勝 + 必敗 = 必勝
 - 必敗+必敗 に動かせばよい

定理:【等価(和を取ると必敗) => 勝ち負け一致】
  - 勝ち負け不一致=>必勝が上の補題で言えているので証明終了

    注意:
      必勝 + 必勝 = 必敗
    は成り立たない! *2 + *1 は 初手で *1 + *1 に行けるのでこれは勝てる

補題:G+G は必敗
 - まねっこmoveをされると負けるしかない

補題:A≡A', B≡B' ならば A+B≡A'+B'
  - A+B+A'+B' = (A+A')+(B+B') = 必敗+必敗 = 必敗

補題:Ai≡Ai' ならば {A0,A1,A2,...}≡{A0',A1',A2',...}
 - {A0,A1,A2,...}+{A0',A1',A2',...} は必敗。なぜならこちらがどう動かしても
    A0+A0', A1+A1', A2+A2', ... のいずれかの必敗状態に遷移させられるから。

-------------------------------------------------------------------------------------------
定理【ゲームの和はxor】
  - *n1 + *n2 = *(n1 xor n2)
  - より一般的に G1≡*n1, G2≡*n2 ならば、G1 + G2 ≡ *(n1 xor n2)

  証明
    - *n1 + *n2 + *(n1 xor n2) が必敗であることを言えば良い。
    - (n1 xor n2 xor (n1 xor n2)) は 0 である
    - 一手動かすと 0 じゃなくなる
        >> n1 と n2 と n1^n2 のどれか一個だけビットが変わるので絶対xorが変わるから
    - 相手は一手動かして 0 に戻せる
        >> a^b^c = x が非ゼロの場合 a=>a^x か b=>b^x か c=>c^x と動かせばよい
        >> つまりa,b,cのどれかは^xすると減ることを言えばよい。
        >> a,b,cのうち最上位ビットが立っているものが奇数個ならxも立つのでxorすれば減る
        >> 偶数個(2個)なら、その最上位ビットを無視した残りをa',b',c'とするとこれも
        >> xorがxなので数学的帰納法的にやることにより巧い減らし方が見つかる。
    - よって最終局面"全部 0"になるのは絶対に自分のターン

-------------------------------------------------------------------------------------------
定理【ゲームの状態遷移はmex】
  - {*n1, ..., *nk} ≡ *mex(n1,...,nk)
      where mex(S) = min(nat \setminus S)

  - より一般的に G1≡*n1, ..., Gk≡*nk ならば、G={G1, ..., Gk} ≡ *mex(n1,...,nk)
    帰納的に、全てのゲームはなんらかの *n と等価

  証明
    - {*n1, ..., *nk} は *mex(n1,...,nk) と等価。
      つまり和を取ると必敗。
      *mex(n1,...,nk) 側を動かした場合、相手は対応する ni に遷移する。
      {*ni} 側を mex(n1,...,nk) より小さいゲームに動かした場合、mex側を対応する値に変える。
      {*ni} 側を mex より大きいゲームに動かした場合、その大きいゲームをmexに下げる。
      で両側等価を保ててしまう。


-------------------------------------------------------------------------------------------
まとめ

・一手動かした次の局面が *n1 または *n2 または ... なゲーム
  {*n1, ..., *nk} = *mex(n1, ..., nk)
・ゲーム *n1 と *n2 とどちらかを選んで一手進められるゲーム
  *n1 + *n2 = *(n1 xor n2)
・ゲーム *n1 と *n2 とどちらか一方または両方一気に進められるゲーム
  *n1 <+> *n2 = *(n1 + n2)     //単に1個の山なのとかわらない
・両方一手ずつ進めるゲーム?????
  *n1 X *n2 = ?