目次と前回の記事

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

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

リンク	説明
marubatsu.py	Marubatsu、Marubatsu_GUI クラスの定義
ai.py	AI に関する関数
test.py	テストに関する関数
util.py	ユーティリティ関数の定義。現在は `gui_play` のみ定義されている
tree.py	ゲーム木に関する Node、Mbtree クラスの定義
gui.py	GUI に関する処理を行う基底クラスとなる GUI クラスの定義

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

スカウト法と move ordering

前回の記事では、αβ 法の効率を高める ために使われる手法として null window search を紹介しました。null window search を使った手法の一つに スカウト（scout）法¹ があります。スカウト法は以前の記事で説明した、子ノードの 評価値の計算の順番 を、max ノードでは最も評価値の高い（min ノードでは最も評価値の低い）と 思われる 子のノードを最初に行うように 並べ替える（order）ことで αβ 法の枝狩りの効率を向上させる、move ordering を前提とする手法 です。つまり、スカウト法 は move ordering を行う αβ 法の効率 を さらに上昇させる という手法です。

今回の記事ではこのスカウト法について説明しようと最初は考えていたのですが、スカウト法による枝狩りの効率の上昇を確認 するためには、move ordering を行う αβ 法 による枝狩りの 効率と比較する必要 があります。そこで、今回の記事では move ordering を行う αβ 法の AI の関数を定義²してその枝狩りの効率を確認し、次回の記事でスカウト法を実装してその効率を比較することにします。

move ordering の精度

上記の move ordering の説明で最も評価値の高いと 思われる と説明したのは、一般的には move ordering の精度（正確性）は 100 % ではないからです。従って move ordering によって 最も評価値が高い子ノードが先頭になるとは限りません。

その理由は、move ordering の精度が 100 % であれば、move ordering だけを使って最善手を計算することができる からです。αβ 法を利用した AI の 目的は最善手を求めること なので、move ordering の精度が 100 % であれば、αβ 法を利用する必要はありません。

なお、精度は状況によって さまざまな計算方法 があり、本記事では 正解率 を精度とすることにします。具体的には、子ノードの順番の 並べ替えを正しく行うことができる割合 のことを move ordering の精度 と呼ぶことにします。従って、move ordering の 精度が 100 % の場合は 必ず正しい順番で並べ替えが行われます。

精度として良く使われる他の指標には相対誤差があります。相対誤差は「絶対誤差／真の値」で計算できます。ただし、真の値 は 正確な値 を、絶対誤差 は 計算した値と真の値の差の絶対値 を表す用語です。また、計算や計測などによって求められた、真の値に近い値 と考えられる値のことを 近似値 と呼びます。

例えば真の値が 10、近似値が 101 の場合は、絶対誤差は 1 で、相対誤差は 1 / 100 = 1 % となります。この場合は相対誤差が 0 となった場合が最も精度が高くなります。

move ordering を行うアルゴリズムに求められる性質

move ordering は、何らかのアルゴリズムで 評価値が最も高い子ノードを計算 し、その子ノードが先頭になるように 合法手の順番を並べ替える 処理を行います。その際に、そのアルゴリズムが 以下のような性質を持つ ことが重要になります。その理由について少し考えてみて下さい。

評価値が最も高い子ノードを 短い時間で計算できる
評価値が最も高い子ノードの計算が ある程度以上の精度 を持つ。ここでいう精度とは、先程説明した 正解率 のことである

短い時間で計算できる必要がある理由 は、move ordering による 枝狩りの効率の上昇による処理時間の短縮よりも、move ordering のための 計算時間が上回ってしまう ことになり、全体の処理時間がかえって長くなってしまう からです。

ある程度以上の精度を持つ必要がある理由 は、精度が低いと、move ordering によって子ノードの評価値の順で うまく並べ替えることができなくなり、枝狩りの効率を高めることができなくなるからです。そのことは、以前の記事で 精度が異なる AI の関数 で 先頭の子ノードのみを入れ替えた場合 の 枝狩りの効率を比較 することで確認済です。

move ordering では数多くのアルゴリズムが考えられているので、本記事ではそのすべてを紹介することはできません。参考までに Chess programming wiki の move ordering のリンクを下記に紹介します。

move ordering のアルゴリズムの種類と本記事が採用するアルゴリズム

move ordering のアルゴリズムの中の有力な手法の一つに 反復深化（iterative deepening） という手法を利用して 最善手 を 効率よく高い精度で計算 するという手法がありますが、その手法は ゲームの決着がついたリーフノードの評価値を元にミニマックス値を計算する という手法では 利用することができない ので今回の記事では紹介しません。反復深化については必要があれば今後の記事で紹介したいと思いますが、興味がある方は参考までに wikipedia と Chess programming wiki の記事のリンクを紹介するので参照して下さい。

本記事では、move ordering について以前の記事で説明した、ルールベースの AI 計算した評価値を利用する という手法を利用することにします。その理由は、以下の通りです。

近似値を αβ 法と比較して短い時間で計算できる

αβ 法 ではミニマックス値を計算する際に枝狩りを効率よく行えた場合でも 数多くの子孫ノードの計算を行う必要 がありますが、本記事で作成したルールベースの AI では、子ノードのみの評価値の計算 を行なっているので αβ 法と比較して短い時間で計算できます。そのことは、下記のプログラムで ゲーム開始時の局面の最善手の計算時間を比較 することで確認することができます。興味がある方は他の局面でも比較してみて下さい。

まず、下記のプログラムで必要なインポートを行い、ゲーム開始時の局面のデータを計算します。比較対象としてインポートする AI は以下の 3 つです。

これまでに紹介した αβ 法の中で 枝狩りの効率が高く計算時間が短い、置換表付き αβ 法 で着手を選択する ai_abs_tt4
ルールベースの AI の中ですべての子ノードの評価値を 0 と計算する 最も処理が少ない、ランダムな着手を選択する ai2s
ルールベースの AI の中で 最も複雑 で、処理時間が長い と考えられる ai14s

上記の AI の関数のアルゴリズムの詳細についてはこちらの記事を参照して下さい。

from marubatsu import Marubatsu
from ai import ai_abs_tt4, ai2s, ai14s

mb = Marubatsu()

次に、下記のプログラムで %%timeit を使って、それぞれの AI の計算時間を計算します。

%%timeit
ai_abs_tt4(mb)

実行結果

310 ms ± 1.01 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

%%timeit
ai2s(mb)

実行結果

345 µs ± 753 ns per loop (mean ± std. dev. of 7 runs, 1,000 loops each)

%%timeit
ai14s(mb)

実行結果

519 µs ± 2.38 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)

ms は 1000 分の 1 秒、μs は ms の 1000 分の 1 の 100 万分の 1 秒です。ai2s のほうが ai14s よりも処理時間が短いですが、どちらのルールベースの AI も 置換表付き αβ 法の 約 1000 分の 1 という 充分に短い時間 で計算を行うことができること確認できました。

ルールベースの AI が様々な精度を持つ

