Pythonで〇×ゲームのAIを一から作成する その108 ゲーム木を利用した AI の処理の改良とプログレスバーの表示

目次と前回の記事

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

以下のリンクから、これまでに作成したモジュールを見ることができます。test.py を入れ忘れていたので今回から入れています。

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

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

プログレスバーによる途中経過の表示

今回の記事では最初に、今後の記事でも何度も利用する ai_match を改良します。

ai_match は、結果が出るまで のしばらくの間、何も表示されない状態で待たされる という欠点があります。また、前回の記事のように、ai_match の処理にものすごく長い時間がかかるような場合は、いつまで待てばよいかの見当がつかない という問題が発生します。

そのような場合は、処理の 進捗状況 （progress）を表す プログレスバー（progress bar）を表示するという工夫が良く行われます。

python には、for 文 による繰り返し処理を行う際に プログレスバーを表示 してくれる、tqdm¹ というモジュールがあるので、その使い方を紹介します。また、tqdm によって表示されるプログレスバーには、後述するように、for 文による 1 秒当たりの繰り返しの回数が表示されるので、処理速度の計測を行うことができるという利点もあります。

tqdm のインストールと使い方

tqdm は組み込みモジュールではないので、以前の記事 で matplotlib をインストールしたのと同様の方法で、Anaconda Navigator などを利用してインストールして下さい。

tqdm モジュールの利用方法は簡単で、下記のプログラムのように、tqdm から tqdm という関数をインポート した後で、for 文の反復可能オブジェクト の部分を、反復可能オブジェクトを実引数とした tqdm の関数呼び出しで置き換えるだけ です。

• 1 行目：tqdm モジュールから tqdm という関数をインポートする
• 3、4 行目：for 文の反復可能オブジェクトに tqdm(range(10000)) 記述して 10000 回の繰り返し処理を行う。この繰り返し処理では pass を記述しているので何も処理は行わない

from tqdm import tqdm

for i in tqdm(range(10000)):
    pass

実行結果（実行結果はコンピューターの性能や状況によって変わります）

100%|██████████| 10000/10000 [00:00<00:00, 5895844.81it/s]

上記のプログラムを実行すると、実行結果のようなプログレスバーが表示されるようになります。表示される数値の意味は、以下の通りです。残りの時間の予測は、これまでの経過時間から計算した予測なので、正確ではありませんが、 あとどれくらいで処理が終わるかの目安 になります。回数/秒の右に表示される it/s は iterations/second ²の略です。

進捗状況(%) |プログレスバー| 繰り返した回数/繰り返す回数 [経過時間<残り時間の予測, 回数/秒]

tqdm モジュールの詳細については、下記のリンク先を参照して下さい。

ai_match の改良

下記は、ai_match をプログレスバーを表示するように修正したプログラムです。

• 11 行目：AI 同士の対戦を行う for 文による繰り返し処理の反復可能オブジェクトの部分を tqdm を利用するように修正する

 1  from marubatsu import Marubatsu
 2  from collections import defaultdict
 3
 4  def ai_match(ai, params=[{}, {}], match_num=10000):
 5      print(f"{ai[0].__name__} VS {ai[1].__name__}")
 6   
 7      mb = Marubatsu()
 8
 9      # ai[0] VS ai[1] と ai[1] VS a[0] の対戦を match_num 回行い、通算成績を数える
10      count_list = [ defaultdict(int), defaultdict(int)]
11      for _ in tqdm(range(match_num)):
12          count_list[0][mb.play(ai, params=params, verbose=False)] += 1
13          count_list[1][mb.play(ai=ai[::-1], params=params[::-1], verbose=False)] += 1
元と同じなので省略

行番号のないプログラム

from marubatsu import Marubatsu
from collections import defaultdict

def ai_match(ai, params=[{}, {}], match_num=10000):
    print(f"{ai[0].__name__} VS {ai[1].__name__}")
    
    mb = Marubatsu()

    # ai[0] VS ai[1] と ai[1] VS a[0] の対戦を match_num 回行い、通算成績を数える
    count_list = [ defaultdict(int), defaultdict(int)]
    for _ in tqdm(range(match_num)):
        count_list[0][mb.play(ai, params=params, verbose=False)] += 1
        count_list[1][mb.play(ai=ai[::-1], params=params[::-1], verbose=False)] += 1

    # ai[0] から見た通算成績を計算する
    count_list_ai0 = [
        # ai[0] VS ai[1] の場合の、ai[0] から見た通算成績
        { 
            "win": count_list[0][Marubatsu.CIRCLE],
            "lose": count_list[0][Marubatsu.CROSS],
            "draw": count_list[0][Marubatsu.DRAW],
        },
        # ai[1] VS ai[0] の場合の、ai[0] から見た通算成績
        { 
            "win": count_list[1][Marubatsu.CROSS],
            "lose": count_list[1][Marubatsu.CIRCLE],
            "draw": count_list[1][Marubatsu.DRAW],
        },
    ]           

    # 両方の対戦の通算成績の合計を計算する
    count_list_ai0.append({})
    for key in count_list_ai0[0]:
        count_list_ai0[2][key] = count_list_ai0[0][key] + count_list_ai0[1][key]

    # それぞれの比率を計算し、ratio_list に代入する
    ratio_list = [ {}, {}, {} ]
    for i in range(3):
        for key in count_list_ai0[i]:
            ratio_list[i][key] = count_list_ai0[i][key] / sum(count_list_ai0[i].values())
            
    # 各行の先頭に表示する文字列のリスト
    item_text_list = [ Marubatsu.CIRCLE, Marubatsu.CROSS, "total" ]    
    
    # 通算成績の回数と比率の表示
    width = max(len(str(match_num * 2)), 7)
    diff_list = [ ("count", count_list_ai0, f"{width}d"),
                  ("ratio", ratio_list, f"{width}.1%") ]
    for title, data, format in diff_list:
        print(title, end="")
        for key in data[0]:
            print(f" {key:>{width}}", end="")
        print()
        for i in range(3):
            print(f"{item_text_list[i]:5}", end="")
            for value in data[i].values():
                print(f" {value:{format}}", end="")
            print()
        print()

