ゲーム系問題
対象戦略
手の自由度
後退解析
明らかに必勝、必敗の状態を見つける。その状態のどちらにも帰着できるような単純な状態を探す。そのような状態に移れないような状態を押し付け続ける。
Grundy Number
ゲームの状態とは、そこから遷移できる状態の集合である
終了状態をは空集合であり、これを\*0と書く
一般に、ある\*nが存在して、nより小さい全ての非負整数iについて、\*iに遷移できるような状態を\*nと書く。また、このような状態をNimberという
ゲームの合成
終了状態
f(G) := 状態Gから最適に行動した時の勝敗
状態の同値関係を以下のように定める
G≡G′⟺∀Hf(G+H)=f(G′+H)
任意の２状態G,G′について、G≡G′⟺f(G+G′)=負け が成り立つ
証明：
G≡G′⟹G+G≡G+G′が成り立つが、対象戦略によりf(G+G)=負け
G≡G′の場合、f(G)=勝ちと仮定して良い。Gから適切に選ぶことで、相手に状態H+G′を渡すことができ、f(H)=負けである。この状態は必敗なので、f(G+G′)=勝ちとなり、G≡G′⟸f(G+G′)=負け
状態G={G1,…,Gk}について、帰納法の仮定により、∀i ∃ni Gi≡niが成り立つ。
G′={n1,…,nk}と定義する。このとき、G≡G′を示す。
現在の状態がG+G′のとき、次の状態をGから選ぶとする。このとき、次の状態がGi+G′になったとする。
この場合、相手はniを選ぶことで必勝になる。したがってf(G+G′)=負け より、G≡G′
次に、G′≡∗mとなる非負整数mが存在することを示す。
f(G′+∗m)=負けとなるようなmを考える。
もしあるiが存在して、ni=mとなるなら、状態\*niを選ぶことで勝ててしまう。そのようなiが存在しないなら、操作をG′から選ぶ限り負け。
次に、操作を\*mから選ぶことを考える。m′=mex(G′)とする。m′<mなら、次の状態をG′+∗m′にすることで勝ててしまう。一方、m′=mのとき、必ずG′から選ばなければならない。
以上より、G≡∗mが成り立つ非負整数mがただ一つ存在し、m=mex(G′)である