最古のボードゲームらしい

　世界最古のボードゲームらしいのですが、存在自体知りませんでした。早速アプリをダウンロードして遊んでみたところ、何回か遊んでいるうちに勝つためのコツというのが少しずつ見えてきて楽しめましたが、それよりもこの単純なルールならすぐに人間に負けないＡＩが作れるんじゃないか？と思い試してみることにしました。

派生のルールがいろいろあるらしい

　Wikipediaによるといろいろな遊び方があるようですが、たまたまダウンロードしたアプリは「ベーシック」と「カラハ」という２つのルールで遊べるもので、ベーシックをやってみてすごく単純なルールに興味を持ったのですが、最初にカラハのルールで遊んでいたら面倒そうなので自分でプログラムを作ってみようなんて思わなかったかも知れません¹。
　先手必勝か後手必勝かを調べる方法は、以前の記事で３手前に打った駒が消える特殊なルールの三目並べを例にして紹介したように、MIN-MAX法（+αβ法）で先読みの深さを徐々に深くしていって（反復深化）、お互い最善手を尽くしても先手が勝つ（先手必勝）のかあるいは後手が勝つ（後手必勝）のかを確認するやり方です。

マンカラベーシックのルール

　普通は６×２列×石４つで行うゲームですが、それだと先読みの際にまたスタックオーバーフローに見舞われるだろうと思い、取り敢えず３×２列で検証することにしました。下図は石が３つの場合です。

　先手と後手が自分の穴のどれかを選んで全ての石を取り出し、矢印のように反時計回りに一つずつ石を撒いていく動作を先手後手交互に繰り返して、先に自分の穴の石が全てなくなれば勝ちです。自分か相手のストアで石を撒き終わった場合はもう一度自分の手番になります。

　※マンカライージーに関する記事も追加しました。

Dartで実装

　今リリースしている自分の将棋関連アプリの中で一番利用されている５五将棋アプリをFlutterで作り直そうかと思って、慣れるためにプログラミング言語はDartにしました。
　石の数は３つの場合List board = [0,3,3,3,0,3,3,3];のようにリストを作ります。添字の0と4がストアになります。カラハのルールだと相手のストアには石を撒かないそうですが、ベーシックのルールだと相手のストアにも石を撒くので、このリストをシーケンシャルに処理していけばいいだけなので処理が単純です。またカラハのように自分の空の穴で石を撒き終わった時に相手の石を取る（capture）ことが出来るというルールもありません。

void main() {
  final List board = [0,3,3,3,0,3,3,3];
  List result = new List();
  Player first = new Player(FIRST);
  Player second = new Player(SECOND);
  print(board);
  Stopwatch watch = new Stopwatch();
  watch.start();
  // result = first.think(board, second, 50, FIRST_WIN);
  // result = second.think(board, first, 50, SECOND_WIN);
  for (var i = 1; i < 50; i++){
    print("i = ${i}");
    result = first.think(board, second, i, FIRST_WIN);
    if (result[0] == FIRST_WIN || result[1] == SECOND_WIN){
      print("=== result = ${result[0]}, ${result[1]}, i = ${i}");
      break;
    }
  }
  print(watch.elapsedMilliseconds);
  print(result);

}

　一手読みから５０手読みまで反復深化で徐々に読みを深くしていって、先手勝ち（999）の評価値が返ってきたら先手必勝、後手勝ち（-999）の評価値が返ってきたら後手必勝となります。この辺りの話は以前の記事を読んでみてください。

  //評価関数
  int evaluate(List board){
    int first = 0;
    int second = 0;
    first = board.getRange(FIRST_START, FIRST_GOAL).where((value) => value == 0).length;
    second = board.getRange(SECOND_START, DENTS).where((value) => value == 0).length;
    if (first == WIN_COUNT && second == WIN_COUNT){
      print("=============== Error =============================");
      return DRAW;
    } else if (first == WIN_COUNT){
      return FIRST_WIN;
    } else if (second == WIN_COUNT){
      return SECOND_WIN;
    } else {
      return (first - second);
    }
  }

