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

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

図のコード

ちょっと頂点間隔が狭かったかなぁ。spring layout で綺麗に作れれば楽だったんだけど微妙にずれたので手打ちした。

図1

\documentclass[margin=0.5cm]{standalone}
\usepackage{tikz,newtxtext,newtxmath}
\usetikzlibrary{graphs,graphdrawing,calc}
\usegdlibrary{trees,force,circular}
\begin{document}

\begin{tikzpicture}[
    nodes={draw,fill=white,circle,minimum size=0.65cm},
    foo/.style={-latex},
  ]
  \node (0) {};
  \node (1) at ($(0)+(60:1)$) {};
  \node (2) at ($(0)+(0:1)$) {};
  \node (3) at ($(1)+(0:1)$) {};
  \node (4) at ($(3)+(30:1)$) {};
  \node (5) at ($(3)+(-30:1)$) {};
  \node (6) at ($(4)+(90:1)$) {};
  \node (7) at ($(5)+(-90:1)$) {};
  \node (8) at ($(5)+(30:1)$) {};
  \node (9) at ($(7)+(-90:1)$) {};
  \node (10) at ($(9)+(-90:1)$) {};
  \node (11) at ($(9)+cos(30)*(1,0)$) {};

  \draw [foo] (0) -- (1);
  \draw [foo] (1) -- (2);
  \draw [foo] (2) -- (0);
  \draw [foo] (2) -- (9);
  \draw [foo] (3) -- (1);
  \draw [foo] (4) -- (3);
  \draw [foo] (5) -- (3);
  \draw [foo] (4) -- (6);
  \draw [foo] (5) -- (7);
  \draw [foo] (8) -- (4);
  \draw [foo] (8) -- (5);
  \draw [foo] (11) -- (8);
  \draw [foo] (9) -- (11);
  \draw [foo] (9) -- (10);
\end{tikzpicture}

\end{document}

図2

\documentclass[margin=0.5cm]{standalone}
\usepackage{tikz,newtxtext,newtxmath}
\usetikzlibrary{graphs,graphdrawing,calc}
\usegdlibrary{trees,force,circular}
\begin{document}

\begin{tikzpicture}[
    nodes={draw,fill=white,circle,minimum size=0.65cm},
    foo/.style={-latex},
    lose/.style={fill=blue!70,text=white},
  ]
  \node (0) {};
  \node (1) at ($(0)+(60:1)$) {};
  \node (2) at ($(0)+(0:1)$) {};
  \node (3) at ($(1)+(0:1)$) {};
  \node (4) at ($(3)+(30:1)$) {};
  \node (5) at ($(3)+(-30:1)$) {};
  \node[lose] (6) at ($(4)+(90:1)$) {L};
  \node[lose] (7) at ($(5)+(-90:1)$) {L};
  \node (8) at ($(5)+(30:1)$) {};
  \node (9) at ($(7)+(-90:1)$) {};
  \node[lose] (10) at ($(9)+(-90:1)$) {L};
  \node (11) at ($(9)+cos(30)*(1,0)$) {};

  \draw [foo] (0) -- (1);
  \draw [foo] (1) -- (2);
  \draw [foo] (2) -- (0);
  \draw [foo] (2) -- (9);
  \draw [foo] (3) -- (1);
  \draw [foo] (4) -- (3);
  \draw [foo] (5) -- (3);
  \draw [foo] (4) -- (6);
  \draw [foo] (5) -- (7);
  \draw [foo] (8) -- (4);
  \draw [foo] (8) -- (5);
  \draw [foo] (11) -- (8);
  \draw [foo] (9) -- (11);
  \draw [foo] (9) -- (10);
\end{tikzpicture}

\end{document}

図3

\documentclass[margin=0.5cm]{standalone}
\usepackage{tikz,newtxtext,newtxmath}
\usetikzlibrary{graphs,graphdrawing,calc}
\usegdlibrary{trees,force,circular}
\begin{document}

\begin{tikzpicture}[
    nodes={draw,fill=white,circle,minimum size=0.65cm,inner sep=0.1cm},
    foo/.style={-latex},
    lose/.style={fill=blue!70,text=white},
    win/.style={fill=red!70,text=white},
  ]
  \node (0) {};
  \node (1) at ($(0)+(60:1)$) {};
  \node (2) at ($(0)+(0:1)$) {};
  \node (3) at ($(1)+(0:1)$) {};
  \node[win] (4) at ($(3)+(30:1)$) {W};
  \node[win] (5) at ($(3)+(-30:1)$) {W};
  \node[lose] (6) at ($(4)+(90:1)$) {L};
  \node[lose] (7) at ($(5)+(-90:1)$) {L};
  \node (8) at ($(5)+(30:1)$) {};
  \node[win] (9) at ($(7)+(-90:1)$) {W};
  \node[lose] (10) at ($(9)+(-90:1)$) {L};
  \node (11) at ($(9)+cos(30)*(1,0)$) {};

  \draw [foo] (0) -- (1);
  \draw [foo] (1) -- (2);
  \draw [foo] (2) -- (0);
  \draw [foo] (2) -- (9);
  \draw [foo] (3) -- (1);
  \draw [foo] (4) -- (3);
  \draw [foo] (5) -- (3);
  \draw [foo] (4) -- (6);
  \draw [foo] (5) -- (7);
  \draw [foo] (8) -- (4);
  \draw [foo] (8) -- (5);
  \draw [foo] (11) -- (8);
  \draw [foo] (9) -- (11);
  \draw [foo] (9) -- (10);