修正箇所

from marubatsu import Marubatsu
from collections import defaultdict

def ai_match(ai, params=[{}, {}], match_num=10000):
    print(f"{ai[0].__name__} VS {ai[1].__name__}")
    
    mb = Marubatsu()

    # ai[0] VS ai[1] と ai[1] VS a[0] の対戦を match_num 回行い、通算成績を数える
    count_list = [ defaultdict(int), defaultdict(int)]
-   for _ in range(match_num):
+   for _ in tqdm(range(match_num)):
        count_list[0][mb.play(ai, params=params, verbose=False)] += 1
        count_list[1][mb.play(ai=ai[::-1], params=params[::-1], verbose=False)] += 1
元と同じなので省略

上記の修正後に下記のプログラムで ai_match で ai_gt1 VS ai2s の対戦を行うと、実行結果のようにプログレスバーが表示されるようになります。プログレスバーの右の 00:31 から、tqdm を記述した for 文の処理に約 31 秒かかり、315.49it/s から、1 秒間に平均すると約 300 回の繰り返し処理が行われたことが確認できます。

from tree import Mbtree
from ai import ai_gt1, ai2s

mbtree = Mbtree.load("dfscore")
ai_match(ai=[ai_gt1, ai2s], params=[{"mbtree":mbtree}, {}])

実行結果

ai_gt1 VS ai2s
100%|██████████| 10000/10000 [00:31<00:00, 315.49it/s]
count     win    lose    draw
o        9697       0     303
x        7786       0    2214
total   17483       0    2517

ratio     win    lose    draw
o       97.0%    0.0%    3.0%
x       77.9%    0.0%   22.1%
total   87.4%    0.0%   12.6%

ゲーム木を利用した AI の処理の改良

前回の記事で、ゲーム木を利用した強解決の AI を作成しました。強解決の AI は 全ての局面で最善手を着手する AI なので、これ以上強い AI を作成することは不可能 です。

ただし、前回の記事で作成した ai_gt1 は、プログラムの記述 や、処理の効率 の面では 改良の余地がある ので、今回の記事ではその改良を行うことにします。どのような改良を行うことができるかについて少し考えてみて下さい。

ノードの局面の最善手の記録による改良

前回の記事で説明したように、ゲーム木を利用した強解決の AI は下記のアルゴリズムで着手を選択します。

1. ゲーム木の中で、現在の局面を表すノードを探す
2. そのノードを使って、その局面の最善手を調べ、その中からランダムに着手を選択する

下記は上記の処理を行う ai_gt1 の定義を表すプログラムです。

 1  def ai_gt1(mb, mbtree):
 2      node = mbtree.root
 3      for move in mb.records[1:]:
 4          node = node.children_by_move[move]
 5
 6      bestmoves = []
 7      for move, childnode in node.children_by_move.items():
 8          if node.score == childnode.score:
 9              bestmoves.append(move)
10      return choice(bestmoves)

ゲーム木のノードの最善手を調べるという、上記の 手順 2 の処理 は いつ行っても同じ結果 になりますが、ai_gt1 ではその処理を 6 ~ 9 行目のプログラムで ai_gt1 が呼び出されるたびに行っている 点に 無駄があります。

そこで、上記の手順 2 の処理を以下の方法で行うように改良することにします。

• 手順 2 の処理 を、ゲーム木のそれぞれの ノードの評価値を計算した後 で行う
• 手順 2 で計算したノードの 最善手の一覧 を、その ノードの属性に代入して記録 する
• AI の処理を行う関数の手順 2 では、ノードの属性に代入された最善手の一覧を利用 する

calc_bestmoves の定義

ゲーム木の すべてのノードの最善手を計算 する Mbtree クラスの メソッドを定義 します。そのメソッドは幅優先アルゴリズムと深さ優先アルゴリズムのどちらを使っても実装できますが、本記事では より簡潔に記述できる再帰呼び出しによる深さ優先アルゴリズム で実装することにします。幅優先アルゴリズムで実装したい人は是非チャレンジしてみて下さい。

そこで、Mbtree クラスに下記のようなメソッドを定義する事にします。なお、本記事では幅優先アルゴリズムで同様の処理を行うメソッドは定義しないので、これまでのようにメソッドの名前の末尾にアルゴリズムの種類を表す _df は付けないことにします。

名前：ノードの最善手の一覧を計算するので、calc_bestmoves とする
処理：ゲーム木の全てのノードの最善手の一覧を、再帰呼び出しによる深さ優先アルゴリズムで計算し、それぞれのノードの属性に記録する
入力：仮引数 node に最善手を計算するノードを代入する
出力：なし

calc_bestmoves はゲーム木の 全てノードの評価値を計算後に実行する ので、ルートノードから 順番に トップダウン にその処理を行うことができます。そのため、下記のプログラムのような、トップダウンな再帰呼び出しによる処理を行う関数として定義できます。

