Pythonで〇×ゲームのAIを一から作成する その105 ミニマックス法によるゲーム木の全てのノードの評価値の計算

目次と前回の記事

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

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

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

ルールベースの AI の一覧については、下記の記事を参照して下さい。

ゲーム木を用いた最強の AI の作成

これまでの記事で作成した ゲーム木を利用 することで、全ての局面 で 局面の状況 と、最善手を調べる ことができます。それによって、以前の記事で説明した〇×ゲームを 強解決 したことになり、全ての局面で最善手を着手 できる 最強の AI を作成 することができます。

そこで、今回の記事ではゲーム木を利用して、全ての局面での局面の状況と、最善手を調べる方法について説明します。

局面の状況の意味

まず、いくつかの用語のおさらいをします。

最善手 とは、お互いが最善手を選択し続けた場合 に、自分にとって 最も有利となる合法手 のことです。

最強の AI とは、全ての局面で最善手を選択する AI のことです。以前の記事で作成したルールベースの ai14 は、その AI が着手を行った場合に出現しない局面では、最善手を選択するかどうかが保証されないので、弱解決の AI です。

また、以前の記事で説明したように、〇×ゲームのような 二人零和有限確定完全情報ゲーム で、ゲームの結果 が、勝利、敗北、引き分け の 3 種類に分類される場合は、全ての局面 は、その局面から 最強の AI どうしが対戦した結果 によって、「先手の必勝の局面」、「引き分けの局面」、「後手の必勝の局面」 の 3 つの状況に分類 することができます。

つまり、ゲーム木の 全てのノードに対して、そのノードの局面の状況が、この 3 つのどれに分類されるかが判明すれば、その情報を元に最善手を選択できるようになり、その結果、最強の AI を作成することができる ようになります。

局面の状況を表すデータの定義

プログラムで局面の状況を扱うためには、3 つの局面の状況 を どのようなデータで表現するかを決める 必要があります。どのようなデータを割り当てるかについては、様々な方法が考えられますが、最善手を選択する際に比較を行う必要がある ので、大小の比較を行うことができる 数値で表すのが良い でしょう。また、その数値はいずれかのプレイヤーの立場から見て 有利な局面の状況のほうが大きな値 にします。そうすることによって、もう片方 のプレイヤーの立場から見ると、小さな値の方が有利な局面 を意味するようになります。

本記事では、上記の条件を満たす値として、下記の表のようなデータを割り当てることにしますが、他のデータを割り当てたり、× のプレイヤーが有利になる局面の状況のほうを大きな値に設定してもかまいませんので、別の値を割り当てたい人は自由に変更して下さい。

なお、〇×ゲームでは、先手は 〇 のプレイヤー、後手は × のプレイヤーなので、局面の状況を「〇の必勝の局面」、「引き分けの局面」、「×の必勝の局面」と言い換えました。

局面の今日今日	データ
〇の必勝の局面	1
引き分けの局面	0
×の必勝の局面	-1

上記のように、〇 のプレイヤーから見て有利な状態に、より大きな数値を割り当てることで、このデータを〇 のプレイヤーの立場から見た局面の 評価値 として考えることができるようになるので、以後は 局面の状況のことを評価値と呼ぶ ことにします。

全てのゲーム木のノードに対して、この評価値がわかれば、以下の方法で 全ての局面の最善手を計算 することができるようになります。

• 〇 のプレイヤーの手番 のノードの場合は、子ノードの中で 最も評価値が高い ノードへの着手を選択する
• × のプレイヤーの手番 のノードの場合は、子ノードの中で、最も評価値が低い ノードへの着手を選択する

評価値を計算するアルゴリズム

次に、ゲーム木の全てのノードの評価値を計算する方法を紹介します。どのような方法で計算できるかについて少し考えてみて下さい。

リーフノードの評価値の計算

ゲーム木のノードの中で、評価値が確定しているノード があります。それは、ゲームの決着が付いた、子ノードが存在しないゲーム木の末端の リーフノード です。〇 の勝利の局面は、〇 の必勝の局面でもあるので、それらのノードに下記の表の評価値を割り当てます。

状態	評価値
〇 の勝利（〇 の必勝の局面）	1
引き分け（引き分けの局面）	0
× の勝利（× の必勝の局面）	-1

全ての子ノードの評価値が求められているノードの評価値の計算

次に、全ての子ノードの評価値が求められている ノードを探し、その評価値を以下の方法で計算します。これは、「自分にとって 最も有利となる着手を選択 する」という 最善手の定義から明らか でしょう。

• ノードが 〇 の手番 の場合は、子ノードの評価値の中で 最も高い 評価値とする
• ノードが × の手番 の場合は、子ノードの評価値の中で 最も低い 評価値とする

上記の方法で評価値を計算する計算を繰り返すことで、全てのノードの評価値が計算できます。なお、そのことの証明は後で行います。

評価値を計算するアルゴリズムのまとめ

評価値の計算を行うアルゴリズム をまとめると以下のようになります。

1. ゲームの決着がついている リーフノードの評価値を全て計算 する
2. 全ての子ノードの評価値が求められている ノードの評価値を計算する
3. 手順 2 を、全ての子ノードの評価値が求められているノードが なくなるまで 繰り返す

ただし、手順 2 では、以下の方法で評価値を計算する。

• ノードが 〇 の手番の場合は、子ノードの評価値の中で最も高い評価値とする
• ノードが × の手番の場合は、子ノードの評価値の中で最も低い評価値とする

アルゴリズムの処理の流れの具体例

具体例として、上記のアルゴリズムで、下図の〇×ゲームの部分木の全てのノードの評価値を計算する処理の流れを紹介します。

リーフノードの評価値の計算

上図の水色、黄色、ピンク色の局面が、決着がついているリーフノードの局面です。それぞれの色のノードの評価値は以下の表のようになります。

局面の色	局面の状態	評価値
水色	〇 の勝利（〇 の必勝の局面）	1
黄色	引き分け（引き分けの局面）	0
ピンク	× の勝利（× の必勝の局面）	-1

