目次と前回の記事

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

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

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

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

引き分けの局面での最善手の優劣

以前の記事で、必勝の局面の最善手 に対して「なるべく早く勝利できる着手に高い評価値を計算する」という方法で 優劣をつける という方法を紹介し、その評価値で着手を選択する ai_gtsv を作成しました。

必勝の局面の最善手に対して優劣をつけても、相手が最善手のみを選択する 最強の AI の場合は勝敗結果は変わりません が、無駄に試合を長引かせることが無くなるので、人間にとってはより好ましい AI を作成することができます。

同様に、引き分けの局面の最善手 に対しても 何らかの基準で優劣をつける ことができます。どのような基準で優劣をつけることができるかを少し考えてみて下さい。

引き分けの局面での最善手の優劣の具体例

左下図の局面は引き分けの局面で、右下図はこの局面のゲーム木の部分木です。この部分木が示すように、合法手である (2, 0)、(0, 2)、(2, 2) の いずれのマスに着手を行っても 相手が最善手を着手すれば 引き分けになる ので、3 つの合法手のすべてが最善手 です。

ただし、部分木からわかるように、(2, 0) または (0, 2) に着手した場合は、相手が最善手を着手しなかった場合に 勝利することができます。一方 (2, 2) に着手した場合は、相手がどこに着手を行っても 必ず引き分けになります。

従って、相手が最善手を着手しない可能性がある場合 は、勝利する可能性がある (2, 0) と (0, 2) のほうが、(2, 2) よりも 優れた着手である と考えることができます。そこで、引き分けの局面の最善手 に対して、相手が最善手を着手しない場合に 勝利できる可能性があるか どうかによって 優劣をつける ことにします。

評価値の計算方法

評価値を利用して着手を選択する AI が行う ミニマックス法 では、〇の手番 では着手した局面の 評価値が最も高い合法手が最善手 となります。そのため、〇を着手した後の × の手番での引き分けの局面の評価値 を下記の式のように設定することで、〇の手番の引き分けの局面で 〇が勝利する可能性がある局面になる合法手が最善手となる¹ようになります。

〇が勝利できる可能性がある場合の評価値 > そうでない場合の評価値

ミニマックス法では 〇の手番の局面の最善手 を計算する際に、〇が着手を行った後の × の手番 の局面の評価値を利用する点に注意して下さい。

× の手番 では着手した局面の評価値が 最も低い 合法手が最善手となるので、× の手番の引き分けの局面で × が勝利する可能性がある局面になる合法手を最善手とする ようにするためには、〇の手番での引き分けの局面の評価値を下記の式のように設定する必要があります。

× が勝利できる可能性がある場合の評価値 < そうでない場合の評価値

下記は、引き分けの局面 に対して そのような評価値を設定する一例 です。上記の条件を満たしていれば、どのような評価値を設定してもかまいませんが、本記事ではこれまで 〇の必勝の局面の評価値を 1 以上、× の必勝の局面の評価値を -1 以下 として計算してきたので、それらの計算の処理を 変更しなくて済む ように、引き分けの局面の評価値 を その間の範囲で設定 することにしました。

× の手番の局面の場合
- 相手の着手によって 〇が勝利する可能性がある 場合は 0.5
- そうでない場合は 0
〇の手番の局面の場合
- 相手の着手によって × が勝利する可能性がある 場合は -0.5
- そうでない場合は 0

このような評価値を計算する方法について少し考えてみて下さい。

× の手番の局面での評価値の計算方法

まず、× の手番の局面での評価値の計算方法 を考えることにします。

引き分けの局面であるか どうかの判定は、これまでに計算した 評価値が 0 であるか どうかで行うことができるので、必要な情報 は 〇が勝利する可能性があるか どうかです。

〇が勝利する可能性がある ということは、その局面で〇が勝利しているか、子孫ノードに〇が勝利する局面が存在する ということを意味します。そのことは、以下のようなアルゴリズムで計算できます。

〇が勝利する可能性があるか どうかを表す 評価値を計算 する。その評価値を 〇の勝利の評価値 と呼ぶことにする
リーフノード の 〇の勝利の評価値 を、最初にミニマックス法で評価値の計算を行う際に設定した以下の表のように計算する

局面の状況	〇の勝利の評価値
〇の勝利	1
引き分け	0
× の勝利	-1

