先手必勝AIと自作AIとのマンカラ対戦
ブログ内トップの関心事
以前「マンカラは先手必勝？後手必勝？」という記事を書いてからは、当ブログに流入してくる検索ワードはずっとマンカラに関するものが一番多いです。「マンカラ 完全解析」とか「マンカラ 先手必勝」とかで検索すると未だに前述の記事が検索上位に表示されます。
ブログもアプリも永らく放置していたのですが、googleにアプリの更新を催促されたのを機会に、久しぶりにマンカラに関して試したことを記事に書いてみようと思います。
マンカラのノード数は？
マンカラの全ノードをメモリーに持つことが出来れば、以前の記事で三目並べでやったようにモンテカルロ法を使って先手必勝か後手必勝が証明できるし、全ノードを保持出来なくても工夫すれば序盤の定石データの作成等何か出来るかもと思いノード数を数えてみることにしました。
やったことは以前「BFSで将棋パズルを解く」に書いたのと同じ方法です。全ての指し手を一手ずつ進めて重複局面を省きながらゲーム木を作る方法なので概算ではなく正確なノード数が求まるはずです。
プログラムはDartで作ったのですが、まずは豆１つのケースで試したら数秒でノード数は1,182,341ノード（重複局面削除済み）と判明しましたが、豆２つでやってみると一日待ってOut of Memoryが出てプログラムが終了してしまいました
おかしいなと思いpsensorでメモリー使用状況を確認したのが以下の画像です。
以前の記事「マンカラは先手必勝？後手必勝？」を書いたときよりPCはハイスペックになっていて、今は128GBのメモリを積んでいるのですが、理由は分かりませんが、どうやらDartでは64GB以上のメモリーを使ってくれないようですガベージコレクションが関係しているのでしょうか？兎に角こういうことをやるのにはDart(Version3.1.2)は向いてませんね。仕方なくC++で書き直して試してみると、
それでも１５分ほどで搭載されているメモリーすべて使い切って、重複局面は排除したのですがノード数を数え切れませんでした
マンカラの完全解析は意外と手強いです。作成したNodeクラスは後にプログラムで使用するつもりの余計な要素も含まれているのですが、sizeofで確認すると１つのNodeオブジェクトは88バイトだったので、128GBで足りないとなると128GB / 88Bで15億ノード以上あるということでしょうか？しかも豆２つでこの状況ですから三目並べと同様のアプローチは無理ですね
ChatGPTに聞いてみる
無料版のChatGPT(GPT3.5)に「マンカラカラハは先手必勝のゲームと証明されていますか？」と聞いてみたところ以下の回答でした。
マンカラ（またはカラハ）が「先手必勝」であるという一般的な証拠や公式な証明は存在しません。このゲームは非常に複雑で、初期配置やプレイヤーのスキルに依存するため、先手と後手の優劣は局面や戦術によって変化します。
マンカラは多くのバリエーションが存在し、さまざまなルールでプレイされることもあるため、先手必勝かどうかについて一般的な結論を出すことは難しいです。一部のバリエーションでは、特定の初期配置や戦術によって先手が有利になることがあるかもしれませんが、一般的なルールでのマンカラは均衡のゲームとされており、どちらが優勢であるかは状況に依存します。
したがって、特定の局面やルールにおいて先手必勝であるかどうかを証明するには、数学的な証拠や研究が必要です。一般的なマンカラゲームが先手必勝であるかどうかについての確かな証拠は提供されていないと言えます。
他にもいろいろ試しましたが、ChatGPTでは明確な回答は得られませんでした。
Wikipediaによると解決済みらしい
ネットを検索するとWikipediaのこの記事で先手必勝が確認されていると出てくるのですが、この記事がどういう理屈で先手必勝を証明しているのか自分にはよく理解できません
そこで同じ記事内の下の方に用意してあるWebゲームと自分のアプリを対戦させてみました。「先手必勝の理屈が分からない奴はこのWebゲームに後手で勝ってみろ！出来ないだろ？だから先手必勝の結論に間違いないんだよ！」という理屈のようですこのゲームの作者の意図はそういうものではないかもしれませんが、自分はそのように解釈しました
自分のアプリも豆６個に対応しているので、自分のアプリが後手で勝ったらおもしろいなぁなんて思いながら対戦させてみました。
結果は自分のアプリの負けでした、残念
このゲームで遊ぶときは左下ののボタンをクリックして、以下のようにチェックマークをOnにしないと同じルールにならない（Capture=横取りの動作が異なります）ので注意が必要です。Nintendo Switch『世界のアソビ大全51』のマンカラソフトもこれと同じルールです。
次に、アプリでは最強に設定しても１１手読みなので１５手読みに設定してPCで試してみたのが冒頭の動画です。
１５手読みにするとRyzen7 5700Gでも一手５分ぐらい掛かるのですが、それでもやはり勝てません。あと一個で引き分けという惜敗ですが、試しに自分の頭で考えてやってみるとゲームの最後までプレイ出来ずに途中で大差で負けます
このWebゲームは豆６個しか試せないようですが、Wikipediaに書いてある通り３個、４個、５個でもすべて先手必勝は間違いなさそうですね。
追記（2023-11-10）
ノード数を数える時に手番データを含めて重複局面を保存しないようにしていたのですが、手番データを含めずにノード数をカウントしたところ、豆２個でもカウント完了出来ました。先手番の局面か後手番の局面かを気にせずに豆の配置の違いだけを数えれば大幅にノード数は減りますが、データとしては使いにくいのであまり意味はありませんけど一応記しておきます。
- 豆１個のケース->647,826ノード
- 豆２個のケース->495,196,185ノード
豆の配置は同じだけど手番が違う局面というのがかなり存在するということみたいです。