色では具体的な評価値がわかりづらいので、下図のように具体的な評価値をゲーム盤の左上に表示します。また、新しく計算された評価値は赤色の文字で表示することにします。

全ての子ノードの評価値が求められているノードの評価値の計算

上図で、全ての子ノードの評価値が求められているノードは、いずれも子ノードが 1 つしかないので、合法手は 1 つしかありません。そのため、それらのノードの評価値は、子ノードの評価値と等しくなります。下図は新しく計算したノードの評価値を加えたものです。

上図で、全ての子ノードの評価値が求められている 3 つのノードは、いずれも × の手番 のノードで、子ノードが 2 つずつあります。そのため、それらのノードの評価値は、子ノードの評価値の中で 最も低い評価値 になります。例えば、上のノードの子ノードの評価値は -1 と 1 なので、その評価値は -1 になります。実際に上のノードで (0, 2) に着手を行うと × が勝利するので、(0, 2) が × にとって最善手であることは明らかです。

下図は新しく計算したノードの評価値を加えたものです。

上図で、全ての子ノードが求められているノードは、赤枠のノードだけです。赤枠のノードは 〇 の手番 のノードなので、3 つの子ノードの評価値の中で 最も高い評価値 である 0 になります。下図は新しく計算したノードの評価値を加えたものです。

これで全てのノードの評価値が計算できました。図から、赤枠のノードは、引き分けの局面であることがわかります。

アルゴリズムの証明

下記のアルゴリズムの手順 1 と 2 が間違っていないことは明らかですが、このアルゴリズムで 全てのノードの評価値を計算できるか どうかに疑問を持つ人がいるのではないかと思います。そこで、このアルゴリズムで全てのノードの評価値を 計算できることを証明 します。

1. ゲームの決着がついている リーフノードの評価値を全て計算 する
2. 全ての子ノードの評価値が求められている ノードの評価値を計算する
3. 手順 2 を、全ての子ノードの評価値が求められているノードが なくなるまで 繰り返す

最も深いノードの性質

ゲーム木の 最も深いノードの深さを d とすると、深さが d のノード は子ノードを持たないので 必ずリーフノードになります。従って、手順 1 で全てのリーフノードの評価値が計算されると、深さが d のノードは 全て評価値が計算される ことになります。

深さが d - 1 のノードの性質

次に、深さが d - 1 のノード の性質を、子ノードを持つ ノードと、子ノードを持たない リーフノードで分けて考えます。

深さ d - 1 のノードが 子ノードを持つ 場合は、その 子ノードの深さは d になります。上記で説明したように、深さ d のノードは 全て評価値が計算されている ので、それらを元に 評価値を計算することができます。

深さ d - 1 のノードが リーフノード の場合は、手順 1 で 評価値は計算済 です。

上記から、深さ d - 1 のノード は 全て評価値を計算できる ことがわかります。

任意の深さのノードの性質

上記では、d はゲーム木の最も深いノードの深さを表していましたが、上記で説明したのと同じ理由で、任意の深さ d¹ に対して下記の性質があることがわかります。

二人零和有限確定完全情報ゲームのゲーム木では、深さ d の全てのノードの評価値が計算されている場合は、深さ d - 1 の全てのノードの評価値を計算できる。

従って、先程の 手順 2 の計算を繰り返すたび に、深さが d - 1、d - 2、・・・、1、0 の順で 全ての深さ のノードの 評価値を計算 することができます。

ミニマックス法を行うプログラムの実装

二人零和有限確定完全情報ゲームは、2 人のプレイヤーが交互に着手を行うので、そのゲーム木は深さが 偶数のノード が 先手の手番 を、奇数のノード が 後手の手番 を表します。

また、評価値を計算するアルゴリズムでは、先手のノード では子ノードの評価値の 最大値（maximum）を、後手 のノードでは子ノードの評価値の 最小値（minimam）を計算するので、深さの浅い順に、最大値と最小値を交互に計算 することになります。そのため、

そのため、二人零和有限確定完全情報ゲームの 評価値を表すゲーム木 のことを ミニマックス木（Mini-Max tree）、評価値を計算するアルゴリズム を ミニマックス法 と呼びます。

ミニマックス法 は先程の証明で説明したように、最も深いノードから 順番に評価値を計算するので、ルートノードから始まる トップダウンな繰り返し処理 で実装できます。

ゲーム木の最も深いノードから順番に計算するトップダウンな繰り返し処理は、ゲーム木の部分木を描画した際の各ノードの高さを計算する Mbtree クラスの calc_node_height で実装済です。そのためミニマックス法は、calc_node_height と同様の方法 で実装することができるので、calc_node_height と比較しながら実装することにします。

幅優先アルゴリズムによる実装

ミニマックス法は 幅優先アルゴリズム と 深さ優先アルゴリズム の どちらでも実装 することができます。前回の記事で説明したように、木構造に対するトップダウンな繰り返し処理は、再帰呼び出しを使った深さ優先アルゴリズム で実装したほうが 簡単 です。

その理由は、幅優先アルゴリズム では 各ノードの深さの一覧を計算する必要がある 点ですが、Mbtree クラスではゲーム木の作成の際に、各ノードの深さの一覧を nodelist_by_depth 属性に代入済 なので、幅優先アルゴリズムでも 簡単に実装 することができます。そこで、ミニマックス法を、幅優先と深さ優先アルゴリズムの両方で実装することにします。

アルゴリズムの修正

トップダウンな幅優先アルゴリズム では、下記のミニマックス法のアルゴリズムの処理を そのまま行うことはできない ので 少しだけ修正 する必要があります。

1. ゲームの決着がついている リーフノードの評価値を全て計算 する
2. 全ての子ノードの評価値が求められている ノードの評価値を計算する
3. 手順 2 を、全ての子ノードの評価値が求められているノードが なくなるまで 繰り返す

具体的には、下記のように修正します。ただし、次に処理を行うゲーム木の深さを d と表記することにします。

1. 最も深いノードから、深さが 0 のノードの順に、下記の手順 2 の処理を行う
2. その深さの全てのノードに対して評価値を計算する

上記がミニマックス法と同じ処理を行うことは、先程の証明から明らかでしょう。