当然ですが、AI が計算する評価値の精度は高ければ高い程 AI が強くなります。本記事で作成したルールベースの AI である ai1s ~ ai14s は、ランダムな着手を行う ai2s との対戦成績 からわかるように 様々な精度を持ちます。そのため、異なる精度の AI によって move ordering の効率がどのように変化するか を実際に比較して 確認することができます。

なお、これまでの記事で作成したルールベースの AI は いずれも強解決の AI ではない ので、それらの AI が計算した 最善手の精度は 100 % ではありません。例えば、弱解決の AI である ai14s は以前の記事で検証したように強解決の AI ではないので、ほとんどの局面で最善手を計算しますが、ほんの一部の局面では間違った最善手を計算します。

move ordering で行う子ノードの並べ替えの方法

max ノードと min ノードでは考え方は同じなので、本記事では以後は基本的に max ノードの場合のみの説明を行います。

以前の記事で説明したように move ordering は、max ノード では 最も評価値の高い子ノードが先頭 に来るように子ノードを 並べ替える ことで 枝狩りの効率が最も高くなります。

また、move ordering の精度が低いせいで 先頭の子ノードの評価値が最も高くならなかった場合 は、同様の理由でその 次の子ノードの評価値が最も高い場合 に枝狩りの効率が 最も高くなります。

そのため、子ノードの評価値を正しい大きさの順で計算できること³が move ordering の精度の高さにつながります。そこで、以後は AI が計算する 評価値の精度 を move ordering の精度と同じ意味で表記 することにします。

以前の記事では、ミニマックス法で計算されたゲーム木を使って本当の（最も評価値が高い）最善手の子ノードを先頭に移動する move_bestmove_to_head や、AI の関数が計算した最善手の子ノードを先頭に移動する move_ai_bestmove_to_head のように、最善手として計算された子ノードのみを先頭に移動する という並べ替えを行いました。本記事ではこの方法で並べ替えを行う move ordering を 先頭のみの move ordering と表記することにします。

先程言及した反復深化を利用した move ordering ではノードの評価値を計算する際に、子ノードの中で最善手である可能性が非常に高いノードをあらかじめ計算しておくことができるため、先頭のみの move ordering が使われるようです。

計算される子ノードの評価値の 精度が 100 % であれば先頭のみの move ordering で充分 ですが、先程説明したように通常は move ordering で計算する 子ノードの評価値の精度が 100 % になることはない ので、move ordering の結果、最も評価値の高い子ノードが先頭にならない場合 があります。その場合は 2 つ目の子ノードは並べ替えが行われていない ため、評価値が最も高くなるとは限らない という問題が発生します。

この問題は、先頭の子ノードだけでなく、すべての子ノードを対象 にして、計算された評価値の順に 並べかえる ことで改善することができます。その場合は、最も評価値が高い子ノードが先頭にならない場合でも、次の子ノードの評価値が最も高くなる可能性が高くなる からです。以後はこの方法で並べ替えを行う move ordering を 全ノードの move ordering と表記することにします。

全ノードの move ordering では、すべての子ノードの評価値を計算する必要がある 点と、すべての子ノードを対象に並べ替えを行う必要がある という点で先頭のみの move ordering よりも 処理に時間がかるという欠点があります。ただし、本記事でこれから実装する、ルールベースの AI を利用して move ordering 最善手を計算する場合 は、その過程ですべての子ノードの評価値を必ず計算する ので、前者の欠点は問題にはなりません。後者の問題は並べ替える子ノードの数が少ない場合は全体の処理時間と比較すると 無視できるほど短く計算できる ので大きな問題ではありません。

本記事では先頭のみの move ordering と全ノードの move ordering の 両方を実装する ことで、枝狩りの効率の差を比較する ことにします。

反復深化を利用した move ordering であらかじめ計算しておくことができるのは、最善手である可能性が高い子ノードだけです。また、高い精度で最善手を計算することができるので、全ノードの move ordering は利用されないようです。

move ordering を行う AI の関数の定義

これまでは、αβ 法で着手を選択する AI を定義する際 に、最短の勝利を目指すかどうか、置換表の利用の有無などの設定ごとに 別々の AI の関数を作ってきました が、それらの設定ごとに move ordering を行う AI を別々に定義するのは大変なので、以下の設定を仮引数で行うことができる AI の関数を定義 する事にします。

最短の勝利を目指すかどうか
ルートノードの評価値を計算する際の α 値と β 値の初期値を設定するかどうか
置換表を利用するかどうか
move ordering を行うかどうか
move ordering を行う場合は、全ノードの move ordering を行うかどうか

また、これまでの AI の関数では、キーワード引数 debug=True を記述することで 評価値を計算したノードの数を表示する という機能を持っていましたが、表示された数値をその後のプログラムで利用することはできませんでした。そこで、評価値を計算したノードの数を返り値として返す機能を持つ ように実装することにします。

下記は、定義する AI の関数の仕様 です。なお、下記の関数は、@ai_by_score のデコレータ式を先頭に記述することで AI の関数として着手を選択するようになります。

名前：αβ 法で評価値を計算する AI で、これまでに説明したすべて（all）の機能を持つので ai_abs_all とする
処理：指定した設定で αβ 法で局面の評価値を計算する。また、評価値を計算したノードの数を返す機能を持つ
入力：下記の表の仮引数を持つ
出力：calc_count が False の場合は評価値を、False の場合は評価値を計算したノードの数を返す

仮引数	デフォルト値	意味
`mb`	なし	評価値を計算する局面
`debug`	`False`	`True` の場合にデバッグの表示を行う
`shortest_victory`	`False`	`True` の場合に最短の勝利を目指す評価値を計算する
`init_ab`	`False`	`True` の場合にルートノードの α 値と β 値の初期値を評価値の最小値と最大値に設定する
`use_tt`	`False`	`True` の場合に置換表を利用する
`ai_for_mo`	`None`	move ordering を行うための AI の関数。`None` の場合は move ordering を行わない
`params`	`{}`	`ai_for_mo` を呼び出す際に記述する実引数の dict
`sort_allnodes`	`False`	`True` の場合に全ノードの move ordering を行う
`calc_count`	`False`	`True` の場合に返り値として評価値を計算したノードの数を返す

`ai_abs_all` の定義

先頭の子ノードを最善手の子ノードに並べ替える という処理は以前の記事で move_ai_bestmove_to_head で実装したので、それを参考に実装することができます。子ノード全体を並べ替える処理 については説明が必要なので 後で実装することにします。

ai_abs_all は置換表付き αβ 法で評価値を計算する ai_abs_tt4 を修正して、以下のように定義することができます。

5 ~ 7 行目：関数の名前を ai_abs_all に修正し、上記の表の仮引数を追加する
10 ~ 25、36 ~ 48 行目：置換表に関する処理を if use_tt: のブロックの中に記述するようにする
31 ~ 34 行目：ai_for_mo が None でない場合に、32 行目で ai_for_mo が計算した最善手の子ノードを、33、34 行目で先頭の子ノードと入れ替える処理を行う。この部分の処理は以前の記事で定義した move_ai_bestmove_to_head メソッドの処理とほぼ同じである
53 ~ 56 行目：ルートノードの評価値を計算する際の α 値と β 値の初期値を計算し、それを使ってルートノードの評価値を計算するように修正する
58、59 行目：calc_count が True の場合に評価値を計算したノードの数を返り値として返すようにする

 1  from ai import ai_by_score, dprint
 2  from copy import deepcopy
 3  
 4  @ai_by_score
 5  def ai_abs_all(mb, debug=False, shortest_victory=False,
 6                 init_ab=False, use_tt=False, ai_for_mo=None,
 7                 params={}, sort_allnodes=False, calc_count=False):        
 8      count = 0
 9      def ab_search(mborig, tt, alpha=float("-inf"), beta=float("inf")):
