はじめに
Nintendo Switch向けソフト「世界のアソビ大全51」に格納されている「マンカラ」というボードゲームを遊んでみました。プレイする中で、どうすると勝てるのかが全く分からなかったので、盤面の状態をもとにどの手を選ぶのが最善なのかを推計するGUIツールを作成してみました。
「マンカラ」とは
ルールについては、以下、youtubeでの任天堂の動画やWikipediaを参照ください。
「マンカラ」には派生ルールがいろいろあるようですが、上記の「世界のアソビ大全51」で採用されているルールは「カラハ（Kalah）」ルールに基づいています。端的には、2人で6個×2列の穴にそれぞれ4個ずつ入っている48個の石を交互に選んで動かしていき、最終的に獲得できた石が多い方が勝ち、というものです。
ちなみに一緒にプレイした相手の家庭内ルールはカラハルールとは異なり、「先に自分の陣地の手を無くした方が勝ち」というルールになっているとか。
このゲームは、いわゆる「二人零和有限確定完全情報ゲーム」「アブストラクトゲーム」に分類されるゲームです。将棋、囲碁、リバーシや〇×ゲーム（Tic-Tac-Toe）も同様の分類であり、要するに「プレーヤーが2人で、全ての情報がお互いに明かされており、偶然の要素が入らないゲーム」ということになります。
情報が完全に公開されていて偶然の要素も無いことから、理論上は完全な先読みが可能です。つまり、このタイプのゲームは双方が最善手を指すこと前提とすると、先手必勝か後手必勝か引き分けかが決まっています。例えば、〇×ゲームは双方ベストを尽くせば必ず引き分けになります。
しかし、実際には選択肢が多くなると完全な先読みを人間が行う事は難しく、そのためゲームとして成立しているといえます。
先行する研究や記事等
Irvingらの研究によると、上記の6個×2列の穴にそれぞれ4個ずつ石が入っているケースでは、先手後手が双方最善手を指した場合「29vs19」で先手の勝ちとなるようです。(Geoffrey Irving, Jeroen Donkers and Jos Uiterwijk(2000).SOLVING KALAH.ICGA Journal)
ただ、上記のとおり実装するとなると、実行端末上にそれなりのストレージ容量が必要になります。
これは少々扱いにくいので、ある程度で探索を打ち切り、評価値をもとに最善手を返す仕組みを検討していたところ、@dsanno様が2020年7月にQiita上で記事を公開していていたので、こちらのロジックをベースとして搭載することとしました。
リンク：rustでマンカラ(ボードゲーム)の思考エンジンを作る
モジュール&ソース
モジュールおよびソースは、Github上で公開しています。
リポジトリ：https://github.com/kyosuke0924/Mancala
モジュールは上記リポジトリの「Release」ボードより「Mancala.zip」を取得してください。
リリース：https://github.com/kyosuke0924/Mancala/releases
稼働環境
以下の環境で動作します。
| 項目 | 要求スペック |
|---|---|
| OS | Windows 10 ver.1607以降(64bit版) |
| 必要なソフトウェア | .NET Framework v4.8 |
| 解像度 | 1280×720 以上 |
WindowsFormsを用いて開発しているため、LinuxやMacOSはサポートしていません。
「.NET Framework v4.8」については、OSWindows 10 May 2019 Update(バージョン 1903)以降を使用している場合は、プリインストールされているため、特段インストール作業は不要です。上記より古いバージョンの場合は、別途Microsoft社のダウンロードページよりダウンロードとインストールを実施してください。
開発環境
開発環境および稼働確認環境は以下の通りです。
| 項目 | スペック |
|---|---|
| OS | Windows 10 ver.20H2 (64bit版) |
| CPU | Intel(R) Core(TM) i7-3770 @ 3.40GHz（4コア8スレッド） |
| RAM | 16.0 GB |
| Storage | SSD 1TB |
| 解像度 | 1920×1080 |
| 開発言語 | C# |
| エディタ | VisualStudio 2019（Windowsフォームアプリケーション） |
もともと、@dsanno様はRustでロジックを書かれていました。
そのため、ロジック部分についてはRust部を流用し、画面から関数をInvokeすれば効率が良かったのですが、Rustの開発技術がなかったため、すべてC#で書き直しています。
処理の速度についてはRustよりC#の方が遅いので、同じ読み手の深さでも、もともとのロジックより少々時間がかかるようになってしまいました。
使用手順
インストーラはありません。
ダウンロードした「Mancala.zip」を任意の場所に解凍し、「Mancala.exe」を実行してください。
設定ファイル
「Mancala.exe.config」がアプリケーションの設定ファイルです。
設定項目は以下のとおりです。
| 項目 | 初期値 | 意味 |
|---|---|---|
| Depth | 12 | 候補手を探索する深さです。値が大きいほど先読みが深くなるため、正確な判定ができますが、処理に時間がかかります。 |
| EndingFileSeedNum | 10 | 後述する終盤データベースを作成する際のシードの数です。これも値が大きいほど、ゲーム終盤の判定が正確になりますが、作成に時間を要するようになり、かつ作成されるファイルの容量が大きくなります。 |
<setting name="Depth" serializeAs="String">
<value>12</value>
</setting>
<setting name="EndingFileSeedNum" serializeAs="String">
<value>10</value>
</setting>
特段、設定は不要ですが、処理時間に余裕があるようであれば、「Depth」の値を大きくすることでより正確な判定が可能です。
逆に処理に時間がかかるようであれば、値を小さくすることで処理時間を短くすることができます。（推計の精度は下がります）
変更する場合は、該当ノードのvalueタグ内の値を変更し、ファイルを上書き保存してください。
画面イメージ
（GIF）
機能について
盤面の各ボタンをクリックしていくと、最善と推計される手がハイライトされます。
画面には、あわせて各情報が表示されます。
候補
次手の候補と、各候補を選んだ場合の形勢を示します。
先手であれば形勢の値が最も大きくなる手、後手であれば形勢の値が最も小さくなる手を最善手としてハイライトします。
| 項目 | 意味 |
|---|---|
| 手 | 各手を意味します。各プレイヤーから見て左側から(1)⇒(6)となります。 |
| 形勢 | 各手を選んだ場合の盤面の評価値です。値が大きいほど先手有利、小さいほど後手有利となります。 |
形勢
初手からの形勢の推移を表す折れ線グラフです。値が大きいほど先手有利、小さいほど後手有利となります。
履歴
初手からの着手履歴、スコア、盤面の状態と形勢を表示します。
| 項目 | 意味 |
|---|---|
| 手番 | 着手が先手か後手かを示します。 |
| 手 | 各手を意味します。各プレイヤーから見て左側から(1)⇒(6)となります。 |
| 先手（後手）スコア | 先手（後手）が獲得した石の数を示します。ゲーム終了時にこの値が大きい方が勝利となります。 |
| 先手（後手）盤面 | 先手（後手）の盤面の状態を示します。各プレイヤーから見て左側から(1)⇒(6)となります。 |
| 形勢 | 各手を選んだ後の形勢を示します。 |
各ボタンの機能
各ボタンの機能は以下のとおりです。
| 項目 | 意味 |
|---|---|
| リセット | 盤面を初期状態に戻します。 |
| 一手戻す | 一手戻します。 |
| 盤面を反転する | 盤面を反転して後手から見た目線の盤面にします。再度クリックすると元に戻ります。 |
| endingファイルを表示 | 終盤データベースを表示します。 |
| endingファイルを作る | 終盤データベースを作成します。 |
| 終了 | アプリケーションを終了します。 |
最善手の推計の仕組み
アプリケーション設定ファイルのDepthに指定した手数分先読みを行い、自分は最も自分にとって状況がよくなる手を、相手は最も自分にとって都合の悪くなる手を指したと仮定した場合に、どの手を選ぶのが最良かに基づき判断しています。（ネガアルファ法）
先読みの末端では、盤面の状態が終局もしくは終盤データベース（各盤面から終局まで完全に読み切って求めた評価値のデータベース）に登録されている状態であれば確定している評価値を、そうでなければ石の配置から予測した推計値を評価値として返す仕組みです。
そのため、終盤に近づけば近づくほど、最善手の推計の精度は高くなります。
@dsanno 様のCUIツールとの違いについて
オリジナルのCUIツールとは、以下の違いがあります。
- 評価値の表示形式
オリジナルでは各手番から見た評価値をそのまま出力していますが、本ツールでは、先手から見た評価値を正、後手から見た評価値を負として示すようにしています。
- 全手の評価値の出力
オリジナルでは最善手のみ評価値を返す仕組みですが、本ツールでは、着手可能な全手の評価値を計算します。
- 探索のマルチスレッド化
全手の探索に伴い、各手の探索をマルチスレッド化しています。（そのためスレッド数が着手可能数以下のマシンでは、若干処理に時間がかかることが懸念されます）
- 終盤データベースの活用
オリジナルの公開モジュールでは終盤データベースについては実装されておりませんが、Github上のソースでは終盤データベースを活用したソースがコミットされていましたので、こちらをもとに実装しています。
- クラス設計
C#での処理を高速化するため、クラス設計を大幅に見直しリファクタリングしています。
また他にも処理速度を向上されるため、関数等に様々な手を入れています。（例えばStackに格納する前に着手可能かどうかを判定して不要なPush,Popを減らす、オブジェクトコピー量を減らすため、不必要なメンバーや要素を持たせない等）
おわりに
元記事にもありますが、探索において各盤面と評価値をメモ化することで探索の時間を減らすことができるため、今後この部分は時間があれば実装していきたいと考えています。（メモリ消費量は多くなりますが）
あとは、ツールを使って実験した結果、
- 自分がピッタリゴールできるときは、その手を選択する。
- 多く石があるポケットが横取りされる場合、防ぐ手を選択する。
- 相手の石の横取りができる場合は、その手を選択する。
- 相手の陣地に渡る石の数を少なくなる手を選択する。（そのため、極力右のポケットから選択する）
の優先順位でムーブをしていくと、勝率が高い気がします。