幅優先アルゴリズムでミニマックス法を実装する際に、for 文で実装する方法と、再帰呼び出しで実装する方法がありますが、for 文のほうが簡単なので、for 文で下記のようなメソッドを実装することにします。再帰呼び出しで実装したい人はチャレンジしてみて下さい。

なお、計算した 評価値をどこに記録するか を決める必要がありますが、本記事ではノードを表す Node クラスの score 属性 にその値を代入することにします。

名前：幅優先アルゴリズムで評価値（score）を計算するので、calc_score_by_bf とする
処理：全てのノードの評価値を計算し、ノードの score 属性に代入する
入力：なし
出力：なし

組み込み関数 reversed の説明

calc_score_by_bf では、nodelist_by_depth 属性に代入された各深さのノードの一覧のデータを、深さの深い順で取り出す 必要があります。そのためには、nodelist_by_depth の要素を、後ろから順番に取り出す という 繰り返し処理 が必要になります。

そのような処理は、list や dict などの、シーケンス型 の要素を 逆順に取り出す ことができる 反復可能オブジェクトを作成 する、組み込み関数 reversed を利用することができます。

下記のプログラムは、reversed の使用例です。実行結果のように、for 文に reversed(a) を記述することで、a の要素が後ろから順番に取り出されて表示されます。

a = [1, 2, 3]
for num in reversed(a):
    print(num)

実行結果

3
2
1

なお、reversed を実行しても、reversed の 実引数に記述した データの要素が逆順になるわけではありません。実際に、上記を実行後に下記のプログラムで a を表示すると、要素の順番が変化していない ことが確認できます。

print(a)

実行結果

[1, 2, 3]

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

list などの シーケンス型 のデータは、reverse メソッド を利用することで、下記のプログラムのように その list の要素を逆順に入れ替える ことができます。組み込み関数 reversed と似ていますが、意味が大きく異なる 点に注意して下さい。

a.reverse()
print(a)

実行結果

[3, 2, 1]

シーケンス型の reverse メソッドの詳細については、下記のリンク先を参照して下さい。

calc_score_by_bf の定義

下記は、calc_score_by_bf で実装するアルゴリズムの再掲です。

1. 最も深いノードから、深さが 0 のノードの順に、下記の手順 2 の処理を行う
2. その深さの全てのノードに対して評価値を計算する

下記は、calc_score_by_bf の定義です。5 行目の for 文が手順 1 を、6 ~ 19 行目の for 文が手順 2 の処理を行います。

• 5 行目：nodelist_by_depth 属性に代入されている各深さのノードの一覧のデータを reversed を使って深さの深い順に取り出して nodelist に代入する繰り返し処理を行う
• 6 行目：nodelist から順番にノードのデータを取り出して node に代入する繰り返し処理を行う
• 7 ~ 12 行目：node の局面が決着がついている場合は、決着の状態に応じた評価値を score 属性に代入する
• 14 行目：決着がついていない場合は、list 内包表記を使って、node の子ノードの評価値を要素として持つ list を作成し、score_list に代入する
• 15、16 行目：局面の手数を表す move_count 属性が偶数（2 で割った余りが 0 になる）の場合はの場合は 〇 の手番なので、score_list の最大値を計算する
• 17、18 行目：奇数の場合は × の手番なので、score_list の最小値を計算する
• 19 行目：計算した評価値を node の score 属性に代入する

 1  from tree import Mbtree
 2  from marubatsu import Marubatsu
 3
 4  def calc_score_by_bf(self):
 5      for nodelist in reversed(self.nodelist_by_depth):
 6          for node in nodelist:
 7              if node.mb.status == Marubatsu.CIRCLE:
 8                  node.score = 1
 9              elif node.mb.status == Marubatsu.DRAW:
10                  node.score = 0
11              elif node.mb.status == Marubatsu.CROSS:
12                  node.score = -1
13              else:
14                  score_list = [childnode.score for childnode in node.children]
15                  if node.mb.move_count % 2 == 0:
16                      score = max(score_list)
17                  else:
18                      score = min(score_list)
19                  node.score = score
20
21  Mbtree.calc_score_by_bf = calc_score_by_bf             

行番号のないプログラム

from tree import Mbtree
from marubatsu import Marubatsu

def calc_score_by_bf(self):
    for nodelist in reversed(self.nodelist_by_depth):
        for node in nodelist:
            if node.mb.status == Marubatsu.CIRCLE:
                node.score = 1
            elif node.mb.status == Marubatsu.DRAW:
                node.score = 0
            elif node.mb.status == Marubatsu.CROSS:
                node.score = -1
            else:
                score_list = [childnode.score for childnode in node.children]
                if node.mb.move_count % 2 == 0:
                    score = max(score_list)
                else:
                    score = min(score_list)
                node.score = score

Mbtree.calc_score_by_bf = calc_score_by_bf  

上記の修正後に、下記のプログラムを実行すると、実行結果のように、ルートノードの評価値として、引き分けの局面であることを表す 0 が表示されます。〇×ゲームは、ゲーム開始時の局面は引き分けの局面なのでこれは正しい値です。

• 1 行目：Mbtree クラスの loadメソッドを使って以前の記事で保存した、幅優先アルゴリズムで作成した Mbtree のインスタンスをファイルから読み込む
• 2 行目：calc_score_by_bf を実行して、ゲーム木の全てのノードの評価値を計算する
• 3 行目：ルートノードの評価値を表示する

mbtree_bf = Mbtree.load("bftree")
mbtree_bf.calc_score_by_bf()
print(mbtree_bf.root.score)

実行結果

0

上記では、幅優先アルゴリズムでゲーム木を作成したインスタンスのファイルを読み込みましたが、深さ優先アルゴリズムでゲーム木を作成 したインスタンスを読み込んでも、ゲーム木の構成は全く同じ なので同じ結果になります。

評価値の視覚化

