Pythonで〇×ゲームのAIを一から作成する その110 データ型による演算子の処理の違いによるバグとboard 属性を利用した局面の表現

目次と前回の記事

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

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

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

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

前回の記事のバグの説明

前回の記事では、ai14s が強解決の AI であることを示したつもりだったのですが、それは 最初に定義した is_strongly_solved にバグがあったため であることが判明しました。

この後で示しますが、実際には ai14s は強解決の AI ではありません。

今回の記事では最初にそのバグの原因を説明します。

バグの発見の経緯

前回の記事では、最初に is_strongly_solved を下記のプログラムのように定義しました。

from util import load_bestmoves, load_mblist
from tqdm import tqdm

def is_strongly_solved(ai):
    bestmoves = load_bestmoves()
    mblist = load_mblist()
    for mb in tqdm(mblist):
        if set(ai(mb, candidate=True)) > set(bestmoves[tuple(mb.records)]):
            return False
    return True

そして、下記のプログラムを実行し、実行結果に True が表示されたので ai14s が強解決の AI だと判断しました。

from ai import ai14s

is_strongly_solved(ai14s)

実行結果

100%|██████████| 294778/294778 [00:49<00:00, 5914.87it/s]
True

前回の記事では、その後で下記のプログラムのように is_strongly_solved を Check_solved クラスの静的メソッドとして定義するように改良し、ai2s に対して is_strongly_solved でチェックを行ったのですが、その時点で満足してしまい、ai14s に対するのチェックを怠ってしまいました。

class Check_solved:
    bestmoves = load_bestmoves()
    mblist = load_mblist()
    
    @staticmethod
    def is_strongly_solved(ai):
        count = 0
        for mb in tqdm(Check_solved.mblist):
            if set(ai(mb, candidate=True)) <= set(Check_solved.bestmoves[tuple(mb.records)]):
                count += 1
        nodenum = len(Check_solved.mblist)
        print(f"{count}/{nodenum} {count/nodenum*100:.2f}%")
        return count == nodenum

前回の記事を投稿した後で、念のために下記のプログラムで ai14s をチェック した所、実行結果のように ai14s が 294778 - 294690 = 88 の局面で最善手以外の合法手を選択する ため、強解決の AI ではない という、先程と異なる判定が表示されました。

Check_solved.is_strongly_solved(ai14s)

実行結果

100%|██████████| 294778/294778 [00:51<00:00, 5721.66it/s]
294690/294778 99.97%
False

この 2 つの結果は矛盾する ので、どちらか（もしくは両方）のプログラムが間違っていることがわかりました。

バグを発生させてしまった理由

結論から言うと、最初に定義したプログラムが間違っています。そこで、間違ったプログラムを記述してしまった理由について説明します。

下記は前回の記事で説明した 強解決の AI であるかを判定 するためのアルゴリズムです。

〇×ゲームの、決着がついていない全ての局面 に対して下記の処理を行う

1. その AI が着手する 可能性のある 合法手の一覧 を計算する
2. 手順 1 で計算した合法手の一覧が、その局面の 最善手の一覧に完全に含まれているか どうかを判定する
3. 含まれていない合法手が存在する 場合は、その AI は 最善手を選択しない局面が存在する ので、強解決の AI ではないことが判明し、処理を完了する
4. 存在しない場合は、次の局面があれば、次の局面に対して手順 1 ~ 4 の処理を行う
5. 次の局面が存在しない 場合は、全ての局面で最善手のみを選択する ことが確定するので、強解決の AI である ことが判明する

記述が長くなるので、以下の説明では A と B という記号を下記の意味で使います。

• ある局面での AI が着手する可能性のある合法手の一覧 を表す集合を A とする
• 同じ局面の 合法手の一覧を表す集合 を B とする

上記の手順 2 では、A の要素が B の要素に完全に含まれているという、数学では $A ⊆ B$ という記号で記述される、包含関係 があることを判定します。そして、次の手順 3 では $A ⊆ B$ ではない場合 に 強解決の AI ではない ことを判定します。

python の集合を表す set は、$A ⊆ B$ であることを <= という演算子で計算できるので、最初に定義した is_strongly_solved では、上記の手順 3 で そうではないことを判定 するために、下記のプログラムのように > という演算子で判定しましたが、それがバグの原因です。

if set(ai(mb, candidate=True)) > set(bestmoves[tuple(mb.records)]):
    return False

数値と set に対する <= 演算子と > の違い

このようなミスをしてしまった理由は、数値 と set で <= 演算子と > 演算子が行う 計算の性質 が下記のように 異なるから です。

• 数値に対する <= 演算子は、前の数値が後の数値「以下」であることを判定する
• 数値に対する > 演算子は、前の数値が後の数値「より大きい」ことを判定する
• 従って、2 つの数値 a、b に対して、a <= b と a > b の計算結果は、必ず True と False が逆になる

従って、数値に対しては <= と > は逆の意味の計算を行うため、<= の条件が満たされないことを判定するために、< 演算子を利用することができます。

何を当たり前のことを言っているのだと思っている人がいるかもしれませんが、set では <= 演算子と > 演算子は、同じ記号を使っていますが 上記と異なる 下記の 計算を行います。

• set に対する <= 演算子は、前の集合を a、後ろの集合を b とすると、以下のいずれかの場合に True を計算する
  • a の全ての要素が b の要素に含まれる（$a ⊆ b$ という包含関係）
  • a と b の要素が等しい（$a = b$ という相当関係）
• set に対する > 演算子は、以下の場合に True を計算する
  • b の全ての要素が a の要素に含まれるがa と b の要素は等しくない（$a ⊃ b$ という包含関係。$a ≠ b$ である）

