Pythonで〇×ゲームのAIを一から作成する その150 αβ 法の処理の効率の性質と改善方法

目次と前回の記事

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

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

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

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

αβ 法の目的のおさらいと〇×ゲームでの効率

αβ 法の目的は、ミニマックス法 で ゲーム木の評価値を計算 する際に、枝狩りを行うことで 計算を行う必要がないノードの処理を省略して 計算時間を短縮 することです。忘れた方は以前の記事を復習して下さい。

〇× ゲームの場合 は ルートノードの評価値を αβ法で計算 すると、最短の勝利を優先しない 評価値を計算する場合は、下記のプログラムの実行結果から ミニマックス法と比較 して 計算時間を約 3.3 % という かなり短い時間で計算 することができます。

なお、ゲーム木のデータは前回の記事で αβ 法の評価値を計算したゲーム木を保存したファイルから読み込んでいます。

from tree import Mbtree

mbtree = Mbtree.load("../data/abtree_root")
mbtree.calc_score_by_ab(mbtree.root, debug=True)

実行結果

計算したノードの数 18297
枝狩りしたノードの数 531649
合計 549946
割合 3.3%

また、最短の勝利を優先する 評価値を計算する場合も、下記のプログラムの実行結果からミニマックス法と比較して計算時間を 約 3.8 % というかなり短い時間で計算することができることがわかります。

mbtree = Mbtree.load("../data/abtree_sv_root")
mbtree.calc_score_by_ab(mbtree.root, debug=True)

実行結果

計算したノードの数 20866
枝狩りしたノードの数 529080
合計 549946
割合 3.8%

今回の記事では以後は最短の勝利を 優先しない 評価値を計算する 場合の説明 を行います。最短の勝利を 優先する場合も同様 なので、興味がある方は調べてみて下さい。

αβ 法の処理の効率の性質

以前の記事で説明したように αβ 法では、α 値や β 値が更新 されると 子孫ノードの評価値の計算の際 に 枝狩りが行われる評価値の範囲が増える ので 枝狩りが行われやすく なります。

max ノード の評価値を計算する際は α 値 は 増加する方向でのみ更新される ので、max ノードの子ノードの評価値を計算する処理を行う際に、最も評価値が高い子ノードの評価値を最初に計算 すると、2 つ目以降の子ノード の評価値を計算する際の α 値が最も高くなり、その結果として 最も多くの枝狩りが行われる ようになります。

同様の理由で min ノード の場合は 最も評価値が低い子ノードの評価値を最初に計算 することで、最も多くの枝狩りが行われるようになります。

max ノードの最も評価値が高い子ノードと、min ノードの最も評価値が低い子ノードは、いずれもそのノードの最善手を着手した子ノード なので、上記は以下のようにまとめることが出来ます。

αβ 法ではそのノードの 最善手を着手した子ノードを最初に計算 することで 最も多くの枝狩りが行われる 。

わかりづらいと思いますので、具体例として以下のようなノード $N$ の評価値を αβ 法で計算する例を紹介します。なお、min ノードの性質は max ノードの逆であるため同様の方法で説明できるため、max ノードのみの説明 を行います。

• max ノードである
• 評価値がそれぞれ -1、0、1 である 3 つの子ノードを持つ
• このノードの評価値を計算する際の α 値と β 値の初期値は、それぞれ負の無限大と正の無限大である

ノード $N$ の評価値を αβ 法で計算する際に、3 つの子ノード の評価値を計算する 順番 は 3 × 2 × 1 = 6 通り あるので、それぞれの場合で行われる処理について説明します。

以下の説明では 3 つの子ノード（child node）を $C_1$、$C_2$、$C_3$ と表記し、$C_1$、$C_2$、$C_3$ の順で子ノードの評価値が計算されるものとします。また、$C_1$、$C_2$、$C_3$ の評価値（score）をそれぞれ $S_1$、$S_2$、$S_3$ と表記することにします。

評価値が高い順に子ノードの評価値を計算した場合の処理

子ノードの 評価値が高い順 に計算を行った場合は、$S_1=1$、$S_2=0$、$S_3=-1$ となり、以下の手順で計算が行われます。なお、下記には記していませんが、α 狩りが行われた場合は残りの子ノードの処理は省略されます。

1. $N$ の最初の子ノードの $C_1$ の評価値を計算する際の α 値と β 値はそれぞれ負の無限大と正の無限大なので、$C_1$ の評価値を計算する際の α 値と β 値の初期値はその値になる
2. $C_1$ の評価値の計算が行われるが、下記の理由から 枝狩りが行われることはない
   • $N$ の子ノードは min ノードであり、min ノードでの枝狩りは α 狩り である
   • α 値の初期値 は 負の無限大 であり、min ノードの計算の最中 に α 値が変更されることはない ので $C_1$ の評価値を計算する際の α 値は常に負の無限大 である
   • α 狩りが行われる条件 は、$C_1$ の 子ノードの評価値が α 値以下 であるが、α 値は負の無限大 なので $C_1$ の評価値を計算する際に α 狩りが行われることはない
3. $C_1$ の評価値が 1 と計算され、α 値が 1 に更新される
4. $N$ の次の子ノード $C_2$ の評価値の計算を α 値が 1、β 値が正の無限大として開始する
5. $C_2$ の子ノードの評価値が α 値以上の場合に α 狩りが行われる
6. $C_2$ の評価値が 0 と計算されるが、α 値以下なので α 値は 1 のまま更新されない
7. $N$ の次の子ノード $C_3$ の評価値の計算を α 値が 1、β 値が正の無限大として開始する
8. $C_3$ の子ノードの評価値が α 値以上の場合に α 狩りが行われる
9. $C_3$ の評価値が -1 と計算されるが、α 値以下なので α 値は 1 のまま更新されない
10. $N$ の評価値が α 値である 1 と計算される