リーフノード以外のノードでは、子ノードの〇の勝利の評価値 の中の 最大値 を、自身の〇の勝利の評価値として計算 する
上記の計算によって、自身のノードまたは 子孫ノードに〇が勝利する局面 が 存在する場合 は〇の勝利の評価値の値が 1、そうでない場合 は 0 以下 になる

なるべく早く勝利する場合の評価値の計算への対応

なるべく早く勝利 する ai_gtsv の評価値は、リーフノードの評価値を以前の記事で説明したように、下記の表で計算されます。ただし、引き分けの場合の評価値は 0 と計算します。

局面の深さ	5	6	7	8	9	評価値の計算式
〇が勝利した場合の評価値	3		2		1	（11 - 局面の深さ）÷ 2
× が勝利した場合の評価値		-2		-1		（局面の深さ - 10）÷ 2

先程の表の評価値と、上記の表の どちらの評価値 に対しても 対応できるようにする ために、先程のアルゴリズムを下記のように修正することにします。

〇が勝利する可能性があるかどうかを表す評価値を計算する。その評価値を〇の勝利の評価値と呼ぶことにする
リーフノードの〇の勝利の評価値を以下の表のように計算する

	〇の勝利の評価値
〇の勝利	正の値
引き分け	0
× の勝利	負の値

リーフノード以外のノードでは、子ノードの〇の勝利の評価値の中の最大値を、自身の〇の勝利の評価値として計算する
上記の計算によって、自身のノードまたは子孫ノードに〇が勝利する局面が存在する場合は〇の勝利の評価値の値が 正の値、そうでない場合は 0 以下の値になる

修正前との違いは上記の（表の見出し以外の）太字になっている部分だけです。

〇の勝利の評価値の意味と名前の変更

〇の勝利の評価値 は、子ノードに〇が勝利する局面が存在するかどうかを判定するだけでなく、下記についての判定を行うこともできる ので、〇の勝利の評価値とは 別の名前にしたほうが良い でしょう。

〇の勝利の評価値	意味
正の値	自身または子孫ノードに〇の勝利の局面が存在する
0	自身または子孫ノードに〇の勝利の局面は存在しないが、引き分けの局面は存在する
負の値	自身または子孫ノードには × の勝利の局面しか存在しない

〇の勝利の評価値は、子孫ノードの〇の勝利の評価値の 最大値を計算 するので、以後は「最大の評価値」と表記することにします²。

上記の表を別の言葉で表現すると下記の表のように、最大の評価値 は 〇にとって最高でどのような結果になるか を表します。

最大の評価値	意味
正の値	最高で〇が勝利する場合がある
0	最高で引き分けになる場合がある
負の値	〇が勝利する可能性はない

〇の手番の局面での評価値の計算方法

〇の手番の局面での評価値の計算 に必要な、× が勝利するかどうかの判定 は、上記の計算方法と同じ考え方で、下記のアルゴリズムで行うことができます。上記と異なる（表の見出し以外の）部分を太字で表記します。

× が勝利する可能性があるかどうかを表す評価値を計算する。その評価値を 最小の評価値 と呼ぶことにする
リーフノードの 最小の評価値 を 先程と同じ 以下の表のように計算する

	最小の評価値
〇の勝利	正の値
引き分け	0
× の勝利	負の値

リーフノード以外のノードでは、子ノードの 最小の評価値 の 最小値 を、自身の 最小の評価値 として計算する
上記の計算によって、自身のノードまたは子孫ノードに × が勝利する局面が存在する場合は、最小の評価値 が 負の値 、そうでない場合は 0 以上の値になる

上記のアルゴリズムと、先程説明した最大の評価値を計算するアルゴリズムの 大きな違い は子ノードの最小の評価値の 最小値 を計算する点と、子ノードの最小の評価値が 負の場合 に × が勝利する局面が存在する点です。従って、最大の評価値と同様に、最小の評価値 から下記の表の内容を判定することができます。

最小の評価値	意味
負の値	自身または子孫ノードに × の勝利の局面が存在する
0	自身または子孫ノードに × の勝利の局面は存在しないが、引き分けの局面は存在する
正の値	自身または子孫ノードには〇の勝利の局面しか存在しない

最大の評価値と最小の評価値の計算

最大の評価値 と 最小の評価値 は、以前の記事で説明した ミニマックス法 を計算する方法と 同様のアルゴリズム で計算できます。