set に対する a <= b と a > b の計算は数値の場合と異なり、逆の計算を行うわけではありません。そのため、その 2 つの計算結果が 必ずしも True と False のように逆になるとは限らない ので、<= の条件が満たされないことを判定するために、< 演算子を利用することはできません。

具体例を挙げて説明します。例えば、下記のプログラムのように a の全ての要素が b に含まれる場合は、b の要素の中に a に含まれない要素は絶対に存在しないので a <= b と a > a の計算結果は True と False が逆になります。

a = set([1, 2])
b = set([1, 2, 3])
print(a <= b)
print(a > b)

実行結果

True
False

下記のプログラムのように、a と b の前後を入れ替えても同様です。このように、どちらかが片方を包含している場合 は、True と False は確かに逆になります。

print(b <= a)
print(b > a)

実行結果

False
True

しかし、下記のプログラムのように、a と b に それぞれお互いの要素に含まれない要素が存在する場合 は、a <= b と b > a の 両方が False になります。これは、どちらの集合ももう片方の集合に対する包含関係にない場合 です。

a = set([1, 2])
b = set([2, 3])
print(a <= b)
print(a > b)

実行結果

False
False

Python の <= 演算子と > 演算子は以下のような関係にある。

• 数値型 のデータに対しては、それぞれが必ず逆の計算を行うため、両方の計算結果は必ず True と False が逆になる
• set に対しては、下記のように 必ずしも逆の計算が行われるわけではない
  • 片方が 包含関係にある 場合は、True と False になる
  • どちらも 包含関係にない 場合は、両方とも False になる

同じ演算子が異なる計算を行う他の例としては、数値に対しては加算を行い、文字列に対しては結合を行う + 演算子があります。

これまで説明していませんでしたが、Python ではクラスに特殊メソッドを定義する事で、+ や <= 等の 演算子が行う処理を自分で定義する事ができます。そのため、他にも同様の例が無数に存在します。

なお、その方法については必要になった時点で紹介します。

間違った判定が行われる理由

下記のプログラムが間違っているのは、A <= B ではないことを判定するために A > B という式を記述していることです。A <= B と A > B の 両方が False になる局面 では、AI が 最善手を選択しないにもかかわらず、A > B が False になる ため、強解決の AI ではないにもかかわらず、下記のプログラムではそのことを 正しく判定できません。

if set(ai(mb, candidate=True)) > set(bestmoves[tuple(mb.records)]):
    return False

一方、修正後の下記のプログラムでは、A <= B の条件を満たす局面の数を数え、その後で そのような局面の数が全局面の数と等しい場合 に強解決の AI であることを判定しているので、強解決の AI であることを 正しく判定することができます。

if set(ai(mb, candidate=True)) <= set(Check_solved.bestmoves[tuple(mb.records)]):
     count += 1

演算子の記号による錯覚

上記のような間違ったプログラムを記述してしまった原因は、数値に対する <= と > の演算子が逆の計算を行うため、set に対しても 同様に逆の計算を行う と 錯覚して勘違いしてしまったから です。数学の世界で集合の包含関係を $A ≦ B$ ではなく、$A ⊆ B$ のように 別の記号を使って表す のは、集合に対する $⊆$ という記号の性質が、数値に対する $≦$ とは 異なる性質を持つ からです。

残念ながら python だけでなく、ほとんどのプログラム言語では、演算子には < のような 半角の記号しか使うことができない ので、python では <= という演算子を集合の $⊆$ という演算子として 代用 しています。そのため、演算子の見た目から 筆者が行ったような 勘違いが起きやすい ので 気を付ける必要があります。

なお、修正後の Check_solved.is_strongly_solved は正しい処理を行うので、プログラムを修正する必要はありません。

ai14s が最善手を選択しない局面の検証

先程の下記のプログラムの実行結果から、ai14s には 最善手を選択しない局面が 88 個ある ことがわかりました。そこで、どのような局面で ai14s が最善手を着手しないかを検証できる ように is_strongly_solved を修正することにします。

Check_solved.is_strongly_solved(ai14s)

実行結果

100%|██████████| 294778/294778 [00:51<00:00, 5721.66it/s]
294690/294778 99.97%
False

具体的には、下記のプログラムのように、最善手を選択しない局面であると判定した場合に、「その局面」、「AI が選択する着手の一覧」、「最善手の一覧」を 記録し、関数の 返り値として返す ように修正することにします。

• 4 行目：最善手以外の、間違った（incorrect）着手が含まれている局面のデータを記録する incorrectlist という変数を空の list で初期化する
• 6 ~ 8 行目：AI が選択する着手の候補の集合と、最善手の集合を candidate と bestmoves に代入し、それを使って判定を行うように修正する。なお、変数に代入した理由は 11 行目でそれらの値を記述する必要があるからである
• 10、11 行目：間違った着手が含まれている場合に、「その局面」、「AI が選択する着手の一覧」、「最善手の一覧」を要素とする tuple を incorrectlist の要素に追加する
• 14 行目：返り値に、incorrectlist を含めるように修正する

 1  @staticmethod
 2  def is_strongly_solved(ai):
 3      count = 0
 4      incorrectlist = []
 5      for mb in tqdm(Check_solved.mblist):
 6          candidate = set(ai(mb, candidate=True))
 7          bestmoves = set(Check_solved.bestmoves[tuple(mb.records)])
 8          if candidate <= bestmoves:
 9              count += 1
10          else:
11              incorrectlist.append((mb, candidate, bestmoves))
12      nodenum = len(Check_solved.mblist)
13      print(f"{count}/{nodenum} {count/nodenum*100:.2f}%")
14      return count == nodenum, incorrectlist
15
16  Check_solved.is_strongly_solved = is_strongly_solved