　評価関数は先手勝ち（999）か後手勝ち（-999）、それ以外は(先手の空になっている穴の数 - 後手の空になっている穴の数)にしていますが、return 0でもいいと思います。形勢判断の評価関数として(先手の空になっている穴の数 - 後手の空になっている穴の数)というのはかなり雑ですが、読み切ってしまうことが目的なので適当で構いません。

結果

　石の数を１〜９個にして、５０手先読みしたそれぞれの結果です。

３×２列（ベーシック）（2020-10-28一部訂正）

※先読み関数の外側のループで手数をカウントしてるため、手数は若干不正確です²。

　先読みメソッドの戻り値は（評価値,指し手）となっていて、評価値に最大値（999）が返ってきたら先手必勝、最小値（-999）が返ってきたら後手必勝です。石の数４個の場合、先手が初手にリストの2の位置を選べば先手必勝であることを表しています。石の数７個の時は後手必勝となりました。指し手に3が返ってきているのは、取り敢えず最善手として3を選んだという意味で、深い意味はありません。先手は勝てないことが分かったけど取り敢えず最善手として3を選んだということです。

検証１（石が１個の時）

　取り敢えず石の数１個の時のケースを確認しましょう。先手が初手に1の場所を選んで石を撒いた直後の状態は以下のようになります。

　後手はこの次にどこを選んでも（以下の図は5を選んだ場合）、先手は3を選べば自分のストアに石を撒き終わるので次も先手の番です。その結果、３手連続で着手することが出来るので以下のように遷移して先手が勝てます。

　先手が一手指した後の状態から、後手の立場で先読みしてみます。

final List board = [0,0,2,1,0,1,1,1];
result = second.think(board, first, 50, SECOND_WIN);

　戻り値は[999, 7]となって後手は7を選ぶけど、先手必勝（999）の結論は変わりません。
　後手は２手目にどこを選んでも負けるのですが、２手目は7を選んだ方が上で紹介した評価関数に従って有利と判定されるので7が最善手となります。初手からの遷移を省略せずに書くと以下のようになります。

　都合７手で先手勝ちなのですが、最後に先手が連続で着手出来るので５手読みで先手必勝と分かります。

[0, 1, 1, 1, 0, 1, 1, 1]
i = 1
i = 2
i = 3
i = 4
=== result = 999, 1, i = 4
6
[999, 1]

　main関数の出力もi = 4（５手読み）で先手が勝つと表示されます。

検証２（石が４個の時）

　石の数が１の場合は簡単に検証できましたが、石の数が２個以上の場合は何十手もかかるので、目で追うだけで検証するのは大変です。簡単にみていきます。
　石の数が４個の場合は2の位置を選べば３８手で先手必勝と表示されます。先手が2の位置を選んで石を撒いたら以下の状態になります。

　この状態から後手の手番で先読みしてみましょう。

final List board = [0,4,0,5,1,5,5,4];
result = second.think(board, first, 50, SECOND_WIN);

　戻り値は[999, 7]となって先手必勝（999）の結論は変わりません。
　今度は初期状態から先手（下側）と後手（上側）の順番を入れ替えて、本来の後手（上側）から先読みしてみると

final List board = [0,4,4,4,0,4,4,4];
result = second.think(board, first, 50, SECOND_WIN);

　戻り値は[-999, 6]となって2の対称の位置にある6を選べば本来の後手（上側）が必勝と判定されます。上下対象の配置なので当然こうなるべきで、これも一応プログラムは正しく動いてそうです。

６×２ではどうなのか

　３×２列のマンカラでなく、通常の６×２列で石の数が４個のマンカラではどうなのか調べたいと思い、まず石１個でやってみました。

final List board = [0,1,1,1,1,1,1,0,1,1,1,1,1,1];
result = second.think(board, first, 50, SECOND_WIN);

　結果は[999, 1]となって先手が初手に1の場所を選べば先手必勝のようです。
　ただ、石２個、３個、４個で試すと循環する手順があるのか、丸一日動かしていても結果が返って来ませんでした。まだ原因がはっきり分かっていませんが、循環する手順があるとしてもそこに入り込む必要なく必勝手順を辿ることが出来たということなので、必勝の結論を返してきた分に関しては間違いないと思います³。バグがなければの話ですが…。
　ベーシックのルール特有のケースかもしれないので、先にカラハのルールを実装して試してみようかなどと考えていますが、いずれにしても読み切るには結構時間が掛かるので、三目並べのように絶対人間に負けないプログラムを作るのは思っていたほど簡単ではないようです。
　カラハのルールだと自分の空の穴で撒き終わった場合に相手の石を取ることが出来るというルールがあるので、ベーシックのルールより早くゲームを終わらせる必勝手順があるような気がしていますが、どうなるか分かりません。

