目次と前回の記事

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

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

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

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

置換表付き αβ 法の視覚化を行うための関数の定義

置換表付き αβ 法での評価値の計算手順は複雑なので、これまでと同様に Mbtree_Anim を利用して 視覚化する ことにします。現状では Mbtree_Anim でアニメーションを行うために 必要なデータを作成する calc_score_by_ab は置換表付き αβ 法の計算を行うことができないので、calc_score_by_ab を以下のように 修正する必要 があります。

置換表付き αβ 法の計算を行うことができる ようにする
適切な視覚化を行うことができるように、アニメーションの フレームに記録するデータを修正 する

今回の記事では前者の calc_score_by_ab が置換表付き αβ 法の計算を行うことができるようにするための修正を行います。後者のフレームに記録するデータの修正は次回の記事で行うことにします。

今回の記事で利用する記号

今回の記事では以下の記号を使って説明を行ないます。また、今回の記事で用いる用語の意味について忘れた方は以前の記事を復習して下さい。

記号	意味
$l$	ミニマックス値の下界（lower bound）
$u$	ミニマックス値の上界（upper bound）
$α$	$α$ 値の初期値
$β$	$β$ 値の初期値
$α 値$	現在の $α$ 値
$β 値$	現在の $β$ 値
$s$	ノードの評価値
$c$	子ノードの評価値
$min(a, b)$	$a$ と $b$ の最小値
$max(a, b)$	$a$ と $b$ の最大値

現状の `calc_score_by_ab` のおさらい

これまでの calc_score_by_ab では評価値の計算の際に、行なわれた処理の種類に応じて アニメーションのフレームの情報として 下記の表の状態の情報を記録 しました。"tt" 以外の状態に関しては以前の記事を、"tt" の状態に関しては以前の記事を参照して下さい。

行われた処理	状態を表す文字列
ノードの処理が開始	"start"
子ノードの評価値の計算の直後	"score"
α 値または β 値に対する処理	"update"
ノードの処理が終了して評価値が確定	"end"
置換表による枝狩りが行われた	"tt"

下記に現状の calc_score_by_ab のプログラムを折りたたんで示します。

calc_score_by_abのプログラム

def calc_score_by_ab(self, abroot, debug=False, minimax=False, init_ab=False, use_tt=False):
    def assign_pruned_index(node, index):
        node.pruned_index = index
        self.num_pruned += 1
        for childnode in node.children:
            assign_pruned_index(childnode, index)
        
    def calc_ab_score(node, tt, alpha=float("-inf"), beta=float("inf")):
        if minimax:
            alpha = float("-inf")
            beta = float("inf")
        if use_tt:
            boardtxt = node.mb.board_to_str()
            key = (boardtxt, alpha, beta)
            if key in tt:
                node.score = tt[key]
                if node.mb.turn == Marubatsu.CIRCLE:
                    alpha = node.score
                else:
                    beta = node.score
                self.nodelist_by_score.append(node)
                self.num_calculated += 1     
                for childnode in node.children:
                    assign_pruned_index(childnode, len(self.nodelist_by_score) - 1)
                self.ablist_by_score.append((alpha, beta, None, "tt",
                                            self.num_calculated, self.num_pruned))
                node.score_index = len(self.nodelist_by_score) - 1  
                return node.score
                
        self.nodelist_by_score.append(node)
        self.ablist_by_score.append((alpha, beta, None, "start",
                                    self.num_calculated, self.num_pruned))
        if node.mb.status != Marubatsu.PLAYING:
            self.calc_score_of_node(node)
            if node.mb.turn == Marubatsu.CIRCLE:
                alpha = node.score
            else:
                beta = node.score
        else:
            if node.mb.turn == Marubatsu.CIRCLE:
                for childnode in node.children:
                    score = calc_ab_score(childnode, tt, alpha, beta)
                    self.nodelist_by_score.append(node)
                    self.ablist_by_score.append((alpha, beta, score, "score",
                                                self.num_calculated, self.num_pruned))
                    if score > alpha:
                        alpha = score
                    self.nodelist_by_score.append(node)
                    if score >= beta:
                        index = node.children.index(childnode)
                        for prunednode in node.children[index + 1:]:
                            assign_pruned_index(prunednode, len(self.nodelist_by_score) - 1)
                    self.ablist_by_score.append((alpha, beta, None, "update",
                                                self.num_calculated, self.num_pruned))
                    if score >= beta:
                        break
                node.score = alpha
            else:
                for childnode in node.children:
                    score = calc_ab_score(childnode, tt, alpha, beta)
                    self.nodelist_by_score.append(node)
                    self.ablist_by_score.append((alpha, beta, score, "score",
                                                self.num_calculated, self.num_pruned))
                    if score < beta:
                        beta = score
                    self.nodelist_by_score.append(node)
                    if score <= alpha:
                        index = node.children.index(childnode)
                        for prunednode in node.children[index + 1:]:
                            assign_pruned_index(prunednode, len(self.nodelist_by_score) - 1)
                    self.ablist_by_score.append((alpha, beta, None, "update",
                                                self.num_calculated, self.num_pruned))
                    if score <= alpha:
                        break
                node.score = beta

        self.nodelist_by_score.append(node)
        self.num_calculated += 1     
        self.ablist_by_score.append((alpha, beta, None, "end",
                                    self.num_calculated, self.num_pruned))
        node.score_index = len(self.nodelist_by_score) - 1  
        if use_tt:
            from util import calc_same_boardtexts   
            
            boardtxtlist = calc_same_boardtexts(node.mb)
            _, alpha, beta = key
            for boardtxt in boardtxtlist:
                tt[(boardtxt, alpha, beta)] = node.score            
        return node.score

    from ai import dprint       
    for node in self.nodelist:
        node.score_index = float("inf")
        node.pruned_index = float("inf")
    self.nodelist_by_score = []
    self.ablist_by_score = []
    self.num_calculated = 0
    self.num_pruned = 0
    if init_ab:
        alpha = -2 if self.shortest_victory else -1
        beta = 3 if self.shortest_victory else 1
    else:
        alpha = float("-inf")
        beta = float("inf")
    calc_ab_score(abroot, {}, alpha, beta)
    total_nodenum = self.num_pruned + self.num_calculated
    ratio = self.num_calculated / total_nodenum * 100
    dprint(debug, "ミニマックス法で計算したか", minimax)    
    dprint(debug, "計算したノードの数",  self.num_calculated)
    dprint(debug, "枝狩りしたノードの数",  self.num_pruned)
    dprint(debug, "合計",  total_nodenum)
    dprint(debug, f"割合 {ratio:.1f}%")

また、calc_score_by_ab 内で定義された、指定したノードの評価値の計算を行う ローカル関数 calc_ab_score では下記のアルゴリズムで処理を行っています。なお、下記ではアニメーションの フレームを記録する処理を太字 にしました。