上記の処理を表にすると以下のようになります。上記の処理からわかるように β 値は $C_1$、$C_2$、$C_3$ での枝狩りに影響しないので省略しました。また、表ではそれぞれの 子ノードの評価値の計算 で α 狩りが行われる条件 を記しました。

	α 値	α 狩りが行われる条件	評価値
$C_1$	負の無限大	α 狩りは行われない	1
$C_2$	1	$C_2$ の子ノードの評価値 ≦ 1	0
$C_3$	1	$C_3$ の子ノードの評価値 ≦ 1	-1

評価値が低い順に子ノードの評価値を計算した場合の処理

子ノードの 評価値が低い順 に計算を行った場合は、$S_1=-1$、$S_2=0$、$S_3=1$ となり、以下の手順で計算が行われます。先ほどの手順と異なる部分を太字 にしました。

1. $N$ の最初の子ノードの $C_1$ の評価値を計算する際の α 値と β 値はそれぞれ負の無限大と正の無限大なので、$C_1$ の評価値を計算する際の α 値と β 値の初期値はその値になる
2. $C_1$ の評価値の計算が行われるが、下記の理由から枝狩りが行われることはない
   • $N$ の子ノードは min ノードであり、min ノードでの枝狩りは α 狩りである
   • α 値の初期値は負の無限大であり、min ノードの計算の最中に α 値が変更されることはないので $C_1$ の評価値を計算する際の α 値は常に負の無限大である
   • α 狩りが行われる条件は、$C_1$ の 子ノードの評価値が α 値以下であるが、α 値は負の無限大なので $C_1$ の評価値を計算する際に α 狩りが行われることはない
3. $C_1$ の 評価値が -1 と計算され、α 値が -1 に更新 される
4. $N$ の次の子ノード $C_2$ の評価値の計算を α 値が -1、β 値が正の無限大として開始する
5. $C_2$ の子ノードの評価値が α 値以上の場合に α 狩りが行われる
6. $C_2$ の評価値が 0 と計算され、α 値より大きい ので α 値は 0 に更新 される
7. $N$ の次の子ノード $C_3$ の評価値の計算を α 値が 0、β 値が正の無限大として開始する
8. $C_3$ の子ノードの評価値が α 値以上の場合に α 狩りが行われる
9. $C_3$ の評価値が 1 と計算され、α 値より大きい ので α 値は 1 に更新 される
10. $N$ の評価値が α 値である 1 と計算される

上記の処理を先程と同様の表にすると以下のようになります。

	α 値	α 狩りが行われる条件	評価値
$C_1$	負の無限大	α 狩りは行われない	-1
$C_2$	-1	$C_2$ の子ノードの評価値 ≦ -1	0
$C_3$	0	$C_3$ の子ノードの評価値 ≦ 0	1

他の場合の処理

残りの場合も同様の方法で処理が行われ、先程と同様の表にすると以下のようになります。

$S_1=1$、$S_2=-1$、$S_3=0$ の場合

	α 値	α 狩りが行われる条件	評価値
$C_1$	負の無限大	α 狩りは行われない	1
$C_2$	1	$C_2$ の子ノードの評価値 ≦ 1	-1
$C_3$	1	$C_3$ の子ノードの評価値 ≦ 1	0

$S_1=0$、$S_2=1$、$S_3=-1$ の場合

	α 値	α 狩りが行われる条件	評価値
$C_1$	負の無限大	α 狩りは行われない	0
$C_2$	0	$C_2$ の子ノードの評価値 ≦ 0	1
$C_3$	1	$C_3$ の子ノードの評価値 ≦ 1	-1

$S_1=0$、$S_2=-1$、$S_3=1$ の場合

	α 値	α 狩りが行われる条件	評価値
$C_1$	負の無限大	α 狩りは行われない	0
$C_2$	0	$C_2$ の子ノードの評価値 ≦ 0	-1
$C_3$	0	$C_3$ の子ノードの評価値 ≦ 0	1

$S_1=-1$、$S_2=1$、$S_3=0$ の場合

	α 値	α 狩りが行われる条件	評価値
$C_1$	負の無限大	α 狩りは行われない	-1
$C_2$	-1	$C_2$ の子ノードの評価値 ≦ -1	1
$C_3$	1	$C_3$ の子ノードの評価値 ≦ -1	0

それぞれの場合の α 狩りが行われる条件の比較

それぞれの場合で α 狩りが行われる条件を比較 すると以下のような表になります。表の中身の意味は以下の通りです。

• 一番上の行には $S_1$、$S_2$、$S_3$ の値を順に表記する
• 表のセルには α 狩り が行われる 子ノードの評価値の条件 を表記する
• $C_1$ ではいずれの場合も α 狩りは行われないので省略した
• 最も条件が緩いものを 太字 で、最も条件が厳しいものを 斜体 で表示した

	1、0、-1	1、-1、0	0、1、-1	0、-1、1	-1、1、0	-1、0、1
$C_2$	1 以下	1 以下	0 以下	0 以下	-1 以下	-1 以下
$C_3$	1 以下	1 以下	1 以下	0 以下	1 以下	0 以下

上記の表から 最初に最も評価値が高い子ノード の評価値を計算した場合に $C_2$ と $C_3$ の 両方で α 狩りが行われる条件が最も緩い ので 最も多く枝狩りが行われる ことがわかります。