マンカラカラハの結果（2020-06-17追記）

　マンカラカラハのルールに対応したので結果を載せておきます。カラハでは自分の穴の石が無くなったら勝ちではなく、先手・後手どちらかの全ての穴が空になったらゲーム終了して残った石は自分のストアに戻し、その時点でのストアに溜まった石の数で勝敗を決めるので、評価関数は先手のストア内の石の数 - 後手のストア内の石の数です。マンカラベーシックのルールに較べて短手数での必勝手順が存在するのは、やはり相手の石を取ることが出来るルールによるものでしょう。

３×２列（カラハ）（2020-10-28一部訂正）

検証（３×２カラハ）

　ベーシック同様簡単に検証してみます。
　例えば石１個の場合、以下のようにベーシックの例と同じようにゲームが進行したとします。

　カラハのルールでも先手・後手どちらかの石が無くなればゲーム終了しますが、最後に残りの石を自分のストアに戻すことになりますので、先に先手の石が空になってもこの進行だと３対３の引き分けになり、当然ですがベーシックとは違う結果になります。
　次に石６個のケースを見てみると、戻り値は[-999, 3]となっていますが、この場合ベーシックの時にも説明したように先手が3を選んだことには深い意味はありません。先手がどこを選んでも負ける（評価値-999）けど最善手として3を選んだというだけの話です。では後手の初手は何が最善手なのか見ていきます。
　石６個で先手が初手に1を選んだ直後の状態は以下のようになります。

　この状態から後手の手番で先読みすると

final List board = [0,0,7,7,1,7,7,7];
result = second.think(board, first, 50, SECOND_WIN);

　結果は[-999, 5]となって後手は２手目に5を選べば勝てると言っています。
　次に先手が2を選んだ場合を見てみましょう。カラハでは相手のストアには石を撒かないことが注意点です。

final List board = [0,7,0,7,1,7,7,7];
result = second.think(board, first, 50, SECOND_WIN);

　結果は[-999, 5]となって後手は5を選べば勝てると言っています。同様に先手が3を選んだ場合を見てみましょう。

final List board = [0,7,7,0,1,7,7,7];
result = second.think(board, first, 50, SECOND_WIN);

　結果は[-999, 6]となって後手は6を選べば勝てると言っています。先手が初手に1,2,3のどれを選んでも後手必勝（-999）の結論は変わっていないので一応プログラムとしては一貫した結果が返ってきています。
　あと、相手の石を取る（capture）ケースも自分なりに確認していますが、図を書くのに疲れたので検証はここまでにします。

６×２列（カラハ）（2020-06-21追記）

　石の数を３個以上にするとベーシックの時と同じように先読みメソッドから返事が返って来ませんでした。千日手になってしまっているのだと思いますが、深くは調べていません。同一局面が現れたら手を変えるようにして千日手を無理やり回避するようにプログラムを改変すると、それは勝ち負けどちらの結果になったとしても必然の手順ではないということになってしまうので、 実験は一旦ここで打ち切ろうと思います。
　（訂正）冷静に考えると石を撒きながら自分のストアを通過する度に動かせる石が減っていくので、千日手（循環手順）があるとは思えません。GUIでテスト中に何かバグが見つかるかもと期待していましたが、アプリのテスト中も今のところバグらしきものは見つけられません⁴ので、局面が増えた時になぜ先読みメソッドがループ？に入るのか謎です。それとこの手の先読みプログラムをDartで作ったのは初めてなのですが、先読みの深さを1000とか10000とかにしてもスタックオーバーフローが発生しない理由がよく分からないのですが、そのことと何か関係があるのかも知れません。

強いマンカラアプリ

