状態がループするゲームの解析(後退解析)

状態がループするゲームは、DAG ではないため動的計画法が使えない。代わりに 後退解析 というテクニックを用いる。

次のゲームを考えよう。n 頂点 m 辺の有向グラフが与えられる。最初、頂点 s に駒が置かれている。プレイヤーは駒を隣接頂点に動かすことができる。この操作を交互に行い、動かせなくなった人が負けである。両者が最適な行動を行ったとき、どちらが勝つか、それとも勝負が決まらないか判定せよ。

有限状態のゲームはこのゲームに還元できる(確定とか二人とか完全情報とかあるけど察して)ので、最も重要なゲームとも言える。簡単なグラフを例にとって、後退解析がどのように行われるのか説明しよう。

解析の基本は、

  • 負け状態に遷移できるなら、その頂点は勝ち
  • 勝ち状態にしか遷移できないなら、その頂点は負け

である。


f:id:pekempey:20180201175639p:plain
図1. 与えられたグラフ


f:id:pekempey:20180201175856p:plain
図2. 移動先がない頂点は負け


f:id:pekempey:20180201180202p:plain
図3. 負け状態に遷移できる頂点は勝ち



f:id:pekempey:20180201180455p:plain
図4. 勝ち状態にしか遷移できないので負け


f:id:pekempey:20180201180640p:plain
図5. 負け状態に遷移できるので勝ち

ここまでの解析は queue を使って(トポロジカルソートみたいな感じでやれば)いける。なお、決まらなかったノードは引き分け状態である。理由を簡単に説明する。まず、決まらなかったノードは勝ち状態か引き分け状態にしか遷移できないはずである。勝ちノードに遷移させた瞬間に負けが確定するので、引き分けノードに遷移するしかない。さらに、引き分けノードからは引き分けノードに必ず遷移できる(もしそうでないなら、勝ち状態か負け状態か判定できるはずである)。すると、引き分けノードから引き分けノードに移動するという操作が無限に行われることが分かる。


https://ideone.com/E5cspI
https://ideone.com/VMzg80
https://ideone.com/bePB9J
https://ideone.com/IxDkWG
https://ideone.com/QzjXuj