Pythonで〇×ゲームのAIを一から作成する その182 反復深化を利用した move ordering

目次と前回の記事

これまでに作成したモジュール

以下のリンクから、これまでに作成したモジュールを見ることができます。

リンク	説明
marubatsu.py	Marubatsu、Marubatsu_GUI クラスの定義
ai.py	AI に関する関数
test.py	テストに関する関数
util.py	ユーティリティ関数の定義
tree.py	ゲーム木に関する Node、Mbtree クラスなどの定義
gui.py	GUI に関する処理を行う基底クラスとなる GUI クラスの定義

AI の一覧とこれまでに作成したデータファイルについては、下記の記事を参照して下さい。

反復深化を利用した move ordering

前回の記事で説明した 反復深化 は、制限時間まで深さの上限を増やしながら計算を行う ため、制限時間内 で計算できた 最も大きな深さの上限 での計算結果を得ることができます。一方で、それより小さな深さの上限 で行う計算に 無駄な処理時間が費やされる という欠点があります。

ただし、この欠点は αβ 法に対する反復深化 の場合は 緩和できる ので、今回の記事ではその手法について説明します。

用語に関する説明

最近の記事では、ゲーム木の探索で計算される値の 精度についての説明 を行っており、静的評価関数が計算した近似値を元にした値であるかどうかを明確にするために、近似値 や 近似値のミニマックス値 という用語を使っていました。

精度に関する話はひと段落した点と、近似値 や 近似値のミニマックス値 は 本記事独自の用語 で 一般的には使われない ので、以後はゲーム木の探索で各 ノードに対して計算される値 の事を一般的に使われている 評価値と表記 することにします。

なお、ミニマックス法と αβ 法のどちらで評価値が計算されたかを 区別したい場合 は評価値のかわりに ミニマックス値 や αβ 値 という用語を使います。

move ordering のおさらい

以前の記事で説明したように、αβ 法 では max ノード の場合は 最も高い評価値 が、min ノード の場合は 最も低い評価値 が計算される子ノードを 最初に計算 した場合に 枝狩りの効率が最も高く なります。また、そのように子ノードの 計算の順番を入れ替える ことを move ordering と呼びます。

以前の記事では、move ordering を行うアルゴリズムには 以下のような性質が求められる ことを説明しました。

• 評価値が最も高い（または低い）子ノードを 短い時間で計算できる
• 評価値が最も高い（または低い）子ノードの計算が ある程度以上の精度 を持つ

上記の性質を満たすアルゴリズムの一つとして、以前の記事では 子ノードに対して静的評価関数が計算した評価値 を利用して move ordering を行うという手法を紹介しました。

反復深化を利用した move ordering の考え方

反復深化 では 深さの上限 を 1 から順番に増やしながら 深さ制限探索を行います。従って、反復深化の処理で 深さの上限が $\boldsymbol{d}$ （ただし、$d > 1$ とする¹）の深さ制限探索を 開始する時点 では、深さの上限が $\boldsymbol{d - 1}$ 以下 の深さ制限探索の 計算は完了 しています。

深さ制限探索 では、設定した 深さの上限 までの深さの各ノードに対して評価値を計算するため、深さの上限が $\boldsymbol{d}$ の場合は、深さが $\boldsymbol{n}$ のノード に対しては、そのノードをルートノード とする 深さの最大値が $\boldsymbol{d - n}$ の部分木 を用いて評価値の計算を行います。従って、深さが $\boldsymbol{n}$ のノードの 評価値 は、深さの上限を $\boldsymbol{d - n}$ とした 深さ制限探索 で評価値が 計算された値だとみなす ことができます。

以前の記事で説明したように、深さ制限探索 では一般的に 深さの上限を増やす ことで計算された 評価値の精度が高まります。また、静的評価関数 がノードに対して 計算する評価値 は 深さの上限が 0 の 深さ制限探索 とみなすことができるので、深さの上限が $\boldsymbol{d}$ の深さ制限探索で計算された 各ノードの評価値 は、深さが $\boldsymbol{d}$ のノード以外 は $\boldsymbol{d - n > 0}$ となるので静的評価関数が直接計算した評価値よりも 精度が高い 考えることができます。

また、各ノードの評価値 は、深さの上限が大きい 深さ制限探索で計算されたほうが 精度が高い と考えることができます。

上記から、反復深化 の処理において 深さの上限が $\boldsymbol{d}$ の深さ制限探索で計算を行う際に、それまでに計算した各ノードの評価値の中で 最も精度が高い と考えられる 深さの上限が $\boldsymbol{d - 1}$ の深さ制限探索で 計算された評価値を元 に move ordering を行うという手法が考えられます。この手法のポイントは、それまでに計算した深さ制限探索 の計算結果が 無駄にならない という点にあります。

この手法で move ordering を行うためには、深さの上限が $\boldsymbol{d - 1}$ の深さ制限探索で行われた 計算の記録が必要 となりますが、その記録は 置換表 を利用することで得ることができます。従って、反復深化を利用した move ordering のアルゴリズムは以下のようになります。

1. 深さ制限探索を行う際に 置換表を利用 する
2. 深さの上限を $\boldsymbol{d}$ とする深さ制限探索を行う際に、深さの上限を $\boldsymbol{d - 1}$ とした深さ制限探索の 置換表を元に move ordering を行う

なお、move ordering には 評価値が最大（または最小） の 子ノードのみを先頭に移動 する方法と、評価値の大きい（または小さい）順 で 並べ替える 方法がありますが、以下の理由から本記事では 前者による move ordering を行うことにします。

• 計算された 評価値の精度 が ある程度以上高ければ、十分大きな効果 が得られる
• 子ノードの数が多くなると、並べかえの処理に大きな時間がかかってしまう ようになる