• 1 行目：最善手を計算するノードを代入する仮引数 node を記述する
• 2 ~ 5 行目：ノードの最善手は トップダウン に計算するので、以前の記事で説明したように、9、10 行目の 再帰呼び出しの処理よりも前に記述 する。なお、2 ~ 5 行目の処理は、ai_gt1 の 6 ~ 9 行目の処理と全く同じである
• 6 行目：計算した最善手の一覧のデータをノードの bestmoves 属性に代入する

 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      for childnode in node.children:
 9          self.calc_bestmoves(childnode)
10        
11  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)
    node.bestmoves = bestmoves
    
    for childnode in node.children:
        self.calc_bestmoves(childnode)
        
Mbtree.calc_bestmoves = calc_bestmoves       

上記を定義後に、下記のプログラムを実行することで、mbtree の全てのノードに対して、最善手の一覧を表す bestmoves 属性が計算されます。

mbtree.calc_bestmoves(mbtree.root)

以前の記事でゲーム開始時の局面ではすべての着手が最善手であることがわかっています。下記のプログラムを実行すると、ルートノードのbestmoves 属性に 9 マスすべてが表示されることから、ルートノードの bestmoves 属性が正しく計算されていることが確認できます。

print(mbtree.root.bestmoves)

実行結果

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

ai_gt2 の定義

次に、最善手をノードの bestmoves 属性を使って計算する AI を定義する事にします。その関数の名前は、ai_gt1 を改良する関数なので ai_gt2 とします。以後もこの方針でゲーム木を利用した AI の処理を行う関数の名前を付けることにします。

ai_gt2 は、下記のプログラムのように定義できます。あらかじめ各ノードの最善手を計算しておくことで、プログラムが ai_gt1 と比べてシンプル になります。

• 8 行目：最善手の一覧は mb の局面を表すノードの bestmoves 属性に代入されるようになったので、その値と choice を使って着手をランダムに選択する

1  from random import choice
2
3  def ai_gt2(mb, mbtree):
4      node = mbtree.root
5      for move in mb.records[1:]:
6          node = node.children_by_move[move]
7
8      return choice(node.bestmoves)

行番号のないプログラム

from random import choice

def ai_gt2(mb, mbtree):
    node = mbtree.root
    for move in mb.records[1:]:
        node = node.children_by_move[move]

    return choice(node.bestmoves)

ai_gt1からの修正箇所

from random import choice

-def ai_gt1(mb, mbtree):
+def ai_gt2(mb, mbtree):
    node = mbtree.root
    for move in mb.records[1:]:
        node = node.children_by_move[move]

-   bestmoves = []
-   for move, childnode in node.children_by_move.items():
-       if node.score == childnode.score:
-           bestmoves.append(move)
-   return choice(bestmoves)
+   return choice(node.bestmoves)

下記のプログラムで ai_match を使って ai_gt2 VS ai2s の対戦を行うと、実行結果のように ai_gt1 VS ai2s とほぼ同じ対戦成績になることがわかります。

ai_match(ai=[ai_gt2, ai2s], params=[{"mbtree":mbtree}, {}])

実行結果（実行結果はランダムなので下記と異なる場合があります）

ai_gt2 VS ai2s
100%|██████████| 10000/10000 [00:32<00:00, 304.67it/s]
count     win    lose    draw
o        9673       0     327
x        7711       0    2289
total   17384       0    2616

ratio     win    lose    draw
o       96.7%    0.0%    3.3%
x       77.1%    0.0%   22.9%
total   86.9%    0.0%   13.1%

ノードを探す処理の効率化

下記はゲーム木を利用した強解決の AI のアルゴリズムの再掲です。

1. ゲーム木の中で、現在の局面を表すノードを探す
2. そのノードを使って、その局面の最善手を調べ、その中からランダムに着手を選択する

上記の手順 1 は、下記の ai_gt2 の 2 ~ 4 行目の処理で行っていますが、この処理も効率化することができます。どのように効率化できるかについて少し考えてみて下さい。

1  def ai_gt2(mb, mbtree):
2      node = mbtree.root
3      for move in mb.records[1:]:
4          node = node.children_by_move[move]
5
6      return choice(node.bestmoves)

局面とノードの対応表による効率化

考え方は、先程の手順 2 の効率化の手法と同じで、あらかじめすべての局面に対して、「局面」と「対応するノード」の 対応表 を表すデータを 計算しておく という方法です。

上記の 2 ~ 4 行目では、ルートノードから順番に mb の棋譜の順番通りに子ノードを辿っていくことでノードを探す処理を行っていますが、そのような対応表をあらかじめ計算しておけば、その表を利用することで 即座に mb に対応するノードを計算 することができます。

この手法は、以前の記事で説明したメモ化に似ていますが、メモ化 は データを計算した際 にそのデータを 記録して取っておく という手法であるのに対し、こちらは あらかじめすべてのデータを計算 して取っておく点が異なります。

具体的には、Mbtree クラスに nodelist_by_mb 属性を追加し、その属性にそのような 対応表を表す dict を記録 することができれば、mb の局面に対応するノードを探す処理を、下記のプログラムの 2 行目のように簡潔に定義する事ができまるようになります。2 行目の mb を表すデータ をどのように記述すれば良いかについて少し考えてみて下さい。