ミニマックス法の場合は α 値と β 値をそれぞれ負の無限大と正の無限大にする¹
置換表を利用する場合で、置換表に「ノード、α 値と β 値」に対する評価値が記録されている場合は以下の処理を行う
1. そのノードの子孫ノードの数を数え、枝狩りが行なわれた数に加える
2. "tt" の状態のフレームを記録 する
3. 置換表に登録された評価値を返り値として返して処理を終了する
ノードの計算の処理を開始する際に "start" の状態のフレームを記録 する
ゲームの決着がついたリーフノードの場合はゲームの勝敗から評価値を計算し、手順 7 へ移動する
max ノードの場合はすべての子ノードに対して以下の処理を行い、α 値をこのノードの評価値として手順 7 へ移動する
1. 子ノードの評価値 $c$ を計算する
2. "score" の状態のフレームを記録 する
3. $α 値 = max(α 値, c)$ を計算する（子ノードの評価値が α 値を超えている場合は α 値を子ノードの評価値に更新する）
4. $β < c$（子ノードの評価値が β 値を超えている）の場合は β 狩りが行なわれるので、残りの子ノードの子孫ノードの数を数えて枝狩りが行われた数に加える
5. "update" の状態のフレームを記録 する
6. $β < c$（β 狩りが行なわれている）の場合は、残りの子ノードの処理を省略する
min ノードの場合はすべての子ノードに対して以下の処理を行い、β 値をこのノードの評価値として手順 7 へ移動する
1. 子ノードの評価値 $c$ を計算する
2. "score" の状態のフレームを記録 する
3. $β 値 = min(β 値, c)$ を計算する
4. $c < α$ の場合は α 狩りが行なわれるので、残りの子ノードの子孫ノードの数を数えて枝狩りが行われた数に加える
5. "update" の状態のフレームを記録 する
6. α 狩りが行なわれている場合は、残りの子ノードの処理を省略する
"end" の状態のフレームを記録 する
置換表を利用する場合は置換表に「ノード、α 値と β 値」に対する評価値を記録する
計算した評価値を返り値として返す

アルゴリズムの修正

上記のアルゴリズムは 置換表付き αβ 法の処理には対応していない ので、calc_score_by_ab で 置換表付き αβ 法の処理を行えるようにする ためには、上記のアルゴリズムを修正する必要があります。また、その際に上記のアルゴリズムにはいくつか わかりづらい点がある のでそれらの点についても修正することにします。どのように修正すればよいかについて少し考えてみて下さい。

記録するフレームの状態の共通化

上記のアルゴリズムでは、置換表を利用する場合と利用しない場合 で 記録するフレームの状態が大きく異なる 場合があります。

具体的には 置換表を利用する場合 で 置換表に評価値が登録されている場合 は 手順 2 で「"tt" の状態のフレームのみを記録」して 処理を終了 します。

一方で、それ以外の場合 は 下記のような順番でフレームが記録 されます。

"start" の状態のフレームを記録する
子ノードの数だけ "start" と "score" の状態のフレームを記録する。ただし、枝狩りが行われた場合は残りの子ノードの記録は省略する
"end" の状態のフレームを記録する

このように、状況に応じて 全く異なるアニメーションのフレームが記録 されるのは わかりづらい という問題があるので、置換表を利用する場合 は 下記のような順番 でフレームを記録することにします。

なお、元のアルゴリズムでは置換表に評価値が登録されていた場合は必ずその評価値が採用されていましたが、置換表付き αβ 法では 置換表に登録されたデータ が 必ず評価値として採用されるとは限らない ので、下記の手順 2 ではその点を考慮しています。

"start" の状態のフレームを記録する
置換表に関する処理を行ったことを表す "tt" の状態のフレームを記録する。置換表に記録されたデータからこのノードの評価値が計算される場合は手順 3 を飛ばして手順 4 に移動する
子ノードの数だけ "score" と "update" の状態のフレームを記録する。ただし、枝狩りが行われた場合は残りの子ノードの記録は省略する
"end" の状態のフレームを記録する

上記のように変更することで、置換表を利用するかどうかに関わらず フレームの記録の方法 が下記のように 共通化されます。

ノードの処理に対するフレームの記録が 常に "start" の状態ではじまり、"end" の状態で終了する ようになる
ノードの評価値 が 必ず "end" の状態のフレームで確定 する
子ノードの評価値を計算する場合は、計算した子ノードの数だけ "score" と "update" の状態のフレームを記録する

また、置換表を利用する場合 は "start" の直後に "tt" の状態 のフレームが記録されるようになり、"tt" の状態のフレームの意味 が下のように 変わります。

変更前：ノードの評価値が確定し、置換表による枝狩りが行われた
変更後：置換表に関する処理が行われた（ノードの評価値はこの時点では確定しない）

max ノードと min ノードの処理の統合

これまでは わかりやすさを重視 して max ノード の場合と min ノード の場合の処理を先程のアルゴリズムの 手順 5 と手順 6 のように分けていました。ai_abs_tt3 などの AI の関数 では max ノードと min ノードで分けた場合に それぞれで行う処理が少ない ので 問題はありませんでした が、calc_score_by_ab の場合は フレームに情報を記録する処理 や、枝狩りが行われたノードの数を計算する処理 が必要となるため、それらの処理を分けて記述すると プログラムがかなり長くなる ためかえって わかりづらくなる という問題があります。また、先程のアルゴリズムの 手順 5 と手順 6 で行う処理の 多くは共通している ので下記のように 統合する ことにします。

子ノードの評価値の符号を反転させ、α 値と β 値入れ替えて符号を反転させるという、以前の記事で簡単に言及した ネガアルファ法 でまとめるという方法もありますが、α 値と β 値が入れ替わるなど、プログラムの意味が見た目からかなりわかりづらくなる ので本記事では採用しません。ただし、αβ 法をネガアルファ法で実装することは実際によくあるので興味がある方は実装してみて下さい。なお、ネガアルファ法による実装例については下記の Wikipedia などを参考にするとよいでしょう。

なお、calc_score_by_ab では max ノードでは α 値がそのノードの評価値となるように計算 していましたが、以前の記事で ノードの評価値を α 値とは別に計算することにした ので、その修正も行ないます。min ノードでも同様です。

ノードの評価値 $s$ を max ノードの場合は負の無限大（または評価値の最小値でも良い）、min ノードの場合は正の無限大（または評価値の最大値でも良い）で初期化する
すべての子ノードに対して以下の処理を行う
1. 子ノードの評価値 $c$ を計算する
2. "score" の状態のフレームを記録 する
3. max ノードの場合は下記の処理を行う
  1. ノードの評価値 $s$ を $s = max(s, c)$ とする
  2. α 値を $α 値 = max(α 値, s)$ とする
  3. $β < s$ の場合は β 狩りが行なわれるので、残りの子ノードの子孫ノードの数を数えて枝狩りが行われた数に加える
4. min ノードの場合は下記の処理を行う
  1. ノードの評価値 $s$ を $s = min(s, c)$ とする
  2. β 値を $β 値 = min(β 値, s)$ とする
  3. $s < α$ の場合は α 狩りが行なわれるので、残りの子ノードの子孫ノードの数を数えて枝狩りが行われた数に加える