置換表を利用するための修正と改良

上記で説明した反復深化での move ordering を行うためには、直前の深さ制限探索 で利用した 置換表の情報が必要 になりますが、現状の αβ 法で深さ制限探索を行う ai_abs_dls は返り値として 置換表の情報を取得することはできません。置換表の情報を取得できるようにする方法について少し考えてみてください。

置換表を利用できるようにするための修正方法

一つの方法として、ai_abs_dls の返り値 として 最善手と共に置換表の情報を返す という手法が考えられますが、返り値が変わってしまう ため、これまでに ai_abs_dls を利用するプログラムを修正 する必要があるという 互換性の問題 が発生します。

別の方法として、ai_abs_dls の 実引数にanalyze=True を記述 して呼び出した際に返り値として返される dict の中に置換表の情報を入れる という方法が考えられます。analyze=True を記述して呼び出すのは処理の分析（analyze）を行うためであり、これまでに記述したプログラムで AI の関数として 最善手を計算する場合 は analyze=True を記述しない ので、この方法の場合は これまでに ai_abs_dls を利用するプログラムを修正する必要はありません。別の方法もあると思いますが、本記事ではこの方法を採用することにします。もっと良い方法を思いついた方は実装してみて下さい。

analyze=True を記述した際の返り値の仕様

現状では analyze=True を記述した際の返り値の dict には下記の情報が記録されます。

キー	キーの値
"candidate"	最善手の一覧を表す list
"score_by_move"	それぞれの合法手を着手した局面の αβ 値

上記に加えて下記の情報を記録することにします。

キー	キーの値
"tt"	置換表のデータ
"time"	処理時間（単位は秒）
"bestmove"	AI が計算した最善手
"score"	最善手を計算するノードの評価値
"count"	計算したノードの数

move ordering を行うために 必要な情報は置換表のデータだけ ですが、それ以外　の "time"、"bestmove"、"score"、"count" を追加した理由は それらの情報が今後の分析に役立つ と考えたからです。例えば、処理時間 や 計算したノードの数 は、move ordering を行う場合と行わない場合の 処理の効率を比較 する際に必要となります。

また、現状の ai_abs_dls には下記のような 問題 があります。

• 指定したの局面の 最善手、αβ 値、計算したノードの数 のいずれか 一つだけが 返り値として得られるので、それらの 複数の値を一度で得る方法がない
• 計算したノードの数 を得るためには calc_score=True と calc_count=True の両方を記述する必要がある点が わかりづらい

analyze=True を記述した際の返り値に それらの 3 つの情報を記録する ことで、上記の問題を解決 することができます。

ai_by_mmscore の修正

analyze=True を記述した際の 処理 は、ai_abs_dls ではなく、ai_abs_dls を デコレート する関数 ai_by_mmscore で行われているので、ai_by_mmscore を修正 する必要があります。

なお、ai_by_mmscore は ai_abs_dls 以外の関数をデコレートすることもできますが、以下の説明では ai_abs_dls をデコレートした場合の説明 を行います。

ai_by_mmscore は、最善手を計算するノードの 子ノードに 対して ai_abs_dls を呼び出して 評価値を計算する処理を行うため、計算したノードの数を計算するためには、それぞれの子ノード に対して ai_abs_dls が呼び出された際に 計算されたノードの数の合計 を計算する必要があります。そのため、@ai_by_mmscore によって デコレートされる ai_abs_dls が評価値だけでなく 計算したノードの数 を返すように修正する必要があります。

具体的には (評価値, 計算したノードの数) という tuple を返す ように ai_abs_dls を修正することにします。なお、ai_abs_dls の修正は ai_by_mmscore の修正の後で行います。

この修正によって仮引数 analyze の値が False の場合の ai_abs_dls の返り値が変わってしまう と 互換性の問題が発生 してしまう点に注意が必要です。具体的には 返り値が変わらないようにするための修正 を下記の 12 ~ 14 行目 で行っています。

下記はそのように ai_by_mmscore を修正したプログラムです²。なお、dprint で表示するメッセージの修正は行っていませんので、修正したい人は自由に修正して下さい。

• 13、20 行目：ai_by_mmscore がデコレートする関数 eval_func の 返り値を (評価値, 計算したノードの数) という tuple に変更したので、それに合わせて返り値を score と count に代入するように修正する
• 12 ~ 14 行目：calc_score=True の場合は、評価値のみを返り値として返す必要がある。修正前のプログラムのように eval_func の返り値をそのまま返す と (評価値, 計算したノードの数) という tuple が返り値として返るので 互換性の問題が発生 する。この点は忘れやすいので注意する事
• 16 行目：処理を開始した際のパフォーマンスカウンターの値を starttime に記録することで、処理時間の計測を開始する
• 18 行目：計算したノードの数の合計を数える変数を 0 で初期化する
• 21 行目：計算したノードの数の合計を、子ノードの評価値を計算した際に計算したノードの数で加算する
• 23 行目：AI が計算する最善手が analyze=True の場合にも必要となるので先に計算するように修正する
• 24 ~ 33 行目：analyze=True の場合の返り値を計算して返すように修正する
• 34、35 行目：analyze=False の場合に先程計算した最善手を返すように修正する

 1  from ai import dprint
 2  from marubatsu import Marubatsu
 3  from copy import deepcopy
 4  from functools import wraps
 5  from time import perf_counter
 6  from random import choice
 7  
 8  def ai_by_mmscore(eval_func):
 9      @wraps(eval_func)
