一回休み（パス）があるゲームでのαβ法

    dart flutter mancala

    気になっていたこと

    　以前「マンカラは先手必勝？後手必勝？」という記事の中で、自分が書いた本（「HTML5+CoffeeScriptで作る最強の三目並べプログラム」）を紹介して、「マンカラは三目並べと違ってパス（一回休み）があるので少しコードを変更する必要がある」と書いたまま詳細は説明してなかったことが気になってたので書くことにしました。本を買って頂いた方にとっては今更な感じはありますが、マンカラのソースコードを元に説明しようと思います。

    αβ法の実装手順

    　当ブログも昔はαβ法で検索するとこの記事が上位に表示されていたのですが、今は他にもっと丁寧な説明のあるサイトが増えたので圏外になってるみたいですね:sweat_smile:でもαβ法の解説に納得出来てもいざコードを書こうとすると出来ないという意見も見かけます。この本では３つのソースコードを用意して、この手順でソースを変更していけばαβ法が実装できますよという例を示しましたが、ここでマンカラを例にして簡単におさらいします。
    　まず、前提として先手は大きい値が有利、後手は小さい値が有利（逆でも可）という静的評価関数を用意します。静的評価関数はマンカラの場合なら(先手のストア内の豆の数 - 後手のストア内の豆の数)になります。
    　その後以下のように局面の先読みを行う関数を実装します。

    1. １つの階層におけるすべての着手を試して静的評価を行い、先手なら一番大きい後手なら一番小さい評価値を得る着手とその時の評価値を返す関数を作る。
    2. 1で作った関数をゲームが終了するか指定された手数（読みの深さ）に達することを終了条件とする再帰関数に書き換える ->ミニマックス法完成
    3. 2で作った関数に下層ノードに評価値を渡すための引数（閾値）を追加して、その閾値と現在の階層の評価値を比較して読みを中断（枝刈り、αβカット）してリターンするか、読みを続けるかの条件を書き加える ->αβ法完成
    4. 3で作った関数に先手、後手、先手という風に順番に着手したのか、先手、先手、先手と連続着手したのか区別するための引数を追加して、αβカットをしている部分に連続着手した場合はαβカットをしないように条件を書き加える

    　この4.の作業をすれば、一回休み（パス）があるゲームでのαβ法が完成します。要は先手か後手が連続着手した場合は何回連続であってもすべて無視して一回の着手と考えて、その最後の一回の評価値と閾値を比較してαβカットを行うようにすればいいだけです。

    実際のコード

    　githubのレポジトリ内のソースコードは以前の記事で使ったコードと大体同じなのですが、以前の記事では先手必勝か後手必勝かを確認するためのものだったので、そのままでは先手あるいは後手の負けが確定したときに最善手を逃します。「勝ちあるいは負けが確定した時点で最善かどうかに拘らず読みを打ち切ってReturn」するようになってました。
    　でも、ここで解説するコードは、実際のアプリ（マンカラナッツ）で使ってるコードと同じで負けが確定しても最善で負けるようになってます。マンカラナッツではC++で作成していますがそれのDart版です。

    　マンカラのゲーム盤はboard変数で表され、14要素の固定長配列になってます。


    後手のストア
    0    		  13   12   11   10    9    8 
    先手のストア
    7
      1    2    3    4    5    6 


    　マンカラのルールを実装している部分は省略して先読みを行うAI部分だけ、行番号を付けて解説します。

    01---  List think(List board, Player oppo, int limit, int pre_value, bool pre_turn){
02---    List result =  List<int>.filled(2, 0, growable: false);
03---    int moved = 0;
04---    int score = 0;
05---    int ret = 0;
06---    int lastscore = (this.turn == FIRST) ? SECOND_WIN : FIRST_WIN;
07---    int lastposi = -1;
08---    var goal = (this.turn == FIRST) ? FIRST_GOAL : DENTS;
09---    var start = (this.turn == FIRST) ? FIRST_START : SECOND_START;

10---    List temp = [0,0,0,0,0,0,0,0,0,0,0,0,0,0];
11---    for (var i = start; i < goal; i++){
12---      temp = List.from(board);
13---      if (temp[i] == 0) continue;
14---      moved = karahaMove(temp, i, this.turn);
15---      ret = gameEnd(temp);
16---      if (ret == ONGAME && limit > 0){
17---        if (moved == FIRST_GOAL || moved == SECOND_GOAL){
18---          result = this.think(temp, oppo, limit - 1, lastscore, false);
19---        } else {
20---          result = oppo.think(temp, this, limit - 1, lastscore, true);
21---        }
22---        score = result[0];
23---      } else {
24---        score = evaluate(temp);
25---        lastscore = score;
26---        lastposi = i;
27---        break;
28---      }
29---      if ((score >= lastscore && this.turn == FIRST) || (score <= lastscore && this.turn == SECOND)){
30---        lastscore = score;
31---        lastposi = i;
32---      }
33---      if (pre_turn == true && ((pre_value < score && this.turn == FIRST) || (pre_value > score && this.turn == SECOND))) {
34---        break;
35---      }
36---    }
37---    result[0] = lastscore;
38---    result[1] = lastposi;
39---    return result;
40---  }
    • 01: 戻り値:[評価値, 着手]の2要素の配列
      board:マンカラのBoardオブジェクト＝要素数14の固定長配列です
      oppo:対戦相手のPlayerオブジェクト
      limit:何手先まで読むのか（読みの深さ）の制限値、0になれば先読みを止める
      pre_value:αβカットの閾値（下層ノードに伝える評価値）
      pre_turn:連続着手か交互の着手かのフラグ（Falseなら連続着手なのでαβカットは行わない）
    • 02: result:戻り値[評価値, 着手]の2要素の配列
    • 03: moved:着手後に最後に豆を巻き終わった位置、自分のストアで豆を巻き終わったら連続で着手可能
    • 04: score:同じ階層での一手毎の評価値を格納
    • 05: ret:ゲーム継続中（ONGAME）かどうかを格納
    • 06: lastscore:最終的な評価値を格納。最初の比較時に必ず値が代入されるように先手の時は最小値、後手の時は最大値で初期化しておく
    • 07: lastposi:最終的に選ばれた着手を格納
    • 08: goal:Board配列の添字。先手、後手、それぞれの着手の末端。先手なら6、後手なら13
    • 09: start:Board配列の添字。先手、後手、それぞれの着手開始位置。先手なら1、後手なら8
    • 10: マンカラの場合一度着手した盤面を元に戻す作業が煩雑なので、引数で渡された盤面データ（board）を元に戻すための作業用の配列を用意
    • 11: 同じ階層で最善手を選択するためのforループ。このfor文は横（同じ手番）との比較で、再帰呼出しは上下（先手と後手）の評価値の比較、階層間の比較になります。
    • 12: 作業用配列に盤面データをコピー
    • 13: 穴に豆がなければ次の穴へ
    • 14: 一手着手
    • 15: ゲームが終了していないか確認
    • 16: 再帰関数の終了条件を満たしていなければ（＝ゲームが終了していなくて、limitで指定された深さまで達していなければ）、再帰呼出しして先読み。
      この時引数のpre_valueには、現時点でのその階層での最善手（lastscore、先手なら最大評価値、後手なら最小評価値）を渡す。
    • 18: 自分のストアで豆を巻き終われば、手番を替えずにもう一手先読み。pre_turn引数にfalseを渡して、手番が変わっていないことを下層ノードに伝える。
    • 20: それ以外は手番を交代してもう一手先読み。pre_turn引数にtrueを渡して、手番が変わったことを下層ノードに伝える。
    • 22: 戻ってきた評価値を格納、同じ階層での評価値の比較に使う。
    • 24: 再帰関数の終了条件を満たしていれば（＝ゲームが終了したか、指定された深さまで読み終わったら）静的評価を行って呼び出し元にリターン
    • 27: 戻り値（result）に値をセットしてリターンするのと同じ
    • 29: 同じ階層での評価値の比較作業。先手の場合はより大きな評価値、後手の場合はより小さな評価値を選択し、その評価値と指し手を保存。
    • 33: 連続着手ではない時（pre_turn == true）だけαβカット。上層から引数で渡されてきた閾値（pre_value）と現局面の評価値を比較し、先手の場合は閾値（pre_value）より大きな評価値だった時、後手の場合は閾値（pre_value）より小さな評価値だった時に読みを中断（その先を読む必要がない）して呼び出し元にリターン

    　大して長くもないのでソースコードを追いかけていって、何をしているのかわからない部分は、解説を見るという感じで理解できるのではないでしょうか？

    αβ法の確認

    　実装したαβ法がうまく機能しているかどうか確認するのに一番簡単な方法は、αβ法を実装している部分をコメントアウトしてみて実装した場合と同じ出力が得られるかどうかです。計算量を削減するのがαβ法なので、ただのミニマックス法で実行した時と同じ結果が得られて尚且つ実行時間が大幅に短縮されるはずです。
    　上のコードで33行目から35行目までをコメントアウトしてdart mancala.dartを実行したところ出力結果は同じで、実行時間は２０分と４時間弱の違いがありました。

    αβ法無し
    $ dart mancala.dart