元と同じなので省略
10          if use_tt:
11              boardtxt = mborig.board_to_str()
12              if boardtxt in tt:
13                  lower_bound, upper_bound = tt[boardtxt]
14                  if lower_bound == upper_bound:
15                      return lower_bound
16                  elif upper_bound <= alpha:
17                      return upper_bound
18                  elif beta <= lower_bound:
19                      return lower_bound
20                  else:
21                      alpha = max(alpha, lower_bound)
22                      beta = min(beta, upper_bound)
23              else:
24                  lower_bound = min_score
25                  upper_bound = max_score
26          
27          alphaorig = alpha
28          betaorig = beta
29  
30          legal_moves = mborig.calc_legal_moves()
31          if ai_for_mo is not None:
32              bestmove = ai_for_mo(mborig, **params)
33              index = legal_moves.index(bestmove)
34              legal_moves[0], legal_moves[index] = legal_moves[index], legal_moves[0]            
35          if mborig.turn == Marubatsu.CIRCLE:
元と同じなので省略
36          if use_tt:
37              from util import calc_same_boardtexts
38      
39              boardtxtlist = calc_same_boardtexts(mborig)
40              if score <= alphaorig:
41                  upper_bound = score
42              elif score < betaorig:
43                  lower_bound = score
44                  upper_bound = score
45              else:
46                  lower_bound = score
47              for boardtxt in boardtxtlist:
48                  tt[boardtxt] = (lower_bound, upper_bound)
49          return score
50                  
51      min_score = -2 if shortest_victory else -1
52      max_score = 3 if shortest_victory else 1
53      alpha = min_score if init_ab else float("-inf")
54      beta = max_score if init_ab else float("inf")
55  
56      score = ab_search(mb, {}, alpha=alpha, beta=beta)
57      dprint(debug, "count =", count)
58      if calc_count:
59          return count
60      if mb.turn == Marubatsu.CIRCLE:
61          score *= -1
62      return score

行番号のないプログラム

from ai import ai_by_score, dprint
from copy import deepcopy

@ai_by_score
def ai_abs_all(mb, debug=False, shortest_victory=False,
               init_ab=False, use_tt=False, ai_for_mo=None,
               params={}, sort_allnodes=False, calc_count=False):        
    count = 0
    def ab_search(mborig, tt, alpha=float("-inf"), beta=float("inf")):
        nonlocal count
        count += 1
        if mborig.status == Marubatsu.CIRCLE:
            return (11 - mborig.move_count) / 2 if shortest_victory else 1
        elif mborig.status == Marubatsu.CROSS:
            return (mborig.move_count - 10) / 2 if shortest_victory else -1
        elif mborig.status == Marubatsu.DRAW:
            return 0
        
        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 ai_for_mo is not None:
            bestmove = ai_for_mo(mborig, **params)
            index = legal_moves.index(bestmove)
            legal_moves[0], legal_moves[index] = legal_moves[index], legal_moves[0]            
        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, 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, tt, alpha, beta))
                if score <= alpha:
                    break
                beta = min(beta, score)   
            
        if use_tt:
            from util import calc_same_boardtexts

            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 = -2 if shortest_victory else -1
    max_score = 3 if shortest_victory else 1
    alpha = min_score if init_ab else float("-inf")
    beta = max_score if init_ab else float("inf")

    score = ab_search(mb, {}, alpha=alpha, beta=beta)
    dprint(debug, "count =", count)
    if calc_count:
        return count
    if mb.turn == Marubatsu.CIRCLE:
        score *= -1
    return score

修正箇所

from ai import ai_by_score, dprint
from copy import deepcopy

@ai_by_score
-def ab_search(mborig, tt, alpha=float("-inf"), beta=float("inf")):
+def ai_abs_all(mb, debug=False, shortest_victory=False,
+              init_ab=False, use_tt=False, ai_for_mo=None,
+              params={}, sort_allnodes=False, calc_count=False):        
    count = 0
    def ab_search(mborig, tt, alpha=float("-inf"), beta=float("inf")):
元と同じなので省略
-       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
+       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 ai_for_mo is not None:
+           bestmove = ai_for_mo(mborig, **params)
+           index = legal_moves.index(bestmove)
+           legal_moves[0], legal_moves[index] = legal_moves[index], legal_moves[0]            
        if mborig.turn == Marubatsu.CIRCLE:
元と同じなので省略
-       from util import calc_same_boardtexts

-       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)
+       if use_tt:
+           from util import calc_same_boardtexts
   
+           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 = -2 if shortest_victory else -1
    max_score = 3 if shortest_victory else 1
+   alpha = min_score if init_ab else float("-inf")
+   beta = max_score if init_ab else float("inf")

-   score = ab_search(mb, {}, alpha=min_score, beta=max_score)
+   score = ab_search(mb, {}, alpha=alpha, beta=beta)
    dprint(debug, "count =", count)
+   if calc_count:
+       return count
    if mb.turn == Marubatsu.CIRCLE:
        score *= -1
    return score

上記の定義後に、下記のプログラムを実行することで、まだ実装していない sort_allnodes 以外のすべての設定の組み合わせ で ai_abs_all が 強解決の AI であることを確認 することができます。move ordering で利用する AI としては ai2s と ai14s を採用しました。

なお、実行結果は長いので途中から省略していますが、すべての場合で強解決であることを表す 100 % が表示されます。

3 ~ 6 行目：for 文を入れ子にすることで、すべての組み合わせに対して 7 ~ 14 行目のブロックを実行する
7 行目：設定を表示する
8 ~ 13 行目：ai_abs_all を呼び出す際のパラメータを params に代入する
14 行目：Check_solved.is_strongly_solved 呼び出して、params の実引数を記述して呼び出した ai_abs_all が強解決の AI であるかどうかを確認する

 1  from util import Check_solved
 2  
 3  for ai_for_mo in [None, ai2s, ai14s]:
 4      for shortest_victory in [False, True]:
 5          for use_tt in [False, True]:
 6              for init_ab in [False, True]:
 7                  print(f"ai_for_mo: {ai_for_mo}, sv: {shortest_victory}, use_tt: {use_tt}, init_ab: {init_ab}")
 8                  params = {
 9                      "ai_for_mo": ai_for_mo,
10                      "shortest_victory": shortest_victory,
11                      "init_ab": init_ab,
12                      "use_tt": use_tt,
13                  }
14                  Check_solved.is_strongly_solved(ai_abs_all, params=params)

行番号のないプログラム

from util import Check_solved