行番号のないプログラム

@staticmethod
def is_strongly_solved(ai):
    count = 0
    incorrectlist = []
    for mb in tqdm(Check_solved.mblist):
        candidate = set(ai(mb, candidate=True))
        bestmoves = set(Check_solved.bestmoves[tuple(mb.records)])
        if candidate <= bestmoves:
            count += 1
        else:
            incorrectlist.append((mb, candidate, bestmoves))
    nodenum = len(Check_solved.mblist)
    print(f"{count}/{nodenum} {count/nodenum*100:.2f}%")
    return count == nodenum, incorrectlist

Check_solved.is_strongly_solved = is_strongly_solved

修正箇所

@staticmethod
def is_strongly_solved(ai):
    count = 0
+   incorrectlist = []
    for mb in tqdm(Check_solved.mblist):
        candidate = set(ai(mb, candidate=True))
        bestmoves = set(Check_solved.bestmoves[tuple(mb.records)])
        if candidate <= bestmoves:
            count += 1
+       else
+           incorrectlist.append((mb, candidate, bestmoves))
    nodenum = len(Check_solved.mblist)
    print(f"{count}/{nodenum} {count/nodenum*100:.2f}%")
-   return count == nodenum
+   return count == nodenum, incorrectlist

Check_solved.is_strongly_solved = is_strongly_solved

最善手を着手しない局面の表示

上記の修正後に、下記のプログラムで ai14 を is_strongly_solved で判定し、その結果を result と incorrectlist に代入します。

result, incorrectlist = Check_solved.is_strongly_solved(ai14s)

実行結果

100%|██████████| 294778/294778 [00:50<00:00, 5833.35it/s]
294690/294778 99.97%

incorrectlist には 88 個の要素があり、それらをすべて表示すると実行結果の表示が長くなるので、下記のプログラムのように、最初の要素のみを表示 してみることにします。

mb, candidate, bestmoves = incorrectlist[0]
print(mb)
print("candidate", candidate)
print("bestmoves", bestmoves)

実行結果

Turn o
o.X
...
...

candidate {(1, 1)}
bestmoves {(0, 1), (0, 2), (2, 2)}

下記のプログラムで表示すればよいと思った人がいるかもしれませんが、実行結果のようにゲーム盤がクラスの情報として表示されてしまいます。

print(incorrectlist[0])

実行結果

(<marubatsu.Marubatsu object at 0x0000020B2AE5D0D0>, {(1, 1)}, {(0, 1), (0, 2), (2, 2)})

最善手を着手しない局面の検証

上記の結果から、ai14s は、下記の局面では (1, 1) のみを着手しますが、確かにその着手は最善手の一覧である (0, 1), (0, 2), (2, 2) には入っていません。

Turn o
o.X
...
...

直観的には真ん中の (1, 1) のマスは有利になるマスなので、(1, 1) が最善手ではないといわれても納得できない人がいるかもしれません。そこで、念のため (1, 1) が本当に 最善手ではないことを検証 してみることにします。

(1, 1) に 〇 が着手を行うと下記の局面になります。この局面では、(2, 2) に 〇 が着手を行うと 〇 が勝利するので、× は (2, 2) に着手を行う必要があります。

Turn x
o.x
.O.
...

(2, 2) に × が着手を行うと下記の局面になります。この局面では、(2, 1) に × が着手を行うと × が勝利するので、〇 は (2, 1) に着手を行う必要があります。

Turn o
o.x
.o.
..X

(2, 1) に 〇 が着手を行うと下記の局面になります。この局面では、(0, 1) に 〇 が着手を行うと 〇 が勝利するので、× は (0, 1) に着手を行う必要があります。

Turn x
o.x
.oO
..x

(0, 1) に × が着手を行うと下記の局面になります。長くなるので省略しますが、この局面から 〇 がどこに着手を行っても × が最善手を着手すると引き分けになります。特に難しくはないと思いますので、実際に確認してみて下さい。

Turn o
o.x
Xoo
..x

次に、最善手の一覧の中の (0, 1) が最善手であることを実証してみることにします。

(0, 1) に 〇 が着手を行うと下記の局面になります。この局面では、(0, 2) に 〇 が着手を行うと 〇 が勝利するので、× は (0, 2) に着手を行う必要があります。

Turn x
o.x
O..
...

(0, 2) に × が着手を行うと下記の局面になります。この局面では、(1, 1) に × が着手を行うと × が勝利するので、〇 は (1, 1) に着手を行う必要があります。

Turn o
o.x
o..
X..

(1, 1) に 〇 が着手を行うと下記の局面になります。この局面では、(2, 1) と (2, 2) のどちらかに 〇 が着手を行うと 〇 が勝利しますが、× がその両方を阻止することはできないので、この時点で 〇 の勝利が確定します

Turn X
o.x
oO.
x..

上記から この局面は必勝の局面 であることがわかりますが、(1, 1) の着手を行うと引き分けになるので、この局面で ai14s は最善手を選択しない ことが確認できました。

ai14s が弱解決の AI でなくなるかどうかの検証

ai14s は強解決の AI ではないことが確認できましたが、最善手を選択しない局面があっても、弱解決の AI ではないとは限りません。その理由は、弱解決の AI は、その AI がゲーム開始時の局面から着手を行った際に 出現しない局面 に対しては 最善手を選択する必要がない からです。

そこで、先程の局面が、ai14s ががゲーム開始時の局面から着手を行った際に 出現しない局面であるか どうかを検証することにします。