1  def ai_gt3(mb, mbtree):
2      node = mbtree.nodelist_by_mb[mb を表すデータ]
3      return choice(node.bestmoves)

ai_gt2からの修正箇所

-def ai_gt2(mb, mbtree):
+def ai_gt3(mb, mbtree):
-   node = mbtree.root
-   for move in mb.records[1:]:
-       node = node.children_by_move[move]
+   node = mbtree.nodelist_by_mb[mb を表すデータ]
    return choice(node.bestmoves)

間違った局面を表すデータの記述方法

以前の記事で説明したように、dict のキー には ハッシュ可能なオブジェクト を利用することができ、以前の記事で説明したように、自分で定義したクラスのインスタンス は ハッシュ可能なオブジェクト なので、dict のキーとして利用できます。

そのため、下記のプログラムのように、局面を表す Marubatsu クラスのインスタンスをキー とし、そのキーの値にその局面を表すノードを代入するという方法を考えた人が多いのではないかと思いますが、このプログラムは 正しく動作しません³。

def ai_gt3(mb, mbtree):
    node = mbtree.nodelist_by_mb[mb]
    return choice(node.bestmoves)

オブジェクトを dict のキーに記述した場合に行われる処理

上記の ai_gt3 の 2 行目の mbtree.nodelist_by_mb[mb] という処理が、意図通りに動作しない理由は、同じ局面 を表す Marubatsu クラスのインスタンスを 複数作成できてしまう からです。例えば、下記のプログラムでは、mb と mb2 にゲーム開始時の局面を表すデータが代入しますが、この 2 つのデータは異なるオブジェクト です。

mb = Marubatsu()
mb2 = Marubatsu()

そのため、下記のプログラムの 1 行目のように、mb をキーとし、そのキーの値にゲーム開始時の局面を表す mbtree のルートノードを代入した dict を作成した後で、2 行目のように mb2 をキーとする値を参照しようとすると、実行結果のようにキーが存在しないことを表す KeyError が発生します。

nodelist_by_mb = { mb: mbtree.root }
print(nodelist_by_mb[mb2])

実行結果

---------------------------------------------------------------------------
KeyError                                  Traceback (most recent call last)
Cell In[10], line 2
      1 nodelist_by_mb = { mb: mbtree.root }
----> 2 print(nodelist_by_mb[mb2])

KeyError: <marubatsu.Marubatsu object at 0x000001A5A4E0D590>

このようなことが起きるのは、自分で定義したクラスのインスタンスを dict のキーにした場合は、オブジェクトの id を使って キーの区別が行われる からです。

上記から、Marubatsu クラスのインスタンスは nodelist_by_mb の キーとして利用できない ことがわかります。そのため、別のデータ を 局面を表すデータとして利用 する必要があります。どのようなデータをキーとすれば良いかについて少し考えてみて下さい。

自分で定義したクラスのインスタンスを dict のキーにした場合は、同じ意味を表すデータであっても、異なるインスタンス は、異なるキー であると 認識される。

このノートは意味がわからない人は読み飛ばしても全く問題ありません。

特殊メソッドである __eq__ と __hash__ を定義することで、nodelist_by_mb[mb2] がエラーにならず、 nodelist_by_mb[mb] と同じ値を参照するようにすることは可能ですが、そのような手法は Marubatsu クラスのインスタンスのような、着手を行うことで内容を変更することができる ミュータブルなデータのクラスに対して行ってはいけない ことになっています。詳細は下記のリンク先を参照して下さい。

dict のキーとして利用可能な局面を表すデータ

局面を表すデータ として、真っ先に思いつく のは ゲーム盤を表す board 属性 のデータではないでしょうか。確かに、〇×ゲームでは⁴ board 属性の値が等しければ同じ局面であることは間違いないのですが、board 属性の値を使って対応表を作成しようとした場合は、ゲーム木の複数のノードが対応してしまう という問題があります。

わかりづらいと思いますので、具体例を挙げて説明します。ゲーム開始時の局面から (0, 0)、(1, 1)、(2, 2) の順で着手が行われた場合と、(2, 2)、(1, 1)、(0, 0) の順で着手が行われた場合は、board 属性の値は全く同じ になりますが、それぞれの局面を表すノード は、ゲーム木の中の 異なるノードに対応 します。

〇×ゲーム は、その局面に至るまでの棋譜が異なっていても、ゲーム盤の状況が同じであれば、最善手は同じになる⁵ ため、最善手を求めるだけ であれば、board 属性の値を使って対応表を作成 しても 問題はありません が、局面とゲーム木のノードを正しく対応させる必要がある 場合は、board 属性の値だけ を使って 対応表を作ることはできません。

局面とゲーム木のノードを正しく対応させるための 局面を表すデータ としては、 棋譜 を利用することができます。ゲーム木の作成の手順を考えれば、局面の 棋譜が一致 していれば、対応するゲーム木のノードが必ず同じになる ことは明らかだからです。棋譜のデータは、Marubatsu クラスの records 属性に代入されているので、records 属性の値をキー とすることで局面とゲーム木のノードの対応表を作成することができます。

ただし、残念ながら、下記のプログラムのようにキーに records 属性の値を そのまま dict のキーにする と実行結果のような エラーが発生 します。

nodelist_by_mb = {mb.records: mbtree.root}

実行結果

---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
Cell In[11], line 1
----> 1 nodelist_by_mb = {mb.records: mbtree.root}

TypeError: unhashable type: 'list'