for ai_for_mo in [None, ai2s, ai14s]:
    for shortest_victory in [False, True]:
        for use_tt in [False, True]:
            for init_ab in [False, True]:
                print(f"ai_for_mo: {ai_for_mo}, sv: {shortest_victory}, use_tt: {use_tt}, init_ab: {init_ab}")
                params = {
                    "ai_for_mo": ai_for_mo,
                    "shortest_victory": shortest_victory,
                    "init_ab": init_ab,
                    "use_tt": use_tt,
                }
                Check_solved.is_strongly_solved(ai_abs_all, params=params)

実行結果

ai_for_mo: None, sv: False, use_tt: False, init_ab: False
  0%|          | 0/431 [00:00<?, ?it/s]
100%|██████████| 431/431 [00:03<00:00, 108.73it/s]
431/431 100.00%
ai_for_mo: None, sv: False, use_tt: False, init_ab: True
100%|██████████| 431/431 [00:03<00:00, 140.83it/s]
431/431 100.00%
略
ai_for_mo: <function ai14s at 0x00000216EC395260>, sv: True, use_tt: True, init_ab: True
100%|██████████| 431/431 [00:04<00:00, 86.67it/s] 
431/431 100.00%

枝狩りの効率の確認

次に、下記のプログラムを実行して、ゲーム開始時の局面 の評価値を上記と同様の設定の組み合わせで計算した際に 評価値が計算されるノードの数を計算 します。なお、評価値が計算されたノードの数を返り値とするため には、指定したノードの評価値を計算することを表す calc_score=True と、評価値ではなく計算されたノードの数を返すようにすることを表す calc_count=True の 両方を記述する必要がある 点に注意して下さい。

calc_count=True だけを記述 した場合は、@ai_by_score の中で定義されたラッパー関数 wrapper 内で、評価値ではなく 計算されたノードの数を使って着手を選択する という、意図しない処理 が行われます。

ただし、move ordering で利用する AI は、下記の理由から下記の 4 つを選択しました。

ai1s：前にある子ノードのほうが高い評価値が計算されるので、実質的に move ordering が行なわれない
ai2s：すべてのノードで 0 を計算するので、でたらめな move ordering が行なわれる
ai10s：ai10s は弱解決の AI ではない ので ai14s より低い精度 の move ordering が行なわれる
ai14s：完璧ではないが、弱解決 で ほぼ完ぺきな精度 で move ordering が行われる

なお、ai10s VS ai2s の対戦成績は 91.5 %、ai14s VS ai2s の対戦成績は 93.9 % なので ai10s はかなり強い AI であり、その精度は高い と考えられます

from ai import ai10s

for ai_for_mo in [None, ai2s, ai10s, ai14s]:
    for shortest_victory in [False, True]:
        for init_ab in [False, True]:
            for use_tt in [False, True]:
                print(f"ai_for_mo: {ai_for_mo}, sv: {shortest_victory}, init_ab: {init_ab}, use_tt: {use_tt}")
                print("count=", ai_abs_all(mb, ai_for_mo=ai_for_mo,
                                          shortest_victory=shortest_victory,
                                          init_ab=init_ab, use_tt=use_tt,
                                          calc_score=True, calc_count=True))

実行結果

ai_for_mo: None, sv: False, init_ab: False, use_tt: False
count= 18297
ai_for_mo: None, sv: False, init_ab: True, use_tt: False
count= 16811
ai_for_mo: None, sv: False, init_ab: False, use_tt: True
count= 1054
略

実行結果を表にまとめると以下のようになります。一番上の行の ab は init_ab、tt は use_tt の値で〇は True、× は False を表します。リンクになっている数値は、過去の記事でその値を計算した記事へのリンクで、そのことからそれらの値が正しく計算されていることが確認できます。なお、ai1s 以外 の AI は、同じ評価値 が計算される 合法手が複数ある場合 はその中から ランダムに最善手を選択する ので、上記のプログラムを実行する度に 実行結果が若干変化する可能性 があります。

最短の勝利を目指さない（shortest_victory=False）場合

	ab × tt ×	ab 〇 tt x	ab × tt 〇	ab 〇 tt 〇
mo なし	18297	16811	1054	832
`ai1s`	18297	16811	1054	832
`ai2s`	14810	11274	884	734
`ai10s`	2267	1980	274	270
`ai14s`	1496	1496	234	239

最短の勝利を目指す（shortest_victory=True）場合

	ab × tt ×	ab 〇 tt x	ab × tt 〇	ab 〇 tt 〇
mo なし	20866	20484	1275	1242
`ai1s`	20866	20484	1275	1242
`ai2s`	17919	17262	1642	1246
`ai10s`	2189	2232	261	277
`ai14s`	1496	1496	234	234

move ordering の有無や AI の種類に関係なく α 値と β 値の初期値を設定 したほうが 多くの場合で高い枝狩りの効率 を持つことが確認できます。また、置換表を利用 したほうが 枝狩りの効率がかなり高くなる ことが確認できます。これらの結果は、これまでの記事で説明した通り なので、ai_abs_all が この 2 つの設定を正しく計算する ことが確認できました。

ai1s は前にある子ノードのほうが高い評価値が計算されるので、実質的に move ordering が行なわれません。従って、上記の表では mo なしと ai_1s の結果が同じ になります。

上記の実行結果では ai1s より ai2s のほうが枝狩りの効率が 高くなる場合と低くなる場合 がありますが、これは ai2s が でたらめな move ordering を行うので 運が良ければ枝狩りの効率が高く なり、運が悪ければ枝狩りの効率が悪く なるからです。

高い精度 で評価値を計算する ai10s と、弱解決で さらに高い精度 で評価値を計算する ai14s は ai1s よりかなり 枝狩りの効率が良く、精度が高い ai14s のほうが ai10s よりも枝狩りの効率が高い ことが確認できます。

上記から、move ordering の精度 は確かに 枝狩りの効率に大きな影響を与える ことがわかります。このことは以前の記事で α 値と β 値の初期設定を行わず、置換表を利用しない場合で確認済ですが、上記ではそれらの設定を行った場合についての確認を行いました。

全ノードの move ordering の実装

先頭のみの move ordering の実装が正しく行われたことが確認できたので、次は 全ノードの move ordering を実装します。

AI が計算する子ノードの評価値 は、下記のプログラムのように、AI の関数の実引数に analyze=True を記述して呼び出すことで計算することができます。なお、実行結果を見やすくするために pprint を使って表示を行っています。

from pprint import pprint

result = ai14s(mb, analyze=True)
pprint(result)

実行結果

{'candidate': [(1, 1)],
 'score_by_move': {(0, 0): 1.5,
                   (0, 1): 1.0,
                   (0, 2): 1.5,
                   (1, 0): 1.0,
                   (1, 1): 2.0,
                   (1, 2): 1.0,
                   (2, 0): 1.5,
                   (2, 1): 1.0,
                   (2, 2): 1.5}}

実行結果の中で、それぞれの合法手を着手した際の評価値 は、score_by_move というキーの値の代入されているので、下記のプログラムでそれを表示すると、その内容は 合法手をキー とし、キーの値に その合法手を着手した際の局面の 評価値が代入 された dict であることがわかります。

score_by_move = result["score_by_move"]
pprint(score_by_move)

実行結果