10      def wrapper(mb_orig, debug=False, *args, rand=True, share_tt=True,
11                  analyze=False, calc_score=True, **kwargs):       
12          if calc_score:
13              score, count = eval_func(mb_orig, debug, *args, **kwargs)
14              return score
15
16          starttime = perf_counter()
17          dprint(debug, "Start ai_by_mmscore")
元と同じなので省略
18          totalcount = 0
19          for move in legal_moves:
元と同じなので省略
20              score, count = eval_func(mb, debug, tt=tt, *args, **kwargs)
21              totalcount += count
22              dprint(debug, "score", score, "best score", best_score)
元と同じなので省略
23          bestmove = choice(best_moves) if rand else best_moves[0]
24          if analyze:
25              return {
26                  "candidate": best_moves,
27                  "score_by_move": score_by_move,
28                  "tt": tt,
29                  "time": perf_counter() - starttime,
30                  "bestmove": bestmove,
31                  "score": best_score,
32                  "count": totalcount,
33              }
34          else:
35              return bestmove
36          
37      return wrapper

行番号のないプログラム

from ai import dprint
from marubatsu import Marubatsu
from copy import deepcopy
from functools import wraps
from time import perf_counter
from random import choice

def ai_by_mmscore(eval_func):
    @wraps(eval_func)
    def wrapper(mb_orig, debug=False, *args, rand=True, share_tt=True,
                analyze=False, calc_score=False, **kwargs):       
        if calc_score:
            score, count = eval_func(mb_orig, debug, *args, **kwargs)
            return score
        
        starttime = perf_counter()
        dprint(debug, "Start ai_by_mmscore")
        dprint(debug, mb_orig)
        legal_moves = mb_orig.calc_legal_moves()
        dprint(debug, "legal_moves", legal_moves)
        maxnode = mb_orig.turn == Marubatsu.CIRCLE
        best_score = float("-inf") if maxnode else float("inf")
        best_moves = []
        tt = {} if share_tt else None
        totalcount = 0
        if analyze:
            score_by_move = {}
        for move in legal_moves:
            dprint(debug, "=" * 20)
            dprint(debug, "move", move)
            mb = deepcopy(mb_orig)
            x, y = move
            mb.move(x, y)
            dprint(debug, mb)
            score, count = eval_func(mb, debug, tt=tt, *args, **kwargs)
            totalcount += count
            dprint(debug, "score", score, "best score", best_score)
            if analyze:
                score_by_move[move] = score
            
            if (maxnode and best_score < score) or (not maxnode and best_score > score):
                best_score = score
                best_moves = [move]
                dprint(debug, "UPDATE")
                dprint(debug, "  best score", best_score)
                dprint(debug, "  best moves", best_moves)
            elif best_score == score:
                best_moves.append(move)
                dprint(debug, "APPEND")
                dprint(debug, "  best moves", best_moves)

        dprint(debug, "=" * 20)
        dprint(debug, "Finished")
        dprint(debug, "best score", best_score)
        dprint(debug, "best moves", best_moves)
        bestmove = choice(best_moves) if rand else best_moves[0]
        if analyze:
            return {
                "candidate": best_moves,
                "score_by_move": score_by_move,
                "tt": tt,
                "time": perf_counter() - starttime,
                "bestmove": bestmove,
                "score": best_score,
                "count": totalcount,
            }
        else:
            return bestmove
        
    return wrapper

修正箇所

from ai import dprint
from marubatsu import Marubatsu
from copy import deepcopy
from functools import wraps
from time import perf_counter
from random import choice

def ai_by_mmscore(eval_func):
    @wraps(eval_func)
    def wrapper(mb_orig, debug=False, *args, rand=True, share_tt=True,
                analyze=False, calc_score=True, **kwargs):       
        if calc_score:
-           return = eval_func(mb_orig, debug, *args, **kwargs)
+           score, count = eval_func(mb_orig, debug, *args, **kwargs)
+           return score
+       starttime = perf_counter()
        dprint(debug, "Start ai_by_mmscore")
元と同じなので省略
+       totalcount = 0
        for move in legal_moves:
元と同じなので省略
-           score = eval_func(mb, debug, tt=tt, *args, **kwargs)
+           score, count = eval_func(mb, debug, tt=tt, *args, **kwargs)
+           totalcount += count
            dprint(debug, "score", score, "best score", best_score)
元と同じなので省略
+       bestmove = choice(best_moves) if rand else best_moves[0]
        if analyze:
            return {
                "candidate": best_moves,
                "score_by_move": score_by_move,
+               "tt": tt,
+               "time": perf_counter() - starttime,
+               "bestmove": bestmove,
+               "score": best_score,
+               "count": totalcount,
            }
-       elif rand:   
-           return choice(best_moves)
-       else:
-           return best_moves[0]
+       else:
+           return bestmove
        
    return wrapper

analyze=True を記述することで評価値を含むデータが返り値として返るようになったので、評価値のみを計算して返す処理を行うための仮引数 calc_score が必要なくなったのではないか と思う人がいるかもしれませんが、評価値のみを計算して返す処理 は、下記のプログラムのように ai_abs_dls の中で 深さの上限の深さのノード の評価値を 静的評価関数で計算する際などで必要となる ので残す必要があります。

        if mborig.status != Marubatsu.PLAYING or depth == maxdepth:
            return eval_func(mborig, calc_score=True, **eval_params)

ai_abs_dls の修正

ai_by_mmscore を上記のように修正した結果、ai_by_mmscore がデコレートする関数 が (評価値, 計算したノードの数) という tuple を返すように修正 する必要があります。

下記はそのように ai_abs_dls を修正したプログラムです。分析以外の目的で計算したノードの数が必要になることはなさそうな点と、計算したノードの数を得るために calc_score=True と calc_count=True の両方を記述するのはわかりにくいと思いましたので、calc_count に関する処理は削除しました。以後は 計算したノードの数が必要 になった場合は analyze=True を記述 することにします。