下記のプログラムで ai14s がゲーム開始時の局面で行う着手の一覧 を表示すると、実行結果に [(1, 1)] が表示されることから、必ず (1, 1) に着手を行います。

from marubatsu import Marubatsu

mb = Marubatsu()
ai14s(mb, candidate=True)

実行結果

[(1, 1)]

先程検証した最善手以外の着手を選択する可能性がある下記の局面では、〇 の 2 手目の手番 で、〇 が (1, 1) 以外のマスに着手されている ので、この局面は ai14s が 〇 を担当した場合に 出現することはありません。従って、この局面で ai14s が最善手を選択していなくても弱解決の AI であることに影響はありません。

Turn o
o.X
...
...

他の最善手以外の着手を選択する可能性がある局面に対するチェックは大変なので行いませんが、ランダムな着手を行う ai2s との対戦で ai14s は敗北しないので、ai14s が弱解決の AI である可能性は高いでしょう。

board 属性による最善手の対応表

以前の記事では、局面のデータからゲーム木のノードを探すために、棋譜を表す records 属性 を使って 局面を表すデータを表現 しました。また、以前の記事でゲーム木には 549946 個のノードがあることがわかっているので、局面を表すデータは 50 万以上ある事になります。

一方、〇× ゲームではゲーム盤の状況を表す board 属性の値が同じであれば、その局面に至るまでの棋譜に関わらず 最善手は同じになる ので、最善手を計算するだけであれば、ゲーム盤の状況を表す board 属性のデータを使って局面のデータを表現してもかまいません。

また、ゲーム開始時の局面から (0, 0)、(1, 1)、(2, 2) の順で着手が行われた場合と、(2, 2)、(1, 1)、(0, 0) の順で着手が行われた場合のように、棋譜が異なっていても board 属性の値が同じになる局面が多数存在する ため、board 属性の種類は 549946 よりは少なくなります。そのため、board 属性の値をキーとした局面と最善手の対応表は、棋譜を表す records 属性の値をキーとした局面と最善手の対応表よりも データサイズを小さくすることができます。

そこで、board 属性の値をキーとした局面と最善手の対応表を作成することにします。

board 属性のハッシュ可能なデータへの変換

board 属性の値は、下記のプログラムの実行結果のように、list を入れ子にしたデータ です。list はハッシュ可能なデータではない ので、このままでは dict のキーとして利用することはできません。そのため、board 属性の値を以前の記事で records 属性の値に対して行ったように、ハッシュ可能なデータに変換する必要があります。

print(mb.board)

実行結果

[['.', '.', '.'], ['.', '.', '.'], ['.', '.', '.']]

その際に、下記のプログラムのように、records 属性を変換した場合と同じ方法で組み込み関数 tuple を使って変換を行うと、実行結果のように、変換された tuple の要素は list のままになる のでハッシュ可能なデータにはなりません。

print(tuple(mb.board))

実行結果

(['.', '.', '.'], ['.', '.', '.'], ['.', '.', '.'])

board 属性の文字列への変換

このような場合は、list の要素も tuple に変換するプログラムを記述する必要がありますが、そのようなプログラムを記述するのは少々面倒です。別の方法として、board 属性のように、要素がすべて文字列データの場合 は、全ての要素を連結 することで、ハッシュ可能なデータである 文字列型のデータに変換する という方法があります。例えば、上記のデータの場合は、下記のような 9 文字の文字列型のデータに変換します。

.........

このような変換を行う場合は list の 全ての要素 が 同じ長さの文字列である必要 があります。異なる長さの文字列の場合は、下記のように間に "," 等の記号を挟んで結合しなければ、どこで区切ればよいかがわからなくなるためです

.,.,.,.,.,.,.,.,.

詳細は省略しますが、board 属性の値を文字列型のデータに変換したほうが、tuple に変換した場合よりも データのサイズが小さくなるという利点があります。

list の要素の連結は、以前の記事で説明した、文字列型のデータの join メソッドを使って行うことができます。以前の記事では、下記のプログラムのように、list の要素に文字列が代入されていた場合の連結を行いましたが、board 属性では list の要素に list が入れ子で代入されているので下記のプログラムではうまく変換できません。

coords = ['A1', 'A2', 'B1', 'B2', 'C1']
print("".join(coords))

実行結果

A1A2B1B2C1

board 属性の場合は、下記のプログラムのように、list の要素を順番に連結 して文字列に変換してから、+ 演算子を使って結合 を行う必要があります。実行結果のように、正しく連結が行われていることが確認できます。

• 1 行目：連結した文字列を計算する txt を空文字で初期化する
• 2 行目：board 属性から各列（column）のデータを表す要素を順番に取り出す繰り返し処理を行う
• 3 行目：列のデータは文字列を要素とする list なので、join を使って要素を連結することができ、連結した文字列を + 演算子で txt に結合する

1  txt = ""
2  for col in mb.board:
3      txt += "".join(col)
4  print(txt)

行番号のないプログラム

txt = ""
for col in mb.board:
    txt += "".join(col)
print(txt)

実行結果

.........

なお、変換された文字列は、ゲーム盤のマスを表す文字を、左上の (0, 0) のマスから 縦方向の列ごとに文字列に変換 します。従って、上記の実行結果の文字列は、先頭の文字から (0, 0)、(0, 1)、(0, 2)、(1, 0)、(1, 1)・・・の順でゲーム盤のマスを表します。

わかりづらくなるので本記事では採用しませんが、下記のプログラムのように、list 内包表記を使って、1 行で上記の処理を記述することもできます。

txt = "".join(["".join(col) for col in mb.board])
print(txt)

実行結果

.........

上記のプログラムでは、下記のプログラムのように list 内包表記を使って、list の各要素を連結した新しい list を作成し、その list に対して連結を行っています。