上記でルートノードの評価値が正しく計算されたことが確認できましたが、このままでは他のノードの評価値がどのように計算されているかを確認するのが大変です。そこで、ゲーム木を GUI で視覚化 する Mbtree_GUI クラスを改良して、ゲーム盤の背景色に評価値を表す色を付けて表示 することで 評価値を視覚化 することにします。その際に、それぞれの評価値に対しては、決着が付いた際のゲーム盤と同じ色でゲーム盤を表示することにします。

draw_board メソッドの修正

ゲームの 決着がついた局面 のゲーム盤の背景色は、Marubatsu_GUI クラスの draw_board 内の下記のプログラムで描画していますが、ノードの評価値の情報 は、Marubatsu クラスには 記録されていない ので、このままでは draw_board で 決着がついていない局面 に対して、評価値に応じた 背景色を描画することはできません。

@staticmethod
def draw_board(ax, mb, show_result=False, emphasize=False, dx=0, dy=0, lw=2):
    # 結果によってゲーム盤の背景色を変更する
    if show_result:
        if mb.status == Marubatsu.PLAYING:
            bgcolor = "white"
        elif mb.status == Marubatsu.CIRCLE:
            bgcolor = "lightcyan"
        elif mb.status == Marubatsu.CROSS:
            bgcolor = "lavenderblush"
        else:
            bgcolor = "lightyellow"
        rect = patches.Rectangle(xy=(dx, dy), width=mb.BOARD_SIZE,
                                height=mb.BOARD_SIZE, fc=bgcolor)
        ax.add_patch(rect)
略

そこで、draw_board に 評価値を代入 する score という仮引数と追加 し、score の値に応じて背景色を変更する ように修正することにします。

ただし、互換性を考慮 して、score をデフォルト値を None としたデフォルト引数とし、score が None の場合 は、これまでと同じ方法でゲーム盤を表示 することにします。

行いたい処理は、ゲーム盤の背景色 を以下のようにする処理です。

• score が None でなければ、score の評価値に応じた色にする
• score が None の場合は、ゲームの状態に応じた色にする

そのため、プログラムでは、それぞれの色を描画する条件式を記述する必要があります。

評価値は、「〇 の勝利の局面」、「引き分けの局面」、「× の勝利の局面」の 3 種類しかないので、score が None でない場合 は、ゲーム盤の背景色がゲーム中であることを表す "white" になることは決してありません。

従って、ゲーム盤の背景色が "white" になる のは 「score が None」 なおかつ「ゲームの状態がゲーム中」 という条件が満たされた場合であることがわかります。

背景色が "lightcyan" になる条件は、「score が 1」または「ゲームの状態が 〇 の勝利の場合」 です。残りの 2 色に関しても同様 です。

従って、draw_board は下記のプログラムのように修正することができます。

• 5 行目：デフォルト値を None とする仮引数 score を追加する
• 8 行目：「score が None」なおかつ「ゲーム中状態がゲーム中」の場合に背景色を白色で描画するように修正する
• 10 行目：〇 の必勝の局面を表す score が 1 の場合を条件に加える
• 12 行目：× の必勝の局面を表す score が -1 の場合を条件に加える
• 14 行目：引き分けの局面を表す score が 0 の場合は、どの条件式も True にならないので、else のブロックが実行されるので、この部分は修正する必要はない

 1  from marubatsu import Marubatsu_GUI
 2  import matplotlib.patches as patches
 3
 4  @staticmethod
 5  def draw_board(ax, mb, show_result=False, score=None, emphasize=False, dx=0, dy=0, lw=2):
 6      # 結果によってゲーム盤の背景色を変更する
 7      if show_result:
 8          if score is None and mb.status == Marubatsu.PLAYING:
 9              bgcolor = "white"
10          elif score == 1 or mb.status == Marubatsu.CIRCLE:
11              bgcolor = "lightcyan"
12          elif score == -1 or mb.status == Marubatsu.CROSS:
13              bgcolor = "lavenderblush"
14          else:
15              bgcolor = "lightyellow"
16          rect = patches.Rectangle(xy=(dx, dy), width=mb.BOARD_SIZE,
17                                  height=mb.BOARD_SIZE, fc=bgcolor)
18          ax.add_patch(rect)
元と同じなので省略
19            
20  Marubatsu_GUI.draw_board = draw_board

行番号のないプログラム

from marubatsu import Marubatsu_GUI
import matplotlib.patches as patches

@staticmethod
def draw_board(ax, mb, show_result=False, score=None, emphasize=False, dx=0, dy=0, lw=2):
    # 結果によってゲーム盤の背景色を変更する
    if show_result:
        if score is None and mb.status == Marubatsu.PLAYING:
            bgcolor = "white"
        elif score == 1 or mb.status == Marubatsu.CIRCLE:
            bgcolor = "lightcyan"
        elif score == -1 or mb.status == Marubatsu.CROSS:
            bgcolor = "lavenderblush"
        else:
            bgcolor = "lightyellow"
        rect = patches.Rectangle(xy=(dx, dy), width=mb.BOARD_SIZE,
                                height=mb.BOARD_SIZE, fc=bgcolor)
        ax.add_patch(rect)

    # emphasize が True の場合は赤色の外枠を描画する
    if emphasize:
        frame = patches.Rectangle(xy=(dx, dy), width=mb.BOARD_SIZE,
                                height=mb.BOARD_SIZE, ec="red", fill=False, lw=lw)
        ax.add_patch(frame)
    
    # ゲーム盤の枠を描画する
    for i in range(1, mb.BOARD_SIZE):
        ax.plot([dx, dx + mb.BOARD_SIZE], [dy + i, dy + i], c="k", lw=lw) # 横方向の枠線
        ax.plot([dx + i, dx + i], [dy, dy + mb.BOARD_SIZE], c="k", lw=lw) # 縦方向の枠線

    # ゲーム盤のマークを描画する
    for y in range(mb.BOARD_SIZE):
        for x in range(mb.BOARD_SIZE):
            color = "red" if (x, y) == mb.last_move else "black"
            Marubatsu_GUI.draw_mark(ax, dx + x, dy + y, mb.board[x][y], color, lw=lw)
            
Marubatsu_GUI.draw_board = draw_board

修正箇所

from marubatsu import Marubatsu_GUI
import matplotlib.patches as patches