ミニマックス法では各ノードの評価値を計算する方法が、手番によって 子ノードの評価値の 最大値を計算するか、最小値を計算するか が 変わります が、最大の評価値 では常に子ノードの最大の評価値の 最大値を計算する 点が異なります。最小の評価値でも同様です。

まず、最大の評価値と最小の評価値を記録する 属性の名前を決める 必要があるので、それぞれ max_score と min_score とすることにします。

Mbtree クラスの `calc_score_of_node` メソッドの修正

リーフノード では、最大の評価値と最小の評価値の 計算方法 は、通常の評価値の計算方法と同じ なので、リーフノードの評価値を計算 する Mbtree クラスの calc_score_of_node メソッドを下記のプログラムのように修正します。

11、12 行目：max_score と min_score 属性に、4 ~ 9 行目で計算したリーフノードの評価値を代入する

 1  from marubatsu import Marubatsu
 2  from tree import Mbtree
 3
 4  def calc_score_of_node(self, node):
 5      if node.mb.status == Marubatsu.CIRCLE:
 6          node.score = (11 - node.depth) / 2 if self.shortest_victory else 1
 7      elif node.mb.status == Marubatsu.DRAW:
 8          node.score = 0
 9      elif node.mb.status == Marubatsu.CROSS:
10          node.score = (node.depth - 10) / 2 if self.shortest_victory else -1
11      node.max_score = node.score
12      node.min_score = node.score
13    
14  Mbtree.calc_score_of_node = calc_score_of_node

行番号のないプログラム

from marubatsu import Marubatsu
from tree import Mbtree

def calc_score_of_node(self, node):
    if node.mb.status == Marubatsu.CIRCLE:
        node.score = (11 - node.depth) / 2 if self.shortest_victory else 1
    elif node.mb.status == Marubatsu.DRAW:
        node.score = 0
    elif node.mb.status == Marubatsu.CROSS:
        node.score = (node.depth - 10) / 2 if self.shortest_victory else -1
    node.max_score = node.score
    node.min_score = node.score
    
Mbtree.calc_score_of_node = calc_score_of_node

修正箇所

from marubatsu import Marubatsu
from tree import Mbtree

def calc_score_of_node(self, node):
    if node.mb.status == Marubatsu.CIRCLE:
        node.score = (11 - node.depth) / 2 if self.shortest_victory else 1
    elif node.mb.status == Marubatsu.DRAW:
        node.score = 0
    elif node.mb.status == Marubatsu.CROSS:
        node.score = (node.depth - 10) / 2 if self.shortest_victory else -1
+   node.max_score = node.score
+   node.min_score = node.score
    
Mbtree.calc_score_of_node = calc_score_of_node

Mbtree クラスの `calc_score_by_bf` メソッドの修正

Mbtree クラスでは、評価値の計算を幅優先アルゴリズムと深さ優先アルゴリズムの両方で行うことができるようにしているので、その両方のメソッドを修正することにします。

まず、幅優先アルゴリズム で評価値の計算を行う calc_score_by_bf （定義後の修正版のリンクはこちら）メソッドを下記のプログラムのように修正します。

8 行目：子ノードの max_score 属性を集めた list を作成し、組み込み関数 max を利用することで、その最大値を計算して max_score 属性に代入する
9 行目：8 行目と同様の方法で、子ノードの min_score 属性の最小値を計算して min_score 属性に代入する

 1  def calc_score_by_bf(self):
元と同じなので省略
 2                  score_list = [childnode.score for childnode in node.children]
 3                  if node.mb.move_count % 2 == 0:
 4                      score = max(score_list)
 5                  else:
 6                      score = min(score_list)
 7                  node.score = score
 8                  node.max_score = max([childnode.max_score for childnode in node.children])
 9                  node.min_score = min([childnode.min_score for childnode in node.children])
元と同じなので省略
10
11  Mbtree.calc_score_by_bf = calc_score_by_bf

行番号のないプログラム

def calc_score_by_bf(self):
    self.nodelist_by_score = self.nodelist[:]
    for nodelist in reversed(self.nodelist_by_depth):
        for node in nodelist:
            if node.mb.status != Marubatsu.PLAYING:
                self.calc_score_of_node(node)
            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
                node.max_score = max([childnode.max_score for childnode in node.children])
                node.min_score = min([childnode.min_score for childnode in node.children])
            self.nodelist_by_score.append(node)
            node.score_index = len(self.nodelist_by_score) - 1 