\end{tikzpicture}

\end{document}

図4

\documentclass[margin=0.5cm]{standalone}
\usepackage{tikz,newtxtext,newtxmath}
\usetikzlibrary{graphs,graphdrawing,calc}
\usegdlibrary{trees,force,circular}
\begin{document}

\begin{tikzpicture}[
    nodes={draw,fill=white,circle,minimum size=0.65cm,inner sep=0.1cm},
    foo/.style={-latex},
    lose/.style={fill=blue!70,text=white},
    win/.style={fill=red!70,text=white},
  ]
  \node (0) {};
  \node (1) at ($(0)+(60:1)$) {};
  \node (2) at ($(0)+(0:1)$) {};
  \node (3) at ($(1)+(0:1)$) {};
  \node[win] (4) at ($(3)+(30:1)$) {W};
  \node[win] (5) at ($(3)+(-30:1)$) {W};
  \node[lose] (6) at ($(4)+(90:1)$) {L};
  \node[lose] (7) at ($(5)+(-90:1)$) {L};
  \node[lose] (8) at ($(5)+(30:1)$) {L};
  \node[win] (9) at ($(7)+(-90:1)$) {W};
  \node[lose] (10) at ($(9)+(-90:1)$) {L};
  \node (11) at ($(9)+cos(30)*(1,0)$) {};

  \draw [foo] (0) -- (1);
  \draw [foo] (1) -- (2);
  \draw [foo] (2) -- (0);
  \draw [foo] (2) -- (9);
  \draw [foo] (3) -- (1);
  \draw [foo] (4) -- (3);
  \draw [foo] (5) -- (3);
  \draw [foo] (4) -- (6);
  \draw [foo] (5) -- (7);
  \draw [foo] (8) -- (4);
  \draw [foo] (8) -- (5);
  \draw [foo] (11) -- (8);
  \draw [foo] (9) -- (11);
  \draw [foo] (9) -- (10);
\end{tikzpicture}

\end{document}

図5

\documentclass[margin=0.5cm]{standalone}
\usepackage{tikz,newtxtext,newtxmath}
\usetikzlibrary{graphs,graphdrawing,calc}
\usegdlibrary{trees,force,circular}
\begin{document}

\begin{tikzpicture}[
    nodes={draw,fill=white,circle,minimum size=0.65cm,inner sep=0.1cm},
    foo/.style={-latex},
    lose/.style={fill=blue!70,text=white},
    win/.style={fill=red!70,text=white},
  ]
  \node (0) {};
  \node (1) at ($(0)+(60:1)$) {};
  \node (2) at ($(0)+(0:1)$) {};
  \node (3) at ($(1)+(0:1)$) {};
  \node[win] (4) at ($(3)+(30:1)$) {W};
  \node[win] (5) at ($(3)+(-30:1)$) {W};
  \node[lose] (6) at ($(4)+(90:1)$) {L};
  \node[lose] (7) at ($(5)+(-90:1)$) {L};
  \node[lose] (8) at ($(5)+(30:1)$) {L};
  \node[win] (9) at ($(7)+(-90:1)$) {W};
  \node[lose] (10) at ($(9)+(-90:1)$) {L};
  \node[win] (11) at ($(9)+cos(30)*(1,0)$) {W};

  \draw [foo] (0) -- (1);
  \draw [foo] (1) -- (2);
  \draw [foo] (2) -- (0);
  \draw [foo] (2) -- (9);
  \draw [foo] (3) -- (1);
  \draw [foo] (4) -- (3);
  \draw [foo] (5) -- (3);
  \draw [foo] (4) -- (6);
  \draw [foo] (5) -- (7);
  \draw [foo] (8) -- (4);
  \draw [foo] (8) -- (5);
  \draw [foo] (11) -- (8);
  \draw [foo] (9) -- (11);
  \draw [foo] (9) -- (10);
\end{tikzpicture}

\end{document}

感想

後退解析という名前がしっくりこない。node 内の文字サイズによって頂点サイズが変わるの不便だと感じてたけど、inner sep=0 にして minimum size を設定すると綺麗になりそうだということが判明した。気が向いたら直す。