@staticmethod
-def draw_board(ax, mb, show_result=False, emphasize=False, dx=0, dy=0, lw=2):
+def draw_board(ax, mb, show_result=False, score=None, emphasize=False, dx=0, dy=0, lw=2):
    # 結果によってゲーム盤の背景色を変更する
    if show_result:
-       if mb.status == Marubatsu.PLAYING:
+       if score is None and mb.status == Marubatsu.PLAYING:
            bgcolor = "white"
-       elif mb.status == Marubatsu.CIRCLE:
+       elif score == 1 or mb.status == Marubatsu.CIRCLE:
            bgcolor = "lightcyan"
-       elif mb.status == Marubatsu.CROSS:
+       elif score == -1 or mb.status == Marubatsu.CROSS:
            bgcolor = "lavenderblush"
        else:
            bgcolor = "lightyellow"
        rect = patches.Rectangle(xy=(dx, dy), width=mb.BOARD_SIZE,
                                height=mb.BOARD_SIZE, fc=bgcolor)
        ax.add_patch(rect)
元と同じなので省略
            
Marubatsu_GUI.draw_board = draw_board

draw_node の修正

次に、draw_board を呼び出す、Node クラスの draw_node メソッドを以下のプログラムのように修正します。

• 6 行目：draw_board の実引数に score=self.score を追加する
• 11 行目：draw_board の実引数に score=childnode.score を追加する。この行では、子ノードを描画 しているので、childnode.score とする必要がある 点に注意する事

 1  from tree import Node, Rect
 2  import matplotlib.pyplot as plt
 3
def draw_node(self, ax=None, maxdepth=None, emphasize=False, size=0.25, lw=0.8, dx=0, dy=0):
元と同じなので省略
 4      # 自分自身のノードを真ん中の位置になるように (dx, dy) からずらして描画する
 5      y = dy + (self.height - 3) / 2
 6      Marubatsu_GUI.draw_board(ax, self.mb, show_result=True, score=self.score, emphasize=emphasize, lw=lw, dx=dx, dy=y)
 7      rect = Rect(dx, y, 3, 3)
 8      # 子ノードが存在する場合に、エッジの線と子ノードを描画する
 9      if len(self.children) > 0:
元と同じなので省略
10                  if maxdepth is None:
11                       Marubatsu_GUI.draw_board(ax, childnode.mb, show_result=True,
12                                                score=childnode.score, dx=dx+5, dy=childnodey, lw=lw)
元と同じなので省略
13
14  Node.draw_node = draw_node

行番号のないプログラム

from tree import Node, Rect
import matplotlib.pyplot as plt

def draw_node(self, ax=None, maxdepth=None, emphasize=False, size=0.25, lw=0.8, dx=0, dy=0):
    width = 8
    if ax is None:
        height = len(self.children) * 4
        fig, ax = plt.subplots(figsize=(width * size, height * size))
        ax.set_xlim(0, width)
        ax.set_ylim(0, height)   
        ax.invert_yaxis()
        ax.axis("off")
        for childnode in self.children:
            childnode.height = 4
        self.height = height         
        
    # 自分自身のノードを真ん中の位置になるように (dx, dy) からずらして描画する
    y = dy + (self.height - 3) / 2
    Marubatsu_GUI.draw_board(ax, self.mb, show_result=True, score=self.score, emphasize=emphasize, lw=lw, dx=dx, dy=y)
    rect = Rect(dx, y, 3, 3)
    # 子ノードが存在する場合に、エッジの線と子ノードを描画する
    if len(self.children) > 0:
        if maxdepth != self.depth:   
            plt.plot([dx + 3.5, dx + 4], [y + 1.5, y + 1.5], c="k", lw=lw)
            prevy = None
            for childnode in self.children:
                childnodey = dy + (childnode.height - 3) / 2
                if maxdepth is None:
                    Marubatsu_GUI.draw_board(ax, childnode.mb, show_result=True, score=childnode.score, dx=dx+5, dy=childnodey, lw=lw)
                edgey = childnodey + 1.5
                plt.plot([dx + 4 , dx + 4.5], [edgey, edgey], c="k", lw=lw)
                if prevy is not None:
                    plt.plot([dx + 4 , dx + 4], [prevy, edgey], c="k", lw=lw)
                prevy = edgey
                dy += childnode.height
        else:
            plt.plot([dx + 3.5, dx + 4.5], [y + 1.5, y + 1.5], c="k", lw=lw)
            
    return rect

Node.draw_node = draw_node

修正箇所

from tree import Node, Rect
import matplotlib.pyplot as plt

def draw_node(self, ax=None, maxdepth=None, emphasize=False, size=0.25, lw=0.8, dx=0, dy=0):
元と同じなので省略
    # 自分自身のノードを真ん中の位置になるように (dx, dy) からずらして描画する
    y = dy + (self.height - 3) / 2
-   Marubatsu_GUI.draw_board(ax, self.mb, show_result=True, emphasize=emphasize, lw=lw, dx=dx, dy=y)
+   Marubatsu_GUI.draw_board(ax, self.mb, show_result=True, score=self.score, emphasize=emphasize, lw=lw, dx=dx, dy=y)
    rect = Rect(dx, y, 3, 3)
    # 子ノードが存在する場合に、エッジの線と子ノードを描画する
    if len(self.children) > 0:
元と同じなので省略
                if maxdepth is None:
                    Marubatsu_GUI.draw_board(ax, childnode.mb, show_result=True,
-                                            dx=dx+5, dy=childnodey,     
+                                            score=childnode.score, dx=dx+5, dy=childnodey, lw=lw)
元と同じなので省略

Node.draw_node = draw_node

視覚化の確認

上記の修正後に、下記のプログラムで視覚化を行うと、実行結果のように各ノードのゲーム盤に評価値に応じた背景色の色がつくようになります。黄色は引き分けの局面を表しているので、1 手目を着手した後の局面は全て引き分けの局面であることがわかります。

from tree import Mbtree_GUI
mbtree_gui = Mbtree_GUI(mbtree_bf)

実行結果

