07 June 2020

    マンカラアプリ マンカラアプリ

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

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

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

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

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

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

    後手のストア
    0↓
    後手 先手のストア
    0↑
    3
    3
    3
    先手
    3
    3
    3


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

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

    Dartで実装

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

     一手読みから50手読みまで反復深化で徐々に読みを深くしていって、先手勝ち(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でもいいと思います。形勢判断の評価関数として(先手の空になっている穴の数 - 後手の空になっている穴の数)というのはかなり雑ですが、読み切ってしまうことが目的なので適当で構いません。

    結果

     石の数を1〜9個にして、50手先読みしたそれぞれの結果です。

    3×2列(ベーシック)

    石の数
    戻り値 [999, 1] [999, 1] [999, 1] [999, 2] [999, 1] [999, 1] [-999, 3] [-999, 3] [999, 3]
    読みの深さ 5手 24手 24手 38手 36手 43手 48手 - -
    結論 先手必勝 先手必勝 先手必勝 先手必勝 先手必勝 先手必勝 後手必勝 後手必勝 先手必勝

    ※先手なのに指し手の数が偶数になるのは、連続で指した場合にまとめて一手とカウントしてるためで、不正確です2

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

    検証1(石が1個の時)

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

    0 1 1 1 0
    0 2 1


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

    0 1 2 0 1
    0 2 0
    0 1 2 0 2
    0 0 1
    0 1 2 0 3
    0 0 0


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

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

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

    0 1 1 1 0
    1 1 1
    0 1 1 1 0
    0 2 1
    1 0 1 1 0
    0 2 1
    1 1 0 1 0
    0 2 1
    1 1 0 1 1
    0 2 0
    1 1 0 1 2
    0 0 1
    1 1 0 1 3
    0 0 0


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

    [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(5手読み)で先手が勝つと表示されます。

    検証2(石が4個の時)

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

    0 4 4 4 0
    4 4 4
    0 4 5 5 1
    4 0 5


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

    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を選べば本来の後手(上側)が必勝と判定されます。上下対象の配置なので当然こうなるべきで、これも一応プログラムは正しく動いてそうです。

    6×2ではどうなのか

     3×2列のマンカラでなく、通常の6×2列で石の数が4個のマンカラではどうなのか調べたいと思い、まず石1個でやってみました。

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

    マンカラカラハの結果(2020-06-17追記)

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

    3×2列(カラハ)

    石の数
    戻り値 [0, 1] [0, 2] [999, 1] [0, 1] [999, 1] [-999, 3] [999, 1]
    読みの深さ 50手 50手 19手 50手 18手 23手 25手
    結論 引分け 引分け 先手必勝 引分け 先手必勝 後手必勝 先手必勝

    検証(3×2カラハ)

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

    0 1 1 1 0
    1 1 1
    0 1 1 1 0
    0 2 1
    1 0 1 1 0
    0 2 1
    1 1 0 1 0
    0 2 1
    1 1 0 1 1
    0 2 0
    1 1 0 1 2
    0 0 1
    1 1 0 1 3
    0 0 0
    3 0 0 0 3
    0 0 0


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

    0 6 6 6 0
    6 6 6
    0 7 7 7 1
    0 7 7


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

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

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

    0 6 6 6 0
    6 6 6
    0 7 7 7 1
    7 0 7


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

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

    0 6 6 6 0
    6 6 6
    0 7 7 7 1
    7 7 0


    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)ケースも自分なりに確認していますが、図を書くのに疲れたので検証はここまでにします。

    6×2列(カラハ)(2020-06-21追記)

    石の数
    戻り値 [999, 6] [999, 5] - -      
    読みの深さ 15手 19手 - -      
    結論 先手必勝 先手必勝 ??? ???      

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

    強いマンカラアプリ

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

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

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

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

     本文中、「先読みメソッドから戻ってこない理由が分からない」とややこしいこと書いていますが、単に私が待ち切れなかっただけのようです。3×2列から6×2列に配列要素を増やすことで当然計算量は増えますが、それだけでなく石の数を増やすことでもかなりの計算量の増加があるようです。
     以下は6×2列のカラハで石の数を2にして、反復深化で先読みさせた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!
    

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

    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ミリ秒=約1時間13分で反復深化で調べるより時間が短縮できます。
    そこで手数は分からなくてもいいから、まず50手以内に必勝手順が存在するかどうかを確認しようと思い、石3個の場合も以下のように一気に50手読みで実行していました。

    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);
    

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

    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
    

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

    • 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は有り」

    ソースファイル

     アプリのアクティブユーザー数が1,000に達したらこの記事で使用しているソース(=アプリからGUI部分を除いたソース)を公開することにしました。もしソースが欲しいと思う方がいれば、アプリのユーザー増加にご協力ください。
     また、MIN-MAX法やαβ法のアルゴリズムに興味のある方は、もしよろしければこの本を買ってみてください。使用言語はCoffeeScript(JavaScript)ですが、本の中の相互再帰のやり方と今回の検証プログラムはほとんど同じやり方で、マンカラの場合は連続で指し手が続くケースがあるのでその部分だけif文(数行)が追加されている感じです。


    1. マンカラベーシックという呼び方が同じでも国や地域によってルールが違うようです。 

    2. 先読み関数から手数を返せば正確になるのですが、今のところやってません。 

    3. この辺りの事情は以前の記事にも書きました。 

    4. アプリの設定をExpertにすると10手読みですが、他のアプリと対戦させてみても結構強いです。絶対負けないプログラムにするにはこの記事の実験結果から考えて20手以上の先読みが必要になると思われるので、アプリに実装するのは応答時間の問題で難しいと思います。海外製の強いアプリをいくつか見つけましたが、データ構造を小さくしたり、定跡データ化したり工夫しているのだと思います。やはり歴史が長い海外製の方がずっと先を行ってそうです。それかオープンソースの優秀なマンカラ用のライブラリが既にあるのかも知れません。 

    5. 自分のプログラムは先手の手番で全ての石が空になったらその時点でゲーム終了としていますが、先手番でゲームが終了したら、後手の指し手をもう一手進めてからゲームを終了するルールもあるようです。石を撒く回数を先手と後手で公平にするという意図でしょうか? 

    6. 以前Cordovaで作成した機械学習型AIアプリを「進化する三目並べ」と題してiPhoneアプリとして公開していたのですが、売れなかったので1年間で止めてしまいました。 



    blog comments powered by Disqus