また、評価値が低い順 に子ノードの評価値を計算した場合に $C_2$ と $C_3$ の 両方で α 枝狩りが行われる条件が最も厳しい ので、最も少なくの枝狩りが行われる こともわかります。

上記の例では α 値と β 値の初期値を負の無限大と正の無限大、子ノードの数を 3、それぞれの子ノードの評価値の値を -1、0、1 としましたが、他の条件でも上記と同じことが言えます。興味がある方は様々な条件で表を作って確認してみて下さい。

max ノードで最も評価値が高い子ノードが複数ある場合

max ノード で 最も評価値が高い子ノード が 複数ある場合 は、それらの中の どの子ノードを最初に計算 しても 上記の表の結果は変わりませんが、実際には最も評価値が高い子ノードの中で どの子ノードを先頭に移動するか によって、枝狩りが行われる数が変わります。その理由について少し考えてみて下さい。

αβ 法では、親ノードから受け渡された α 値と β 値 を利用して計算を行います。また、子ノードの評価値が計算 されることで、α 値または β 値を更新 します。

従って、最初に計算する子ノード は必ず 親ノードから受け渡された α 値と β 値 を利用して計算を行を行う必要があります。

例えば max ノードで $C_1$、$C_2$ という 2 つの子ノードが、最も高い $S$ という評価値を持つ場合に、$C_1$ の評価値を最初に計算すると以下の順番で計算が行われます。

1. 親ノードから受け継がれた α 値と β 値を初期値として $C_1$ の評価値を計算する
2. $C_1$ の評価値が $S$ と計算され、α 値 < $S$ の場合は α 値を $S$ で更新する
3. $C_2$ の評価値を計算する

一方 $C_2$ を最初に計算すると以下の順番で計算が行われます。

1. 親ノードから受け継がれた α 値と β 値を初期値として $C_2$ の評価値を計算する
2. $C_2$ の評価値が $S$ と計算され、α 値 < $S$ の場合は α 値を $S$ で更新する
3. $C_1$ の評価値を計算する

親ノードから受け継がれた α 値が $S$ よりも小さい場合 は上記の手順 2 で α 値が更新される ので、$C_1$ と $C_2$ を計算する際の α 値の初期値 は、$C_1$ と $C_2$ の どちらを最初に計算するか によって、下記の表のように 異なります。

	$C_1$ を先に計算した場合	$C_2$ を先に計算した場合
$C_1$	親から受け継がれた α 値	$S$
$C_2$	$S$	親から受け継がれた α 値

α 値の初期値が異なれば $C_1$、$C_2$ の評価値の計算を行った際の 枝狩りの数は異なる 場合が生じるので、どちらを先に計算するか によって 枝狩りの数が異なる 可能性が生じます。

ただし、一般的には最も評価値が高い子ノードの中で、どの子ノードを最初に計算すると最も枝狩りが行われるかを 知ることは困難 です。また、ほとんどの場合は枝狩りの数が大きく異なることはない ので、最初に計算する子ノードは どれを選んでも構わない でしょう。

なお、この性質は max ノードで評価値の低い順に計算する場合も同様です。

αβ 法の枝狩りの効率のまとめ

ここまでの内容をまとめると以下のようになります。

αβ 法では子ノードの評価値を計算する際に、最善手を着手した子ノードを最初に計算 すると 最も多くの枝狩り が行われる。

最善手を着手した子ノードが複数ある場合 は、その中のどの子ノードを最初に計算するかによって、枝狩りの数が異なる場合があるが、ほとんどの場合で大きく異なることはないので 一般的にはどれを選んでも良い。

なお、わざわざ効率の悪い処理を行うことは通常はないので、下記の内容は上記のまとめから除外しました。

αβ 法では、max ノードの子ノードの評価値を計算する際に、評価値が低い順に子ノードの計算を行うと最も少なく枝狩りが行われる。min ノードでは、評価値の大小を逆に考えると同じことが言える。

効率の良い αβ 法の処理を行う工夫

残念ながら αβ 法の計算 を行う際に、それぞれの 子ノードの評価値の正確な値 を あらかじめ知ることはできません¹。そのため、αβ 法で効率の良い計算を行いたい場合に、αβ 法以外の方法 で 最善手と思われる着手を見積もる ことで、最も評価値が高いと 考えられる 子ノードの評価値の計算を最初に行うという工夫があります。

例えば本記事でこれまでに作成した αβ 法とは異なる方法で最善手を計算する関数を利用 するなどの方法があるので、この後で実際に行ってみることにします。他にも αβ 法の効率を高める様々な方法が考えられているので、興味がある方は調べてみると良いでしょう。

αβ 法の枝狩りの効率の確認

上記が本当に正しいか どうかを、以下のそれぞれの場合で αβ 法を実行して比較することで 確認する ことにします。なお、下記では max ノードでの条件を記述していますが、min ノードではその逆の条件で計算を行います。

• 最善手を着手した子ノードを最初に計算する
• 様々な AI で計算した最善手を着手した子ノードを最初に計算する。なお、弱解決でない AI は本当の最善手を計算するとは限らない
• max ノードでは評価値が低い順に、min ノードでは評価値が高い順に子ノードを計算する

上記のような計算を行う方法について少し考えてみて下さい。

最善手を着手した子ノードを最初に計算する

αβ 法で評価値を計算する calc_score_by_ab では、子ノードの評価値を計算する際 に、下記のプログラムのように 子ノードの一覧が list で記録 されている children 属性の先頭の要素から順番 に計算を行っています。

    for childnode in node.children:

そのため、ゲーム木の 全てのノードに対して、下記の処理を行った後で calc_score_by_ab を実行する ことで、評価値が最も高い子ノードが最初に計算される ようになります。

• 最善手を着手した子ノードを children 属性の list の 要素から探す
• 見つけた要素 を children 属性の 先頭の要素と交換 する

上記の処理を行う方法について少し考えてみて下さい。

見つけた要素を先頭に移動し、先頭から見つけた要素までを 1 つずつ後ろにずらすという方法も考えられますが、順番を維持する必要がないのであれば、ずらすという処理に時間がかかるのであまりお勧めしません。

例えば、1000 冊の本が並べられている本棚の 900 冊目の本を先頭に移動したい場合に、1 冊目と 900 冊目を交換するのは簡単ですが、900 冊目を取り出して、1 ~ 899 冊目の本を 1 つずつずらして、900 冊目を 1 冊目の所にいれるのは大変です。

上記の処理の記述方法

最善手を着手した子ノードが代入された要素を children 属性の先頭の要素と交換するということは、最善手の要素の インデックスを i とした場合に 0 番と i 番の要素を入れ替える 処理を行うということです。

ノードが node という変数に代入されている場合は、以前の記事で説明した、変数の値を入れ替える方法を利用することで下記のプログラムのように記述することができます。

node.children[0], node.children[i] = node.children[i], node.children[0]

最善手を着手した子ノードが代入された children 属性の要素の インデックス は、以下の手順で求めることができます。

• 最善手を着手した子ノードの 評価値は 、そのノードの評価値と等しい
• children 属性の 先頭の要素から そのノードの評価値と 等しい要素を探す

なお、先程説明したように 最善手が複数ある場合 は、その中の どの最善手を選択しても枝狩りの数は大きく変わらない ので、最初に見つかった最善手を選択する ことにします。

従って node の最善手を着手した子ノードを children 属性の先頭と入れ替える処理は下記のプログラムのように記述することができます。

• 1 行目：組み込み関数 enumerate を利用して children 属性の先頭の要素から順番に、そのインデックスと要素を変数に代入するという繰り返し処理を行う
• 2 ~ 4 行目：親ノードと子ノードの評価値が等しい場合は、最善手を着手した子ノードなので、4 行目でそのノードと先頭のノードを交換し、5 行目の break 文で繰り返し処理を終了する

1  for i, childnode in enumerate(node.children):
2      if node.score == childnode.score:
3          node.children[0], node.children[i] = node.children[i], node.children[0]
4          break

ゲームの決着がついたノードには子ノードは存在しませんが、その場合は children 属性に空の list が代入されているので、2 ~ 4 行目の処理は 1 度も行われません

先頭の子ノードの評価値が親ノードの評価値と等しい場合は i に 0 が代入された状態で 3 行目が実行されますが、その場合は下記のプログラムのように 0 番の要素に 0 番の要素が代入されるという処理が 2 回行われ、実質的に何の処理も行われないことになるので問題はありません。

node.children[0], node.children[0] = node.children[0], node.children[0]

以下の手順で先頭に移動したい要素のインデックスを求めることもできます。同様の方法を、この後の move_ai_bestmove_to_head で実際に利用します。また、この方法は Mbtree クラスの draw_subtree メソッドの中で既に記述しています。

• 1 行目：子ノードが存在しない場合に 2 行目を実行するとエラーになるので子ノードが存在する場合のみ処理を行うようにする
• 2 行目：最善手の一覧を表す bestmoves 属性の中から先頭の要素を取り出す
• 3 行目：最善手を着手したノードを children_by_move 属性から取り出す
• 4 行目：実引数に記述した値が代入されている要素のインデックスを計算する list の index メソッド を利用してインデックスを計算する

1  if len(node.bestmoves) > 0:
2      bestmove = node.bestmoves[0]
3      bestnode = node.children_by_move[bestmove]
4      index = node.children.index(bestnode)

Mbtree クラスの move_bestmove_to_head の定義

すべてのノード に対して上記の処理を行う move_bestmove_to_head というメソッドを Mbtree クラスに下記のプログラムのように定義する事にします。なお、先頭（head）に移動する子ノードは 最善手（bestmove）のノード なので、そのような名前にしました。

全てのノードに対して先程の処理を記述しているだけなので、説明は省略します。

from tree import Mbtree

def move_bestmove_to_head(self):
    for node in self.nodelist:
        for i, childnode in enumerate(node.children):
            if node.score == childnode.score:
                node.children[0], node.children[i] = node.children[i], node.children[0]
                break
            
Mbtree.move_bestmove_to_head = move_bestmove_to_head

以前の記事で説明したように、αβ 法では 本当の評価値とは異なる評価値 が計算される ノードが存在する ので、下記のプログラムのように 新しくゲーム木を作成 しそのデータに対して move_bestmove_to_head メソッドを 呼び出す必要 があります。その後で calc_score_by_ab を実行すると、実行結果のように評価値を計算するノードの割合が 0.4 % のように、先程の 3.3 % と比べて さらに少なくなったことが確認 できます。

mbtree = Mbtree(algo="df")
mbtree.move_bestmove_to_head()
mbtree.calc_score_by_ab(mbtree.root, debug=True)

実行結果

計算したノードの数 2312
枝狩りしたノードの数 547634
合計 549946
割合 0.4%

なお、αβ 法で 最も効率よく枝狩りを行なえる場合 は、計算する必要があるノード数が 全体のノードの数の平方根の値くらいになる と言われています。$\sqrt{549946} = 約 741.5 $ なので、上記の 2312 は平方根よりは多いですが、〇× ゲームのゲーム木では 平方根と大きく変わらないくらいの効率 で枝狩りが行うことができていることが確認できました。