• 3 行目：仮引数 calc_count を削除する
• 5 行目：calc_count に関する処理を削除し、常に (評価値, 計算したノードの数) を返すように修正する

1  @ai_by_mmscore
2  def ai_abs_dls(mb, debug=False, timelimit_pc=None, maxdepth=1, eval_func=None,
3                 eval_params={}, use_tt=False, tt=None):           
元と同じなので省略
4      dprint(debug, "count =", count)
5      return score, count

行番号のないプログラム

@ai_by_mmscore
def ai_abs_dls(mb, debug=False, timelimit_pc=None, maxdepth=1, eval_func=None,
               eval_params={}, use_tt=False, tt=None):           
    count = 0
    def ab_search(mborig, depth, tt, alpha=float("-inf"), beta=float("inf")):
        nonlocal count
        if timelimit_pc is not None and perf_counter() >= timelimit_pc:
            raise RuntimeError("time out")
        
        count += 1
        if mborig.status != Marubatsu.PLAYING or depth == maxdepth:
            return eval_func(mborig, calc_score=True, **eval_params)
        
        if use_tt:
            boardtxt = mborig.board_to_str()
            if boardtxt in tt:
                lower_bound, upper_bound = tt[boardtxt]
                if lower_bound == upper_bound:
                    return lower_bound
                elif upper_bound <= alpha:
                    return upper_bound
                elif beta <= lower_bound:
                    return lower_bound
                else:
                    alpha = max(alpha, lower_bound)
                    beta = min(beta, upper_bound)
            else:
                lower_bound = min_score
                upper_bound = max_score
        
        alphaorig = alpha
        betaorig = beta

        legal_moves = mborig.calc_legal_moves()
        if mborig.turn == Marubatsu.CIRCLE:
            score = float("-inf")
            for x, y in legal_moves:
                mb = deepcopy(mborig)
                mb.move(x, y)
                score = max(score, ab_search(mb, depth + 1, tt, alpha, beta))
                if score >= beta:
                    break
                alpha = max(alpha, score)
        else:
            score = float("inf")
            for x, y in legal_moves:
                mb = deepcopy(mborig)
                mb.move(x, y)
                score = min(score, ab_search(mb, depth + 1, tt, alpha, beta))
                if score <= alpha:
                    break
                beta = min(beta, score)   
            
        from util import calc_same_boardtexts

        if use_tt:
            boardtxtlist = calc_same_boardtexts(mborig)
            if score <= alphaorig:
                upper_bound = score
            elif score < betaorig:
                lower_bound = score
                upper_bound = score
            else:
                lower_bound = score
            for boardtxt in boardtxtlist:
                tt[boardtxt] = (lower_bound, upper_bound)
        return score
                
    min_score = float("-inf")
    max_score = float("inf")
    
    if tt is None:
        tt = {}
    score = ab_search(mb, depth=0, tt=tt, alpha=min_score, beta=max_score)
    dprint(debug, "count =", count)
    return score, count

修正箇所

@ai_by_mmscore
def ai_abs_dls(mb, debug=False, timelimit_pc=None, maxdepth=1, eval_func=None,
-              eval_params={}, use_tt=False, tt=None, calc_count=False):
+              eval_params={}, use_tt=False, tt=None):           
元と同じなので省略
    dprint(debug, "count =", count)
-   if calc_count:
-       return count
-   return score
+   return score, count

ai_abs_dls 以外 の @ai_by_mmscore でデコレートする関数 に対しても 同様の修正を行う必要 があります。長くなるのと今回の記事でそれらの関数を利用しないので本記事ではその修正を記述しませんが、今回の記事の最後で示す ai.py の修正版の ai_new.py ではその修正を行っておくことにします。

上記の修正後に下記のプログラムを実行して、ai_abs_dls に analyze=True を記述せず にゲーム開始時の局面の計算を行うと、実行結果のように修正前と同様に 最善手の計算が行われる ことが確認できます。

from ai import ai14s

mb = Marubatsu()
eval_params = { "minimax": True }
print(ai_abs_dls(mb, maxdepth=9, eval_func=ai14s, eval_params=eval_params))

実行結果（ゲーム開始時の局面は全ての合法手が最善手なので、下記とは異なる表示になる場合があります）

(2, 2)

下記のプログラムで calc_score=True を記述して実行すると、実行結果のようにゲーム開始時の局面の 評価値のみが表示 されることが確認できます。

print(ai_abs_dls(mb, maxdepth=9, eval_func=ai14s, eval_params=eval_params, calc_score=True))

実行結果

0.0

下記のプログラムで analyze=True を記述して計算を行うと、実行結果のように返り値として 先ほど追加した情報が記録された dict が返される ことが確認できます。ただし、use_tt=True を記述しなかった ので 置換表のデータは空の dict になります。

from pprint import pprint

pprint(ai_abs_dls(mb, maxdepth=9, eval_func=ai14s, eval_params=eval_params, analyze=True))

実行結果（ゲーム開始時の局面は全ての合法手が最善手なので、"bestmove" は下記とは異なる表示になる場合があります）

{'bestmove': (1, 0),
 'candidate': [(0, 0),
               (1, 0),
               (2, 0),
               (0, 1),
               (1, 1),
               (2, 1),
               (0, 2),
               (1, 2),
               (2, 2)],
 'count': 30709,
 'score': 0.0,
 'score_by_move': {(0, 0): 0.0,
                   (0, 1): 0.0,
                   (0, 2): 0.0,
                   (1, 0): 0.0,
                   (1, 1): 0.0,
                   (1, 2): 0.0,
                   (2, 0): 0.0,
                   (2, 1): 0.0,
                   (2, 2): 0.0},
 'time': 1.5907108001410961,
 'tt': {}}