Mbtree.calc_score_by_bf = calc_score_by_bf

修正箇所

def calc_score_by_bf(self):
元と同じなので省略
                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
+               node.max_score = max([childnode.max_score for childnode in node.children])
+               node.min_score = min([childnode.min_score for childnode in node.children])
元と同じなので省略

Mbtree.calc_score_by_bf = calc_score_by_bf

github 上の mbtree.py に記述している calc_score_by_bf メソッドの docstring のコメントに「深さ優先探索」という間違った記述がされていることに気が付きましたので、今回の記事から「幅優先探索」に修正します。なお、過去の記事にさかのぼって docstring を修正するのは大変な点と、プログラムのバグではないので過去の記事にさかのぼっての修正は行わないことにします。

上記の修正後に、下記のプログラムを実行して 幅優先アルゴリズム でゲーム木の評価値を計算することで、ルートノード に max_score と min_score 属性が 計算されている ことが確認できます。

mbtree = Mbtree(shortest_victory=True)
print("max_score", mbtree.root.max_score)
print("min_score", mbtree.root.min_score)

実行結果

     9 depth 1 node created
    72 depth 2 node created
   504 depth 3 node created
  3024 depth 4 node created
 15120 depth 5 node created
 54720 depth 6 node created
148176 depth 7 node created
200448 depth 8 node created
127872 depth 9 node created
     0 depth 10 node created
total node num = 549946
max_score 3.0
min_score -2.0

Mbtree クラスの `calc_score_by_df` メソッドの修正

次に、深さ優先アルゴリズム で評価値の計算を行う calc_score_by_df （修正版のリンクはこちら）メソッドを下記のプログラムのように修正します。

20 行目：関数の返り値に、max_score 属性と min_score 属性の値を返すようにする
3、4 行目：子ノードの最大の評価値と最小の評価値の一覧を記録する max_score_list と min_score_list を空の list で初期化する
6 ~ 9 行目：再帰呼び出しの返り値を score、max_score、min_score に代入し、それぞれを score_list、max_score_list、min_score_list の要素に追加する
16、17 行目：max_score_list の要素の最大値を計算して max_score 属性に代入する。min_score 属性に関しても同様の処理を行う

 1  def calc_score_by_df(self, node):          
元と同じなので省略
 2          score_list = []
 3          max_score_list = []
 4          min_score_list = []
 5          for childnode in node.children:
 6              score, max_score, min_score = self.calc_score_by_df(childnode)
 7              score_list.append(score)
 8              max_score_list.append(max_score)
 9              min_score_list.append(min_score)
10              self.nodelist_by_score.append(node)
11          if node.mb.move_count % 2 == 0:
12              score = max(score_list)
13          else:
14              score = min(score_list)
15          node.score = score
16          node.max_score = max(max_score_list)
17          node.min_score = min(min_score_list)
元と同じなので省略
18      return node.score, node.max_score, node.min_score 
19
20  Mbtree.calc_score_by_df = calc_score_by_df

行番号のないプログラム

def calc_score_by_df(self, node):          
    self.nodelist_by_score.append(node)
    if node.mb.status != Marubatsu.PLAYING:
        self.calc_score_of_node(node)
    else:
        score_list = []
        max_score_list = []
        min_score_list = []
        for childnode in node.children:
            score, max_score, min_score = self.calc_score_by_df(childnode)
            score_list.append(score)
            max_score_list.append(max_score)
            min_score_list.append(min_score)
            self.nodelist_by_score.append(node)
        if node.mb.move_count % 2 == 0:
            score = max(score_list)
        else:
            score = min(score_list)
        node.score = score
        node.max_score = max(max_score_list)
        node.min_score = min(min_score_list)
        
    self.nodelist_by_score.append(node)
    node.score_index = len(self.nodelist_by_score) - 1        
    return node.score, node.max_score, node.min_score 

Mbtree.calc_score_by_df = calc_score_by_df

修正箇所

def calc_score_by_df(self, node):          
元と同じなので省略
        score_list = []
+       max_score_list = []
+       min_score_list = []
        for childnode in node.children:
-           score_list.append(self.calc_score_by_df(childnode))
+           score, max_score, min_score = self.calc_score_by_df(childnode)
+           score_list.append(score)
+           max_score_list.append(max_score)
+           min_score_list.append(min_score)
            self.nodelist_by_score.append(node)
        if node.mb.move_count % 2 == 0:
            score = max(score_list)
        else:
            score = min(score_list)
        node.score = score
+       node.max_score = max(max_score_list)
+       node.min_score = min(min_score_list)
元と同じなので省略
-   return node.score 
+   return node.score, node.max_score, node.min_score 

Mbtree.calc_score_by_df = calc_score_by_df

上記の修正後に、下記のプログラムを実行して 深さ優先アルゴリズム でゲーム木の評価値を計算することで、実行結果のようにルートノードに max_score と min_score 属性が計算されていることが確認できます。

mbtree = Mbtree(algo="df", shortest_victory=True)
print("max_score", mbtree.root.max_score)
print("min_score", mbtree.root.min_score)

実行結果

max_score 3.0
min_score -2.0

引き分けの局面での最善手の優劣を考慮した評価値の計算

次に、今回の記事の最初で説明した下記の 引き分けの局面での最善手の優劣を考慮した評価値の計算の実装 を行います。どのように実装すればよいかについて少し考えてみて下さい。

× の手番の局面の場合
- 相手の着手によって 〇が勝利する可能性がある 場合は 0.5
- そうでない場合は 0
〇の手番の局面の場合
- 相手の着手によって × が勝利する可能性がある 場合は -0.5
- そうでない場合は 0

Mbtree クラスの `calc_score_by_bf` の中で実装する方法

簡単に思いつく方法として、評価値を計算する calc_score_by_bf や calc_score_by_df の中 で 上記の処理を行う という方法があるでしょう。その方法でも実装することは可能ですが、いくつかの工夫を行わないとうまく実装できない という問題があります。ただし、思いつきやすい方法なので、実際に実装してどのような工夫が必要になるかを説明し、その後で別の方法で実装する方法を紹介することにします。

calc_score_by_bf の場合は、下記のプログラムのように実装します。

5 ~ 11 行目：引き分けの局面の場合の処理を記述する
6 ~ 8 行目：× の手番で max_score の値が正の場合は、子ノードに〇が勝利する局面が存在するので、評価値を 0.5 に修正する
9 ~ 11 行目：〇の手番で min_score の値が負の場合は、子ノードに × が勝利する局面が存在するので、評価値を -0.5 に修正する

 1  def calc_score_by_bf(self):
元と同じなので省略
 2                  node.score = score
 3                  node.max_score = max([childnode.max_score for childnode in node.children])
 4                  node.min_score = min([childnode.min_score for childnode in node.children])
 5             if node.score == 0:
 6                  if node.mb.move_count % 2 == 1:
 7                      if node.max_score > 0:
 8                          node.score = 0.5
 9                  else:
10                      if node.min_score < 0:
11                          node.score = -0.5
元と同じなので省略
12
13  Mbtree.calc_score_by_bf = calc_score_by_bf

行番号のないプログラム

def calc_score_by_bf(self):
    self.nodelist_by_score = self.nodelist[:]
    for nodelist in reversed(self.nodelist_by_depth):
        for node in nodelist:
            if node.mb.status != Marubatsu.PLAYING:
                self.calc_score_of_node(node)
            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
                node.max_score = max([childnode.max_score for childnode in node.children])
                node.min_score = min([childnode.min_score for childnode in node.children])
            if node.score == 0:
                if node.mb.move_count % 2 == 1:
                    if node.max_score > 0:
                        node.score = 0.5
                else:
                    if node.min_score < 0:
                        node.score = -0.5
            self.nodelist_by_score.append(node)
            node.score_index = len(self.nodelist_by_score) - 1 

Mbtree.calc_score_by_bf = calc_score_by_bf

修正箇所

def calc_score_by_bf(self):
元と同じなので省略
                node.score = score
                node.max_score = max([childnode.max_score for childnode in node.children])
                node.min_score = min([childnode.min_score for childnode in node.children])
+           if node.score == 0:
+               if node.mb.move_count % 2 == 1:
+                   if node.max_score > 0:
+                       node.score = 0.5
+               else:
+                   if node.min_score < 0:
+                       node.score = -0.5
元と同じなので省略

Mbtree.calc_score_by_bf = calc_score_by_bf