5. "update" の状態のフレームを記録 する
6. α 狩りまたは β 狩りが行われた場合は残りの子ノードの処理を省略する

置換表付き αβ 法への対応

最後に、置換表を利用する場合 のアルゴリズムを前回の記事で説明した 置換表付き αβ 法が行う処理に修正 する必要があります。

また、フレームにノードの情報を記録する処理に関する以下のような修正も行いました。

置換表付き αβ 法では、決着がついた リーフノードの評価値の計算 に 置換表は利用しない ので、その処理を行う下記の 手順 3 を、置換表の処理を行う 手順 4 の前に移動 した
リーフノードの場合 でも "end" の状態のフレームを記録する必要がある ので、リーフノードの場合は 手順 3 の実行後 に処理を終了せずに 手順 6 へ移動 するようにした
"end" のフレームに置換表の更新の情報を記録 できるようにするために、置換表に情報を記録する 手順 7 を フレームに "end" の状態の情報を記録する 手順 8 の前に移動 した

下記はそのように修正したアルゴリズムです。

ミニマックス法の場合は α 値と β 値をそれぞれ負の無限大と正の無限大にする
ノードの計算の処理を開始する際に "start" の状態のフレームを記録 する
ゲームの決着がついたリーフノードの場合はゲームの勝敗から評価値を計算し、手順 6 へ移動する
置換表を利用する場合は以下の処理を行う
1. 置換表にノードの評価値の範囲の情報が記録されている場合は以下の処理を行う
  1. 置換表から $l$（下界）と $u$ （上界）を取り出す
  2. $l = u$ の場合は $l$ をそのノードの評価値とし、子孫ノードの枝狩りが行なわれたことを記録する
  3. $u < α$ の場合は fail low なので $u$ をそノードの評価値とし、子孫ノードの枝狩りが行なわれたことを記録する
  4. $β < l$ の場合は fail high なので $l$ をそノードの評価値とし、子孫ノードの枝狩りが行なわれたことを記録する
  5. それ以外の場合は $α = min(α, l)$、$β = max(β, u)$ とする
2. 置換表にノードの情報が記録されていない場合は $l$ と $u$ を以下のように設定する
  - ルートノードの α 値と β 値を評価値の最小値と最大値とする場合は、評価値の最小値と評価値の最大値とする
  - そうでない場合は負の無限大と正の無限大とする
3. 子孫ノードの枝狩りが行なわれたことが記録されていた場合は、子孫ノードの数を数えて枝狩りが行われた数に加える
4. "tt" の状態のフレームを記録 する
5. 子孫ノードの枝狩りが行なわれたことが記録されていた場合は手順 6 へ移動する
ノードの評価値 $s$ を max ノードの場合は負の無限大（または評価値の最小値でも良い）、min ノードの場合は正の無限大（または評価値の最大値でも良い）で初期化し、すべての子ノードに対して以下の処理を行う
1. 子ノードの評価値 $c$ を計算する
2. "score" の状態のフレームを記録 する
3. max ノードの場合は下記の処理を行う
  1. ノードの評価値 $s$ を $s = max(s, c)$ とする
  2. α 値を $α 値 = max(α 値, s)$ とする
  3. $β < s$ の場合は β 狩りが行われるので枝狩りが行われたことを記録する
4. min ノードの場合は下記の処理を行う
  1. ノードの評価値 $s$ を $s = min(s, c)$ とする
  2. β 値を $β 値 = min(β 値, s)$ とする
  3. $s < α$ の場合は α 狩りが行われるので枝狩りが行われたことを記録する
5. 枝狩りが行われたことが記録されている場合は残りの子ノードの子孫ノードの数を数え、枝狩りが行われた数に加える
6. "update" の状態のフレームを記録 する
7. 枝狩りが行われたことが記録されている場合は、残りの子ノードの処理を省略する
置換表を利用する場合は以下の処理を行う
1. $s ≦ α$ の場合は fail low なので $u = s$ とする
2. そうでなく $s < β$ の場合は exact value なので $l = s$、$u = s$ とする
3. そうでない場合は fail high なので $l = s$ とする
4. 置換表の同一局面に対してミニマックス値の下界と上界である $s$ と $l$ を記録する
"end" の状態のフレームを記録 する
計算した評価値を返り値として返す

`calc_score_for_anim` の定義

上記のアルゴリズムは calc_score_by_ab のアルゴリズムを かなり修正している ので、calc_score_by_ab を修正するのではなく、Mbtree クラスに上記のアルゴリズムの処理を行う別の 新しいメソッドを定義する 事にします。なお、メソッドの名前は 視覚化（アニメーション）を行うためのデータを計算する ことから calc_score_for_anim という名前にしました。

calc_score_for_anim の実装手順として、上記のアルゴリズムの手順を順番 に calc_score_by_ab のプログラムを参考にしながら 実装することにします。

calc_score_by_ab は元々は置換表を利用しない αβ 法のみの計算を行うプログラムでしたが、後からミニマックス法の計算や、置換表による計算処理を追加しました。このように、関数に後から機能をどんどん追加していくと、プログラムの構造が わかりづらくなったり、効率が悪くなったりする ことがよくあります。そのような場合に機能を追加するとプログラムがさらにわかりづらくなるので、今回の記事で行ったように アルゴリズムから設計しなおして、新しい関数として定義し直す ということがよくあります。

上記のアルゴリズム以外の部分の実装

上記のアルゴリズムは、calc_score_for_anim 内で定義するローカル関数で行なわれる処理です。最初に それ以外の部分 を calc_score_by_ab を参考に下記のプログラムのように 定義する ことにします。以降の説明では calc_score_by_ab との違いについて説明します。

なお、calc_score_by_ab では、最短の勝利目指す評価値を計算するかどうか を 指定することができない点が不便² なので、この機会に 仮引数 shortest_victory を追加する ことにしました。なお、shortest_victory という属性は Mbtree クラスからインスタンスを作成した際に作られているので、仮引数 shortest_victory はデフォルト値を None とするデフォルト引数とし、None 以外の値が代入されていた場合に shortest_victory 属性の値をその値で更新することにします。

なお、下記は calc_score_for_anim の一部であるため、実行しても意味がないため行番号のないプログラムは省略します。calc_score_for_anim のプログラム全体は、すべての手順の実装の説明後に示します。