　自分のプログラムを１０手読みに設定して日本製の２つのアプリと何回か対戦させたのですが、負けは経験していないので今のところバグは無いのではと思っています⁵。数あるAndroidアプリの中で一番強いマンカラアプリがどれなのか知りませんが、全体的に強さを追求しているアプリは少ないのかも知れません。それと海外製のアプリもいくつか触ってみましたが、ルールが微妙に違っていたりする⁶ので、強さを比較するためにはそれぞれのルールに対応しなければならず結構大変です。海外製のアプリと強さを比較するために今後ルールを変更するかも知れません。そうすると上記の表の結果も変わって来ると思います。いろいろ派生ルールがあると面倒です、しかも何回か対戦しないと気付かないような微妙な違いなので厄介です。
※一例を挙げるとこの海外製アプリと対戦させて自分のプログラムが勝ち判定出した後に負けたのですが、このアプリはカラハとは違ってOwareというルールになっているようです。違うルールで先読みしていたら負けるのも当然です。

アプリ作ってみました（2020-07-05追記）

　マンカラアプリを作ってみました。まだ機能は少ないですが、今後追加していくつもりです。
　せっかくFlutterで作ったのでiPhone版もリリースしたいところですが、開発者登録費用の年間約10,000円を回収できる目処が立てばリリースするかも知れません⁷。

計算量の問題だけだったみたい（2020-08-01追記）

　本文中、「先読みメソッドから戻ってこない理由が分からない」とややこしいこと書いていますが、単に私が待ち切れなかっただけのようです。３×２列から６×２列に配列要素を増やすことで当然計算量は増えますが、それだけでなく石の数を増やすことでもかなりの計算量の増加があるようです。
　以下は６×２列のカラハで石の数を２にして、反復深化で先読みさせたFlutterのテストの実行結果です。

00:02 +0: First thinking test2 depth = 1
result = [1, 5], depth = 1
00:02 +1: First thinking test2 depth = 2
result = [0, 5], depth = 2
00:02 +2: First thinking test2 depth = 3
result = [3, 5], depth = 3
00:02 +3: First thinking test2 depth = 4
result = [4, 5], depth = 4
00:02 +4: First thinking test2 depth = 5
result = [5, 5], depth = 5
00:02 +5: First thinking test2 depth = 6
result = [4, 5], depth = 6
00:02 +6: First thinking test2 depth = 7
result = [5, 5], depth = 7
00:02 +7: First thinking test2 depth = 8
result = [4, 5], depth = 8
00:02 +8: First thinking test2 depth = 9
result = [4, 5], depth = 9
00:03 +9: First thinking test2 depth = 10
result = [4, 5], depth = 10
00:04 +10: First thinking test2 depth = 11
result = [3, 5], depth = 11
00:08 +11: First thinking test2 depth = 12
result = [5, 5], depth = 12
00:17 +12: First thinking test2 depth = 13
result = [4, 5], depth = 13
00:46 +13: First thinking test2 depth = 14
result = [5, 5], depth = 14
01:47 +14: First thinking test2 depth = 15
result = [6, 5], depth = 15
05:41 +15: First thinking test2 depth = 16
result = [2, 6], depth = 16
16:16 +16: First thinking test2 depth = 17
result = [3, 6], depth = 17
41:56 +17: First thinking test2 depth = 18
result = [999, 5], depth = 18
92:59 +18: All tests passed!

　最後の行の１９手読みの実行時間は９２分５９秒ですが、反復深化で調べると１手読みからの累積時間が必要となる（同じ経路を何度も調べている）ので、手間を惜しんで以下のように一気に５０手読みをさせていました。

final List board = [0,2,2,2,2,2,2,0,2,2,2,2,2,2];
Stopwatch watch = new Stopwatch();
watch.start();
result = first.think(board, second, 50, FIRST_WIN);
print(watch.elapsedMilliseconds);
print(result);

　この実行結果は以下のようになります。

4389283
[999, 5]

　4389283ミリ秒＝約１時間１３分で反復深化で調べるより時間が短縮できます。
そこで手数は分からなくてもいいから、まず５０手以内に必勝手順が存在するかどうかを確認しようと思い、石３個の場合も以下のように一気に５０手読みで実行していました。