AI が計算した最善手を着手した子ノードを最初に計算する

次に、指定した AI で計算した最善手 を着手した子ノードを 最初に計算 する move_ai_bestmove_to_head というメソッドを Mbtree クラスに定義する事にします。この関数の 仮引数 は AI の関数を代入する ai とその パラメータ―を代入する params です。

Mbtree クラスの move_ai_bestmove_to_head の定義

下記は move_ai_bestmove_to_head の定義です。

• 1 行目：仮引数 ai と params を持つメソッドとして定義する。また params はデフォルト値を {} とするデフォルト引数とする
• 3 行目：子ノードが存在する場合のみ処理を行うようにする
• 4 行目：node の局面に対する最善手の計算を仮引数 ai に代入された AI で行う。またその際に、仮引数 params に代入されたパラメータを利用する
• 5 行目：list の index メソッドを利用して children 属性の list の中から bestmove が代入されている要素のインデックスを計算する
• 6 行目：0 番と i 番の要素を入れ替える

1  def move_ai_bestmove_to_head(self, ai, params={}):
2      for node in self.nodelist:
3          if len(node.children) > 0:
4              bestmove = ai(node.mb, **params)
5              bestnode = node.children_by_move[bestmove]
6              i = node.children.index(bestnode)
7              node.children[0], node.children[i] = node.children[i], node.children[0]
8              
9  Mbtree.move_ai_bestmove_to_head = move_ai_bestmove_to_head

行番号のないプログラム

def move_ai_bestmove_to_head(self, ai, params={}):
    for node in self.nodelist:
        if len(node.children) > 0:
            bestmove = ai(node.mb, **params)
            bestnode = node.children_by_move[bestmove]
            i = node.children.index(bestnode)
            node.children[0], node.children[i] = node.children[i], node.children[0]
            
Mbtree.move_ai_bestmove_to_head = move_ai_bestmove_to_head

様々な AI を利用した αβ 法の計算

上記の定義後に、下記のプログラムで ai1s から ai14s で計算した 最善手を着手した子ノードを最初に計算 した場合の αβ 法の計算を行います。なお、先ほどの move_bestmove_to_head と異なり、最善手 はゲーム木のノードの score 属性ではなく AI の関数で計算する ので、ゲーム木のデータを毎回作り直す必要はありません。

なお、これらの AI では最善手を計算する際に 乱数を利用する ので、下記の実行結果とは 異なる結果になる場合があります。

• 1 行目：ai モジュールを ai_module という名前でインポートする
• 3 行目：1 ~ 14 までの整数の繰り返し処理を行う
• 4、5 行目：AI の名前を変数に代入し、print で表示する
• 6 行目：getattr を利用して AI の関数を ai のモジュールから取り出す
• 7 行目：取り出した AI の関数を実引数に記述して move_ai_bestmove_to_head を呼び出す
• 8 行目：キーワード引数 debug=True を記述して calc_score_by_ab を呼び出して、ルートノードの評価値を計算した結果を表示する

1  import ai as ai_module
2
3  for i in range(1, 15):
4      ainame = f"ai{i}s"
5      print(ainame)
6      ai = getattr(ai_module, ainame)
7      mbtree.move_ai_bestmove_to_head(ai)
8      mbtree.calc_score_by_ab(mbtree.root, debug=True)

行番号のないプログラム

import ai as ai_module

for i in range(1, 15):
    ainame = f"ai{i}s"
    print(ainame)
    ai = getattr(ai_module, ainame)
    mbtree.move_ai_bestmove_to_head(ai)
    mbtree.calc_score_by_ab(mbtree.root, debug=True)

実行結果

ai1s
計算したノードの数 18297
枝狩りしたノードの数 531649
合計 549946
割合 3.3%
ai2s
計算したノードの数 14941
枝狩りしたノードの数 535005
合計 549946
割合 2.7%
ai3s
計算したノードの数 8906
枝狩りしたノードの数 541040
合計 549946
割合 1.6%
ai4s
計算したノードの数 8461
枝狩りしたノードの数 541485
合計 549946
割合 1.5%
ai5s
計算したノードの数 5721
枝狩りしたノードの数 544225
合計 549946
割合 1.0%
ai6s
計算したノードの数 4839
枝狩りしたノードの数 545107
合計 549946
割合 0.9%
ai7s
計算したノードの数 2156
枝狩りしたノードの数 547790
合計 549946
割合 0.4%
ai8s
計算したノードの数 1918
枝狩りしたノードの数 548028
合計 549946
割合 0.3%
ai9s
計算したノードの数 1756
枝狩りしたノードの数 548190
合計 549946
割合 0.3%
ai10s
計算したノードの数 2337
枝狩りしたノードの数 547609
合計 549946
割合 0.4%
ai11s
計算したノードの数 1582
枝狩りしたノードの数 548364
合計 549946
割合 0.3%
ai12s
計算したノードの数 1496
枝狩りしたノードの数 548450
合計 549946
割合 0.3%
ai13s
計算したノードの数 1496
枝狩りしたノードの数 548450
合計 549946
割合 0.3%
ai14s
計算したノードの数 1496
枝狩りしたノードの数 548450
合計 549946
割合 0.3%

下記は上記の実行結果から、計算したノードの数 と 割合 を 表にまとめたもの です。それぞれの AI については以前の記事を参照して下さい。