実装の確認

上記の修正後に下記のプログラムを実行すると、実行結果のように ルートノード の score 属性の値が 0.5 である事が表示されます。ルートノード は 引き分けの局面 で、子ノードに〇が勝利する局面は明らかに存在する ので、正しい処理が行われているように見えます。

mbtree = Mbtree(shortest_victory=True)
print(mbtree.root.score)

実行結果

略
0.5

次に、それぞれのノードでどのような評価値が計算されているか を Mbtree_GUI クラスを利用して 視覚的に確認する ことにします。そのためには、局面と最善手・評価値の対応表のデータを作成 する必要があるので、下記のプログラムの 1 行目のように作成し、Mbtree_GUI クラスで表示すると、実行結果のような エラーが発生 します。

なお、1 行目で作成されるデータは間違ったデータなので、作成したデータを保存したファイルを今後利用することはありません。そのため、ファイルの名前には適当な名前（test.dat）としました。また、2 行目で Marubatsu_GUI が作成する Dropdown の項目のラベルも適当な名前（test）としました。

from tree import Mbtree_GUI

data = mbtree.calc_and_save_bestmoves_and_score_by_board("test.dat")
Mbtree_GUI(scoretable_dict={"test": data})

実行結果

略
File c:\Users\ys\ai\marubatsu\135\tree.py:495, in Mbtree.create_subtree(self)
    493 childmb = deepcopy(node.mb)
    494 board_str = node.mb.board_to_str()               
--> 495 x, y = bestmoves_and_score_by_board[board_str]["bestmoves"][0]
    496 childmb.move(x, y)
    497 childnode = Node(childmb, parent=node, depth=depth+1, 
    498                 bestmoves_and_score_by_board=bestmoves_and_score_by_board)   

IndexError: list index out of range

エラーの原因の検証

エラーメッセージから、bestmoves_and_score_by_board[board_str]["bestmoves"][0] の処理を行う際に、list の範囲外（out of range）のインデックスの要素を参照 したことがわかります。

bestmoves_and_score_by_board[board_str]["bestmoves"] には、board_str の局面の 最善手の一覧を表す list が代入されており、その中の 0 番の要素を参照 した際にエラーが発生しているので、最善手の一覧を表す list が 空の list になっていることが推測 されます。

そこで、最善手の一覧を計算 する処理を行う Mbtree クラスの calc_bestmove の処理を検証 することにします。下記は、calc_bestmove の定義です。この中にバグの原因がある ので、どこにバグがあるかについて少し考えてみて下さい。

 1  def calc_bestmoves(self, node):
 2      bestmoves = []
 3      for move, childnode in node.children_by_move.items():
 4          if node.score == childnode.score:
 5              bestmoves.append(move)
 6      node.bestmoves = bestmoves
 7
 8      key = tuple(node.mb.records)
 9      self.nodelist_by_mb[key] = node
10      self.bestmoves_by_mb[key] = bestmoves
11
12      for childnode in node.children:
13          self.calc_bestmoves(childnode)

上記の中で、最善手の一覧を計算 する処理は、2 ~ 5 行目 のプログラムで行っています。この中で、最善手であるか どうかの判定は、4 行目で 自身のノード評価値 と 子ノードの評価値 が 等しいかどうか で行っています。この判定 がバグが発生する原因です。

引き分けの局面の評価値の計算方法を修正する前では確かにこの判定方法で最善手を判定することができましたが、修正後 は引き分けの局面の ノードの評価値 が 0 から 0.5 または -0.5 に変更 される場合があるので、自身のノードの評価値と最善手の子ノードの 評価値が一致しなくなる場合が発生します。そのため、この方法では正しく判定できません。

この部分を下記のプログラムのように、〇の手番 の場合は 子ノードの評価値の最大値 を、× の手番 の場合は子ノードの評価値の 最小値 を計算し、その値と比較する ように修正する必要があります。

なお、3 行目 で 子ノードが存在する場合のみ処理を行う ように修正しているのは、空の list を実引数に記述して max または min を呼び出すと エラーが発生する からです。リーフノード には 子ノードが存在しない ので、下記のプログラムの 3 行目を記述しなかった場合は、4 行目の score_list の値が空の list になる場合 があり、6、8 行目で エラーが発生 します。