final List board = [0,3,3,3,3,3,3,0,3,3,3,3,3,3];
Stopwatch watch = new Stopwatch();
watch.start();
result = first.think(board, second, 50, FIRST_WIN);
print(watch.elapsedMilliseconds);
print(result);

　そして、丸一日経ってもプログラムが終了しないので、おかしいなぁと悩んでた訳です。
　でも、このやり方だと石２個の時のように必勝の結論が得られればいいですが、その結論が得られない場合、計算量が指数関数的に増えて必要な時間も増えていきます。
　試しに石３個の場合にどれぐらいの時間が必要なのか確認してみたのが以下の結果です。

00:08 +0: First thinking test3 depth = 1
result = [5, 4], depth = 1
00:08 +1: First thinking test3 depth = 2
result = [4, 4], depth = 2
00:08 +2: First thinking test3 depth = 3
result = [1, 5], depth = 3
00:08 +3: First thinking test3 depth = 4
result = [3, 5], depth = 4
00:08 +4: First thinking test3 depth = 5
result = [1, 6], depth = 5
00:08 +5: First thinking test3 depth = 6
result = [3, 6], depth = 6
00:08 +6: First thinking test3 depth = 7
result = [3, 5], depth = 7
00:08 +7: First thinking test3 depth = 8
result = [2, 5], depth = 8
00:08 +8: First thinking test3 depth = 9
result = [2, 5], depth = 9
00:09 +9: First thinking test3 depth = 10
result = [4, 5], depth = 10
00:12 +10: First thinking test3 depth = 11
result = [3, 5], depth = 11
00:24 +11: First thinking test3 depth = 12
result = [2, 5], depth = 12
01:09 +12: First thinking test3 depth = 13
result = [3, 5], depth = 13
04:02 +13: First thinking test3 depth = 14
result = [3, 5], depth = 14
13:20 +14: First thinking test3 depth = 15
result = [4, 5], depth = 15
42:39 +15: First thinking test3 depth = 16
result = [4, 5], depth = 16
136:42 +16: First thinking test3 depth = 17

　最初の内は読みが深くなっても時間はそれほど変わりませんが、途中から一手読みが深くなる毎に２倍、３倍と増えていくのが分かります。１８手読みまでに必勝手順は見つからず、１８手読みの時に136分（約２時間強）以上かかっています。このペースで時間が増えていくと５０手読みだと数週間では済まないかも知れません。どおりで１日では終わらない訳です。５０手までに必勝手順が存在すれば数日で終了するかも知れませんがなんとも言えません。また、石４個だとさらに時間が必要になります。数ヶ月掛かるんじゃないでしょうか？
　ちなみに石１個だと「１５手で先手必勝」の結論が、実行時間わずか７秒で得られます。石１個→７秒、石２個→１時間強なら、石３個→「丸一日あれば十分かな」と考えたのが甘かったようです。
　実行環境は

• CPU:Intel(R) Core(TM) i7-2600K CPU @ 3.40GHz
• Memory: 12GB
• Dart: Dart VM version: 2.8.4 (stable) (Unknown timestamp) on "linux_x64"

です。どうしようか思案中です。

　※ TypeScriptとC++でも試してみました→「Dartは遅いけど、FlutterでGUIは有り」。
　※ 強いアプリを厳選して手動で対戦させて、先手必勝なのか後手必勝なのか推測してみました→「マンカラは後手でも勝てるか？」。

ソースファイル

　以前の記事の「３手前に打った駒が消える特殊なルールの三目並べ」のようにgithubでソースを公開しようと思っていたのですが、google play内の日本製のマンカラアプリで遊んでみて、少し惜しくなったというのが本音です。アプリのアクティブユーザー数が1,000に達したらこの記事で使用しているソース（=アプリからGUI部分を除いたソース）を公開しようと思ってます。
　またMIN-MAX法やαβ法のアルゴリズムに興味のある方は、よろしければこの本を買ってみてください。使用言語はCoffeeScript（JavaScript）ですが、本の中の相互再帰のやり方と今回の検証プログラムはほとんど同じやり方で、マンカラの場合は連続で指し手が続くケースがあるのでその部分だけif文（数行）が追加されている感じです。

追記（2023-11-18）

　AI部分の解説記事と合わせてgithubにソースファイル公開しました。