AI	ノードの数	割合
なにもしない	18297	3.3 %
ai1s	18297	3.3 %
ai2s	14941	2.7 %
ai3s	8906	1.6 %
ai4s	8461	1.5 %
ai5s	5721	1.0 %
ai6s	4839	0.9 %
ai7s	2156	0.4 %
ai8s	1918	0.3 %
ai9s	1756	0.3 %
ai10s	2337	0.4 %
ai11s	1582	0.3 %
ai12s	1496	0.3 %
ai13s	1496	0.3 %
ai14s	1496	0.3 %
move_bestmove_to_head で 最善手を先頭に移動	2312	0.4 %

計算結果の考察

ai1s は左上のマスから順に空いているマスを調べて着手する AI なので children 属性の先頭の要素を常に選択する AI です。従って なにもせずに αβ 法を計算した際と同じ結果 になります。

ai2s は ランダムな着手を行う AI です。何もしない場合よりは 若干割合が減っている のはおそらくランダムに着手を行ったほうが、なにもしない場合よりも 先頭のノードの評価値が平均的に高くなる からだと思います²。

ai3s は 真ん中のマスに優先的に着手する という 単純な AI なので決して 強くはありません。それにも関わらず、ai3s を利用することで枝狩りを行わないノードの割合を、何もしない場合の 3.3 % と比べて 約半分の 1.6 % に減らすことが出来ている点が気になった人はいないでしょうか？その理由について少し考えてみて下さい。

ai3s は 〇 が最初に真ん中のマスに着手しなかった場合は、× の 1 手目で必ず最善手を着手する AI です。〇 の 1 手目は 9 通りの着手があるため、× の 1 手目を表す 深さ 1 の 9 つのノードのうち 8 つのノード で ai3s は 必ず最善手を選択 します。

ゲーム木では一般的に 深さが浅い程、子孫ノードの数が多くなる ので、αβ 法では枝狩りを行ったノードの 深さが浅い程、一般的に多くの枝狩りを行うことができます。そのため、深さが 1 のノードの多くで最善手を選択 する ai3 を利用することで多くの枝狩りを行うことが出来、その結果割合を 1.6 % まで減らすことが出来たと考えられます。

ai3s から 強くなるための様々な工夫 が少しづつ行われており、その結果 最善手が先頭に移動する場合が多くなる ため 割合も減っていく ことが確認できます。

ai8s はまだ 弱解決の AI ではありません が、弱解決の AI である ai12s 以降の AI と 割合が大きく変わりません。このことから、弱解決の AI ではなくても、ある程度以上の強さを持った AI を利用することで、αβ 法の効率を大きく改善することが出来る ことがわかります。

なお、弱解決の ai12s 以降の AI を利用 した場合は、move_bestmove_to_head によって 最善手を最初に計算する場合 と比べて 割合が低くなっています。これは、先程説明したように、最善手が複数存在する場合 に、どの最善手の子ノードを最初に計算するかによって 枝狩りの数が若干変わることが原因 です。ただし、この程度の差であれば処理時間に大きな差は生じないので、気にする必要はないでしょう。

上記の表をまとめると以下のようになります。

最善手と思われる着手を計算する AI を利用する ことで αβ 法の枝狩りの効率 を以下のように 改善することができる

• AI の精度が低すぎる と効率を上げることは できない
• AI の精度が高いほど より 多くの効率をあげることができる が、一定の精度から先 は 効率がほとんど変わらなくなる

max ノードで評価値が低い順、min ノードで評価値が高い順に子ノードを計算する

αβ 法が 最低でもどのくらいの効率を得ることが出来るか を、max ノードで評価値が低い順、min ノードで評価値が高い順 に子ノードを計算することで確認することにします。

max ノードで評価値が低い順に子ノードを計算するためには、すべての max ノードの children 属性の 要素を評価値が低い順に並べ替える 必要があります。min ノードの場合は高い順に並べる必要があります。データを何らかの基準で 並べ替える ことを ソート（sort） と呼び、python では以下の方法で list のソート を行うことができます。

• list の sort メソッド を利用する
• 組み込み関数 sorted を利用する

list の sort メソッドの詳細は下記のリンク先を参照して下さい。

組み込み関数 sorted の詳細は下記のリンク先を参照して下さい。

なお、ソートを行うアルゴリズム にはさまざまなものがあり、アルゴリズムを勉強する際に役立つ ので、今後の記事でソートのアルゴリズムについて取り上げる予定です。

list の sort メソッドと組み込み関数 sorted の使い方

この 2 つは似ていますが、sort メソッド はその list の要素そのものがソートされる のに対し、sorted は 元の list は変更せず に、元のリストの要素をソートした 新しい list を作成して返す 処理を行う点が 異なります。また、sorted は list だけでなく、反復可能オブジェクトであればなんでもソートできる 点が異なります。

具体例を挙げます。下記のプログラムは list が代入された a に対して sort メソッド を呼び出すことで、a の要素を小さい順にソート するプログラムです。

a = [3, 1, 2, 5, 4]
a.sort()
print(a)

実行結果

[1, 2, 3, 4, 5]

一方、下記のプログラムは sorted を利用して a の要素をソートした 新しい list を作成 して b に代入 しています。実行結果からわかるように a の中身は変更されません。

a = [3, 1, 2, 5, 4]
b = sorted(a)
print(a)
print(b)

実行結果

[3, 1, 2, 5, 4]
[1, 2, 3, 4, 5]

また、下記のプログラムのように sorted は list だけでなく、反復可能オブジェクトである tuple のソート を行うこともできます。tuple はその内容を後から変更できない イミュータブル なオブジェクト³ですが、sorted は元の tuple を変更するのではなく 新しい list を作成する のでこのような処理を行うことができます。