エラーメッセージからわかるようにこのエラーの原因は、records 属性の値が、ハッシュ可能なデータ型ではない（unhashable）list であるから です。

この問題は、list を ハッシュ可能なデータである tuple に変換する ことで解決することができます。list を tuple に変換する方法は簡単で、下記のプログラムの 2 行目のように、組み込み関数 tuple の実引数に list を記述するだけ です。実行結果のように b には、a と 同じ要素を持つ tuple が代入されます。

a = [1, 2, 3]
b = tuple(a)
print(a)
print(b)

実行結果

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

なお、組み込み関数 tuple は、下記のプログラムのように、その 要素の値は tuple に変換してくれない 点に注意して下さい。実行結果のように、全体は tuple に変換されますが、1 番の要素の list は変換後も list のまま です。

a = [1, [2, 3]]
b = tuple(a)
print(a)
print(b)

実行結果

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

ハッシュ可能なデータ は、その中に ハッシュ可能ではないデータが存在してはいけない ので、tuple の要素に list が存在する場合はハッシュ可能なデータではありません。list を tuple を使って ハッシュ可能なデータに 変換する場合 は その点に注意 して下さい。

なお、records 属性の要素は、ハッシュ可能なデータ である None と tuple のみから構成 されるので、tupleを利用することでハッシュ可能なデータに変換することができます。

逆に、組み込み関数 list を使って下記のプログラムのように tuple を list に変換することもできます。なお、要素に tuple があった場合にその要素が list に変換されない点は組み込み関数 tuple による変換と同様です。

a = (1, (2, 3))
b = list(a)
print(a)
print(b)

実行結果

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

calc_bestmoves の修正

nodelist_by_mb 属性の計算は、ゲーム木を作成する際に行うことができますが、Mbtree クラスにはゲーム木を作成するメソッドが create_tree_by_bf と create_tree_by_df の 2 種類がある ので、その両方にその処理を記述するのは面倒 です。

nodelist_by_mb 属性は calc_bestmoves の処理の際にも計算できる ので、そちらでその処理を行うことにします。下記は、そのように calc_bestmoves を修正したプログラムです。

• 2 行目：棋譜を表す node.mb.records 属性を tuple を使って変換したデータをキーとするキーの値に node を代入する。calc_bestmoves は、ゲーム木の 全てのノードに対して呼び出される ので、全てのノードで nodelist_by_mb が計算 される

1  def calc_bestmoves(self, node):
2      self.nodelist_by_mb[tuple(node.mb.records)] = node
元と同じなので省略
3        
4  Mbtree.calc_bestmoves = calc_bestmoves 

行番号のないプログラム

def calc_bestmoves(self, node):
    self.nodelist_by_mb[tuple(node.mb.records)] = node

    bestmoves = []
    for move, childnode in node.children_by_move.items():
        if node.score == childnode.score:
            bestmoves.append(move)
    node.bestmoves = bestmoves
    
    for childnode in node.children:
        self.calc_bestmoves(childnode)
        
Mbtree.calc_bestmoves = calc_bestmoves       

修正箇所

def calc_bestmoves(self, node):
+   self.nodelist_by_mb[tuple(node.mb.records)] = node
元と同じなので省略
        
Mbtree.calc_bestmoves = calc_bestmoves       

上記の修正後に、下記のプログラムを実行して mbtree の 全てのノードに対する nodelist_by_mb を計算 します。なお、calc_bestmoves メソッドを呼び出す前に、nodelist_by_mb 属性に空の dict を代入しておく必要がある点に注意して下さい。

mbtree.nodelist_by_mb = {}
mbtree.calc_bestmoves(mbtree.root)

次に、nodelist_by_mb が正しく計算されているかどうかを確認します。

下記のプログラムは、ゲーム開始時の局面を表す mb の records 属性を使って、nodelist_by_mb からゲーム開始時の局面を表すルートノードを探すことができることを確認するプログラムです。実行結果から、探すことができたことが確認できます。

• 1 行目：mb の records 属性を tuple に変換し、records に代入する
• 2 行目：nodelist_by_mb 属性から、records のキーの値を参照して root に代入する
• 3 行目：root と mbmtree.root が同じオブジェクトであることを、同一性（同一のオブジェクトであるかどうか）を判定する is 演算子で計算する

records = tuple(mb.records)
root = mbtree.nodelist_by_mb[tuple(records)]
print(root is mbtree.root)

ai_gt3 の定義と ai_match による対戦

nodelist_by_mb が計算されていることが確認できたので、ai_gt3 を下記のプログラムのように定義します。

def ai_gt3(mb, mbtree):
    node = mbtree.nodelist_by_mb[tuple(mb.records)]
    return choice(node.bestmoves)

ai_gt2からの修正箇所

-def ai_gt2(mb, mbtree):
+def ai_gt3(mb, mbtree):
-   node = mbtree.root
-   for move in mb.records[1:]:
-       node = node.children_by_move[move]
+   node = mbtree.nodelist_by_mb[tuple(mb.records)]
    return choice(node.bestmoves)

上記を定義した後で ai_match で対戦すると、実行結果のような対戦成績が表示されます。対戦成績は ai_gt1 VS ai2s とほぼ同じなので正しく実装できていることが確認できます。

ai_match(ai=[ai_gt3, ai2s], params=[{"mbtree":mbtree}, {}])

実行結果

ai_gt3 VS ai2s
100%|██████████| 10000/10000 [00:32<00:00, 309.37it/s]
count     win    lose    draw
o        9692       0     308
x        7800       0    2200
total   17492       0    2508

