セカンドベストは後手必勝だった

SecondBest プログラミング

こんにちは。
先日の記事でセカンドベストというボードゲームの局面数を数えました。その結果、気合を入れて解析していた Tokyo Doves よりもはるかに局面数が少なく、解析の難易度もさほど高くなさそうなことが分かりました。

ということで、解析するコードを書きました↓
github.com

とりあえず実行

上記のプログラムは以下の手順で実行できます。
1. Rust をインストールします。
www.rust-lang.org
2. 先ほど紹介した git リポジトリをクローンします。git がインストールされていてインターネットに接続されている端末であれば、以下のコマンドでクローンできるはずです。

git clone https://github.com/mat-der-D/second-best-analysis

3. リポジトリ直下のところで端末を開き、以下のコマンドを実行します。

cargo run --release

4. 必要な追加のパッケージのダウンロードとビルドののち、計算が開始します。私の手元の環境ではビルド完了から測って35秒ほどで計算が終了します。
5. 画面に以下のように表示されます。

The second player wins in 42 steps

つまり、42手で終わる後手必勝です。

簡単に解説

今回やったことは、ハトの解析でも行った後退解析です。後退解析そのものについては↓の記事でしっかりめに説明したので今回は省略します。
smooth-pudding.hatenablog.com

ハトの解析との違いは以下の3つです。

  • 自滅する手しかない局面が存在すること
  • 最善手ではなく二番目の手しか選べないこと
  • 局面数が極めて少ないこと

自滅する手しかない局面が存在すること

ハトでは、以下の記事で説明したように、その手で負けが確定するような手は回避することができました。
smooth-pudding.hatenablog.com
それにより、ある局面が勝敗が確定しているとすれば、奇数手で勝つか、偶数手で負けるかの二択でした。
一方セカンドベストでは、自分の石を動かしたことにより相手の石がそろってしまうような手しか選べない局面が存在します。
したがってハトの後退解析の記事で説明したように

Win1 → Lose2 → Win3 → Lose4 → ...

という一列とはならず、

Win0 → Lose1 → Win2 → Lose3 → ...
Lose0 → Win1 → Lose2 → Win3 → ...

という二つの列を同時に追いかけることになります。
ちなみにこの追いかける計算は、冒頭のリポジトリでは "analysis::analyze_backward" という関数で行っています。

最善手ではなく二番目の手しか選べないこと

これがこのゲームの最大の特徴ですね。ゲームの実装以上に、探索プログラム部分の実装の方に注意が必要なポイントになっています。
例えば Win1 に属するための条件は、普通のボードゲームであれば

ある手を選べば、即座に自分の勝利が確定する局面

となります。一方セカンドベストでは

それを選ぶと即座に自分の勝利が確定するような手が、少なくとも2つ存在するような局面

となります。この部分に混乱があり、何度かプログラムの書き直しが必要になりました。

局面数が極めて少ないこと

こちらは嬉しい性質です。前回の記事で、各局面を4 byte で集めたとして、全体で 32MB 程度にしかならないと述べました（実際それぐらいでした）。
そのため、ひとつのプログラムですべての局面を列挙した上で、何度もループを回すということが現実的な時間で実行可能になります。
実際、冒頭のプログラムでは最初に 8,363,027 通りの局面を全列挙した上で何度もぐるぐるループして解析しています。
ハトの解析を終わらせるのに、データの工夫や並列計算を駆使しても数カ月かかった*1ことを思えば、はるかに楽な状況でした。

感想

今回もボードはビット演算で表現したのですが、それ自身がとても面白かったです。石を置ける場所の数が "8" だったり、各場所にある石の個数が "0~3" だったりと、ビット演算で表現することを見越して設計したのかと勘違いするぐらいピッタリの数値で、とても気持ちよかったです。実装はすべて冒頭リポジトリで公開しているので、よければその部分も読んで面白みを感じ取ってみてください。
気が向いたら、また別の記事でもう少し必勝の手についても紹介しようと思います。
ではまた。

追記 (2023/12/23)

この記事を作者のダイキチさんにリプライでお伝えしたところ、返信をいただけました↓

  • 返信うれしい！！！！！！
  • ビット演算で設計しやすいのは勘違いではなかった！！！
  • 作者の解析結果と一致していた！！！
  • というか作者も解析してたんだすげぇ！！！

さらに追記 (2023/12/23)


「作者も解析していてその結果と一致していた」は早とちりだったみたいです。
とはいえ経験豊富な作者の方の感覚ともズレていないようなので、きっと大外しはしてないでしょう。たぶん。

*1:実は解析完了しています。まとめたらまた記事にします。