世界最古のボードゲーム『マンカラ』で後手の必勝法を見つける

マンカラとは

世界最古のボードゲームらしいです。

自分は知らなかったのですが、QuizKnockの動画で見て知りました。

動画内での説明によると、世界中で遊ばれているらしくマイナールールがたくさんあるようです。
今回は動画で用いていたルールに準拠して話していきます。

ざっくりルールの説明:

• 各プレイヤーは自分の枠を3つ持っていて、最初各枠に3つずつ駒が置かれている
• 各プレイヤーは自分のターンに、自分の枠を1つ選び、枠に含まれるコマを反時計回りに1つずつ移動させる
  • 3個駒があれば、1つ隣の枠に1つ、2つ隣の枠に1つ、というように移動する
• 移動したコマのうち一番遠くに移動したコマがプレイヤーの枠の間にある誰にも属していない枠に入った場合、もう一度行動できる
• 自分の枠から全てコマを無くしたら勝ち

こちらの記事が分かりやすいです。(自分の枠が6個、コマは4個となっていますが大体同じです)

どうやら先手必勝らしい

QuizKnockの動画をみると、どうやら先手必勝であることがわかっているようです。
上の動画ではなく、別の動画で、min max法を実装して探索して最善手を指し続けるプログラムを作られていました。

というわけで、この記事では、

• 先手必勝であることを確認するため再実装してみる
• 他のパラメータを調整することで後手が必勝になる設定を探す

ということにチャレンジしてみたいと思います！

Pythonでの実装

min max法についてはたくさん記事がありますし、元動画内でも概要が説明されているので省略します。

min max法で探索している部分のコードはこちら：

from board import Board


def search_with_min_max(player_id: int, board: Board) -> Dict[str, int]:
    dp = {}
    original_player_id = player_id

    def _evaluate(player_id: int, board: Board) -> Dict[str, int]:
        value = dp.get("|".join([str(i) for i in board.data]) + f"_{player_id}")
        if value is not None:
            return value

        candidates = board.get_players_movable_grids(player_id=player_id)
        eval_tables = {}
        result = None
        for action in candidates.keys():
            tmp_board = deepcopy(board)
            act_again = tmp_board.move(action)
            if tmp_board.does_player_win(player_id=player_id):
                if player_id == original_player_id:
                    result = {"action": action, "value": 1}
                else:
                    result = {"action": action, "value": -1}
                break

            new_player_id = player_id if act_again else (player_id + 1) % board.players_num

            eval_tables[action] = _evaluate(player_id=new_player_id, board=tmp_board)["value"]

        if result is None:
            if player_id == original_player_id:
                best_action = max(eval_tables, key=eval_tables.get)
            else:
                best_action = min(eval_tables, key=eval_tables.get)

            result = {"action": best_action, "value": eval_tables[best_action]}

        dp["|".join([str(i) for i in board.data]) + f"_{player_id}"] = result
        return result

    return _evaluate(player_id=player_id, board=board)

行動順のplayerと盤面、呼び出し元のplayerを受け取り、再起的に評価値を計算しています。

盤面とplayerから次に実行できる行動をリストアップし、それぞれの行動を実施した際に遷移する盤面の評価値を計算し、行動したplayerが呼び出し元のplayerと一致しているかどうかでminかmaxのどちらかの基準で行動するようにしています。

(もっと綺麗な書き方はあると思うのですが、今回はこれで...)

愚直に再起だけで書いたところ遅くて計算が返って来なくなってしまったので、一度計算した盤面とPlayerの組に対しては評価値とその時の行動をメモしておくようにしています。これにより、ある程度の規模であれば計算できるようになりました。

シミュレーションには他にもBoardクラスやPlayerクラス、Gameクラスも実装しています。
興味がある方はこちらを参照ください。

CLIですが、今回実装したmin max法のアルゴリズムと対戦できるようにもなっています。(自分が後手だとちゃんと勝てないし、自分が先手でも最善手を打たないとすぐひっくり返される)

from player import Human, MinMaxPlayer
game = Game(player_classes=[MinMaxPlayer, Human])
winner = game.run()

ほんとに先手必勝だった

まずはQuizKnockの動画で使われていた設定で計算して、本当に先手が必勝なのかを確認します。

動画内では、枠の個数は3つずつ、枠の中にあるコマは3つずつ、Player間の枠(ゴールと呼ばれる？)は1つ、の設定だったので、次のコードで試すことができます。

board = Board(grids_per_player=3, init_pieces_per_grid=3, grids_between_players=1)
print(search_with_min_max(player_id=0, board=board))

#=> {'action': 0, 'value': 1}