下図は、1 手目で真ん中の (1, 1) に着手したノードを中心とした部分木の図です。図から、その局面が以下の性質を持つ事がわかります。

• × が四隅に着手を行うと引き分けの局面になる
• × が辺に着手を行うと 〇 の必勝の局面になる

実際に × が (1, 0) に着手した場合は、下図のように (0, 0)、(2, 2)、(0, 1) の順で着手することで、〇 がその次に (0, 2) と (2, 1) のどちらかに着手すれば勝利するので、× が辺に着手を行うと 〇 の必勝の局面になることが正しいことがわかります。

下図は、別の局面を中心とした部分木です。下図をじっくりと見て、赤枠で囲われたノードとそのノードから辿れる子ノードの評価値が全て正しく計算されていることを確認して下さい。また、下記以外の様々な部分木を表示して確認してみて下さい。

プログラムのバグとその検証

実は、上記の draw_node にはバグがあります。具体的には、下記のプログラムのように、新しくファイルから Mbtree クラスのインスタンスを 読み込んだデータを使って Mbtree_GUI で ゲーム木を表示 しようとすると実行結果のような エラーが発生 します。このエラーの原因について少し考えてみて下さい。

mbtree_bf2 = Mbtree.load("bftree")
mbtree_gui = Mbtree_GUI(mbtree_bf2)

実行結果

略
Cell In[7], line 19
     17 # 自分自身のノードを真ん中の位置になるように (dx, dy) からずらして描画する
     18 y = dy + (self.height - 3) / 2
---> 19 Marubatsu_GUI.draw_board(ax, self.mb, show_result=True, score=self.score, emphasize=emphasize, lw=lw, dx=dx, dy=y)
     20 rect = Rect(dx, y, 3, 3)
     21 # 子ノードが存在する場合に、エッジの線と子ノードを描画する

AttributeError: 'Node' object has no attribute 'score'

エラーメッセージから Node クラスのインスタンスに score 属性が存在しない ことが原因であることがわかります。Node クラスの score 属性 は、先程定義した calc_score_by_bf によって計算される ので、calc_score_by_bf を定義する前に作成 した Mbtree クラスのインスタンスを保存したファイルのデータの中の Node には score 属性は存在しません。

組み込み関数 getattr を利用した修正

過去に作成した Mbtree クラスのインスタンスを二度と使わないのであれば、このエラーは無視しても構わないでしょう。そうではなく、score 属性が存在しない Mbtree クラスのインスタンスに対しても Mbtree_GUI クラスで表示を行いたい 場合は、この エラーが発生しないよう にプログラムを修正する必要があります。

この問題は、以前の記事や、以前の記事で利用した、組み込み関数 getattr を利用することで解決することができます。

getattr は、1 つ目の実引数 に オブジェクト を、2 つ目の実引数 に 属性の名前 を記述することで、指定した属性の値 を 返り値として返す 処理を行いますが、。その際に、存在しない属性を記述すると下記のプログラムのようにエラーが発生します。

一方、getattr に 3 つ目の実引数を記述 することで、オブジェクトに 存在しない属性を指定した場合 に、3 つ目の実引数の値を返す 処理を行います。

例えば、上記の mbtree_bf2 の ルートノード には score 属性は存在しない ので、下記のプログラムを実行するとエラーが発生します。

print(getattr(mbtree_bf2.root, "score"))

実行結果

---------------------------------------------------------------------------
AttributeError                            Traceback (most recent call last)
Cell In[10], line 1
----> 1 print(getattr(mbtree_bf2.root, "score"))

AttributeError: 'Node' object has no attribute 'score'

一方、下記のプログラムのように、getattr の 3 つ目の実引数に None を記述すると、実行結果のように、score 属性が存在する mbtree_bf.root の場合は score 属性の値 が、score 属性が存在しない mbtree_bf2.root の場合は None が表示されます。

print(getattr(mbtree_bf.root, "score", None))
print(getattr(mbtree_bf2.root, "score", None))

実行結果

0
None

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

draw_node のバグの修正

先程 draw_node を score に None が代入された場合 は、以前と同じ処理を行う ように修正したので、下記のプログラムのように draw_node を修正することで、先程の問題を解決することができます。

• 5、11 行目：キーワード引数 score の値を、getattr を利用してノードに score 属性が存在しない場合は None が計算されるように修正する

 1  def draw_node(self, ax=None, maxdepth=None, emphasize=False, size=0.25, lw=0.8, dx=0, dy=0):
元と同じなので省略
 2      # 自分自身のノードを真ん中の位置になるように (dx, dy) からずらして描画する
 3      y = dy + (self.height - 3) / 2
 4      Marubatsu_GUI.draw_board(ax, self.mb, show_result=True, 
 5                               score=getattr(self, "score", None), emphasize=emphasize, lw=lw, dx=dx, dy=y)
 6      rect = Rect(dx, y, 3, 3)
 7      # 子ノードが存在する場合に、エッジの線と子ノードを描画する
 8      if len(self.children) > 0:
元と同じなので省略
 9                  if maxdepth is None:
10                      Marubatsu_GUI.draw_board(ax, childnode.mb, show_result=True,
11                                               score=getattr(childnode, "score", None), dx=dx+5, dy=childnodey, lw=lw)
元と同じなので省略
12
13  Node.draw_node = draw_node

行番号のないプログラム