{(0, 0): 1.5,
 (0, 1): 1.0,
 (0, 2): 1.5,
 (1, 0): 1.0,
 (1, 1): 2.0,
 (1, 2): 1.0,
 (2, 0): 1.5,
 (2, 1): 1.0,
 (2, 2): 1.5}

従って、上記の dict のキー を、キーの値の順で並べ替える ことで、AI が計算した評価値の順で合法手の一覧を並べ替えることができます。

以前の記事では、list の sort メソッド や組み込み関数 sorted を利用して list の要素を特定の基準で並べ替える 方法を紹介しましたが、残念ながら dict は sort メソッドを持たない ので、sort メソッドでは dict の要素を並べ替えることはできません。

また、dict に対して下記のプログラムのように sorted を使って並べ替えを行うと dict のキーの値ではなく、dict のキーのみが並べ替えられる ためうまくいきません。なお、以前の記事で説明したように、sorted の返り値は list になるので、下記の実行結果は dict ではなく list になる点にも注意が必要です。

pprint(sorted(score_by_move))

実行結果

[(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (2, 0), (2, 1), (2, 2)]

dict の要素の並べ替え

dict の要素 は下記の手順で並べ替えることができます。

dict を、以下のような要素を持つ list に変換 する
- dict のキーと キーの値 を要素として持つ tuple
sort メソッドまたは組み込み関数 sorted を利用してその list を、tuple のキーの値を表す要素の順 で 並べ替える
並べ替えた list を dict に変換する

dict からキーと キーの値 を要素として持つ tuple を 順番に取り出す という処理は、dict の items メソッドを利用して下記のプログラムのように記述することができます。

for item in score_by_move.items():
    print(item)

実行結果

((0, 0), 1.5)
((1, 0), 1.0)
((2, 0), 1.5)
((0, 1), 1.0)
((1, 1), 2.0)
((2, 1), 1.0)
((0, 2), 1.5)
((1, 2), 1.0)
((2, 2), 1.5)

このことから、dict の items メソッド が dict を上記の 手順 1 のような list に変換する処理 だと 勘違いされがち ですが、items メソッドの 返り値 は for 文で利用できるという意味では list と似ていますが、list とは異なるデータです。実際に、下記のプログラムのように items メソッドの返り値を list だと考えて 0 番の要素を取り出して 表示しようとすると エラーが発生 します。

items = score_by_move.items()
items[0]

実行結果

---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
Cell In[12], line 2
      1 items = score_by_move.items()
----> 2 items[0]

TypeError: 'dict_items' object is not subscriptable

上記のエラーメッセージは dict の items メソッドの返り値が list ではないので list のように [] を使って要素を取り出すことができないという意味を表します。なお、subscript は、$ x_1 $ の 1 のような、数学の変数の右下に小さく表示する 下付き文字 のことで、同じ名前 の変数で 複数の数値を区別して扱う 際に使用します。python では、list や dict の右に記述する [] によって要素を参照する仕組みのことを指します。

dict の items メソッドの返り値 は、下記のプログラムの実行結果のように組み込み関数 list の実引数に記述して呼び出す ことで、list に変換 することができます。

score_by_move_list = list(items)
pprint(score_by_move_list)

実行結果

[((0, 0), 1.5),
 ((1, 0), 1.0),
 ((2, 0), 1.5),
 ((0, 1), 1.0),
 ((1, 1), 2.0),
 ((2, 1), 1.0),
 ((0, 2), 1.5),
 ((1, 2), 1.0),
 ((2, 2), 1.5)]

list の `sort` メソッドを利用した並べ替え

dict を list に変換 したので、以前の記事で紹介した list の sort メソッドや組み込み関数 sorted を利用してキーの値の順で list の要素を並べ替えることができます。下記は sort メソッドの場合のプログラムで、実行結果のように キーの値の小さい順で並べ替え られます。

下記のプログラムでは以前の記事で説明した ラムダ式 を使って list の要素に代入された tuple の中で、評価値が代入されている 1 番の要素を使って並べ替え を行っています。ラムダ式の lambda x:x[1] の中の x が list の要素 を、x[1] が並べ替えの基準として利用する値 を表します。

score_by_move_list.sort(key=lambda x:x[1])
pprint(score_by_move_list)

実行結果

[((1, 0), 1.0),
 ((0, 1), 1.0),
 ((2, 1), 1.0),
 ((1, 2), 1.0),
 ((0, 0), 1.5),
 ((2, 0), 1.5),
 ((0, 2), 1.5),
 ((2, 2), 1.5),
 ((1, 1), 2.0)]

組み込み関数 `sorted` を利用した並べ替え

組み込み関数 sorted を利用する場合は、下記のプログラムのように記述します。

score_by_move_list = sorted(items, key=lambda x:x[1])
pprint(score_by_move_list)

実行結果

[((1, 0), 1.0),
 ((0, 1), 1.0),
 ((2, 1), 1.0),
 ((1, 2), 1.0),
 ((0, 0), 1.5),
 ((2, 0), 1.5),
 ((0, 2), 1.5),
 ((2, 2), 1.5),
 ((1, 1), 2.0)]

また、組み込み関数 sorted は list だけでなく、反復可能オブジェクト の並べ替えを行うことができます。dict の items メソッドの 返り値は反復可能オブジェクト なので、下記のプログラムのように list に変換せずに 直接 dict の items メソッドの返り値を使って並べ替え を行うことができます。また、sorted の返り値 は、並べ替えるデータの種類に関わらず list になる ので、下記のプログラム尾ように組み込み関数 list を利用しなくても良いという利点 があります。上記の性質から、dict の要素の並べ替えを行う場合 は、sorted を利用したほうがプログラムが 少し簡潔 になります。

score_by_move_list = sorted(score_by_move.items(), key=lambda x:x[1])
pprint(ordered_score_by_move_list)

実行結果

[((1, 0), 1.0),
 ((0, 1), 1.0),
 ((2, 1), 1.0),
 ((1, 2), 1.0),
 ((0, 0), 1.5),
 ((2, 0), 1.5),
 ((0, 2), 1.5),
 ((2, 2), 1.5),
 ((1, 1), 2.0)]

キーの順番での並べ替えと、大きい順の並べ替え

本記事では利用しませんが、dict のキーの値ではなく、キーの順番で並べ替えを行う場合 は下記のプログラムのようにラムダ式の中で 並べ替えの基準を表す部分 に dict のキーを表す x[0] を記述 します。

score_by_move_list.sort(key=lambda x:x[0])
pprint(score_by_move_list)

実行結果

[((0, 0), 1.5),
 ((0, 1), 1.0),
 ((0, 2), 1.5),
 ((1, 0), 1.0),
 ((1, 1), 2.0),
 ((1, 2), 1.0),
 ((2, 0), 1.5),
 ((2, 1), 1.0),
 ((2, 2), 1.5)]

組み込み関数 sorted でも同様のラムダ式を記述することで並べ替えを行うことができますが、下記のプログラムのように 実引数に dict の items メソッドの返り値を直接記述したほうが簡単 です。なお、score_by_move のキーは小さい順で並んでいるので、下記のプログラムでは キーワード引数 reverse=True を記述して逆順に並べ替えました。

pprint(sorted(score_by_move.items(), reverse=True))

実行結果

[((2, 2), 1.5),
 ((2, 1), 1.0),
 ((2, 0), 1.5),
 ((1, 2), 1.0),
 ((1, 1), 2.0),
 ((1, 0), 1.0),
 ((0, 2), 1.5),
 ((0, 1), 1.0),
 ((0, 0), 1.5)]

キーの値の 大きい順で並べ替えたい場合 は、下記のプログラムのように キーワード引数 reverse=True を記述 します。

score_by_move_list.sort(key=lambda x:x[1], reverse=True)
pprint(score_by_move_list)

実行結果

[((1, 1), 2.0),
 ((0, 0), 1.5),
 ((0, 2), 1.5),
 ((2, 0), 1.5),
 ((2, 2), 1.5),
 ((0, 1), 1.0),
 ((1, 0), 1.0),
 ((1, 2), 1.0),
 ((2, 1), 1.0)]

こうして並べ替えが行われた list を dict に戻す方法 は簡単で、下記のプログラムのように 組み込み関数 dict の実引数に記述して呼び出す という処理を記述するだけです。変数名の ordered は、並べ替えられという意味の英語です。なお、pprint はキーワード引数 sort_dicts=False を記述しないと キーの内容の順で並べ替えられて表示されてしまう ため記述しました。

ordered_score_by_move = dict(score_by_move_list)
pprint(ordered_score_by_move, sort_dicts=False)

実行結果

{(1, 1): 2.0,
 (0, 0): 1.5,
 (0, 2): 1.5,
 (2, 0): 1.5,
 (2, 2): 1.5,
 (0, 1): 1.0,
 (1, 0): 1.0,
 (1, 2): 1.0,
 (2, 1): 1.0}

下記は sort_dicts=False を記述しなかった場合で、キーの順で並べ替えて表示されています。

pprint(ordered_score_by_move)

実行結果

{(0, 0): 1.5,
 (0, 1): 1.0,
 (0, 2): 1.5,
 (1, 0): 1.0,
 (1, 1): 2.0,
 (1, 2): 1.0,
 (2, 0): 1.5,
 (2, 1): 1.0,
 (2, 2): 1.5}

キーの値による dict のキーの並べ替え

上記では dict の要素をキーの値の順で並べ替え ましたが、move ordering で必要となる のはそのような dict ではなく、並べ替えられた合法手のみを要素として持つ list です。従って、上記の 手順 3 を実行して list を dict に戻す必要はありません。

その代わりに、手順 2 で並べ替えられた list から 合法手のみを要素として持つ list を下記のプログラムで list 内包表記を使って 作成する処理 を行います。

ordered_move_list = [x[0] for x in score_by_move_list]
print(ordered_move_list)

実行結果

[(1, 1), (0, 0), (0, 2), (2, 0), (2, 2), (0, 1), (1, 0), (1, 2), (2, 1)]

dict に変換した後で、下記のプログラムで list に変換するという方法もあります。

ordered_move_list = list(ordered_score_by_move.keys())
print(ordered_move_list)

実行結果

[(1, 1), (0, 0), (0, 2), (2, 0), (2, 2), (0, 1), (1, 0), (1, 2), (2, 1)]

処理のまとめ

下記は上記で説明した処理をまとめたプログラムです。なお、評価値は高い順に並べる必要がある ので、sort メソッドのキーワード引数に reverse=True を記述 しました。

result = ai14s(mb, analyze=True)
score_by_move = result["score_by_move"]
items = score_by_move.items()
score_by_move_list = list(items)
score_by_move_list.sort(key=lambda x:x[1], reverse=True)
orderd_move_list = [x[0] for x in score_by_move_list]
print(orderd_move_list)

実行結果

[(1, 1), (0, 0), (2, 0), (0, 2), (2, 2), (1, 0), (0, 1), (2, 1), (1, 2)]

上記のプログラムはかなり冗長なので、下記のプログラムのように、いくつかの処理をまとめる ことにします。

1 行目：上記の 1、2 行目の処理を 1 行でまとめた
2 行目：先程説明した、組み込み関数 sorted を利用した並べ替えに修正した

1  score_by_move = ai14s(mb, analyze=True)["score_by_move"]
2  score_by_move_list = sorted(score_by_move.items(), key=lambda x:x[1], reverse=True)
3  orderd_move_list = [x[0] for x in score_by_move_list]
4  print(orderd_move_list)

行番号のないプログラム

score_by_move = ai14s(mb, analyze=True)["score_by_move"]
score_by_move_list = sorted(score_by_move.items(), key=lambda x:x[1], reverse=True)
orderd_move_list = [x[0] for x in score_by_move_list]
print(orderd_move_list)

修正箇所

-result = ai14s(mb, analyze=True)
-score_by_move = result["score_by_move"]
+score_by_move = ai14s(mb, analyze=True)["score_by_move"]
-items = score_by_move.items()
-score_by_move_list = list(items)
-score_by_move_list.sort(key=lambda x:x[1], reverse=True)
+score_by_move_list = sorted(score_by_move.items(), key=lambda x:x[1], reverse=True)
orderd_move_list = [x[0] for x in score_by_move_list]
print(orderd_move_list)

実行結果

[(1, 1), (0, 0), (2, 0), (0, 2), (2, 2), (1, 0), (0, 1), (2, 1), (1, 2)]

下記のプログラムのように、無理やり 1 行のプログラムにまとめることもできますが、プログラムがわかりづらくなるので本記事では採用しません。

orderd_move_list = [x[0] for x in sorted(ai14s(mb, analyze=True)["score_by_move"].items(), key=lambda x:x[1], reverse=True)]
print(orderd_move_list)

実行結果

[(1, 1), (0, 0), (2, 0), (0, 2), (2, 2), (1, 0), (0, 1), (2, 1), (1, 2)]

`ai_abs_all` の修正

AI が計算した評価値の順で子ノードの評価値を並べ替える方法がわかったので、ai_abs_all を下記のプログラムのように修正します。

9 ~ 12 行目:sort_allnodes が True の場合は上記で説明した方法で評価値の高い順で合法手を並べ替えた list を計算し、legal_moves という変数に代入する。なお、@ai_by_score のデコレータ式でデコレートする関数 は、max ノードでも min ノードでも 常に高いほうが有利であるという意味の評価値を計算する ので、常に評価値の高い順 に並べ替えれば良い
13 ~ 17 行目：sort_allnodes が False の場合は修正前と同じ処理を行う

 1  @ai_by_score
 2  def ai_abs_all(mb, debug=False, shortest_victory=False,
 3                 init_ab=False, use_tt=False, ai_for_mo=None,
 4                 params={}, sort_allnodes=False, calc_count=False):        
 5      count = 0
 6      def ab_search(mborig, tt, alpha=float("-inf"), beta=float("inf")):
元と同じなので省略
 7          legal_moves = mborig.calc_legal_moves()
 8          if ai_for_mo is not None:
 9              if sort_allnodes:
10                  score_by_move = ai_for_mo(mborig, analyze=True, **params)["score_by_move"]
11                  score_by_move_list = sorted(score_by_move.items(), key=lambda x:x[1], reverse=True)
12                  legal_moves = [x[0] for x in score_by_move_list]
13              else:
14                  legal_moves = mborig.calc_legal_moves()
15                  bestmove = ai_for_mo(mborig, **params)
16                  index = legal_moves.index(bestmove)
17                  legal_moves[0], legal_moves[index] = legal_moves[index], legal_moves[0]
18          if mborig.turn == Marubatsu.CIRCLE:
元と同じなので省略

行番号のないプログラム

@ai_by_score
def ai_abs_all(mb, debug=False, shortest_victory=False,
               init_ab=False, use_tt=False, ai_for_mo=None,
               params={}, sort_allnodes=False, calc_count=False):        
    count = 0
    def ab_search(mborig, tt, alpha=float("-inf"), beta=float("inf")):
        nonlocal count
        count += 1
        if mborig.status == Marubatsu.CIRCLE:
            return (11 - mborig.move_count) / 2 if shortest_victory else 1
        elif mborig.status == Marubatsu.CROSS:
            return (mborig.move_count - 10) / 2 if shortest_victory else -1
        elif mborig.status == Marubatsu.DRAW:
            return 0
        
        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 ai_for_mo is not None:
            if sort_allnodes:
                score_by_move = ai_for_mo(mborig, analyze=True, **params)["score_by_move"]
                score_by_move_list = sorted(score_by_move.items(), key=lambda x:x[1], reverse=True)
                legal_moves = [x[0] for x in score_by_move_list]
            else:
                legal_moves = mborig.calc_legal_moves()
                bestmove = ai_for_mo(mborig, **params)
                index = legal_moves.index(bestmove)
                legal_moves[0], legal_moves[index] = legal_moves[index], legal_moves[0]
        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, 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, 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 = -2 if shortest_victory else -1
    max_score = 3 if shortest_victory else 1
    alpha = min_score if init_ab else float("-inf")
    beta = max_score if init_ab else float("inf")

    score = ab_search(mb, {}, alpha=alpha, beta=beta)
    dprint(debug, "count =", count)
    if calc_count:
        return count
    if mb.turn == Marubatsu.CIRCLE:
        score *= -1
    return score

修正箇所

@ai_by_score
def ai_abs_all(mb, debug=False, shortest_victory=False,
               init_ab=False, use_tt=False, ai_for_mo=None,
               params={}, sort_allnodes=False, calc_count=False):        
    count = 0
    def ab_search(mborig, tt, alpha=float("-inf"), beta=float("inf")):
元と同じなので省略
        legal_moves = mborig.calc_legal_moves()
        if ai_for_mo is not None:
-           legal_moves = mborig.calc_legal_moves()
-           bestmove = ai_for_mo(mborig, **params)
-           index = legal_moves.index(bestmove)
-           legal_moves[0], legal_moves[index] = legal_moves[index], legal_moves[0]
+           if sort_allnodes:
+               score_by_move = ai_for_mo(mborig, analyze=True, **params)["score_by_move"]
+               score_by_move_list = sorted(score_by_move.items(), key=lambda x:x[1], reverse=True)
+               legal_moves = [x[0] for x in score_by_move_list]
+           else:
+               legal_moves = mborig.calc_legal_moves()
+               bestmove = ai_for_mo(mborig, **params)
+               index = legal_moves.index(bestmove)
+               legal_moves[0], legal_moves[index] = legal_moves[index], legal_moves[0]
        if mborig.turn == Marubatsu.CIRCLE:
元と同じなので省略

枝狩りの効率の比較による検証

上記の修正後に、下記のプログラムを実行すると、全ノードの move ordering を行う場合 でも ai_abs_all が強解決の AI である ことを確認することができます。先程のプログラムとの違いはパラメータの dict に sort_allnodes: True を追加した点です。

for ai_for_mo in [None, ai2s, ai14s]:
    for shortest_victory in [False, True]:
        for use_tt in [False, True]:
            for init_ab in [False, True]:
                print(f"ai_for_mo: {ai_for_mo}, sv: {shortest_victory}, use_tt: {use_tt}, init_ab: {init_ab}")
                params = {
                    "ai_for_mo": ai_for_mo,
                    "shortest_victory": shortest_victory,
                    "init_ab": init_ab,
                    "use_tt": use_tt,
                    "sort_allnodes": True,
                }
                Check_solved.is_strongly_solved(ai_abs_all, params=params)

実行結果

ai_for_mo: None, sv: False, use_tt: False, init_ab: False
100%|██████████| 431/431 [00:03<00:00, 110.35it/s]
431/431 100.00%
ai_for_mo: None, sv: False, use_tt: False, init_ab: True
100%|██████████| 431/431 [00:03<00:00, 137.48it/s]
431/431 100.00%
略

次に、下記のプログラムで ゲーム開始時の局面 の評価値を計算した際に 評価値が計算されるノードの数 を、全ノードの move ordering を行う場合 で先程と同様の様々な設定で計算します。なお、move ordering を行わない場合 は結果は変わらないので省略しました。また、実質的に　move ordering を行わない ai1s とでたらめな move ordering を行う ai2s を比較する意味はないので、それらの計算も省略しました。

for ai_for_mo in [ai10s, ai14s]:
    for shortest_victory in [False, True]:
        for use_tt in [False, True]:
            for init_ab in [False, True]:
                print(f"ai_for_mo: {ai_for_mo}, sv: {shortest_victory}, init_ab: {init_ab}, use_tt: {use_tt}")
                print("count=", ai_abs_all(mb, ai_for_mo=ai_for_mo,
                                          shortest_victory=shortest_victory,
                                          init_ab=init_ab, use_tt=use_tt,
                                          sort_allnodes=True, calc_score=True, calc_count=True))

実行結果

ai_for_mo: <function ai10s at 0x00000216EC394D60>, sv: False, init_ab: False, use_tt: False
count= 2305
ai_for_mo: <function ai10s at 0x00000216EC394D60>, sv: False, init_ab: True, use_tt: False
count= 2082
ai_for_mo: <function ai10s at 0x00000216EC394D60>, sv: False, init_ab: False, use_tt: True
count= 285
略

下記は上記の結果と、先程の move ordering の 結果をまとめた ものです。下記の表の 上段が先頭のみの move ordering、下段が全ノードの move ordering を行う場合の結果です。

最短の勝利を目指さない（shortest_victory=False）場合

	ab × tt ×	ab 〇 tt x	ab × tt 〇	ab 〇 tt 〇
`ai10s`	2267 2305	1980 2082	274 285	270 260
`ai14s`	1496 1496	1496 1496	234 239	239 239

最短の勝利を目指す（shortest_victory=True）場合

	ab × tt ×	ab 〇 tt x	ab × tt 〇	ab 〇 tt 〇
`ai10s`	2189 2305	2232 2305	261 285	277 285
`ai14s`	1496 1496	1496 1496	234 239	234 239

実行結果から、いずれれの場合も 結果がほとんど変わらない か、一部の結果では全ノードの move ordering を行う場合のほうが効率が悪いことが確認できました。この結果はおかしいと思えるかもしれませんが理由があります。その理由について少し考えてみて下さい。

すべての局面での合計での比較

move ordering による枝狩りの効率は、すべてのノードで同じであるとは限りません。そのため、ゲーム開始時の局面では たまたま効率が変わらなかった可能性 があります。そこで、〇× ゲームの すべてのノード 対して評価値の計算を行ない、評価値が計算されたノードの数の 合計を比較 することにします。ただし、その際に Check_Solved が強解決の AI であるかの判定を行う際と同様に、同一局面は重複して計算しない ことにします。

下記はそのような計算を行うためのプログラムです。

3 行目：同一局面を除いた〇× ゲームの全ての局面を表す list をファイルから読み込む。この処理は Check_solved で行なっている処理と同じである
9、10 行目：それぞれの move ordering での合計を計算する変数を 0 で初期化する
11 ~ 19 行目：すべての局面に対してそれぞれの move ordering で ai_abs_all を呼び出し、count と count2 に計算したノードの数を加算する
20 行目：それぞれの move ordering での合計を表示する

 1  from util import load_mblist
 2  
 3  mblist = load_mblist("../data/mblist_by_board_min.dat")
 4  for ai_for_mo in [ai10s, ai14s]:
 5      for shortest_victory in [False, True]:
 6          for use_tt in [False, True]:
 7              for init_ab in [False, True]:
 8                  print(f"ai_for_mo: {ai_for_mo}, sv: {shortest_victory}, init_ab: {init_ab}, use_tt: {use_tt}")
 9                  count = 0
10                  count2 = 0
11                  for mb in mblist:
12                      count += ai_abs_all(mb, ai_for_mo=ai_for_mo,
13                                          shortest_victory=shortest_victory,
14                                          init_ab=init_ab, use_tt=use_tt,
15                                          sort_allnodes=False, calc_score=True, calc_count=True)
16                      count2 += ai_abs_all(mb, ai_for_mo=ai_for_mo,
17                                          shortest_victory=shortest_victory,
18                                          init_ab=init_ab, use_tt=use_tt,
19                                          sort_allnodes=True, calc_score=True, calc_count=True)
20                  print("count=", count)
21                  print("count2=", count2)

行番号のないプログラム

from util import load_mblist

mblist = load_mblist("../data/mblist_by_board_min.dat")
for ai_for_mo in [ai10s, ai14s]:
    for shortest_victory in [False, True]:
        for use_tt in [False, True]:
            for init_ab in [False, True]:
                print(f"ai_for_mo: {ai_for_mo}, sv: {shortest_victory}, init_ab: {init_ab}, use_tt: {use_tt}")
                count = 0
                count2 = 0
                for mb in mblist:
                    count += ai_abs_all(mb, ai_for_mo=ai_for_mo,
                                        shortest_victory=shortest_victory,
                                        init_ab=init_ab, use_tt=use_tt,
                                        sort_allnodes=False, calc_score=True, calc_count=True)
                    count2 += ai_abs_all(mb, ai_for_mo=ai_for_mo,
                                        shortest_victory=shortest_victory,
                                        init_ab=init_ab, use_tt=use_tt,
                                        sort_allnodes=True, calc_score=True, calc_count=True)
                print("count=", count)
                print("count2=", count2)

実行結果

ai_for_mo: <function ai10s at 0x00000216EC394D60>, sv: False, init_ab: False, use_tt: False
count= 13816
count2= 13214
ai_for_mo: <function ai10s at 0x00000216EC394D60>, sv: False, init_ab: True, use_tt: False
count= 8745
count2= 7938
ai_for_mo: <function ai10s at 0x00000216EC394D60>, sv: False, init_ab: False, use_tt: True
count= 10371
count2= 9904
略

下記は実行結果をまとめた表です。

最短の勝利を目指さない（shortest_victory=False）場合

	ab × tt ×	ab 〇 tt x	ab × tt 〇	ab 〇 tt 〇
`ai10s`	13816 13214	8475 7938	10371 9904	6625 5976
`ai14s`	10683 10679	6131 6076	8795 8792	5003 4964

最短の勝利を目指す（shortest_victory=True）場合

	ab × tt ×	ab 〇 tt x	ab × tt 〇	ab 〇 tt 〇
`ai10s`	15048 13950	13131 11818	11082 10300	9806 8811
`ai14s`	10691 10679	9267 9251	8810 8796	7556 7549

上記の結果から、move ordering の関数に ai10s を利用した場合の比較を行うと、下段の 全ノードの move ordering を行う場合のほうが 計算されたノードの数がいずれも 約 5 ~ 10 % 減り、効率が高くなることが確認できました。このことから、弱解決ではない ai10s で move ordering を行う場合は、先頭の子ノードを並べ替えるよりは、全ての子ノードを並べ替えたほうが効率が向上する ことが確認できました。

一方、move ordering の関数に ai14s を利用した場合の比較を行うと move ordering の種類によって効率がほとんど変わらないことが確認できます。全ノードの move ordering を行う場合のほうが 一部の例外を除いてほんの少しだけ効率が上がっているのは、ai14s は弱解決の AI なので、ほんの一部の局面で正しい評価値を計算できないからでしょう。従って、精度が非常に高い AI で move ordering を行う場合は、ほとんどの場合で先頭の子ノードの評価値が一番高くなるため、先頭の子ノードを並べ替えるだけで充分 であることがわかります。

上記から move ordering で全ノードの move ordering を行う必要があるかどうかは、以下の 2 つの時間を見積り、全体の処理時間が短くなるほうを適切に選択 する必要があります。

move ordering による枝狩りの効率の差による処理時間
move ordering を行うための計算に必要な処理時間

本記事で紹介したルールベースの AI を使って move ordering を行う場合は、後者の処理時間はほとんどかわらないので、全ノードの move ordering を行う方が良いでしょう。一方本記事では説明していませんが、move ordering で良く使われる反復深化の場合は、全ノードの move ordering を行う場合は後者の処理時間が前者よりも長くなる可能性が高いので先頭のみの move ordering が使われているのだと思います。

今回の記事のまとめ

今回の記事では、move ordering を行う αβ 法の AI を定義し、先頭のみと全ノードのそれぞれで move ordering の精度と枝狩りの効率化の関係について説明しました。

次回の記事ではスカウト法を紹介し、move ordering を行う αβ 法との比較を行います。

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

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

次回の記事

一般的にはスカウト法と実質的に同じ処理を行う ネガスカウト（negascout）法のほうが良く使われる ようです。ネガスカウト法については次回の記事で説明します ↩
move ordering の説明を行った以前の記事では Mbtree クラスの move_ai_bestmove_to_head メソッドなどを定義して 作成済のゲーム木の子ノードの順番を直接並べ替える という move ordering を行いましたが、αβ 法で ゲーム木を実際に作成せず に move ordering を行う AI の関数は定義しませんでした ↩
この条件が満たされていれば move ordering で 子ノードを正しく並べ替えることができる ので、計算される評価値は αβ 法で計算される -1 ~ 1 のような値と 異っていてもかまいません。例えば ai14s では 100 のような -1 ~ 1 の範囲とは全く異なる評価値を計算します ↩