print(["".join(col) for col in mb.board])

実行結果

['...', '...', '...']

こちらの方が良いと思った人は採用して下さい。

board を文字列に変換するメソッドの定義

上記の処理を毎回記述するのは面倒なので、Marubatsu クラスに下記のようなメソッドを定義する事にします。

名前：borad 属性を文字列（string）型のデータに変換するので board_to_str と命名する
処理：board 属性の要素を連結した文字列を作成する
入力：なし
出力：board 属性の要素を連結した文字列

下記は、board_to_str メソッドの定義です。先ほど説明した処理を行っているだけなので、特に難しい点はないと思いますので説明は省略します。

def board_to_str(self):
    txt = ""
    for col in self.board:
        txt += "".join(col)
    return txt

Marubatsu.board_to_str = board_to_str

下記のプログラムで、いくつかの局面で board_to_str 属性を呼び出したものです。実行結果から正しく動作しすることが確認できます。

print(mb.board_to_str())
mb.move(0, 0)
print(mb.board_to_str())
mb.move(1, 0)
print(mb.board_to_str())
mb.move(0, 2)
print(mb.board_to_str())
mb.move(2, 2)
print(mb.board_to_str())

実行結果

.........
o........
o..x.....
o.ox.....
o.ox....x

board 属性を利用した局面と最善手の対応表の作成

board 属性を利用した局面と最善手の対応表は下記のアルゴリズムで作成できます。

• 対応表を表すデータを空の dict で初期化する
• ゲーム木の全てのノードの局面に対して下記の処理を行う
• その局面を文字列に変換したデータが、dict のキーに存在していなければ、その局面の 最善手を対応表に登録する。dict のキーに存在している場合は登録済なので何もしない

下記は対応表を作成するプログラムです。なお、対応表を代入する変数の名前は bestmoves_by_board としました。

• 3 行目：ゲーム木のデータをファイルから読み込む
• 4 行目：best_moves_by_board を空の dict で初期化する
• 5 行目：すべてのゲーム木のノードに対する繰り返し処理を行う
• 6 行目：局面の board 属性を文字列に変換して txt に代入する
• 7 行目：best_moves_by_board のキーに txt が存在しないことを判定する
• 8 行目：存在しない場合は、txt のキーの値にそのノードの最善手の一覧を代入する

1  from tree import Mbtree
2
3  mbtree = Mbtree.load("../data/aidata")
4  bestmoves_by_board = {}
5  for node in mbtree.nodelist:
6      txt = node.mb.board_to_str()
7      if not txt in bestmoves_by_board.keys():
8          bestmoves_by_board[txt] = node.bestmoves

行番号のないプログラム

from tree import Mbtree

mbtree = Mbtree.load("../data/aidata")
bestmoves_by_board = {}
for node in tqdm(mbtree.nodelist):
    txt = node.mb.board_to_str()
    if not txt in bestmoves_by_board.keys():
        bestmoves_by_board[txt] = node.bestmoves

上記のプログラムを実行後に、下記のプログラムを実行して bestmoves_by_board の要素の数を表示すると、実行結果から〇×ゲームの ゲーム盤の種類は 5478 種類 であることがわかります。これは、ゲーム木のノードの数の約 1/100 です。

len(bestmoves_by_board)

実行結果

5478

bestmoves_by_board は今後も利用するので、下記のプログラムでファイルに保存します。

import pickle
import gzip
with gzip.open("../data/bestmoves_by_board.dat", "wb") as f:
    pickle.dump(bestmoves_by_board, f)

作成した bestmoves_by_board.dat のファイルサイズは 約 20 KB でした。これは、bestmoves.dat の約 2800 KB と比較して 1/100 以下 なので、実際に 大幅にデータの量が減っている ことが確認できました。

bestmoves_by_board を利用した AI の定義

この bestmoves_by_board を使って下記のプログラムのように gt_ai6 という強解決の AI を定義することができます。ai_gt5との違いは、仮引数の名前と、dict のキーに mb.board_to_str() を記述する点です。

また、この後で is_strongly_solved を利用して ai_gt6 が強解決の AI であるかどうかを検証するので、仮引数 candidate を追加 しました。

• 3 行目：デフォルト値を False とする仮引数 candidate を追加する
• 4、5 行目：candidate が False の場合は最善手の一覧を返す
• 6、7 行目：candidate が False の場合は最善手の中からランダムに選んだ着手を返す

1  from random import choice
2
3  def ai_gt6(mb, bestmoves_by_board, candidate=False):
4      if candidate:
5          return bestmoves_by_board[mb.board_to_str()]
6      else:
7          return choice(bestmoves_by_board[mb.board_to_str()])

修正箇所

from random import choice

def ai_gt6(mb, bestmoves_by_board, candidate=False):
    if candidate:
        return bestmoves_by_board[mb.board_to_str()]
    else:
        return choice(bestmoves_by_board[mb.board_to_str()])

ai_gt5からの修正箇所

from random import choice

-def ai_gt5(mb, bestmoves):
+def ai_gt6(mb, bestmoves_by_board, candidate=False):
-   return choice(bestmoves[tuple(mb.records)])
+   if candidate:
+       return bestmoves_by_board[mb.board_to_str()]
+   else:
+       return choice(bestmoves_by_board[mb.board_to_str()])

上記のプログラムを実行後に、下記のプログラムで ai_match を使って ai2s と対戦を行うと、実行結果のように ai_gt5 VS ai2s とほぼ同じ通算成績になることが確認できます。

from ai import ai2s, ai_match

ai_match(ai=[ai_gt6, ai2s], params=[{"bestmoves_by_board": bestmoves_by_board}, {}])

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