1、2 行目：メソッドの名前を calc_score_for_anim に修正し、デフォルト引数値を None とするデフォルト引数 shortest_victory を追加する
9 ~ 11 行目：「ミニマックス法で計算するか」、「α 値と β 値の初期値を設定するか」、「置換表を利用するか」という情報は、Mbtree_Anim でアニメーションを行う際に利用できる と 状況に合わせた表示を行うことができるようになる ので、それらを同じ名前の属性に代入するように修正した
12、13 行目：shortest_victory が None でない場合に、同名の属性をその値で更新する
23 ~ 25 行目：init_ab が True の場合は前回の記事の ai_abs_tt4 と同様の考え方で min_score と max_score に評価値の最小値と最大値を変数に代入し、それを 29 行目でルートノードの α 値と β 値の初期値として設定するように修正した。また、ここで変数に代入した評価値の最小値と最大値はこの後の手順 4-2 の実装で ai_abs_tt4 と同様に置換表にデータが登録されていなかった場合の下界と上界の値に代入する
26 ~ 28 行目：init_ab が False の場合は min_score と max_score に負の無限大と正の無限大を代入することで、ルートノードの α 値と β 値の初期値を負の無限大と正の無限大とする ai_abs_tt3 と同様の処理が行われるようになる
29 行目：ルートノードを計算する処理を呼び出す際に、α 値と β 値の初期値として min_score と max_score を設定するように修正した。また、ノードの評価値を計算するローカル関数の名前をこの後で calc_node_score という名前に変更するので、それに合わせて呼び出す関数の名前を修正した

 1  def calc_score_for_anim(self, abroot, debug=False, minimax=False, init_ab=False,
 2                          use_tt=False, shortest_victory=None):
 3      def assign_pruned_index(node, index):
 4          node.pruned_index = index
 5          self.num_pruned += 1
 6          for childnode in node.children:
 7              assign_pruned_index(childnode, index)
 8  
 9      self.minimax = minimax
10      self.init_ab = init_ab
11      self.use_tt = use_tt
12      if shortest_victory is not None:
13          self.shortest_victory = shortest_victory
14
15      from ai import dprint       
16      for node in self.nodelist:
17          node.score_index = float("inf")
18          node.pruned_index = float("inf")
19      self.nodelist_by_score = []
20      self.ablist_by_score = []
21      self.num_calculated = 0
22      self.num_pruned = 0
23      if init_ab:
24          min_score = -2 if self.shortest_victory else -1
25          max_score = 3 if self.shortest_victory else 1
26      else:
27          min_score = float("-inf")
28          max_score = float("inf")
29      calc_node_score(abroot, {}, min_score, max_score)
30      total_nodenum = self.num_pruned + self.num_calculated
31      ratio = self.num_calculated / total_nodenum * 100
32      dprint(debug, "ミニマックス法で計算したか", minimax)    
33      dprint(debug, "計算したノードの数",  self.num_calculated)
34      dprint(debug, "枝狩りしたノードの数",  self.num_pruned)
35      dprint(debug, "合計",  total_nodenum)
36      dprint(debug, f"割合 {ratio:.1f}%")

修正箇所

-def calc_score_by_ab(self, abroot, debug=False, minimax=False, init_ab=False, use_tt=False):
+def calc_score_for_anim(self, abroot, debug=False, minimax=False, init_ab=False,
+                        use_tt=False, shortest_victory=None):
    def assign_pruned_index(node, index):
        node.pruned_index = index
        self.num_pruned += 1
        for childnode in node.children:
            assign_pruned_index(childnode, index)

+   self.minimax = minimax
+   self.init_ab = init_ab
+   self.use_tt = use_tt
+   if shortest_victory is not None:
+       self.shortest_victory = shortest_victory

    from ai import dprint       
    for node in self.nodelist:
        node.score_index = float("inf")
        node.pruned_index = float("inf")
    self.nodelist_by_score = []
    self.ablist_by_score = []
    self.num_calculated = 0
    self.num_pruned = 0
    if init_ab:
-       alpha = -2 if self.shortest_victory else -1
+       min_score = -2 if self.shortest_victory else -1
-       beta = 3 if self.shortest_victory else 1
+       max_score = 3 if self.shortest_victory else 1
    else:
-       alpha = float("-inf")
+       min_score = float("-inf")
-       beta = float("inf")
+       max_score = float("inf")
-   calc_node_score(abroot, {}, alpha, beta)
+   calc_node_score(abroot, {}, min_score, max_score)
    total_nodenum = self.num_pruned + self.num_calculated
    ratio = self.num_calculated / total_nodenum * 100
    dprint(debug, "ミニマックス法で計算したか", minimax)    
    dprint(debug, "計算したノードの数",  self.num_calculated)
    dprint(debug, "枝狩りしたノードの数",  self.num_pruned)
    dprint(debug, "合計",  total_nodenum)
    dprint(debug, f"割合 {ratio:.1f}%")

`calc_node_score` の定義

calc_score_by_ab ではノードの評価値を計算するローカル関数の名前を calc_ab_score としていましたが、calc_score_for_anim でその名前をそのまま使うのは変なので calc_node_score という名前に変更 することにします。

また、置換表付き αβ 法 では α 値と β 値の初期値を記録しておく 必要があります。ai_abs_tt2 ではその処理を calc_ab_score のブロックの中（リンク先の ai_abs_tt2 の 13、14 行目）で行っていましたが、よく考えると 仮引数の名前を alphaorig、betaorig に修正したほうが良い 気がしましたので、2 行目をそのように修正しました。

2 行目：関数の名前を calc_node_score に、仮引数の名前を alphaorig と betaorig に修正した

1  def calc_score_of_anim(self, abroot, debug=False, minimax=False, init_ab=False, use_tt=False, shortest_victory=None):
略
2      def calc_node_score(node, tt, alphaorig=float("-inf"), betaorig=float("inf")):
略

修正箇所

def calc_score_of_anim(self, abroot, debug=False, minimax=False, init_ab=False, use_tt=False, shortest_victory=None):
略
-   def calc_ab_score(node, tt, alpha=float("-inf"), beta=float("inf")):
+   def calc_node_score(node, tt, alphaorig=float("-inf"), betaorig=float("inf")):
略

手順 1 の実装

手順 1 の ミニマックス法で評価値を計算する場合の処理 は下記のプログラムのように元の calc_score_by_ab とほぼ同じ ですが、4、5 行目で負の無限大と正の無限大を代入する 変数の名前を alphaorig と betaorig に修正 した点が異なります。

1  def calc_score_of_anim(self, abroot, debug=False, minimax=False, init_ab=False, use_tt=False, shortest_victory=None):
略
2      def calc_node_score(node, tt, alphaorig=float("-inf"), betaorig=float("inf")):
3          if minimax:
4              alphaorig = float("-inf")
5              betaorig = float("inf")
略

修正箇所

def calc_score_of_anim(self, abroot, debug=False, minimax=False, init_ab=False, use_tt=False, shortest_victory=None):
略
    def calc_node_score(node, tt, alphaorig=float("-inf"), betaorig=float("inf")):
        if minimax:
-           alpha = float("-inf")
+           alphaorig = float("-inf")
-           beta = float("inf")
+           betaorig = float("inf")
略

手順 2 の実装

手順 2 の "start" のフレームを記録する処理 は下記のプログラムのように、元の calc_score_by_ab の中で "start" のフレームを記録する処理の位置が変わっただけ です。なお、本記事の最初で説明したように、6、7 行目の フレームに記録する情報に関する修正は次回の記事で行う 予定なので、今回の記事では フレームに情報を記録する処理の内容は修正しません。ただし、先程仮引数の名前を alphaorig と betaorig に変更したせいで、使われなくなった alpha と beta をそのまま記述するとエラーが発生するので、alphaorig と betaorig に変えるという修正を行う必要があります。