となり、初期状態の先手の評価値は1で必勝でした。動画での結論通りですね。
ちなみに最善手はindex=0の枠を選択する、と算出されていました。

後手を必勝にしたい

このように、QuizKnockで使用されていた設定でシミュレートすると、動画内でも述べられていた通り、先手に必ず勝利できる最善手が存在することが自分のコードでも確認することができました。

ここからが本番です。
どうにかして後手が必勝になるような設定を見つけたいです。

今回変更した条件は以下：

• Playerに属する枠の数(default=3)
• 枠一つあたりの初期配置のコマの数 (default=3)
• どのPlayerにも属さない枠の数 (default=1)

Playerの数も変えてみたかったのですが、MinMax法を用いた探索が帰ってこなくなってしまったので断念しました。もう少し工夫すれば現実的な時間内に計算できるのかも？

Playerに属する枠の数

デフォルトは3つずつ各プレイヤーの枠があります。これを増やしたり減らしたりすることで先手有利が変わるのかを見てみました。

(枠の数を4つ以上にすると木が大きくなってしまって計算が返って来なくなってしまったので、1,2に減らしてみました)

結果は3個の時と変わらず、先手が必勝のままでした。

{'action': 0, 'value': 1} # 1個の時
{'action': 0, 'value': 1} # 2個の時

どちらの場合も初手は一番小さい枠のコマを動かすのも枠が3個の時と同じでした。

枠一つあたりの初期配置のコマの数

次は、枠に最初に置かれているコマの個数を3個から変えてみました。

1,2,3,4,5,6個の場合を試したところ、全て先手必勝のままでした。
段々と計算が重くなるので、この辺りでやめましたが、このままずっと先手必勝のままなんですかね...?

ちなみにその際の最善手は個数によって変動がありました。

{'action': 0, 'value': 1} # 1個
{'action': 0, 'value': 1} # 2個
{'action': 0, 'value': 1} # 3個
{'action': 0, 'value': 1} # 4個
{'action': 2, 'value': 1} # 5個
{'action': 1, 'value': 1} # 6個

5個と6個の時に最善手が一番小さい枠ではなくなっています。

5個の時にindex=2を選択すると、index=3,4,5,6,7に駒が移動し、index=7はPlayerに属していない枠でもう一度行動できます。

6個の時もindex=1を選択すると、index=2,3,4,5,6,7に駒が移動し、同様にもう一度行動ができます。
再行動できる行動を優先しているのでしょうか。

必ずしもそうではないようで、例えば駒が1個の時はindex=2を動かせばindex=3に移動し、再行動できるはずですが最善手はindex=0となっています。そこまで簡単な話でもないようです。

どのPlayerにも属さない枠の数

最後に、PlayerとPlayerの間にある枠の数を1個から増やしてみました。
直感的にはこの枠が増えると再行動しやすくなりそうです。

結果は、なんと2個の時だけ後手必勝になり、それ以外の設定だと先手必勝のままでした。

3個以上の時は考えてみると当然で、自分のどの枠を選んでも再行動できるので、3回自分のターンが連続できて、先手が勝ってしまいますね。

残る枠が2個の時だけこの戦法は使えない(index=0,1は再行動できるが2の時だけはみ出してしまうため)ので、後手に勝ち筋があるわけですが、なんとこの記事中で初めて後手に必勝法が存在するケースとなっていました。

2個の時の最善手はこちら：

Turn 1
[3, 3, 3]
[0, 0]
[3, 3, 3]
[0, 0]

Player 0
Action 0
Action 1
[0, 0, 5]
[2, 1]
[4, 3, 3]
[0, 0]

Player 1
Action 5
Action 6

Turn 2
[1, 0, 5]
[2, 1]
[0, 0, 5]
[2, 2]

Player 0
Action 0
[0, 1, 5]
[2, 1]
[0, 0, 5]
[2, 2]

Player 1
Action 7
Player 1 wins!
[1, 2, 6]
[2, 1]
[0, 0, 0]
[3, 3]

おわりに

マンカラを遊んでいて、後手になってしまったがどうしても勝ちたい！そんな時は、「Playerに属していない間の枠の数、2個にしない？」と言ってみましょう！後手必勝になります！ (ただし後手の場合の最善手を覚えている必要があります)

最後までお読みいただきありがとうございました！

Future work

• 高速化して他の条件でも動かしてみる
• 2つの条件を同時に動かすことで他にも後手必勝のパターンを探す

今回は他の条件は固定して、一つだけ設定を変えるという方法で実験しましたが、
例えばコマの数と枠の数を同時に変えたりした際に後手が必勝になる可能性もあるので、そこを調べてみるのも面白そうですね。