[0, 2, 2, 2, 2, 2, 2, 0, 2, 2, 2, 2, 2, 2]
=== result = 1, 6, i = 1
=== result = 4, 5, i = 2
=== result = 3, 5, i = 3
=== result = 2, 5, i = 4
=== result = 4, 5, i = 5
=== result = 5, 5, i = 6
=== result = 4, 5, i = 7
=== result = 5, 5, i = 8
=== result = 5, 5, i = 9
=== result = 4, 5, i = 10
=== result = 5, 6, i = 11
=== result = 5, 6, i = 12
=== result = 5, 5, i = 13
=== result = 5, 5, i = 14
=== result = 7, 5, i = 15
=== result = 12, 5, i = 16
=== result = 999, 5, i = 17
14208572
[999, 5]
    αβ法有り
    $ dart mancala.dart
[0, 2, 2, 2, 2, 2, 2, 0, 2, 2, 2, 2, 2, 2]
=== result = 1, 6, i = 1
=== result = 4, 5, i = 2
=== result = 3, 5, i = 3
=== result = 2, 5, i = 4
=== result = 4, 5, i = 5
=== result = 5, 5, i = 6
=== result = 4, 5, i = 7
=== result = 5, 5, i = 8
=== result = 5, 5, i = 9
=== result = 4, 5, i = 10
=== result = 5, 6, i = 11
=== result = 5, 6, i = 12
=== result = 5, 5, i = 13
=== result = 5, 5, i = 14
=== result = 7, 5, i = 15
=== result = 12, 5, i = 16
=== result = 999, 5, i = 17
1276771
[999, 5]

    先手必勝か後手必勝かだけを確認したい場合

    　前述しましたが、最善手に拘らずに先手必勝なのか、後手必勝なのかだけを調べたい場合は、同じ階層での評価値の比較の際に、１個差の負けでも大差の負けでも同じと考えて、先手勝ちあるいは後手勝ちの結論が出た段階ですぐに呼び出し元にReturnすればいいだけです。例えば以下のコードを32行目と33行目の間に入れれば、指定された読みの深さ内で先手勝ちあるいは後手勝ちの結論が出たことになるので、そこで探索を打ち切り呼び出し元にリターンすれば探索時間を大幅に短縮できます。
    　ただこの時に使用する静的評価関数は単に(先手のストア内の豆の数 - 後手のストア内の豆の数)とするだけではなく、ゲームが終了しているかどうかを確認して先手勝ち（FIRST_WIN）、後手勝ち（SECOND_WIN）の特別な値を返すようにしておく必要があります。

          if ((score >= FIRST_WIN && this.turn == FIRST)||(score <= SECOND_WIN && this.turn == SECOND)) {
        lastscore = score;
        lastposi = i;
        break;
      }

    　上記のコードを追加した後、豆２個のケースで試したら、自分の環境では約半分近くの時間で先手必勝を読み切れました。