ratio     win    lose    draw
o       96.9%    0.0%    3.1%
x       78.0%    0.0%   22.0%
total   87.5%    0.0%   12.5%

さらなる改良

下記の ai_gt3 をさらに改良することができます。どのように改良できるかについて少し考えてみて下さい。

def ai_gt3(mb, mbtree):
    node = mbtree.nodelist_by_mb[tuple(mb.records)]
    return choice(node.bestmoves)

上記のプログラムでは、局面を表すデータからノードを調べ、そのノードの bestmoves 属性を計算するという処理を行っていますが、この処理は 局面と最善手の一覧の対応表を作成 することで 1 回の処理で行う ことができるようになります。具体的には、その 対応表をあらかじめ計算 して Mbtree クラスの bestmoves_by_mb という属性に 代入しておけば、ai_gt4 を下記のプログラムのように 1 行で記述 することができます。

def ai_gt4(mb, mbtree):
    return choice(mbtree.bestmoves_by_mb[tuple(mb.records)])

行番号のないプログラム

def ai_gt4(mb, mbtree):
    return choice(mbtree.bestmoves_by_mb[tuple(mb.records)])

ai_gt3からの修正箇所

-def ai_gt3(mb, mbtree):
+def ai_gt4(mb, mbtree):
-   node = mbtree.nodelist_by_mb[tuple(mb.records)]
-   return choice(node.bestmoves)
+   return choice(mbtree.bestmoves_by_mb[tuple(mb.records)])

calc_bestmoves の修正

bestmoves_by_mb 属性は、最善手の一覧を計算した後 でなければ計算できないので、下記のプログラムのように calc_bestmoves で計算 する必要があります。

• 8 行目：nodelist_by_mb と bestmoves_by_mb で キーの意味は共通する ので、キーとして用いる棋譜を表すデータを key という変数に 代入しておく
• 9 行目：この処理は元は 2 行目に記述していたが、10 行目の bestmoves_by_mb の処理と同様の処理なので、まとめて処理を行うためにここに移動した
• 10 行目：best_moves_by_mb の key の値に bestmoves を代入して記録する。なお、この処理は、2 ~ 6 行目で bestmoves を計算した後で行う必要がある

 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)
14        
15  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)
    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):
-   self.nodelist_by_mb[tuple(node.mb.records)] = node
    bestmoves = []
    for move, childnode in node.children_by_move.items():
        if node.score == 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        

上記の修正後に、下記のプログラムを実行して mbtree の bestmoves_by_mb を計算します。なお、calc_bestmoves メソッドを呼び出す前に、bestmoves_by_mb 属性に空の dict を代入しておく必要がある点に注意して下さい。

mbtree.nodelist_by_mb = {}
mbtree.bestmoves_by_mb = {}
mbtree.calc_bestmoves(mbtree.root)

上記の実行後に ai_match で対戦すると、実行結果のような対戦成績が表示されます。対戦成績は ai_gt1 VS ai2s とほぼ同じなので正しく実装できていることが確認できます。

ai_match(ai=[ai_gt4, ai2s], params=[{"mbtree":mbtree}, {}])

実行結果

ai_gt4 VS ai2s
100%|██████████| 10000/10000 [00:32<00:00, 307.99it/s]
count     win    lose    draw
o        9714       0     286
x        7704       0    2296
total   17418       0    2582

ratio     win    lose    draw
o       97.1%    0.0%    2.9%
x       77.0%    0.0%   23.0%
total   87.1%    0.0%   12.9%

最善手の計算に必要なデータの分離

下記の ai_gt4 の 2 行目をよく見ると、ai_gt4 の処理に必要なデータ は bestmoves_by_mb 属性だけ であり、mbtree の他のデータは必要がないことがわかります。

def ai_gt4(mb, mbtree):
    return choice(mbtree.bestmoves_by_mb[tuple(mb.records)])

そのため、下記のプログラムのように、仮引数に bestmoves_by_mb のデータを代入 するように ai_gt5 を定義する事ができます。

def ai_gt5(mb, bestmoves):
    return choice(bestmoves[tuple(mb.records)])

行番号のないプログラム

def ai_gt5(mb, bestmoves):
    return choice(bestmoves[tuple(mb.records)])

ai_gt4からの修正箇所

-def ai_gt4(mb, mbtree):
+def ai_gt5(mb, bestmoves):
-   return choice(mbtree.bestmoves_by_mb[tuple(mb.records)])
+   return choice(bestmoves[tuple(mb.records)])

上記の定義後に ai_match で対戦すると、実行結果のような対戦成績が表示されます。対戦成績は ai_gt1 VS ai2s とほぼ同じなので正しく実装できていることが確認できます。

ai_match(ai=[ai_gt5, ai2s], params=[{"bestmoves":mbtree.bestmoves_by_mb}, {}])

実行結果

ai_gt5 VS ai2s
100%|██████████| 10000/10000 [00:32<00:00, 308.59it/s]
count     win    lose    draw
o        9632       0     368
x        7774       0    2226
total   17406       0    2594

ratio     win    lose    draw
o       96.3%    0.0%    3.7%
x       77.7%    0.0%   22.3%
total   87.0%    0.0%   13.0%

データのファイルサイズの比較

このように ai_gt5 を定義する事の 利点 は、AI の処理を行う際に必要なデータを保存した際の ファイルの大きさ にあります。