下記のプログラムで use_tt=True を記述して計算を行うと、実行結果のように "tt" のキーの値 に 置換表のデータが記録されている ことが確認できます。また、置換表を利用した結果、計算したノードの数 を表す "count" のキーの値が 30709 から 1175 に、処理時間 を表す "time" のキーの値が 約 1.60 から 約 0.17 に減った ことも確認できます。

pprint(ai_abs_dls(mb, maxdepth=9, eval_func=ai14s, eval_params=eval_params, 
                  use_tt=True,  analyze=True))

実行結果（ゲーム開始時の局面は全ての合法手が最善手なので、"bestmove" は下記とは異なる表示になる場合があります）

{'bestmove': (1, 1),
 'candidate': [(0, 0),
               (1, 0),
               (2, 0),
               (0, 1),
               (1, 1),
               (2, 1),
               (0, 2),
               (1, 2),
               (2, 2)],
 'count': 1175,
 'score': 0.0,
 'score_by_move': {(0, 0): 0.0,
                   (0, 1): 0.0,
                   (0, 2): 0.0,
                   (1, 0): 0.0,
                   (1, 1): 0.0,
                   (1, 2): 0.0,
                   (2, 0): 0.0,
                   (2, 1): 0.0,
                   (2, 2): 0.0},
 'time': 0.16863269917666912,
 'tt': {'........o': (0.0, 0.0),
        '.......o.': (0.0, 0.0),
略
        'xxoxxooo.': (300, 300)}}

本記事では行いませんがデコレータ関数 ai_by_score と、ai_by_score によってデコレートされる関数に対しても同様の修正を行うことができます。余裕がある方は行ってみて下さい。

置換表を利用した move ordering の方法

次に、置換表を利用した move ordering の 具体的な方法 について考える必要があります。どのようにすれば良いかについて少し考えてみて下さい。

αβ 法 では、枝狩りが行われた場合 は 評価値が計算されない子ノード が生じます。そこで、枝狩りが行われるノード と、行われないノード の場合に 分けて考えること にします。

枝狩りが行われない場合

枝狩りが行われない場合 は、すべての子ノードの評価値が計算される ので、max ノード の場合は置換表に記録された子ノードの評価値の中で 最も高い評価値 の子ノードを 先頭に移動 します。min ノード の場合は 最も低い評価値 の子ノードを 先頭に移動 します。

上記の 先頭に移動する子ノード は、AI が計算した 最善手を着手したノード と考えることができるので、最善手を着手した子ノードを先頭に移動 すれば良いことがわかりました。

枝狩りが行われる場合

枝狩りが行われる場合は、枝狩りが行われるきっかけとなったノード を 先頭に移動する ことで 他の子ノードをすべて枝狩り することができます。max ノード では、子ノードの評価値が はじめて β 値を超えた場合 に枝狩りが行われるので、評価値が計算された子ノードの中 で 最も高い評価値 の子ノードを 先頭に移動 します。min ノードの場合は、最も低い評価値 の子ノードを 先頭に移動 します。

上記から、枝狩りの有無に関わらず、max ノードでは 評価値が計算された子ノードの中 で 最も高い評価値 の子ノードを 先頭に移動、min ノードでは 最も高い評価値 の子ノードを 先頭に移動 すれば良いことがわかりました。

このような、枝狩りのきっかけとなる着手 のことを refutation move³ と呼ぶようです。refutation とは 論破 という意味の英単語で、おそらくその着手を行った局面の評価値を計算することで、残りの合法手の計算を行わなくても良いと論破できたみなされることから、そのような名前がついているのではないかと思います。

参考までに refutation move の Chess programming wiki のリンクを下記に示します。

move ordering を行う着手の用語について

上記から、最善手または refutation move を行った子ノードを先頭に移動すれば良いことがわかりましたが、「最善手または refutation move」と表記するのは冗長です。また、refutation move は、max ノードの場合は残りの枝狩りを行った子ノードの中にそれよりも高い評価値の子ノードが存在しているかもしれないので、厳密には最善手であるとは言えない かもしれませんが、先程説明したように最善手も refutation move も 同じ方法で計算できる ので、以後は move ordering の文脈 では 最善手 という用語が refutation move を含む ことにし、最善手を行った子ノード を先頭に移動すると表記することにします。

最善手の置換表への記録

置換表のデータから 評価値が計算された子ノードの中 で、最も高い（または低い）評価値 の子ノードを計算することは可能ですが、そのような計算は 深さ制限探索を行う際に計算できる ので、move ordering を行う際に 置換表から改めて計算を行うのは無駄 です。

具体的には 深さ制限探索を行う際に計算された最善手 を、置換表のデータに記録しておく ことで 計算の手間を省く ことができます。

置換表に最善手または refutation move を記録するという手法は、下記の Chess Programming Wiki の置換表（Transposition Table）の項目の「What Information is Stored（どのような情報が記録されているか）」の所にも記載されているようです。

置換表に最善手を記録するという手法には、置換表に記録する データの量が増えるという欠点 があります。〇× ゲームのように、置換表にすべての局面のデータを記録することが可能な場合は問題にはなりませんが、多くのゲームではゲーム木の規模が大きすぎるため、置換表に計算したすべての局面のデータを記録することは不可能です。そのような場合は、置換表に記録するデータを減らすことでより多くの局面のデータを記録したほうが良いという考え方もあるため、置換表に最善手を記録するという手法が必ずしも最善であるとは限りません。

ai_abs_dls の修正