def draw_node(self, ax=None, maxdepth=None, emphasize=False, size=0.25, lw=0.8, dx=0, dy=0):
    width = 8
    if ax is None:
        height = len(self.children) * 4
        fig, ax = plt.subplots(figsize=(width * size, height * size))
        ax.set_xlim(0, width)
        ax.set_ylim(0, height)   
        ax.invert_yaxis()
        ax.axis("off")
        for childnode in self.children:
            childnode.height = 4
        self.height = height         
        
    # 自分自身のノードを真ん中の位置になるように (dx, dy) からずらして描画する
    y = dy + (self.height - 3) / 2
    Marubatsu_GUI.draw_board(ax, self.mb, show_result=True, 
                             score=getattr(self, "score", None), emphasize=emphasize, lw=lw, dx=dx, dy=y)
    rect = Rect(dx, y, 3, 3)
    # 子ノードが存在する場合に、エッジの線と子ノードを描画する
    if len(self.children) > 0:
        if maxdepth != self.depth:   
            plt.plot([dx + 3.5, dx + 4], [y + 1.5, y + 1.5], c="k", lw=lw)
            prevy = None
            for childnode in self.children:
                childnodey = dy + (childnode.height - 3) / 2
                if maxdepth is None:
                    Marubatsu_GUI.draw_board(ax, childnode.mb, show_result=True,
                                             score=getattr(childnode, "score", None), dx=dx+5, dy=childnodey, lw=lw)
                edgey = childnodey + 1.5
                plt.plot([dx + 4 , dx + 4.5], [edgey, edgey], c="k", lw=lw)
                if prevy is not None:
                    plt.plot([dx + 4 , dx + 4], [prevy, edgey], c="k", lw=lw)
                prevy = edgey
                dy += childnode.height
        else:
            plt.plot([dx + 3.5, dx + 4.5], [y + 1.5, y + 1.5], c="k", lw=lw)
            
    return rect

Node.draw_node = draw_node

修正箇所

def draw_node(self, ax=None, maxdepth=None, emphasize=False, size=0.25, lw=0.8, dx=0, dy=0):
元と同じなので省略
    # 自分自身のノードを真ん中の位置になるように (dx, dy) からずらして描画する
    y = dy + (self.height - 3) / 2
    Marubatsu_GUI.draw_board(ax, self.mb, show_result=True, 
-                            score=self.score, emphasize=emphasize, lw=lw, dx=dx, dy=y)
+                            score=getattr(self, "score", None), emphasize=emphasize, lw=lw, dx=dx, dy=y)
    rect = Rect(dx, y, 3, 3)
    # 子ノードが存在する場合に、エッジの線と子ノードを描画する
    if len(self.children) > 0:
元と同じなので省略
                if maxdepth is None:
                    Marubatsu_GUI.draw_board(ax, childnode.mb, show_result=True,
-                                            score=childnode.score, dx=dx+5, dy=childnodey, lw=lw)
+                                            score=getattr(childnode, "score", None), dx=dx+5, dy=childnodey, lw=lw)
元と同じなので省略

Node.draw_node = draw_node

上記の修正後に、下記のプログラムを実行することで、mbtree_bf2 でもエラーが発生しないようになることが確認できます。また、mbtree_bf2 では Node に score 属性が存在しないので、実行結果のように決着がついていないゲーム盤の背景に色が表示されません。

mbtree_gui = Mbtree_GUI(mbtree_bf2)

実行結果

深さ優先アルゴリズムによる実装

Mbtree クラスでは、ゲーム木を作成する際に各深さのノードの一覧を nodelist_by_depth 属性に記録していたので、幅優先アルゴリズムで各ノードの評価値を簡単に記述できましたが、一般的 には 木構造のデータ に対して トップダウンな繰り返し処理 を行う場合は、深さ優先アルゴリズムを再帰呼び出し で記述するのが 簡単 です。

そこで、ゲーム木の全てのノードの評価値をミニマックス法で、深さ優先アルゴリズムと再帰呼び出しを使って計算する下記のようなメソッドを定義する事にします。

名前：深さ優先アルゴリズムで評価値を計算するので、calc_score_by_df とする
処理：仮引数に代入されたノードの評価値を計算する
入力：仮引数 node に評価値を計算するノードを代入する
出力：計算したノード node の評価値

なお、前回の記事ではトップダウンな再帰呼び出しでノードを代入する仮引数の名前を N としましたが、後で calc_score_by_bf と比較するために node という名前にしました。

calc_score_by_df は下記のプログラムで実装することができます。

• 2 ~ 7 行目：node の局面が決着がついている場合は、決着の状態に応じた評価値を node の score 属性に代入する
• 9 行目：決着がついていない場合は、list 内包表記を使って 子ノードの評価値 を要素として持つ list を作成 し、score_list に代入する。その際に、子ノードの評価値は 再帰呼び出しによって計算を行い、その 返り値を要素の値とする
• 10、11 行目：局面の手数を表す move_count 属性の値が偶数の場合は 〇 の手番なので、score_list の最大値を計算する
• 12、13 行目：奇数の場合は × の手番なので、score_list の最小値を計算する
• 14 行目：計算した評価値を node の score 属性に代入する
• 16 行目：node の評価値を返り値として返す。なお、この処理は、決着がついている場合と、ついていない場合に 共通する処理 なので、最後の行でまとめて行うことができる

 1  def calc_score_by_df(self, node):
 2      if node.mb.status == Marubatsu.CIRCLE:
 3          node.score = 1
 4      elif node.mb.status == Marubatsu.DRAW:
 5          node.score = 0
 6      elif node.mb.status == Marubatsu.CROSS:
 7          node.score = -1
 8      else:
 9          score_list = [self.calc_score_by_df(childnode) for childnode in node.children]
10          if node.mb.move_count % 2 == 0:
11              score = max(score_list)
12          else:
13              score = min(score_list)
14          node.score = score
15
16      return node.score
17
18  Mbtree.calc_score_by_df = calc_score_by_df  

行番号のないプログラム

def calc_score_by_df(self, node):
    if node.mb.status == Marubatsu.CIRCLE:
        node.score = 1
    elif node.mb.status == Marubatsu.DRAW:
        node.score = 0
    elif node.mb.status == Marubatsu.CROSS:
        node.score = -1
    else:
        score_list = [self.calc_score_by_df(childnode) for childnode in node.children]
        if node.mb.move_count % 2 == 0:
            score = max(score_list)
        else:
            score = min(score_list)
        node.score = score

    return node.score

Mbtree.calc_score_by_df = calc_score_by_df 

上記のプログラムを、先程定義した下記の calc_score_by_bf と比較してみて下さい。nodelist_by_depth が計算済であれば、プログラムの見た目にそれほど大きな違いはないことがわかると思います。ただし、プログラムは似ていても、処理の流れは全く異なります。