下記のプログラムで、mbtree と mbtree.bestmoves_by_mb のデータをファイルに保存し、ファイルサイズを比較 すると以下の表のようになります。なお、mbtree のファイル名は、ai_gt1 ~ ai_gt4 に必要なデータがすべて含まれているので aidata.mbtree とし、mbtree.bestmoves_by_mb のファイル名は bestmoves.dat としました。

import pickle
import gzip
mbtree.save("aidata")
with gzip.open("bestmoves.dat", "wb") as f:
    pickle.dump(mbtree.bestmoves_by_mb, f)

ファイル名	データサイズ	読み込み時間
aidata.mbtree	約 21.8 MB	16.6 秒
bestmoves.dat	約 2.8 MB	0.7 秒

bestmoves.dat には、ゲーム木に関するデータが含まれていない ので、表のように ファイルサイズが約 1/8 になる という利点があります。そのため、下記のプログラムでファイルからデータを読み込むとそれぞれの処理にかかる時間は表のように 大きな差 がでます。AI と対戦する前にファイルの読み込みで 15 秒も待たされるのは苦痛なので、この差は大きな利点と言えるでしょう。

mbtree.load("aidata")

with gzip.open("bestmoves.dat", "rb") as f:
    bestmoves = pickle.load(f)

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

Mtree クラスに新しく calc_bestmoves メソッドを追加したので、下記のプログラムのように __init__ メソッドで calc_bestmoves を呼び出すように修正することにします。

• 4 ~ 8 行目：評価値を計算した後で、calc_bestmoves を呼び出すように修正する

1  from tree import Node
2
3  def __init__(self, algo="bf"):
元と同じなので省略
4      self.nodelist_by_mb = {}
5      self.bestmoves_by_mb = {}
6      self.calc_bestmoves(self.root)
7
8  Mbtree.__init__ = __init__

行番号のないプログラム

from tree import Node

def __init__(self, algo="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.nodelist_by_score = []
        self.calc_score_by_df(self.root)
    self.nodelist_by_mb = {}
    self.bestmoves_by_mb = {}
    self.calc_bestmoves(self.root)

Mbtree.__init__ = __init__

修正箇所

from tree import Node

def __init__(self, algo="bf"):
元と同じなので省略
+   self.nodelist_by_mb = {}
+   self.bestmoves_by_mb = {}
+   self.calc_bestmoves(self.root)

Mbtree.__init__ = __init__

実行結果は省略しますが、上記の修正後に下記のプログラムで Mbtree クラスのインスタンスを作成し、それを使って ai_gt4 の対戦を行うことで、Mbtree のインスタンスの作成時に nodelist_by_mb 属性と bestmoves_by_mb 属性が正しく計算されたことが確認できます。

mbtree2 = Mbtree()
ai_match(ai=[ai_gt4, ai2s], params=[{"mbtree":mbtree2}, {}])

AI 処理時間の差の計測

下記は、ai_match で ai_gt1 ~ ai_gt5 までが対戦を行った際のプログレスバーの部分を抜粋して並べたものです。この中で 00:31<00:00 の 前の数字が処理時間 を表します。処理が効率的になっているにも関わらず、それぞれの処理時間に差がほとんど変わらない 点が気になっている人がいるかもしれませんが、その理由は ai_gt1 ~ ai_gt5 の処理時間 は、ai_match で行われる 他の処理にかかる時間と比べて非常に短い からです。

ai_gt1 VS ai2s
100%|██████████| 10000/10000 [00:31<00:00, 315.49it/s]
ai_gt2 VS ai2s
100%|██████████| 10000/10000 [00:32<00:00, 304.67it/s]
ai_gt3 VS ai2s
100%|██████████| 10000/10000 [00:32<00:00, 309.37it/s]
ai_gt4 VS ai2s
100%|██████████| 10000/10000 [00:32<00:00, 307.99it/s]
ai_gt5 VS ai2s
100%|██████████| 10000/10000 [00:32<00:00, 308.59it/s]

そのため、ai_gt1 ~ ai_gt5 の処理時間を調べるためには、それぞれの関数のみの処理時間 を %%timeit などで 計測する必要があります。その際に、下記のプログラムのように 1 つの局面で処理時間を測る のはあまり よいやり方ではない でしょう。その理由は、局面によって それぞれの AI が行う 処理時間が変わる場合がある からです。例えば、ai_gt1 は mb に対応するノードを探す際に ルートノードから順番に子ノードを辿って探す ので、ルートノード の局面と 深さが深いノード の局面では、計算時間に差が生じます。

%%timeit
ai_gt1(mb, mbtree)

そこで、ランダムな局面に対する処理時間を計測 することにします。〇×ゲームの 全局面 のノードは Mbtree クラスの nodelist 属性に代入 されているので、下記のプログラムのように choice を使うことでランダムな局面に対する処理が行われるようになるはずなのですが、実行結果のようなエラーが発生します。このエラーの原因を少し考えてみて下さい。

• 2 行目：choice(mbtree.nodelist) によって、ゲーム木の中からランダムにノードを一つ選択し、その mb 属性を最初の引数に記述する

%%timeit
ai_gt1(choice(mbtree.nodelist).mb, mbtree)

実行結果

略
File c:\Users\ys\ai\marubatsu\108\ai.py:1023, in ai_gt1(mb, mbtree)
   1021     if node.score == childnode.score:
   1022         bestmoves.append(move)
-> 1023 return choice(bestmoves)

File c:\Users\ys\Anaconda3\envs\marubatsu\Lib\random.py:373, in Random.choice(self, seq)
    370 # As an accommodation for NumPy, we don't use "if not seq"
    371 # because bool(numpy.array()) raises a ValueError.
    372 if not len(seq):
--> 373     raise IndexError('Cannot choose from an empty sequence')
    374 return seq[self._randbelow(len(seq))]

IndexError: Cannot choose from an empty sequence

エラーメッセージは「空（empty）のシーケンス型のデータから（from）選択（choose）することはできない（can not）」という意味で、ai_gt1 の return choice(bestmoves) によってエラーが発生していることがわかります。従って、bestmoves に空の list が代入 された状態で choice(bestmoves) が呼び出された ことが推測されます。

Python のバージョン 3.10 では「IndexError: list index out of range」という別のエラーメッセージが表示されるようです。このように、Python のバージョンによっては、エラーの表記が異なる場合があるようです。なお、本記事では Python のバージョン 3.11 でプログラムを実行しています。

実際に mbtree.nodelist に記録されたノードの中には ゲームの決着がついた局面のノードも含まれており、そのようなノードには 合法手が存在しない ので、bestmoves 属性には空の list が代入 されます。エラーの原因が判明したので、下記のプログラムで、mbtree.nodelist から、ゲームの決着がついていないノード の mb 属性を抜き出して mblist に代入 することにします。

• 1 行目：mblist を空の list で初期化する
• 2 行目：mbtree.nodelist の全ての要素に対する繰り返し処理を行う
• 3、4 行目：ノードの局面がゲーム中の場合に、mblist に node.mb を追加する

1  mblist = []
2  for node in mbtree.nodelist:
3      if node.mb.status == Marubatsu.PLAYING:
4          mblist.append(node.mb)

行番号のないプログラム

mblist = []
for node in mbtree.nodelist:
    if node.mb.status == Marubatsu.PLAYING:
        mblist.append(node.mb)

上記を実行すると、下記のプログラムでランダムな局面に対して ai_gt1 が行う処理時間の平均を計測することができるようになります。

%%timeit
ai_gt1(choice(mblist), mbtree)

実行結果

6.41 µs ± 221 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)

