こんにちは。前回の記事↓では、後退解析の結果を深堀してみました。
smooth-pudding.hatenablog.com
この記事の中で、両者が最適戦略を取った場合の局面のバリエーションを数えました。今回は、この最適戦略のルートを可視化してみます。
なお今回の記事は以下のアドベントカレンダーに参加しています。
adventar.org
可視化の方針
前回の記事で書いた表の一部を抜粋します。
| 初期からの手数 | 局面数 |
| 0~8 | 1 |
| 9~11 | 2 |
| 12, 13 | 3 |
この表では各手数での局面の数しか分からないですが、実際にはどの局面からどの局面になるのかという対応関係があります。これを可視化してみることを考えます。
前回の記事の最後には8手までの進行を紹介しましたが、これは 0~8 の各局面が順番に矢印でつながっているという風に表現できそうです。例えば以下のような感じです。
記号は X{何手目か}_{同じ手数の0から始まる通し番号} という風にしてみました。
次に8手目から9手目に移る際は局面数が増えているので、次善手が2通りあることが分かります。この場合は、X8_0 から矢印をふたつ伸ばして X9_0, X9_1 につなげればよさそうです。同じ考え方で11手目までグラフにしてみるとこんな感じなります。
12, 13 手目に進むところも同様です。以下のような図になります。
どうやら11手目の一方が2つに分岐したようですね。
可視化
この方法で、42手までをすべてグラフにしてみたのがこちら・・・と言いたいところですが、局面数が多すぎて見切れないサイズになってしまうので、35手までの範囲でグラフにしたものを作りました。
これでもだいぶでかいですね。
このグラフをじ～っと眺めていると、途中で長い一本道があることに気づきました。
そこでこの一本道に入るところ以外の道を切って、もう少し先まで追いかけてみましょう。40手目まで出すとこんな感じになりました。
どうやら一本道だったのは35手目までで、36手目以降はどんどん分岐が進んでいるようでした。
Graphviz と DOT 言語
さて、今回の可視化は Graphviz というツールを使いました。
graphviz.org
Graphviz は DOT 言語と呼ばれる形式で書かれた .dot ファイルを画像ファイルに変換してくれるツールです。
DOT 言語はグラフを記述するための形式で、かなり自由度があります。今回の0~13手目のグラフは、DOT言語で以下のように書いたものです。
digraph besttree {
X10_1 -> X11_0;
X6_0 -> X7_0;
X10_0 -> X11_1;
X5_0 -> X6_0;
X7_0 -> X8_0;
X8_0 -> X9_0;
X4_0 -> X5_0;
X12_0 -> X13_0;
X11_1 -> X12_0;
X11_0 -> X12_2;
X12_1 -> X13_2;
X1_0 -> X2_0;
X9_0 -> X10_0;
X0_0 -> X1_0;
X3_0 -> X4_0;
X9_1 -> X10_1;
X11_1 -> X12_1;
X12_2 -> X13_1;
X2_0 -> X3_0;
X8_0 -> X9_1;
}今回は書き出す順番を気にせずプログラムで自動生成したのですが、結果のグラフはいい感じに整形されていたので、Graphviz が結構内部で頑張ってくれているのかなと思っています。
今回のグラフはシンプルなものでしたが、フローチャートを作ったり、部分的に色を塗ったりと、かなりいろいろなことができるようです。グラフを作ってみることに興味がでた方は、Graphviz や DOT言語というキーワードでぜひ検索してみてください。
おまけ
長い一本道に入った最初の局面は画像の通りです（先手黒手番）。さて、黒手番が次に選ぶべき次善手は何でしょうか？