なお、実行結果からわかるように、sorted が返す値 は、実引数に記述したデータの種類に関わらず 必ず list になります。

a = (3, 1, 2, 5, 4)
b = sorted(a)
print(a)
print(b)

実行結果

(3, 1, 2, 5, 4)
[1, 2, 3, 4, 5]

このように、list の sort メソッド と、組み込み関数 sorted はどちらもソートを行いますが 異なる点がある ので、状況に応じて使い分ける必要 があります。

大きい順のソート

上記のソートでは数値の小さい順にソートが行われましたが、大きい順にソートを行う 場合はどちらの場合でも下記のプログラムのように 反転（reverse） を表すキーワード引数 reverse=True を記述 します。

a = [3, 1, 2, 5, 4]
a.sort(reverse=True)
print(a)
a = [3, 1, 2, 5, 4]
b = sorted(a, reverse=True)
print(a)
print(b)

実行結果

[5, 4, 3, 2, 1]
[3, 1, 2, 5, 4]
[5, 4, 3, 2, 1]

以後の説明 は sort メソッドも組み込み関数 sorted も 同じ なので sort メソッドのみの説明を行います。

数値以外のデータのソート

sort メソッドは < 演算子を利用 してソートの処理を行っています⁴。そのため、< 演算子で比較を行うことができるデータ であれば、数値以外のデータが要素に代入されていても 利用することができます。

例えば、文字列型 のデータは < 演算子 で 辞書順で比較が行われる ので下記のプログラムのように 辞書順でソート することができます。

a = ["happy", "sad", "angry"]
a.sort()
print(a)

実行結果

['angry', 'happy', 'sad']

直観的に反すると思うかもしれませんが、下記のプログラムのように 小文字は大文字よりも大きい と判定されます。

print("abc" > "ABC")

実行結果

True

これは、文字列の比較 は 文字コード（文字を表す番号のこと）の数値 で行われるためで、半角の文字の文字コードを定めたASCII 文字コード表では小文字よりも大文字の方が文字コードの数字が大きく設定されているからです。

一方、クラスから作成されたインスタンス は、通常は < 演算子で比較することはできません⁵。そのため、ノードを表す Node クラスのインスタンス は < 演算子で比較することができないの で、下記のプログラムのように children 属性に代入されたノードの一覧を表す list の sort メソッドを呼び出すと実行結果のような エラーが発生 します。

mbtree.root.children.sort()

実行結果

---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
Cell In[13], line 1
----> 1 mbtree.root.children.sort()

TypeError: '<' not supported between instances of 'Node' and 'Node'

上記の Node クラスのインスタンス（instances）どうし（between）を < 演算子で比較することができない（not supported）というエラーメッセージはそのことを表しています。

children 属性の要素に代入された ノードのソート は、ノードの score 属性に代入された評価値を基準 として行う必要があります。そのような場合は、sort メソッドに下記のような キーワード引数 key を記述 することでソートを行うことができます。

• キーワード引数 key には以下のような 関数を代入 する
  • ソートを行う list の要素を代入 する 仮引数を 1 つだけ 持つ
  • 返り値 として、仮引数に代入されたオブジェクトの中の、ソートの基準となるデータを返す。返り値のデータは必ず < 演算子で比較できる必要がある
  • 関数の名前は何でもよい

具体例を挙げて説明します。下記のプログラムの 3 ~ 7 行目は 果物（fruit）の値段と名前を表す dict を要素として持つ list です。この list の要素を 値段の小さい順でソート するために、9、10 行目でこの list の要素を代入する仮引数 を持ち、price のキーの値を返す という処理を行う keyfunc という関数を定義 しています。12 行目で キーワード引数 key=keyfunc を記述して sort メソッドを呼び出す ことで、実行結果のように 値段の小さい順に list の要素がソートされた ことが確認できます。

 1  from pprint import pprint
 2  
 3  fruits = [
 4      { "name": "orange", "price": 200},
 5      { "name": "melon", "price": 1000},
 6      { "name": "apple", "price": 100},
 7  ]
 8  
 9  def keyfunc(fruit):
10      return fruit["price"]
11  
12  fruits.sort(key=keyfunc)
13  pprint(fruits)

行番号のないプログラム

from pprint import pprint

fruits = [
    { "name": "orange", "price": 200},
    { "name": "melon", "price": 1000},
    { "name": "apple", "price": 100},
]

def keyfunc(fruit):
    return fruit["price"]

fruits.sort(key=keyfunc)
pprint(fruits)

実行結果

[{'name': 'apple', 'price': 100},
 {'name': 'orange', 'price': 200},
 {'name': 'melon', 'price': 1000}]

ラムダ式（lambda expression）による関数の定義

上記の keyfunc という 関数 は、12 行目のキーワード引数でしか利用されません。一度しか利用しない関数 を上記のように 定義するのは記述が面倒 なので、Python ではこのような関数を ラムダ式 という記述方法で 簡潔に記述 することができるようになっています。

ラムダ式 は、下記のように記述して定義する 関数 で、ラムダ式を 変数やキーワード引数に直接代入 することができます。仮引数 の部分は通常の関数と同様の方法で () で囲わずに記述 します。また、文の所 には 1 つの文だけを記述 することができます。

lambda 仮引数: 文

上記のラムダ式は 下記のような関数を定義 したのと同じ意味を持ちます。ただし、ラムダ式で定義した関数を <lambda>() のような方法で呼び出すことはできないので、必ず変数やキーワード引数に代入する必要 があります。

def <lambda>(仮引数):
    return 文