def calc_score_by_bf(self):
    for nodelist in reversed(self.nodelist_by_depth):
        for node in nodelist:
            if node.mb.status == Marubatsu.CIRCLE:
                node.score = 1
            elif node.mb.status == Marubatsu.DRAW:
                node.score = 0
            elif node.mb.status == Marubatsu.CROSS:
                node.score = -1
            else:
                score_list = [childnode.score for childnode in node.children]
                if node.mb.move_count % 2 == 0:
                    score = max(score_list)
                else:
                    score = min(score_list)
                node.score = score

calc_score_by_df との違い（ただし、インデントの違いは無視しました）

-def calc_score_by_df(self, node):
+def calc_score_by_bf(self):
+   for nodelist in reversed(self.nodelist_by_depth):
        for node in nodelist:
            if node.mb.status == Marubatsu.CIRCLE:
                node.score = 1
            elif node.mb.status == Marubatsu.DRAW:
                node.score = 0
            elif node.mb.status == Marubatsu.CROSS:
                node.score = -1
            else:
-               score_list = [self.calc_score_by_df(childnode) for childnode in node.children]
+               score_list = [childnode.score for childnode in node.children]
                if node.mb.move_count % 2 == 0:
                    score = max(score_list)
                else:
                    score = min(score_list)
                node.score = score

-    return node.score                

実行結果は同じなので省略しますが、上記の修正後に、下記のプログラムを実行すると、calc_score_by_df で評価値を計算した mbtree_by_df を Mbtree_GUI で正しく表示できることが確認できます。実際に様々な操作を行って、正しく表示できることを確認して下さい。

mbtree_by_df = Mbtree.load("dftree")
mbtree_by_df.calc_score_by_df(mbtree_by_df.root)
mbtree_gui = Mbtree_GUI(mbtree_by_df)

上記の 1 行目では、calc_score_by_df のアルゴリズムに合わせて、深さ優先アルゴリズムで作成したデータをファイルから読み込んでいますが、幅優先アルゴリズムで作成したデータを読み込んでも結果は変わりません。

Mbtree クラスの __init__ メソッドの修正

評価値を計算できるようになったので、下記のプログラムのように Mbtree クラスの __init__ 属性を修正して、Mbtree クラスのインスタンスを作成した際に、評価値も計算するようにします。その際に、せっかくなので、ゲーム木の作成と同じアルゴリズムで評価値を計算することにしましたが、どちらのアルゴリズムで評価値を計算してもかまいません。

• 7、14 行目：ゲーム木の作成後に評価値を計算する関数を呼び出す

 1  def __init__(self, algo:str="bf"):   
 2      self.algo = algo
 3      Node.count = 0
 4      self.root = Node(Marubatsu())
 5      if self.algo == "bf":  
 6          self.create_tree_by_bf()
 7          self.calc_score_by_bf()
 8      else:
 9          self.nodelist = [self.root]
10          self.nodelist_by_depth = [[] for _ in range(10)]
11          self.nodelist_by_depth[0].append(self.root)
12          self.nodenum = 0
13          self.create_tree_by_df(self.root)
14          self.calc_score_by_df(self.root)
15        
16  Mbtree.__init__ = __init__

行番号のないプログラム

def __init__(self, algo:str="bf"):   
    self.algo = algo
    Node.count = 0
    self.root = Node(Marubatsu())
    if self.algo == "bf":  
        self.create_tree_by_bf()
        self.calc_score_by_bf()
    else:
        self.nodelist = [self.root]
        self.nodelist_by_depth = [[] for _ in range(10)]
        self.nodelist_by_depth[0].append(self.root)
        self.nodenum = 0
        self.create_tree_by_df(self.root)
        self.calc_score_by_df(self.root)
        
Mbtree.__init__ = __init__

修正箇所

def __init__(self, algo:str="bf"):   
    self.algo = algo
    Node.count = 0
    self.root = Node(Marubatsu())
    if self.algo == "bf":  
        self.create_tree_by_bf()
+       self.calc_score_by_bf()
    else:
        self.nodelist = [self.root]
        self.nodelist_by_depth = [[] for _ in range(10)]
        self.nodelist_by_depth[0].append(self.root)
        self.nodenum = 0
        self.create_tree_by_df(self.root)
+       self.calc_score_by_df(self.root)
        
Mbtree.__init__ = __init__

実行結果は同じなので省略しますが、上記の修正後に下記のプログラムを実行することで、修正したプログラムが正しく動作することが確認できます。

mbtree_by_bf3 = Mbtree()
mbtree_gui = Mbtree_GUI(mbtree_by_bf3)
mbtree_by_df2 = Mbtree(algo="df")
mbtree_gui = Mbtree_GUI(mbtree_by_df2)

データの保存

評価値入りのゲーム木を作成したので、下記のプログラムでファイルに保存します。その際に、ファイル名を "bfscore" と "dfscore" としました。

mbtree_by_bf3.save("bfscore")
mbtree_by_df2.save("dfscore")

実行結果

save completed.
save completed.

今回の記事のまとめ

今回の記事では、ゲーム木の評価値を計算する方法として、ミニマックス法を紹介し、ミニマックス法でゲーム木の評価値を計算するメソッドを、幅優先アルゴリズムと深さ優先アルゴリズムの両方で実装しました。次回の記事では、評価値を計算したゲーム木を使って、最強の AI を作成する方法を紹介する予定です。

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

今回の記事で作成した mbtree_bf と mbtree_df の中身は、以前にファイルに保存したデータと全く同じなので、改めてファイルに保存することはしません。

リンク	説明
marubatsu.ipynb	本記事で入力して実行した JupyterLab のファイル
marubatsu_new.py	今回の記事で更新した marubatsu.py
tree_new.py	今回の記事で更新した tree.py
bfscore.mbtree	幅優先探索アルゴリズムで作成した、評価値を含むゲーム木の保存ファイル
dfscore.mbtree	深さ優先探索アルゴリズムで作成した、評価値を含むゲーム木の保存ファイル

次回の記事

1. ただし、深さ 0 のルートノードは親ノードを持たないので、d は 0 を除きます ↩