ai_gt6 VS ai2s
100%|██████████| 10000/10000 [00:30<00:00, 322.85it/s]
count     win    lose    draw
o        9683       0     317
x        7780       0    2220
total   17463       0    2537

ratio     win    lose    draw
o       96.8%    0.0%    3.2%
x       77.8%    0.0%   22.2%
total   87.3%    0.0%   12.7%

次に、is_strongly_solved を利用して ai_gt6 が強解決の AI であることを確認したいのですが、is_strongly_solved は、ai_gt6s のような mb 以外の仮引数を必要とする AI の関数には対応していない ので修正する必要があります。

Check_solved クラスの修正と改良

上記で説明した修正以外にも、Check_solved クラスには改良の余地があるのでそれらを順番に修正することにします。

is_strongly_solved メソッドの修正

まず、is_strongly_solved メソッドが ai_gt6 を検証できるようにするために、下記のプログラムのように仮引数 params を追加します。

• 2 行目：デフォルト値を None とする仮引数 params を追加する
• 3、4 行目：params が None の場合に params に空の dict を代入する
• 8 行目：ai の実引数に **params を追加する

 1  @staticmethod
 2  def is_strongly_solved(ai, params=None):
 3      if params is None:
 4          params = {}
 5      count = 0
 6      incorrectlist = []
 7      for mb in tqdm(Check_solved.mblist):
 8          candidate = set(ai(mb, candidate=True, **params))
 9          bestmoves = set(Check_solved.bestmoves[tuple(mb.records)])
10          if candidate <= bestmoves:
11              count += 1
12          else:
13              incorrectlist.append((mb, candidate, bestmoves))
14      nodenum = len(Check_solved.mblist)
15      print(f"{count}/{nodenum} {count/nodenum*100:.2f}%")
16      return count == nodenum, incorrectlist
17    
18  Check_solved.is_strongly_solved = is_strongly_solved

行番号のないプログラム

@staticmethod
def is_strongly_solved(ai, params=None):
    if params is None:
        params = {}
    count = 0
    incorrectlist = []
    for mb in tqdm(Check_solved.mblist):
        candidate = set(ai(mb, candidate=True, **params))
        bestmoves = set(Check_solved.bestmoves[tuple(mb.records)])
        if candidate <= bestmoves:
            count += 1
        else:
            incorrectlist.append((mb, candidate, bestmoves))
    nodenum = len(Check_solved.mblist)
    print(f"{count}/{nodenum} {count/nodenum*100:.2f}%")
    return count == nodenum, incorrectlist
    
Check_solved.is_strongly_solved = is_strongly_solved

修正箇所

@staticmethod
-def is_strongly_solved(ai):
+def is_strongly_solved(ai, params=None):
+   if params is None:
+       params = {}
    count = 0
    incorrectlist = []
    for mb in tqdm(Check_solved.mblist):
-       candidate = set(ai(mb, candidate=True))
+       candidate = set(ai(mb, candidate=True, **params))
        bestmoves = set(Check_solved.bestmoves[tuple(mb.records)])
        if candidate <= bestmoves:
            count += 1
        else:
            incorrectlist.append((mb, candidate, bestmoves))
    nodenum = len(Check_solved.mblist)
    print(f"{count}/{nodenum} {count/nodenum*100:.2f}%")
    return count == nodenum, incorrectlist
    
Check_solved.is_strongly_solved = is_strongly_solved

上記の修正後に下記のプログラムで、ai_gt6 が強解決の AI であることを検証すると、実行結果のように強解決の AI であることが確認できます。なお、1 行でプログラムを記述すると長くなるので 2 行に分けてプログラムを記述しました。また、incorrectlist の値は強解決の AI であることを検証するだけであれば必要がないので表示していません。

params = {"bestmoves_by_board": bestmoves_by_board}
result, incorrectlist = Check_solved.is_strongly_solved(ai_gt6, params=params)
print(result)

実行結果

100%|██████████| 294778/294778 [00:01<00:00, 270543.00it/s]
294778/294778 100.00%
True

bestmoves_by_board を利用した判定

is_strongly_solved では、強解決の AI であることを判定する際に、決着がついた局面を除いた 294778 個¹のゲーム木のノードに対して処理を行っていましたが、この中には 大量の同じ board 属性を持つ局面が存在する のでかなり 無駄な処理 を行っています。

mblist_by_board の計算と保存

そこで、board 属性が異なる局面 を集めた mblist_by_board を作成し、それと先程作成した bestmoves_by_board を使って判定を行うように修正することにします。

mblist_by_board は、bestmoves_by_board を計算する際に、下記のプログラムで計算できます。なお、下記のプログラムでは、bestmoves_by_board を改めて計算し直していますが、これは mblist_by_board を計算する際に必要となる からです。

• 2 行目：mblist_by_board を空の list で初期化する
• 7、8 行目：txt が bestmoves_by_board のキーに存在せず、ゲーム中の局面の場合に、mblist_by_board の要素に mb を追加する

1  bestmoves_by_board = {}
2  mblist_by_board = []
3  for node in mbtree.nodelist:
4      txt = node.mb.board_to_str()
5      if not txt in bestmoves_by_board.keys():
6          bestmoves_by_board[txt] = node.bestmoves
7          if node.mb.status == Marubatsu.PLAYING:
8              mblist_by_board.append(mb)

行番号のないプログラム

bestmoves_by_board = {}
mblist_by_board = []
for node in mbtree.nodelist:
    txt = node.mb.board_to_str()
    if not txt in bestmoves_by_board.keys():
        bestmoves_by_board[txt] = node.bestmoves
        if node.mb.status == Marubatsu.PLAYING:
            mblist_by_board.append(node.mb)

