ゲーム系問題のはなし

この記事はこのスライドの受け売りなので, ちゃんと知りたい人はこっちを読んでください。

はじめに

ゲーム系の問題は以下の三つに大別できます。

• 後ろから探索
• grundy数を計算
• adhocな必勝法を見つける 順番にみていきましょう

  後ろから探索

  単純にゲーム木を探索する方法です。制約があまりキツくない問題に使うことができます。まずこれから考えるのが良いでしょう。実装にはメモ化再帰やDPを使うことが多いです。

  例題

  例題,例題2

  grundy数を計算

  grundy数は不偏ゲームの状態に定義される数であり, その定義は以下の通りです。

• terminal positionではgrundy数は0
• それ以外では、その局面から１手で移動できる局面のgurundy数の集合に含まれない最小の自然数 このように定義すると、負け局面ではgrundy数は0、それ以外では正の自然数になります。 grundy数の重要な性質として、いくつかのゲームが合わさったようなゲームに対して、そのgrundy数はそれぞれのゲームのgrundy数の排他的論理和(xor)になることが挙げられます。

  ad hocな必勝法を見つける

  天才になってください。 とはいえこれだけだと僕のような凡人には厳しいのでいくつか考えるヒントを書いておきます。

• とにかく実験 全探索できる範囲で試してみましょう。規則性が見つかるかもしれません
• 相手と対称な動きをするのが最善
• 偶奇性を考える
• 必敗局面から必敗局面には移動できない

  例題

  例題1, 例題2, 例題3, 例題4

  その他

• 実はどう行動しても結果が変わらないという場合もある例題
• 最後の形をイメージする