3 行目：子ノードが存在する場合のみ処理を行うように修正する
4 行目：子ノードの評価値の一覧を表す list を計算する
5 ～ 8 行目：最善手の評価値として、〇の手番の場合は子ノードの評価値の最大値を、× の手番の場合は最小値を計算する
10 行目：最善手であるかどうかの判定を、上記で計算した最善手の評価値と比較することで行うように修正する

 1  def calc_bestmoves(self, node):
 2      bestmoves = []
 3      if len(node.children) > 0:
 4          score_list = [childnode.score for childnode in node.children]
 5          if node.mb.move_count % 2 == 0:
 6              bestscore = max(score_list)
 7          else:
 8              bestscore = min(score_list)
 9          for move, childnode in node.children_by_move.items():
10              if bestscore == childnode.score:
11                  bestmoves.append(move)
12      node.bestmoves = bestmoves
元と同じなので省略
13               
14  Mbtree.calc_bestmoves = calc_bestmoves

行番号のないプログラム

def calc_bestmoves(self, node):
    bestmoves = []
    if len(node.children) > 0:
        score_list = [childnode.score for childnode in node.children]
        if node.mb.move_count % 2 == 0:
            bestscore = max(score_list)
        else:
            bestscore = min(score_list)
        for move, childnode in node.children_by_move.items():
            if bestscore == childnode.score:
                bestmoves.append(move)
    node.bestmoves = bestmoves

    key = tuple(node.mb.records)
    self.nodelist_by_mb[key] = node
    self.bestmoves_by_mb[key] = bestmoves

    for childnode in node.children:
        self.calc_bestmoves(childnode)                    
                
Mbtree.calc_bestmoves = calc_bestmoves

修正箇所

def calc_bestmoves(self, node):
    bestmoves = []
-   for move, childnode in node.children_by_move.items():
-       if node.score == childnode.score:
-           bestmoves.append(move)
+   if len(node.children) > 0:
+       score_list = [childnode.score for childnode in node.children]
+       if node.mb.move_count % 2 == 0:
+           bestscore = max(score_list)
+       else:
+           bestscore = min(score_list)
+       for move, childnode in node.children_by_move.items():
+           if bestscore == childnode.score:
+               bestmoves.append(move)
    node.bestmoves = bestmoves
元と同じなので省略
                
Mbtree.calc_bestmoves = calc_bestmoves

上記の修正後に下記のプログラムでゲーム木を計算しなおして、Mbtree_GUI を実行すると、実行結果のように評価値として 0.5 が計算される 引き分けの局面のノードの色 が、〇の必勝の局面を表す水色で表示 されるという 問題が発生している ことがわかります。このようなことが起きる原因について少し考えてみて下さい。

mbtree = Mbtree(shortest_victory=True)
data = mbtree.calc_and_save_bestmoves_and_score_by_board("test.dat")
mbtree_gui = Mbtree_GUI(scoretable_dict={"test": data})

実行結果

ノードの色の表示のバグの検証と修正

この問題は、ノードを表示 する Marubatsu_GUI クラスの draw_board メソッドの中で、下記のプログラムの 7 ~ 12 行目のように ゲーム盤の背景色の計算 を 評価値が正、0、負を判定する条件式 で行っているからです。

 1  @staticmethod
 2  def draw_board(ax, mb, show_result=False, score=None, bc=None, bw=1, darkness=0, dx=0, dy=0, lw=2):
 3      # 結果によってゲーム盤の背景色を変更する
 4      if show_result:
 5          if score is None and mb.status == Marubatsu.PLAYING:
 6              bgcolor = "white"
 7          elif (score is not None and score > 0) or mb.status == Marubatsu.CIRCLE:
 8              bgcolor = "lightcyan"
 9          elif (score is not None and score < 0) or mb.status == Marubatsu.CROSS:
10              bgcolor = "lavenderblush"
11          else:
12              bgcolor = "lightyellow"  
略

引き分けの局面 の評価値に 優劣をつける 場合は、引き分けの局面の評価値が 範囲を持つようにする 必要があります。そこで、本記事では、現状の評価値の計算方法にあわせて、-1 < 評価値 < 1 の場合に、引き分けの局面である事を表すようにすることにします。下記はそのように draw_board メソッドを修正したプログラムです。