続けて ai_gt2 ~ ai_gt5 の計測を行います。なお、ai_gt5 では、先程ファイルからデータを読み込んだ bestmoves を実引数に記述しました。

%%timeit
ai_gt2(choice(mblist), mbtree)

実行結果

5.66 µs ± 104 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)

%%timeit
ai_gt3(choice(mblist), mbtree)

実行結果

3.59 µs ± 54.3 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)

%%timeit
ai_gt4(choice(mblist), mbtree)

実行結果

2.81 µs ± 27.8 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)

%%timeit
ai_gt5(choice(mblist), bestmoves)

実行結果

3.18 µs ± 39 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)

下記はそれぞれの処理の平均時間をまとめた表です。ai_gt1 から ai_gt4 まで、処理の効率化が行われるたびに、平均時間が減っている ことが確認でき、ai_gt1 と ai_gt4 では 2 倍以上の差が生じることがわかりました。なお、ai_gt4 と ai_gt5 は実質的に同じ処理を行っているので同じ所要時間になるはずなのですが、結果は若干 ai_gt5 のほうが所要時間がかかるようです。これが誤差なのか、それとも何か理由があるのかはよくわかりません。

AI	平均時間
ai_gt1	6.41 μs
ai_gt2	5.66 μs
ai_gt3	3.59 μs
ai_gt4	2.98 μs
ai_gt5	3.29 μs

上記の計測 では、ai_gt1 などの処理とは 関係のない、ランダムにノードを選択する choice(mblist) の処理が含まれています。従って、ai_gt1 などの処理時間は 厳密には choice(mblist) の処理時間を引く 必要があります。

下記のプログラムで choice(mblist) の処理時間を計測した所、実行結果から処理時間の平均は 599 ns = 約 0.6 μs であることがわかりました。これは、上記の表の計測時間と比べると 1/50 以下であるため、ほとんど気にする必要はないでしょう。

%%timeit
choice(mblist)

実行結果

599 ns ± 24.8 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)

今回の記事のまとめ

今回の記事では、for 文の処理に対してプログレスバーを表示する方法を紹介し、その後でゲーム木を利用する AI の処理の効率化を行いました。

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

リンク	説明
marubatsu.ipynb	本記事で入力して実行した JupyterLab のファイル
tree_new.py	今回の記事で更新した tree.py
ai_new.py	今回の記事で更新した ai.py
aidata.mbtree	ゲーム木を利用する AI で必要となるデータが計算されたゲーム木のデータを保存するファイル
bestmoves.dat	局面と最善手の一覧の対応表のデータを保存するファイル

今回の記事からデータファイルを下記の記事にまとめることにしました。

次回の記事

1. tqdm の公式のドキュメントによると、tqdm はアラビア語では progress、スペイン語の I love you の頭文字という意味を持つそうです ↩

2. iterations は繰り返しの回数を表す単語の複数形です ↩

3. 本記事では赤色の背景の警告のノートは、間違ったプログラムが記述されていることを表します ↩

4. 点数があるゲームや、将棋の持ち駒のように、ゲーム盤以外のデータが存在するゲームは、それらのデータも含める必要があります ↩

5. 将棋の場合は千日手というルールが、以後の場合はコウというルールがあるので、ゲーム盤の状況が全く同じであっても、過去の局面の状況が異なると最善手が同じであるとは限りません ↩