先程のプログラムはラムダ式を利用することで、下記のプログラムのように簡潔に記述することができます。先ほどの keyfunc の定義 が 7 行目の lambda fruits: fruits["price"] という ラムダ式で記述 されています。

1  fruits = [
2      { "name": "orange", "price": 200},
3      { "name": "melon", "price": 1000},
4      { "name": "apple", "price": 100},
5  ]
6  
7  fruits.sort(key=lambda fruit: fruit["price"])
8  pprint(fruits)

行番号のないプログラム

fruits = [
    { "name": "orange", "price": 200},
    { "name": "melon", "price": 1000},
    { "name": "apple", "price": 100},
]

fruits.sort(key=lambda fruit: fruit["price"])
pprint(fruits)

修正箇所

fruits = [
    { "name": "orange", "price": 200},
    { "name": "melon", "price": 1000},
    { "name": "apple", "price": 100},
]

-def keyfunc(fruit):
-   return fruit["price"]

-fruits.sort(key=keyfunc)
+fruits.sort(key=lambda fruit: fruit["price"])
pprint(fruits)

実行結果

[{'name': 'apple', 'price': 100},
 {'name': 'orange', 'price': 200},
 {'name': 'melon', 'price': 1000}]

ラムダ式 はこのように、以下のような条件を満たす関数を定義 する際に 良く使われる ので、覚えておくと便利です。

• プログラムの中で 一度しか呼び出されない
• 関数が行う処理を 1 つの文で記述できる
• 1 つの文が行った計算結果を 返り値として返す

ラムダ式の詳細については、下記のリンク先を参照して下さい。

組み込み関数 max や min でも上記と同様の キーワード引数 key を記述することで、数値以外のデータの最大値や最小値を計算することが出来ます。

下記は、先程と同じデータの中の最も値段の高い果物を表示するプログラムです。

fruits = [
    { "name": "orange", "price": 200},
    { "name": "melon", "price": 1000},
    { "name": "apple", "price": 100},
]

print(max(fruits, key=lambda fruit: fruit["price"]))

実行結果

{'name': 'melon', 'price': 1000}

Mbtree クラスの sort_children_by_worst_score メソッドの定義

すべてのノード に対して children 属性の要素を、max ノードでは評価値の低い順、min ノードでは評価値の高い順 で 並べ替える 処理を行う sort_children_by_worst_score というメソッドを Mbtree クラスに定義する事にします。下記はそのメソッドの定義です。最善手（best move）と逆の順で並べ替えるので最悪（worst）を名前に入れました。

• 5 行目：〇 の手番の max ノードの場合は評価値の小さい順、× の手番の min ノードの場合は大きい順で並べ替える必要があるので sort メソッドのキーワード引数に記述する値をそのように計算する
• 6 行目：list の sort メソッドに、要素の score 属性を取り出して返す関数をラムダ式を利用して定義し、3 行目で計算した順番でソートする

1  from marubatsu import Marubatsu
2
3  def sort_children_by_worst_score(self):
4      for node in self.nodelist:
5          reverse = False if node.mb.turn == Marubatsu.CIRCLE else True
6          node.children.sort(key=lambda childnode: childnode.score, reverse=reverse)
7      
8  Mbtree.sort_children_by_worst_score = sort_children_by_worst_score

行番号のないプログラム

from marubatsu import Marubatsu

def sort_children_by_worst_score(self):
    for node in self.nodelist:
        reverse = False if node.mb.turn == Marubatsu.CIRCLE else True
        node.children.sort(key=lambda childnode: childnode.score, reverse=reverse)
    
Mbtree.sort_children_by_worst_score = sort_children_by_worst_score

先程の mbtree の各ノードの評価値は αβ 法の計算処理によって正しくない値が計算されている場合があるので、上記の定義後に下記のプログラムでゲーム木を作成し sort_children_by_worst_score で子ノードの順番を並べ変えたゲーム木に対して calc_score_by_ab を呼び出すと、割合 が実行結果のように何もしない場合の 3.3 % と比べて 10 倍以上の 36.2 % という値になる ことがわかります。

mbtree = Mbtree(algo="df")
mbtree.sort_children_by_worst_score()
mbtree.calc_score_by_ab(mbtree.root, debug=True)

実行結果

計算したノードの数 198837
枝狩りしたノードの数 351109
合計 549946
割合 36.2%

また、この結果から 〇×ゲームのゲーム木 の場合は 最悪の場合 でも αβ 法を利用することでミニマックス法の 1/3 の時間で処理を行うことができる ことが確認できました。

今回の記事のまとめ

今回の記事では、αβ 法の処理の効率の性質 について説明し、最善手の着手が行われた子ノードの評価値を最初に計算する ことで、最も多くの枝狩りを行うことが出来る ことを示しました。また、ある程度の精度を持つ AI を利用 することで、αβ 法の 処理の効率を大幅に改善できる ことを示しました。

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

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

次回の記事

近日公開予定です

1. あらかじめ知ることができているのであれば、αβ 法を行わなくても子ノードの評価値の最大値（または最小値）を計算することで即座に評価値の計算を行うことができます ↩

2. 本当にそうであるかどうかについて知りたい場合は実際に検証する必要がありますが、特に重要ではないと思いますので本記事では検証はしません。興味がある方は実際に検証してみると良いでしょう ↩

3. tuple に sort メソッドが存在しないのはそのためです ↩

4. そのことは sorted の公式ドキュメントに記述されています ↩

5. 今回の記事では紹介しませんが、特殊メソッドを定義する事で < 演算子で比較することができるようになり、その場合は sort メソッドで比較できるようになります ↩