10 行目：評価値が 1 以上の場合に〇の必勝の局面であることを判定するように修正する
12 行目：評価値が -1 以下の場合に × の必勝の局面であることを判定するように修正する

 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, bc=None, bw=1, darkness=0, 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 is not None and score >= 1) or mb.status == Marubatsu.CIRCLE:
11              bgcolor = "lightcyan"
12          elif (score is not None and score <= -1) or mb.status == Marubatsu.CROSS:
13              bgcolor = "lavenderblush"
14          else:
15              bgcolor = "lightyellow"      
元と同じなので省略
16
17  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, bc=None, bw=1, darkness=0, dx=0, dy=0, lw=2):
    # 結果によってゲーム盤の背景色を変更する
    if show_result:
        if score is None and mb.status == Marubatsu.PLAYING:
            bgcolor = "white"
        elif (score is not None and score >= 1) or mb.status == Marubatsu.CIRCLE:
            bgcolor = "lightcyan"
        elif (score is not None and 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)

    # ゲーム盤の枠を描画する
    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)

    # darkness 0 より大きい場合は、半透明の黒い正方形を描画して暗くする
    if darkness > 0:
        ax.add_artist(patches.Rectangle(xy=(dx, dy), width=mb.BOARD_SIZE,
                                        height=mb.BOARD_SIZE, fc="black", alpha=darkness))

    # bc が None でない場合はその色で bw の太さで外枠を描画する
    if bc is not None:
        frame = patches.Rectangle(xy=(dx, dy), width=mb.BOARD_SIZE,
                                height=mb.BOARD_SIZE, ec=bc, fill=False, lw=bw)
        ax.add_patch(frame)
    
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, bc=None, bw=1, darkness=0, dx=0, dy=0, lw=2):
    # 結果によってゲーム盤の背景色を変更する
    if show_result:
        if score is None and mb.status == Marubatsu.PLAYING:
            bgcolor = "white"
-       elif (score is not None and score > 0) or mb.status == Marubatsu.CIRCLE:
+       elif (score is not None and score >= 1) or mb.status == Marubatsu.CIRCLE:
            bgcolor = "lightcyan"
-       elif (score is not None and score < 0) or mb.status == Marubatsu.CROSS:
+       elif (score is not None and score <= -1) or mb.status == Marubatsu.CROSS:
            bgcolor = "lavenderblush"
        else:
            bgcolor = "lightyellow"      
元と同じなので省略

Marubatsu_GUI.draw_board = draw_board

上記の修正後に下記のプログラムを実行すると、実行結果のように引き分けの局面の色が正しく表示されるようになりますが、深さが 2、4、6 の 〇の手番の引き分けの局面 に 0.5 という評価値が計算 されていることがわかります。先ほど説明した評価値の計算では、〇の手番の引き分けの局面 の評価値は 0 または -0.5 のいずれかになるので、この評価値は間違っています。

data = mbtree.calc_and_save_bestmoves_and_score_by_board("test.dat")
mbtree = Mbtree_GUI(scoretable_dict={"test": data})

実行結果

また、上図の深さ 5 の × の手番の一番上のノードをクリックすると下図のような部分木が表示されます³。図から、(0, 1)、(2, 1) に着手した局面には子孫ノードに × が勝利するノードが存在 し、(0, 2)、(2, 2) に着手した場合は × が勝利するノードが 存在しない ので、この局面の 最善手は (0, 1) と (2, 1) になるはず ですが、図のように合法手の局面の 評価値が全て 0.5 になっているため、全ての合法手が最善手 になるという 間違いが発生 しています。

次回の記事では、このバグを修正することにします。何がバグの原因かについて余裕がある方は考えてみて下さい。

今回の記事のまとめ

今回の記事では、引き分けの局面 での 最善手の優劣 について説明し、そのような評価値を計算するために必要な 最大の評価値と最小の評価値の計算 を実装しました。

また、それらの値を利用して 引き分けの局面 で 勝利できる可能性がある合法手 を 最善手として計算する ための実装を開始しました。ただし、現状の実装にはバグが存在するので、次回の記事でそのバグを修正します。

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

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

次回の記事

もちろん、〇が勝利する可能性が存在しない場合は除きます ↩
評価値の最大値という表現は、子ノードの評価値の最大値のように別の意味で利用しているので、「最大の評価値」という表現にしました ↩
部分木全体を表示すると画像が大きくなるので、そのノードとそのノードの子ノードの範囲の図としました ↩