LOG IN

マンカラを知ったのでコードを書いてみた

by らきいば

この記事はAFTAC2019、13日目の記事です。AFTACについては藤岡さんのブログを参照してください。

1. きっかけ

こんにちは。「マンカラ」ってご存知ですか?

実は、こう言っている僕も最近知りました。Youtubeでこの動画を見たのです。

世界最古のボードゲームが超簡単なのに奥が深い!!【紀元前アフリカのボドゲ】https://youtu.be/OL3m2ZbKb1o

(動画では最初の2分30秒くらいでルール解説を行っています)

さらに調べるとWikipediaにも記事がありました。

(この記事はこの後、マンカラのルールを知っているものとして、書いていきますので是非動画かWikipediaでルールの確認をお願いします)

一般的には、自陣が6マスで行うことが多いようですが、最初に紹介したクイズノックのローカルルール(動画)では「自陣3マス×1マス3つ」で行っています。

そしてこれを見た僕は思ったんです。

「これぐらいだったら、コンピューターで解析できるんじゃね?」

マンカラは、Wikipediaにもあるように二人零和有限確定完全情報ゲームです。つまり、すべての手を解析すれば、「先手必勝」「後手必勝」「引き分け」のいずれかがはっきりと分かる、ということです。(ただしこのマンカラには「引き分け」が存在しないので「引き分け」となることはありません)

2. 理論

思ったからには、コードが書きたくなってくるというのが性です。ということでやっつけ仕事で2日くらいで書きました。言語はおなじみJavaです。

やっつけ仕事なので、かなりいい加減でデバッグ用に使っていたコードがコメントアウトした状態で散乱しています。ほんとうに見にくくてごめんなさい。

ところで、この記事の名前は「マンカラを知ったのでコードを書いてみた」であって、「マンカラの必勝法を調べてみた」ではありません。実のところ、このコードはマンカラの全手筋の樹形図を描くためのものであって、最善手を打ち合えばどちらが勝つのかを調べるものではありません。

このコードを書くにあたって、色々と考えるうちに見つけた、マンカラの重要な真理をお伝えします。それは「任意の盤面はそれ以前に同一盤面が現れることはない」です。なぜなら、相手と自分の陣地にあるコマの合計は、一つ前のターンと比べて同じか少ないかのどちらかにしかなり得ないからです。

この重大な真理に気づかず、力任せで全数検索すると時間がかなり掛かってしまいます。(僕は早々に気がついたのでどれくらい時間がかかるかは計測していません)単純計算では端の部分も含めて8マスがあり、区別のないコマ18個を並べ替える方法は8^18で1京8000兆通りぐらいあります。(片方の端のマスに18個全部が集まるという場面など多くのゲームとして成立していない場面が含まれているので実際にはかなり少ないです。)ということで、盤面をスタック(保存)しておき、同じ盤面が現れたら、それ以降の計算を行わないという方式でコードを書きました。イメージ的にはこんな感じです。(ペイントの5分クオリティなので、雑なのは気にすると負け)この場合、右から順に捜査していくので、盤面Aから盤面Cをまず走査し、その下の盤面E,Fをすでに走査しているので、その後出てきた同一盤面では計算をストップしています。

3. 実装

※この節はがっつりプログラムの内容です。興味のない方は、4へお進みください。

前出のソースコードの画像を見てください。tglクラスは盤面自体を保持するクラスで、コンストラクタ実行時に初期化されます。

viwe(viewのタイポ)はint型の配列で8つの要素を持ち、例えば [1, 2, 0, 4, 2, 1, 4, 4] のように表されます。この場合、プレイヤー1の自陣が左から順に1個、2個、0個のコマを持っており、プレイヤー2は左から2個、1個、4個のコマを持っていることを示しています。

int型のlinkはほとんど使いませんでしたが、自分のインスタンスの一手前の盤面のID(uniqe_id:uniqueのタイポ)を保持しています。そしてこのIDはall_viweの添字と一致しているため、容易に前方へたどることが出来ます。

ArrayList<tgl>型のall_viweは作成された盤面の一覧を静的に保持しています。今回のtglクラスでは、インスタンスの引数となる盤面はすでにall_viweにないかチェックされたものとして動きます。というよりも、tglクラスはそもそも手動でインスタンスを作成することをほとんど想定していません。

これがope (Operation) メソッドです。tglクラスのメンバで現在の盤面から引数に与えられたマスを操作しようとするとどうなるのかを実行するメソッドです。現在の番ではないプレイヤーのコマを動かそうとしたり、範囲外のコマを動かそうとしたり、コマを動かした後の盤面がall_viweにすでに存在していたりすると、nullを、そうでなければ動かした後の新しいtglインスタンスを返します。

また、tglクラスのメンバにnextメソッドも存在します。これは単純に、次の手番の人が実行可能な手を配列で返すメソッドです。この2つのメソッドから分かるように、初期盤面さえ、tglクラスのコンストラクタに渡してしまえば、あとはnext()とope(int g)を交互に呼び出すだけで面倒な処理(次のプレイヤーだとかIDの処理だとか)をすべてしてくれるのです。

このプログラムを組むにあたってつまずいたのは、

ということです。もちろん、どれもよくよく考えれば当たり前なのですが、そういうところでつまずいてしまいました。(どれもすぐ気づき、修正できましたが。)

4. 結果

調査盤面数は18847盤面でうち972盤面がゲーム終了盤面でした。つまり、1京8000兆盤面ぐらいあると思われていた盤面は、実際には18847通りしかなかったことが分かりました。

この画像は、ゲーム終了盤面を一覧として表示した画像です。(ファイル名はresultのタイポ)この972盤面を数えてみた(もちろんJavaで)ところ、後手勝利盤面が先手勝利盤面より20盤面多かったことが分かりました。ただ、探索盤面が一部カットされているので、実際にどちらが有利なのかは不明です。

またこの画像は、解析中の組み合わせを表示したものです。

「----end----」とあるのは、その盤面でゲーム終了したことを、「----next----」とあるのは同じ盤面が以前探索したところにあり(初めてみた盤面ではない)、それ以上の走査はせず、次に行くことを示しています。

ただし、同一盤面を含めると(つまり全数検索すると)この何倍にも膨れ上がることが分かっています。

最後になりましたが、マンカラは最善手を打ち続けると、どちらが勝つのか、だれか調べてください!(他力本願)

追伸

タイポ、多すぎじゃね?

OTHER SNAPS