先程修正した ai_abs_dls は、置換表に関する修正は行っていない ので、置換表にはノードの αβ 値の下界と上界の情報 しか記録されていません。そこで、置換表 のノードのデータとして (αβ 値の下界 , αβ 値の上界, 最善手) という tuple を記録 するように修正することにします。下記はそのように ai_abs_dls を修正したプログラムです。

• 7 行目：置換表に記録するデータの変更にあわせて 最善手を変数に代入 するように修正した。なお、ここで変数に代入した 最善手の値は αβ 法の処理では利用しない ので、_ という名前の変数に代入した
• 13 ~ 16 行目：max ノードでの再帰呼び出しの返り値を abscore という変数に代入し、score より大きい場合に最善手を記録する変数に着手した合法手を代入するように修正した。また、評価値の値の更新はその後の 16 行目で行うように修正した
• 25 ~ 28 行目：min ノードで上記と同様の処理を行うように修正した
• 38 行目：置換表に (αβ 値の下界, αβ 値の上界, 最善手) を記録するように修正した

 1  @ai_by_mmscore
 2  def ai_abs_dls(mb, debug=False, timelimit_pc=None, maxdepth=1, eval_func=None,
 3                 eval_params={}, use_tt=False, tt=None):    
元と同じなので省略
 4          if use_tt:
 5              boardtxt = mborig.board_to_str()
 6              if boardtxt in tt:
 7                  lower_bound, upper_bound, _ = tt[boardtxt]
元と同じなので省略
 8          if mborig.turn == Marubatsu.CIRCLE:
 9              score = float("-inf")
10              for x, y in legal_moves:
11                  mb = deepcopy(mborig)
12                  mb.move(x, y)
13                  abscore = ab_search(mb, depth + 1, tt, alpha, beta)
14                  if abscore > score:
15                      bestmove = (x, y)
16                  score = max(score, abscore)
17                  if score >= beta:
18                      break
19                  alpha = max(alpha, score)
20          else:
21              score = float("inf")
22              for x, y in legal_moves:
23                  mb = deepcopy(mborig)
24                  mb.move(x, y)
25                  abscore = ab_search(mb, depth + 1, tt, alpha, beta)
26                  if abscore < score:
27                      bestmove = (x, y)
28                  score = min(score, abscore)
29                  if score <= alpha:
30                      break
31                  beta = min(beta, score)   
32              
33          from util import calc_same_boardtexts
34  
35          if use_tt:
36              boardtxtlist = calc_same_boardtexts(mborig)
元と同じなので省略
37              for boardtxt in boardtxtlist:
38                  tt[boardtxt] = (lower_bound, upper_bound, bestmove)
39          return score
元と同じなので省略

行番号のないプログラム

@ai_by_mmscore
def ai_abs_dls(mb, debug=False, timelimit_pc=None, maxdepth=1, eval_func=None,
               eval_params={}, use_tt=False, tt=None):           
    count = 0
    def ab_search(mborig, depth, tt, alpha=float("-inf"), beta=float("inf")):
        nonlocal count
        if timelimit_pc is not None and perf_counter() >= timelimit_pc:
            raise RuntimeError("time out")
        
        count += 1
        if mborig.status != Marubatsu.PLAYING or depth == maxdepth:
            return eval_func(mborig, calc_score=True, **eval_params)
        
        if use_tt:
            boardtxt = mborig.board_to_str()
            if boardtxt in tt:
                lower_bound, upper_bound, _ = tt[boardtxt]
                if lower_bound == upper_bound:
                    return lower_bound
                elif upper_bound <= alpha:
                    return upper_bound
                elif beta <= lower_bound:
                    return lower_bound
                else:
                    alpha = max(alpha, lower_bound)
                    beta = min(beta, upper_bound)
            else:
                lower_bound = min_score
                upper_bound = max_score
        
        alphaorig = alpha
        betaorig = beta

        legal_moves = mborig.calc_legal_moves()
        if mborig.turn == Marubatsu.CIRCLE:
            score = float("-inf")
            for x, y in legal_moves:
                mb = deepcopy(mborig)
                mb.move(x, y)
                abscore = ab_search(mb, depth + 1, tt, alpha, beta)
                if abscore > score:
                    bestmove = (x, y)
                score = max(score, abscore)
                if score >= beta:
                    break
                alpha = max(alpha, score)
        else:
            score = float("inf")
            for x, y in legal_moves:
                mb = deepcopy(mborig)
                mb.move(x, y)
                abscore = ab_search(mb, depth + 1, tt, alpha, beta)
                if abscore < score:
                    bestmove = (x, y)
                score = min(score, abscore)
                if score <= alpha:
                    break
                beta = min(beta, score)   
            
        from util import calc_same_boardtexts

        if use_tt:
            boardtxtlist = calc_same_boardtexts(mborig)
            if score <= alphaorig:
                upper_bound = score
            elif score < betaorig:
                lower_bound = score
                upper_bound = score
            else:
                lower_bound = score
            for boardtxt in boardtxtlist:
                tt[boardtxt] = (lower_bound, upper_bound, bestmove)
        return score
                
    min_score = float("-inf")
    max_score = float("inf")
    
    if tt is None:
        tt = {}
    score = ab_search(mb, depth=0, tt=tt, alpha=min_score, beta=max_score)
    dprint(debug, "count =", count)
    return score, count

修正箇所

@ai_by_mmscore
def ai_abs_dls(mb, debug=False, timelimit_pc=None, maxdepth=1, eval_func=None,
               eval_params={}, use_tt=False, tt=None):    
元と同じなので省略
        if use_tt:
            boardtxt = mborig.board_to_str()
            if boardtxt in tt:
-               lower_bound, upper_bound = tt[boardtxt]
+               lower_bound, upper_bound, _ = tt[boardtxt]
元と同じなので省略
        if mborig.turn == Marubatsu.CIRCLE:
            score = float("-inf")
            for x, y in legal_moves:
                mb = deepcopy(mborig)
                mb.move(x, y)
-               score = max(score, ab_search(mb, depth + 1, tt, alpha, beta))
+               abscore = ab_search(mb, depth + 1, tt, alpha, beta)
+               if abscore > score:
+                   bestmove = (x, y)
+               score = max(score, abscore)
                if score >= beta:
                    break
                alpha = max(alpha, score)
        else:
            score = float("inf")
            for x, y in legal_moves:
                mb = deepcopy(mborig)
                mb.move(x, y)
-               score = min(score, ab_search(mb, depth + 1, tt, alpha, beta))
+               abscore = ab_search(mb, depth + 1, tt, alpha, beta)
+               if abscore < score:
+                   bestmove = (x, y)
+               score = min(score, abscore)
                if score <= alpha:
                    break
                beta = min(beta, score)   
            
        from util import calc_same_boardtexts

        if use_tt:
            boardtxtlist = calc_same_boardtexts(mborig)
元と同じなので省略
            for boardtxt in boardtxtlist:
-               tt[boardtxt] = (lower_bound, upper_bound)
+               tt[boardtxt] = (lower_bound, upper_bound, bestmove)
        return score
元と同じなので省略

上記の修正後に下記のプログラムを実行すると、実行結果のように 置換表 のノードのデータに 最善手を表すデータが追加された ことが確認できます。

result = ai_abs_dls(mb, maxdepth=9, eval_func=ai14s, eval_params=eval_params, 
                    use_tt=True, analyze=True)
tt = result["tt"]
pprint(tt)

実行結果

{'........o': (0.0, 0.0, (1, 1)),
 '.......o.': (0.0, 0.0, (0, 0)),
略
 'xxoxxooo.': (300, 300, (0, 2))}

置換表の最善手の確認

上記で計算した 置換表に記録された最善手が正しいか どうかを確認することにします。その方法について少し考えてみて下さい。

principal variation による確認

置換表が正しいかどうか を確認する方法の一つに、置換表に登録された最善手を着手し続けた局面を表示 するという方法があります。〇× ゲーム の ゲーム木の深さは 9 なので、先程計算した 深さの上限を 9 とした深さ制限探索は 正しい最善手を計算 します。〇× ゲームの ゲーム開始時の局面 は 引き分けの局面 なので、置換表に登録された最善手を着手し続けると 引き分けの局面になるはず です。

上記のような ゲーム木の探索を行う AI が計算した 最善手を着手し続けた合法手の一覧 のことを、principal variation と呼びます。principal とは「主要な」、「第一の」、variation とは「変動」、「変化」という意味を持つ英単語で、ゲーム木の文脈 では principal は「最善の」、variation は「現在の局面から特定の局面まで 着手した合法手の一覧」を表します。

従って、ゲーム木の探索 における principal variation は、ゲーム木の探索を行った結果得られた、現在の局面から探索した深さの上限まで お互いが最善手を着手し続けた場合 の 最善手の一覧 を表します。

principal variation は一般的に PV と表記されるので本記事でも 以後は PV と表記 することにします。また、日本語では PV のことを AI の読み筋 と表記することがあるようです。将棋や囲碁等の中継で AI 最善手とみなした着手が行われた場合の 数手先までの AI の着手の予想 が表示される場合がありますが、それが PV（読み筋）です。

また、以前の記事で実装した ゲーム木を視覚化 する Mbtree_GUI が表示するゲーム木は PV を視覚化する機能 を持ちます。そのことを下記のプログラムを実行して示します。

from tree import Mbtree_GUI

Mbtree_GUI()

Mbtree_GUI は 選択した局面が赤枠で表示 され、 選択した局面の子ノード のうち、最善手を着手 した子ノードを 明るく表示 し、それ以外 の子ノードを 暗く表示 する機能を持ちます。また、子ノードの右に表示 される 背景が灰色の部分の子孫ノード は、その子ノードの局面から お互いが最善手を着手し続けた場合の局面の一覧 を表しています。従って、明るく表示された子ノードと、その右に表示される局面の 着手を表す赤色のマークが PV を表します。

下図は ゲーム開始時の局面 を選択した場合の図です。ゲーム開始時の局面では すべての合法手が最善手 なので、下図では 8 つのすべての子ノードの局面が明るく表示 されます。例えば 一番上の子ノードの場合の PV は (0, 0)、(1, 1)、(1, 0)、(2, 0)、(0, 2)、(0, 1)、(2, 1)、(1, 2)、(2, 2)　となります。この局面には 8 種類の PV がありますが、PV が複数存在する場合はその中の 1 つだけを示すのが一般的だと思います。

下図ではゲーム開始時の局面で (0, 0) を着手した局面を選択 した場合の図です。この局面の 最善手は (1, 1) だけ なので、(1, 1) を着手した子ノードのみが明るく表示 され、その右にその後お互いが最善手を着手し続けた場合の局面の一覧が表示されます。従って、この局面の PV は (1, 1)、(1, 0)、(2, 0)、(0, 2)、(0, 1)、(2, 1)、(1, 2)、(2, 2)　のみ となります。

参考までに PV に関する Chess programming wiki を下記に示します。

置換表からの PV の計算