修正箇所

bestmoves_by_board = {}
+mblist_by_board = []
for node in mbtree.nodelist:
    txt = node.mb.board_to_str()
    if not txt in bestmoves_by_board.keys():
        bestmoves_by_board[txt] = node.bestmoves
+       if node.mb.status == Marubatsu.PLAYING:
+           mblist_by_board.append(node.mb)

上記のプログラムを実行後に、下記のプログラムを実行して mblist_by_board の要素の数を表示すると、実行結果から〇×ゲームのゲーム盤のうち、決着がついていない局面の種類は 4520 種類である ことがわかります。

len(mblist_by_board)

実行結果

4520

mblist_by_board は今後も利用するので、下記のプログラムでファイルに保存します。

with gzip.open("../data/mblist_by_board.dat", "wb") as f:
    pickle.dump(mblist_by_board, f)

mblist_by_board.dat のファイルサイズは 38 KB で、mblist.dat の 約 2300 KB と比較して 大幅に小さくなる ことが確認できます。

Check_solved クラスの修正

次に、下記のプログラムのように Check_solved が今回の記事で保存したデータを利用するように修正します。

• 2 行目：クラス属性の名前を bestmoves_by_board にし、bestmoves_by_board.dat からデータを読み込むように修正する
• 3 行目：クラス属性の名前を mblist_by_board にし、mblist_by_board.dat からデータを読み込むように修正する
• 11、18 行目：mblist を mblist_by_board に修正する
• 13 行目：bestmoves を bestmoves_by_board に修正し、キーに board_to_str メソッドで計算した文字列を記述するように修正する

 1  class Check_solved:
 2      bestmoves_by_board = load_bestmoves("../data/bestmoves_by_board.dat")
 3      mblist_by_board = load_mblist("../data/mblist_by_board.dat")
 4   
 5      @staticmethod
 6      def is_strongly_solved(ai, params=None):
 7          if params is None:
 8              params = {}
 9          count = 0
10          incorrectlist = []
11          for mb in tqdm(Check_solved.mblist_by_board):
12              candidate = set(ai(mb, candidate=True, **params))
13              bestmoves = set(Check_solved.bestmoves_by_board[mb.board_to_str()])
14              if candidate <= bestmoves:
15                  count += 1
16              else:
17                  incorrectlist.append((mb, candidate, bestmoves))
18          nodenum = len(Check_solved.mblist_by_board)
19          print(f"{count}/{nodenum} {count/nodenum*100:.2f}%")
20          return count == nodenum, incorrectlist

行番号のないプログラム

class Check_solved:
    bestmoves_by_board = load_bestmoves("../data/bestmoves_by_board.dat")
    mblist_by_board = load_mblist("../data/mblist_by_board.dat")
    
    @staticmethod
    def is_strongly_solved(ai, params=None):
        if params is None:
            params = {}
        count = 0
        incorrectlist = []
        for mb in tqdm(Check_solved.mblist_by_board):
            candidate = set(ai(mb, candidate=True, **params))
            bestmoves = set(Check_solved.bestmoves_by_board[mb.board_to_str()])
            if candidate <= bestmoves:
                count += 1
            else:
                incorrectlist.append((mb, candidate, bestmoves))
        nodenum = len(Check_solved.mblist_by_board)
        print(f"{count}/{nodenum} {count/nodenum*100:.2f}%")
        return count == nodenum, incorrectlist

修正箇所

class Check_solved:
-   bestmoves = load_bestmoves()
+   bestmoves_by_board = load_bestmoves("../data/bestmoves_by_board.dat")
-   mblist = load_mblist()
+   mblist_by_board = load_mblist("../data/mblist_by_board.dat")
    
    @staticmethod
    def is_strongly_solved(ai, params=None):
        if params is None:
            params = {}
        count = 0
        incorrectlist = []
-       for mb in tqdm(Check_solved.mblist):
+       for mb in tqdm(Check_solved.mblist_by_board):
            candidate = set(ai(mb, candidate=True, **params))
-           bestmoves = set(Check_solved.bestmoves[tuple(mb.records)])
+           bestmoves = set(Check_solved.bestmoves_by_board[mb.board_to_str()])
            if candidate <= bestmoves:
                count += 1
            else:
                incorrectlist.append((mb, candidate, bestmoves))
-       nodenum = len(Check_solved.mblist)
+       nodenum = len(Check_solved.mblist_by_board)
        print(f"{count}/{nodenum} {count/nodenum*100:.2f}%")
        return count == nodenum, incorrectlist

上記の修正後に、下記のプログラムで ai14s が強解決の AI であるかを判定します。実行結果から、ai14s は強解決の AI ではなく、4520 - 4468 = 52 種類の局面で最善手を選択しない ことが確認できました。また、修正前は同じ処理に 50 秒かかった のに対し、調べる局面の数が大幅に減ったことで 1 秒で処理が終了 していることも確認できます。

result, incorrectlist = Check_solved.is_strongly_solved(ai14s)
print(result)

実行結果

100%|██████████| 4520/4520 [00:01<00:00, 2639.10it/s]
4468/4520 98.85%
False

次に、下記のプログラムで ai_gt6 が強解決の AI であるかを判定します。実行結果から、ai_gt6 は強解決の AI である事が確認できました。なお、こちらは修正前でも 1 秒で処理が完了していたので、処理速度の差はほとんど感じられないかもしれませんが、下記では 0 秒と表示され、これはおそらく四捨五入した秒数なのでこちらも 処理速度が速くなっていることが確認できます。