1  def calc_score_of_anim(self, abroot, debug=False, minimax=False, init_ab=False, use_tt=False, shortest_victory=None):
略
2      def calc_node_score(node, tt, alphaorig=float("-inf"), betaorig=float("inf")):
3          手順 1 のプログラム
4
5          self.nodelist_by_score.append(node)
6          self.ablist_by_score.append((alphaorig, betaorig, None, "start",
7                                       self.num_calculated, self.num_pruned))
略

修正箇所

def calc_score_of_anim(self, abroot, debug=False, minimax=False, init_ab=False, use_tt=False, shortest_victory=None):
略
    def calc_node_score(node, tt, alphaorig=float("-inf"), betaorig=float("inf")):
        手順 1 のプログラム

        self.nodelist_by_score.append(node)
-       self.ablist_by_score.append((alpha, beta, None, "start",
+       self.ablist_by_score.append((alphaorig, betaorig, None, "start",
                                     self.num_calculated, self.num_pruned))
略

手順 3 の実装

手順 3 の リーフノードに関する処理 は下記のプログラムのように記述します。

7, 8 行目：リーフノード では 必ず正確なミニマックス値が計算される ので、上界と下界 を 計算した評価値で更新する ように修正した
元の calc_score_by_ab では α 値または β 値にノードの評価値を計算していたが、以前の記事で ノードの評価値を α 値や β 値とは別に計算することにした ので、α 値または β 値に評価値を代入する処理は削除 した

1  def calc_score_of_anim(self, abroot, debug=False, minimax=False, init_ab=False, use_tt=False, shortest_victory=None):
略
2      def calc_node_score(node, tt, alphaorig=float("-inf"), betaorig=float("inf")):
3          手順 1、2 のプログラム
4
5          if node.mb.status != Marubatsu.PLAYING:
6              self.calc_score_of_node(node)
7              lower_bound = node.score
8              upper_bound = node.score
略

修正箇所

def calc_score_of_anim(self, abroot, debug=False, minimax=False, init_ab=False, use_tt=False, shortest_victory=None):
略
    def calc_node_score(node, tt, alphaorig=float("-inf"), betaorig=float("inf")):
        手順 1、2 のプログラム

        if node.mb.status != Marubatsu.PLAYING:
            self.calc_score_of_node(node)
+           lower_bound = node.score
+           upper_bound = node.score
-           if node.mb.turn == Marubatsu.CIRCLE:
-               alpha = node.score
-           else:
-               beta = node.score
略

実際にはリーフノードに対して置換表を利用することはないので、リーフノードの評価値の範囲を置換表に記録する必要はありません。ただし、リーフノードの場合に置換表にデータを記録しないという処理を記述すると、プログラムが長く、少しだけわかりづらくなるため、本記事ではリーフノードの評価値の範囲も置換表に記録することにします³。

リーフノードの評価値の範囲を置換表に記録すると、その分だけコンピューターのメモリを消費してしまうという欠点が生じるので、その点が気になる方は置換表にデータを記録する処理を行う手順 6 を、リーフノードの場合は行わないようにすると良いでしょう。また、その場合は上記の 7、8 行目を記述する必要はありません。

手順 4 の実装

手順 4 は少々長いので以下に再掲します。

置換表を利用する場合は以下の処理を行う。

置換表にノードの評価値の範囲の情報が記録されている場合は以下の処理を行う
1. 置換表から $l$（下界）と $u$ （上界）を取り出す
2. $l = u$ の場合は $l$ をそのノードの評価値とし、子孫ノードの枝狩りが行なわれたことを記録する
3. $u < α$ の場合は fail low なので $u$ をそノードの評価値とし、子孫ノードの枝狩りが行なわれたことを記録する
4. $β < l$ の場合は fail high なので $l$ をそノードの評価値とし、子孫ノードの枝狩りが行なわれたことを記録する
5. それ以外の場合は $α = min(α, l)$、$β = max(β, u)$ とする
置換表にノードの情報が記録されていない場合は $l$ と $u$ を以下のように設定する
- ルートノードの α 値と β 値を評価値の最小値と最大値とする場合は、評価値の最小値と評価値の最大値とする
- そうでない場合は負の無限大と正の無限大とする
子孫ノードの枝狩りが行なわれたことが記録されていた場合は、子孫ノードの数を数えて枝狩りが行われた数に加える
"tt" の状態のフレームを記録 する

下記は手順 4 を実装したプログラムです。

6 行目：手順 3 の処理が行なわれた場合 は 手順 6 に移動する必要がある ので、手順 4、5 の処理は手順 3 の if 文に対する else のブロックの中に記述する必要 がある
7 行目：手順 4-1-2 ~ 4-1-4 で、枝狩りが行われたことを記録できるようにする ために、枝狩りが行われたことを表すローカル変数 pruned を False で初期化 する
8 ~ 23 行目：手順 4-1 の処理を行う。ai_abs_tt2とほぼ同じだが、alpha と beta を alphaorig と betaorig に修正する点と、置換表に記録されていたデータをこのノードの評価値とする際に 評価値を返り値として返すのではなく、node.score に評価値を代入 し、pruned に True を代入 する点が 異なる
24 ~ 26 行目：手順 4-2 の処理を行う。$l$ と $u$ に代入する値は先程の処理で min_score と max_score に代入済なので、それらの変数の値をそのまま代入すればよい
27 ~ 29 行目：手順 4-3 の処理を行う
30 ~ 32 行目：手順 4-4 の処理を行う。alpha と beta という仮引数の名前を変えたので、31 行目では alphaorig と betaorig に修正した。また、元の calc_score_by_ab ではこの時点で ノードの評価値が確定して処理を終了していた ので self.num_calculated += 1 と node.score_index = len(self.nodelist_by_score) - 1 という処理を行っていたが、先程 記録するフレームの状態を共通化 したことで ノードの評価値の確定は常に "end" のフレームで記録することにした、それらの処理を削除した
33、34 行目：子孫ノードの 枝狩りが行われたことが記録されていた場合 は 手順 6 へ移動するため に、手順 5 の処理 を pruned が False の場合のみ行うようにした

 1  def calc_score_of_anim(self, abroot, debug=False, minimax=False, init_ab=False, use_tt=False, shortest_victory=None):
略
 2      def calc_node_score(node, tt, alphaorig=float("-inf"), betaorig=float("inf")):
 3          手順 1、2 のプログラム
 4          if node.mb.status != Marubatsu.PLAYING:
 5              手順 3 のプログラム
 6          else:
 7              pruned = False
 8              if use_tt:
 9                  boardtxt = node.mb.board_to_str()
10                  if boardtxt in tt:
11                      lower_bound, upper_bound = tt[boardtxt]
12                      if lower_bound == upper_bound:
13                          node.score = lower_bound
14                          pruned = True
15                      elif upper_bound <= alphaorig:
16                          node.score = upper_bound
17                          pruned = True
18                      elif betaorig <= lower_bound:
19                          node.score = lower_bound
20                          pruned = True
21                      else:
22                          alphaorig = min(alphaorig, lower_bound)
23                          betaorig = max(betaorig, upper_bound)
24                  else:
25                      lower_bound = min_score
26                      upper_bound = max_score
27              if pruned:
28                  for childnode in node.children:
29                      assign_pruned_index(childnode, len(self.nodelist_by_score) - 1)  
30              self.nodelist_by_score.append(node)
31              self.ablist_by_score.append((alphaorig, betaorig, None, "tt",
32                                           self.num_calculated, self.num_pruned))
33              if not pruned:
34                  手順 5 のプログラム
略

修正箇所（一部ai_abs_tt2からの修正箇所があります）

def calc_score_of_anim(self, abroot, debug=False, minimax=False, init_ab=False, use_tt=False, shortest_victory=None):
略
    def calc_node_score(node, tt, alphaorig=float("-inf"), betaorig=float("inf")):
        手順 1、2 のプログラム
        if node.mb.status != Marubatsu.PLAYING:
            手順 3 のプログラム
        else:
+           pruned = False
            if use_tt:  # このブロックの中は ai_abs_tt2 からの修正箇所です
                boardtxt = node.mb.board_to_str()
                if boardtxt in tt:
                    lower_bound, upper_bound = tt[boardtxt]
                    if lower_bound == upper_bound:
-                       return lower_bound
+                       node.score = lower_bound
+                       pruned = True
-                   elif upper_bound <= alpha:
+                   elif upper_bound <= alphaorig:
-                       return upper_bound
+                       node.score = upper_bound
+                       pruned = True
-                   elif beta <= lower_bound:
+                   elif betaorig <= lower_bound:
-                       return lower_bound
+                       node.score = lower_bound
+                       pruned = True
                    else:
-                       alpha = min(alpha, lower_bound)
+                       alphaorig = min(alphaorig, lower_bound)
-                       beta = max(beta, upper_bound)
+                       betaorig = max(betaorig, upper_bound)
                else:
                    lower_bound = min_score
                    upper_bound = max_score
                if pruned:
                    for childnode in node.children:
                        assign_pruned_index(childnode, len(self.nodelist_by_score) - 1)  
            self.nodelist_by_score.append(node)
-           self.num_calculated += 1     
-           self.ablist_by_score.append((alpha, beta, None, "tt",
+           self.ablist_by_score.append((alphaorig, betaorig, None, "tt",
                                         self.num_calculated, self.num_pruned))
-           node.score_index = len(self.nodelist_by_score) - 1  
+           if not pruned:
                手順 5 のプログラム
略

手順 5 の実装

手順 5 も少々長いので再掲します。

ノードの評価値 $s$ を max ノードの場合は負の無限大（または評価値の最小値でも良い）、min ノードの場合は正の無限大（または評価値の最大値でも良い）で初期化し、すべての子ノードに対して以下の処理を行う

子ノードの評価値 $c$ を計算する
"score" の状態のフレームを記録 する
max ノードの場合は下記の処理を行う
1. ノードの評価値 $s$ を $s = max(s, c)$ とする
2. α 値を $α 値 = max(α 値, s)$ とする
3. $β < s$ の場合は β 狩りが行われるので枝狩りが行われたことを記録する
min ノードの場合は下記の処理を行う
1. ノードの評価値 $s$ を $s = min(s, c)$ とする
2. β 値を $β 値 = min(β 値, s)$ とする
3. $s < α$ の場合は α 狩りが行われるので枝狩りが行われたことを記録する
枝狩りが行われたことが記録されている場合は残りの子ノードの子孫ノードの数を数え、枝狩りが行われた数に加える
"update" の状態のフレームを記録 する
枝狩りが行われたことが記録されている場合は、残りの子ノードの処理を省略する

下記は手順 5 を実装したプログラムです。下記ではノードの評価値 $s$ を評価値の最小値または最大値で初期化しました。なお、元のプログラムから大幅に変わっているので修正箇所は省略します。

9、10 行目：現在の α 値と β 値を表す変数 alpha、beta を α 値と β 値の初期値で初期化する
11 行目：この後で max ノードであるかどうかを何度も判定する必要がある ので、maxnode というローカル変数に max ノードであるかどうかを計算して代入 する
12 行目：ノードの評価値を評価値の最小値または最大値で初期化する処理を行う
13 行目：すべての子ノードに対する繰り返し処理を行う
14 行目：手順 5-1 の処理を行う。再帰呼び出しを行う関数呼び出しの名前を calc_node_score に修正した
15 ~ 17 行目：手順 5-2 の処理を行う。score を node.score に修正した
18 ~ 22 行目：手順 5-3 の処理を行う
23 ~ 27 行目：手順 5-4 の処理を行う
28 ~ 31 行目：手順 5-5 の処理を行う
32 ~ 34 行目：手順 5-6 の処理を行う
35、36 行目：手順 5-7 の処理を行う

 1  def calc_score_of_anim(self, abroot, debug=False, minimax=False, init_ab=False, use_tt=False, shortest_victory=None):
略
 2      def calc_node_score(node, tt, alphaorig=float("-inf"), betaorig=float("inf")):
 3          手順 1、2 のプログラム
 4          if node.mb.status != Marubatsu.PLAYING:
 5              手順 3 のプログラム
 6          else:
 7              手順 4 のプログラム
 8              if not pruned:
 9                  alpha = alphaorig
10                  beta = betaorig
11                  maxnode = node.mb.turn == Marubatsu.CIRCLE
12                  node.score = min_score if maxnode else max_score
13                  for childnode in node.children:
14                      childscore = calc_node_score(childnode, tt, alpha, beta)
15                      self.nodelist_by_score.append(node)
16                      self.ablist_by_score.append((alpha, beta, node.score, "score",
17                                                   self.num_calculated, self.num_pruned))
18                      if maxnode:
19                          node.score = max(node.score, childscore)
20                          alpha = max(node.score, alpha)
21                          if node.score >= beta:
22                              pruned = True
23                      else:
24                          node.score = min(node.score, childscore)
25                          beta = min(node.score, beta)
26                          if node.score <= alpha:
27                              pruned = True
28                      if pruned:
29                          index = node.children.index(childnode)
30                          for prunednode in node.children[index + 1:]:
31                              assign_pruned_index(prunednode, len(self.nodelist_by_score) - 1)
32                      self.nodelist_by_score.append(node)
33                      self.ablist_by_score.append((alpha, beta, None, "update",
34                                                    self.num_calculated, self.num_pruned))
35                      if pruned:
36                          break    
略

修正箇所

def calc_score_of_anim(self, abroot, debug=False, minimax=False, init_ab=False, use_tt=False, shortest_victory=None):
略
    def calc_node_score(node, tt, alphaorig=float("-inf"), betaorig=float("inf")):
        手順 1、2 のプログラム
        if node.mb.status != Marubatsu.PLAYING:
            手順 3 のプログラム
        else:
            手順 4 のプログラム
            if not pruned:
                alpha = alphaorig
                beta = betaorig
                maxnode = node.mb.turn == Marubatsu.CIRCLE
                node.score = min_score if maxnode else max_score
                for childnode in node.children:
                    childscore = calc_ab_score(childnode, tt, alpha, beta)
                    self.nodelist_by_score.append(node)
                    self.ablist_by_score.append((alpha, beta, node.score, "score",
                                                 self.num_calculated, self.num_pruned))
                    if maxnode:
                        node.score = max(node.score, childscore)
                        alpha = max(node.score, alpha)
                        if node.score >= beta:
                            pruned = True
                    else:
                        node.score = min(node.score, childscore)
                        beta = min(node.score, beta)
                        if node.score <= alpha:
                            pruned = True
                    if pruned:
                        index = node.children.index(childnode)
                        for prunednode in node.children[index + 1:]:
                            assign_pruned_index(prunednode, len(self.nodelist_by_score) - 1)
                    self.nodelist_by_score.append(node)
                    self.ablist_by_score.append((alpha, beta, None, "update",
                                                  self.num_calculated, self.num_pruned))
                    if pruned:
                        break 
略

21、22 行目の 手順 5-3-3 の処理では、手順 4 で利用した pruned という変数を使いまわしています。その際に 8 行目の処理から この時点では pruned に必ず False が代入されている ので、手順 4 の場合のように pruned を False で 初期化する必要はありません。

わかりづらいと思った方は、pruned を False で初期化する処理を記述するか、pruned とは別の変数で枝狩りが行われたことを記録して下さい。ただしその場合はその変数を False で初期化する処理を記述するのを忘れないようにして下さい。

手順 6 の実装

手順 6 の 評価値の範囲を置換表に記録する処理 は ai_abs_tt3 とほぼ同じ で、下記のプログラムのように記述できます。異なる点は置換表を利用するかどうかの判定を行う部分と、score が node.score になった点などです。

def calc_score_of_anim(self, abroot, debug=False, minimax=False, init_ab=False, use_tt=False, shortest_victory=None):
略
    def calc_node_score(node, tt, alphaorig=float("-inf"), betaorig=float("inf")):
        手順 1、2 のプログラム
        if node.mb.status != Marubatsu.PLAYING:
            手順 3 のプログラム
        else:
            手順 4 のプログラム
            if not pruned:
                手順 5 のプログラム
        
        if use_tt:
            from util import calc_same_boardtexts
            
            boardtxtlist = calc_same_boardtexts(node.mb)           
            if node.score <= alphaorig:
                upper_bound = node.score
            elif node.score < betaorig:
                lower_bound = node.score
                upper_bound = node.score
            else:
                lower_bound = node.score
            for boardtxt in boardtxtlist:
                tt[boardtxt] = (lower_bound, upper_bound)     
略

修正箇所

def calc_score_of_anim(self, abroot, debug=False, minimax=False, init_ab=False, use_tt=False, shortest_victory=None):
略
    def calc_node_score(node, tt, alphaorig=float("-inf"), betaorig=float("inf")):
        手順 1、2 のプログラム
        if node.mb.status != Marubatsu.PLAYING:
            手順 3 のプログラム
        else:
            手順 4 のプログラム
            if not pruned:
                手順 5 のプログラム
        
+       if use_tt:
+           from util import calc_same_boardtexts
            
            boardtxtlist = calc_same_boardtexts(node.mb)  
            if node.score <= alphaorig:
-               upper_bound = score
+               upper_bound = node.score
            elif node.score < betaorig:
-               lower_bound = score
+               lower_bound = node.score
-               upper_bound = score
+               upper_bound = node.score
            else:
-               lower_bound = score
+               lower_bound = node.score
            for boardtxt in boardtxtlist:
                tt[boardtxt] = (lower_bound, upper_bound)     
略

手順 7、8 の実装

手順 7、8 の "end" の状態のフレームを記録 し、計算した評価値を返り値として返す処理 は下記のプログラムのように 14 行目で alpha と beta を alphaorig と betaorig に修正した以外は元の calc_score_by_ab と同じです。

 1  def calc_score_of_anim(self, abroot, debug=False, minimax=False, init_ab=False, use_tt=False, shortest_victory=None):
略
 2      def calc_node_score(node, tt, alphaorig=float("-inf"), betaorig=float("inf")):
 3          手順 1、2 のプログラム
 4          if node.mb.status != Marubatsu.PLAYING:
 5              手順 3 のプログラム
 6          else:
 7              手順 4 のプログラム
 8              if not pruned:
 9                  手順 5 のプログラム
10  
11          手順 6 のプログラム
12          self.nodelist_by_score.append(node)
13          self.num_calculated += 1     
14          self.ablist_by_score.append((alphaorig, betaorig, None, "end",
15                                      self.num_calculated, self.num_pruned))
16          node.score_index = len(self.nodelist_by_score) - 1          
17          return node.score

修正箇所

def calc_score_of_anim(self, abroot, debug=False, minimax=False, init_ab=False, use_tt=False, shortest_victory=None):
略
    def calc_node_score(node, tt, alphaorig=float("-inf"), betaorig=float("inf")):
        手順 1、2 のプログラム
        if node.mb.status != Marubatsu.PLAYING:
            手順 3 のプログラム
        else:
            手順 4 のプログラム
            if not pruned:
                手順 5 のプログラム

        手順 6 のプログラム
        self.nodelist_by_score.append(node)
        self.num_calculated += 1     
-       self.ablist_by_score.append((alpha, beta, None, "end",
+       self.ablist_by_score.append((alphaorig, betaorig, None, "end",
                                    self.num_calculated, self.num_pruned))
        node.score_index = len(self.nodelist_by_score) - 1          
        return node.score

`calc_score_of_anim` の実装と確認

下記は calc_score_of_anim を定義するプログラムです。

from marubatsu import Marubatsu
from tree import Mbtree

def calc_score_for_anim(self, abroot, debug=False, minimax=False, init_ab=False, use_tt=False, shortest_victory=None):
    def assign_pruned_index(node, index):
        node.pruned_index = index
        self.num_pruned += 1
        for childnode in node.children:
            assign_pruned_index(childnode, index)
            
    def calc_node_score(node, tt, alphaorig=float("-inf"), betaorig=float("inf")):
        if minimax:
            alphaorig = float("-inf")
            betaorig = float("inf")            

        self.nodelist_by_score.append(node)
        self.ablist_by_score.append((alphaorig, betaorig, None, "start",
                                     self.num_calculated, self.num_pruned))

        if node.mb.status != Marubatsu.PLAYING:
            self.calc_score_of_node(node)
            lower_bound = node.score
            upper_bound = node.score
        else:
            pruned = False
            if use_tt:
                boardtxt = node.mb.board_to_str()
                if boardtxt in tt:
                    lower_bound, upper_bound = tt[boardtxt]
                    if lower_bound == upper_bound:
                        node.score = lower_bound
                        pruned = True
                    elif upper_bound <= alphaorig:
                        node.score = upper_bound
                        pruned = True
                    elif betaorig <= lower_bound:
                        node.score = lower_bound
                        pruned = True
                    else:
                        alphaorig = min(alphaorig, lower_bound)
                        betaorig = max(betaorig, upper_bound)
                else:
                    lower_bound = min_score
                    upper_bound = max_score
                if pruned:
                    for childnode in node.children:
                        assign_pruned_index(childnode, len(self.nodelist_by_score) - 1)  
            self.nodelist_by_score.append(node)
            self.ablist_by_score.append((alphaorig, betaorig, None, "tt",
                                         self.num_calculated, self.num_pruned))
            if not pruned:
                alpha = alphaorig
                beta = betaorig
                maxnode = node.mb.turn == Marubatsu.CIRCLE
                node.score = min_score if maxnode else max_score
                for childnode in node.children:
                    childscore = calc_node_score(childnode, tt, alpha, beta)
                    self.nodelist_by_score.append(node)
                    self.ablist_by_score.append((alpha, beta, node.score, "score",
                                                 self.num_calculated, self.num_pruned))
                    if maxnode:
                        node.score = max(node.score, childscore)
                        alpha = max(node.score, alpha)
                        if node.score >= beta:
                            pruned = True
                    else:
                        node.score = min(node.score, childscore)
                        beta = min(node.score, beta)
                        if node.score <= alpha:
                            pruned = True
                    if pruned:
                        index = node.children.index(childnode)
                        for prunednode in node.children[index + 1:]:
                            assign_pruned_index(prunednode, len(self.nodelist_by_score) - 1)
                    self.nodelist_by_score.append(node)
                    self.ablist_by_score.append((alpha, beta, None, "update",
                                                  self.num_calculated, self.num_pruned))
                    if pruned:
                        break 
                    
        if use_tt:
            from util import calc_same_boardtexts
            boardtxtlist = calc_same_boardtexts(node.mb)
            
            if node.score <= alphaorig:
                upper_bound = node.score
            elif node.score < betaorig:
                lower_bound = node.score
                upper_bound = node.score
            else:
                lower_bound = node.score
            for boardtxt in boardtxtlist:
                tt[boardtxt] = (lower_bound, upper_bound) 

        self.nodelist_by_score.append(node)
        self.num_calculated += 1     
        self.ablist_by_score.append((alphaorig, betaorig, None, "end",
                                    self.num_calculated, self.num_pruned))
        node.score_index = len(self.nodelist_by_score) - 1          
        return node.score                
                                    
    self.minimax = minimax
    self.init_ab = init_ab
    self.use_tt = use_tt
    if shortest_victory is not None:
        self.shortest_victory = shortest_victory

    from ai import dprint       
    for node in self.nodelist:
        node.score_index = float("inf")
        node.pruned_index = float("inf")
    self.nodelist_by_score = []
    self.ablist_by_score = []
    self.num_calculated = 0
    self.num_pruned = 0
    if init_ab:
        min_score = -2 if self.shortest_victory else -1
        max_score = 3 if self.shortest_victory else 1
    else:
        min_score = float("-inf")
        max_score = float("inf")
    calc_node_score(abroot, {}, min_score, max_score)
    total_nodenum = self.num_pruned + self.num_calculated
    ratio = self.num_calculated / total_nodenum * 100
    dprint(debug, "ミニマックス法で計算したか", minimax)    
    dprint(debug, "計算したノードの数",  self.num_calculated)
    dprint(debug, "枝狩りしたノードの数",  self.num_pruned)
    dprint(debug, "合計",  total_nodenum)
    dprint(debug, f"割合 {ratio:.1f}%") 
    
Mbtree.calc_score_for_anim = calc_score_for_anim

上記のプログラムを実行後に、下記のプログラムで、以下のそれぞれの場合で ルートノードの評価値を計算した際に計算されるノード数などの情報を表示 します。実行結果 に表示される「計算したノードの数」が前回の記事（ai_mmdfs、ai_mmdfs_tt、ai_abs）と前回の記事（ai_abs_tt3）と前回の記事（ai_abs_tt4）の結果と同じであることから、calc_score_for_anim が正しい処理を行うことができる ことが確認できました。

置換表を利用しないミニマックス法（ai_mmdfs と同じ）
置換表を利用したミニマックス法（ai_mmdfs_tt と同じ）
置換表を利用しない αβ 法（ai_abs と同じ）
置換表付き αβ 法（ai_abs_tt3 と同じ）
置換表付き αβ 法で α 値と β 値の初期値を評価値の最小値と最大値に設定する（ai_abs_tt4 と同じ）

mbtree = Mbtree.load("../data/abtree_root")

print("ai_mmdfs")
mbtree.calc_score_for_anim(mbtree.root, minimax=True, init_ab=False, use_tt=False, debug=True)
print()
print("ai_mmdfs_tt")
mbtree.calc_score_for_anim(mbtree.root, minimax=True, init_ab=False, use_tt=True, debug=True)
print()
print("ai_abs_tt")
mbtree.calc_score_for_anim(mbtree.root, minimax=False, init_ab=False, use_tt=False, debug=True)
print()
print("ai_abs_tt3")
mbtree.calc_score_for_anim(mbtree.root, minimax=False, init_ab=False, use_tt=True, debug=True)
print()
print("ai_abs_tt4")
mbtree.calc_score_for_anim(mbtree.root, minimax=False, init_ab=True, use_tt=True, debug=True)

実行結果

ai_mmdfs
ミニマックス法で計算したか True
計算したノードの数 549946
枝狩りしたノードの数 0
合計 549946
割合 100.0%

ai_mmdfs_tt
ミニマックス法で計算したか True
計算したノードの数 2271
枝狩りしたノードの数 547675
合計 549946
割合 0.4%

ai_abs_tt
ミニマックス法で計算したか False
計算したノードの数 18297
枝狩りしたノードの数 531649
合計 549946
割合 3.3%

ai_abs_tt3
ミニマックス法で計算したか False
計算したノードの数 1173
枝狩りしたノードの数 548773
合計 549946
割合 0.2%

ai_abs_tt4
ミニマックス法で計算したか False
計算したノードの数 832
枝狩りしたノードの数 549114
合計 549946
割合 0.2%

今回の記事のまとめ

今回の記事では、置換表付き αβ 法 での 評価値の計算手順を視覚化するためのデータを計算 する calc_score_for_anim を定義しました。次回の記事では今回の記事で作成したデータを利用して、置換表付き αβ 法の計算手順の視覚化の処理を実装します。

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

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

次回の記事

そうすることで、計算された評価値が必ず exact value の範囲に収まり、正確な評価値（ミニマックス値）を計算できるようになります ↩
現状では、calc_score_by_ab で最短の勝利を目指すような評価値を計算するためには、ゲーム木を作成する際の実引数に shortest_victory=True を記述する必要があります ↩
リーフノードの場合は置換表を利用しないということは、でたらめな評価値の範囲を置換表に登録しても構わないということなので、7、8 行目を省略してもプログラムは正しく動作します。ただし、その内容を利用しないからと言って、間違った内容をプログラムに記述すると、後でそのプログラムを見た際にそれが正しいと勘違いしてしまう可能性があるため、実際には利用しない値であったとしても 7、8 行目は記述しておいたほうが良いと思います ↩