@ai_by_mmscore でデコレートされた ai_abs_dls は指定したノードの 子ノードをルートノードとする部分木に対して計算を行う ので、計算の際に利用した 置換表には指定したノードのデータは記録されません。実際に下記のプログラムで ゲーム開始時の局面 に対して ai_abs_dls で計算を行った際の 置換表 から ゲーム開始時の局面のデータを表示 しようとすると、実行結果のようにそのようなキーは存在しないという KeyError が発生 します。

print(tt[mb.board_to_str()])

実行結果

---------------------------------------------------------------------------
KeyError                                  Traceback (most recent call last)
Cell In[10], line 1
----> 1 print(tt[mb.board_to_str()])

KeyError: '.........'

そのため、最初の局面の最善手 は ai_abs_dls の 返り値の "bestmove" のキーの値に代入 されているので、それを利用 する必要があります。その後 は 置換表から最善手を取り出して着手し続ける ことで PV を表示 することができます。

下記は PV を計算して表示するプログラムです。

• 1 行目：先程の ai_abs_dls の返り値から最善手を取り出して bestmove に代入する
• 2 行目：PV を記録する変数を空の list で初期化する
• 3 行目：ゲームの決着がつくまで繰り返し処理を行う
• 4 行目：PV の要素に次の最善手を追加する
• 5 ~ 10 行目：次の最善手を表示し、その最善手を着手する。ただし、バグがあった場合に置換表に正しい最善手が記録されていない可能性があることを考慮し、着手しようとしたマスにマークが配置済の場合はメッセージを表示して処理を中断するようにした
• 11 行目：最善手を着手した局面を表示する
• 12 ~ 16 行目：置換表から mb の局面の最善手を取り出して bestmove に代入する。深さの上限を超えた局面 のデータは 置換表に登録されない ので、置換表に局面の情報が 登録されていない場合 は繰り返し 処理を終了する（2025/08/07 修正：15 行目が else になっていなかった点を修正しました）
• 17 行目：計算された PV を表示する

 1  bestmove = result["bestmove"]
 2  PV = []
 3  while mb.status == Marubatsu.PLAYING:
 4      PV.append(bestmove)
 5      print(bestmove)
 6      x, y = bestmove
 7      if mb.board[x][y] != Marubatsu.EMPTY:
 8          print("そのマスには着手済みです")
 9          break
10      mb.move(x, y)
11      print(mb)
12      boardtxt = mb.board_to_str()
13      if boardtxt in tt:
14          _, _, bestmove = tt[boardtxt]
15      else:
16          break
17  print(PV)

行番号のないプログラム

bestmove = result["bestmove"]
PV = []
while mb.status == Marubatsu.PLAYING:
    PV.append(bestmove)
    print(bestmove)
    x, y = bestmove
    if mb.board[x][y] != Marubatsu.EMPTY:
        print("そのマスには着手済みです")
        break
    mb.move(x, y)
    print(mb)
    boardtxt = mb.board_to_str()
    if boardtxt in tt:
        _, _, bestmove = tt[boardtxt]
    else:
        break
print(PV)

実行結果（最初の最善手はランダムに選択されるので、下記と異なる表示が行われる場合があります）

(0, 2)
Turn x
...
...
O..

(1, 1)
Turn o
...
.X.
o..

(1, 0)
Turn x
.O.
.x.
o..

(1, 0)
そのマスには着手済みです
[(0, 2), (1, 1), (1, 0), (1, 0)]

実行結果から、4 手目の最善手 が既に マークが配置されているマスに着手 を行おうとしているため、置換表に登録された 最善手が間違っている ことが確認できます。その原因については次回の記事で説明します。

このようなバグが発生する原因について余裕がある方は考えてみて下さい。なお、筆者も上記の実行結果を見るまでは先ほど修正した ai_abs_dls のプログラムが正しいと勘違いしていました。これまでに何度も説明しているように、実装したプログラムが正しく動作するかを確認することは非常に重要です。

今回の記事では置換表から PV を計算する手法を紹介しましたが、多くのゲームはゲーム木の規模が大きすぎるため置換表に計算したノードの情報をすべて記録することはできません。そのような場合は、置換表から PV を計算できるとは限らない点に注意が必要です。下記の PV に関する Chess Programming Wiki のリンク先には、この理由から PV を計算するという目的では置換表は一般的には利用されない（For this reason, the TT is generally not used to collect PV）と記述されているようです。

実際には探索を行う際に PV を計算するという手法が一般的だと思います。ただし、その場合は PV を計算する分だけ探索の処理に少し時間がかかるという小さな欠点があります。その手法については下記を参考にして下さい。

今回の記事のまとめ

今回の記事では 反復深化を利用した move ordering について説明し、move ordering を行うために 必要なデータを置換表に記録する処理を実装 しました。ただし、その処理にバグがあることが判明したので、次回の記事で修正することにします。

本記事で入力したプログラム

リンク	説明
marubatsu.ipynb	本記事で入力して実行した JupyterLab のファイル
ai.py	本記事で更新した ai_new.py

次回の記事

更新履歴

更新日時	更新内容
2025/08/07	PV を計算するプログラムの最後の if 文の else の部分が間違っていた点を修正しました

1. $d=1$ の場合は、それ以前に深さ制限探索が行われていないためです ↩

2. 変数名が best_moves と bestmove のように統一感がないのは、本記事を書き始めたころは best_moves のように単語の間を必ず _ 区切るようにしていたのに対し、記事を書いていくにつれていつのまにか筆者も気づかないうち bestmove のように区切らなくても意味が分かる場合は _ で区切らないように方針が変わったからです。統一感がない点が気になった方はどちらかに統一して下さい ↩

3. refutation move の日本語訳が見つからなかったのと、そのまま直訳しても意味がわからないと思いましたので日本語訳はつけませんでした。良い日本語訳をご存じの方がいればコメントなどで教えて頂ければ助かります ↩