params = {"bestmoves_by_board": bestmoves_by_board}
result, incorrectlist = Check_solved.is_strongly_solved(ai_gt6, params=params)
print(result)

実行結果

100%|██████████| 4520/4520 [00:00<00:00, 107608.52it/s]
4520/4520 100.00%
True

Check_solved の問題点と修正

Check_solved には以下のような問題点があります。

• Check_solved の定義を実行した際に ファイルからデータを読み込む
• Check_solved は util.py に記述されているので、util.py に記述されている 他の gui_play などの関数をインポートした際 にも、Check_solved は実行されてしまい、ファイルが読み込まれてしまう
• そのため、例えば gui_play をインポートした後で、Check_solved を利用しないような場合でも、利用しないファイルの読み込みが行われる せいで 無駄な待ち時間が生じる

このような問題を解決するアルゴリズムを下記に示します。

• ファイルから読み込んだデータを代入するクラス属性は None で初期化 する
• ファイルのデータが実際に必要になる is_strongly_solved を実行した際に、対応するクラス属性の値が None の場合にファイルからデータを読み込み、クラス属性に代入 する
• クラス属性の値が None でない場合は、そのクラス属性に必要なデータが代入されているのでそれを利用する

上記のアルゴリズムで、クラスの定義を実行した際にファイルを読み込まず、必要になった時点 でファイルを 一度だけ読み込む ようにすることができます。

下記は、そのように Check_solved を修正したプログラムです。

• 2、3 行目：クラス属性を None で初期化する
• 7 ~ 10 行目：クラス属性の値が None の場合にファイルからデータを読み込んでそのクラス属性に代入する

 1  class Check_solved:
 2      bestmoves_by_board = None
 3      mblist_by_board = None
 4   
 5      @staticmethod
 6      def is_strongly_solved(ai, params=None):
 7          if Check_solved.bestmoves_by_board is None:
 8              Check_solved.bestmoves_by_board = load_bestmoves ("../data/bestmoves_by_board.dat")
 9          if Check_solved.mblist_by_board is None:
10              Check_solved.mblist_by_board = load_mblist("../data/mblist_by_board.dat")            
11          if params is None:
12              params = {}
元と同じなので省略

行番号のないプログラム

class Check_solved:
    bestmoves_by_board = None
    mblist_by_board = None
    
    @staticmethod
    def is_strongly_solved(ai, params=None):
        if Check_solved.bestmoves_by_board is None:
            Check_solved.bestmoves_by_board = load_bestmoves ("../data/bestmoves_by_board.dat")
        if Check_solved.mblist_by_board is None:
            Check_solved.mblist_by_board = load_mblist("../data/mblist_by_board.dat")            
        if params is None:
            params = {}
        count = 0
        incorrectlist = []
        for mb in tqdm(Check_solved.mblist_by_board):
            candidate = set(ai(mb, candidate=True, **params))
            bestmoves = set(Check_solved.bestmoves_by_board[mb.board_to_str()])
            if candidate <= bestmoves:
                count += 1
            else:
                incorrectlist.append((mb, candidate, bestmoves))
        nodenum = len(Check_solved.mblist_by_board)
        print(f"{count}/{nodenum} {count/nodenum*100:.2f}%")
        return count == nodenum, incorrectlist

修正箇所

class Check_solved:
-   bestmoves_by_board = load_bestmoves("../data/bestmoves_by_board.dat")
+   bestmoves_by_board = None
-   mblist_by_board = load_mblist("../data/mblist_by_board.dat")
+   mblist_by_board = None
    
    @staticmethod
    def is_strongly_solved(ai, params=None):
+       if Check_solved.bestmoves_by_board is None:
+           Check_solved.bestmoves_by_board = load_bestmoves ("../data/bestmoves_by_board.dat")
+       if Check_solved.mblist_by_board is None:
+           Check_solved.mblist_by_board = load_mblist("../data/mblist_by_board.dat")            
        if params is None:
            params = {}
元と同じなので省略

上記の修正後に、下記のプログラムで ai14s と ai_gt6 が強解決の AI であるかを判定することで、実行結果から修正したプログラムが正しく動作することを確認できます。

result, incorrectlist = Check_solved.is_strongly_solved(ai14s)
print(result)
params = {"bestmoves_by_board": bestmoves_by_board}
result, incorrectlist = Check_solved.is_strongly_solved(ai_gt6, params=params)
print(result)

実行結果

100%|██████████| 4520/4520 [00:01<00:00, 2644.79it/s]
4468/4520 98.85%
False
100%|██████████| 4520/4520 [00:00<00:00, 110638.59it/s]
4520/4520 100.00%
True

今回の記事のまとめ

今回の記事では、前回の記事のバグの原因と、数値と set で <= と > 演算子が 行う処理が異なる ことを説明しました。

また、board 属性を利用して最善手の対応表を作成する ことで、データを保存する ファイルのサイズが大幅に小さくなり、強解決の AI であるかを判定する 処理時間を大幅に減らす ことができることを説明しました。

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

今回の記事で定義した load_bestmoves、load_mblist、Check_solved クラスは util.py に保存することにします。

リンク	説明
marubatsu.ipynb	本記事で入力して実行した JupyterLab のファイル
marubatsu_new.py	今回の記事で更新した marubatsu.py
ai_new.py	今回の記事で更新した ai.py
util_new.py	今回の記事で更新した util.py
bestmoves_by_board.dat	board 属性を利用した局面と最善手の一覧の対応表保存するファイル
mblist_by_board.dat	board 属性を利用した決着がついていない局面の一覧を保存するファイル

次回の記事

1. この数字は、実行結果の is_strongly_solved の実行結果の「294778/294778」確認できます ↩