Pythonで〇×ゲームのAIを一から作成する その109 強解決の AI であるかの判定

目次と前回の記事

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

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

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

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

データファイルの保存場所の変更

これまでの記事では、データが保存された aidata.mbtree や bestmoves.dat などのファイルを marubatsu.ipynb と同じフォルダに保存 していましたが、記事が変わるたびにそれらのファイルを記事に対応するフォルダにコピーするのは、ディスク容量の無駄遣い になります。

そこで、今回の記事から、記事を保存するフォルダの 親フォルダに data という名前のフォルダを作成 し、その中にデータファイルを保存する ことにします。

下記は github のその data フォルダのリンクです。

相対パスの記述方法

これまでは、ファイルを開く際に aidata.mbtree のように、 ファイル名だけ の ファイルのパス（住所のこと）を記述 してきましたが、そのようなファイルの記述の方法を 相対パス と呼びます。相対パスでは、実行する python のファイル（本記事の場合は marubatsu.ipynb のことです）を 基準 として、相対的にファイルがどこにあるかを示す 方法で、ファイル名だけを記述した場合は、同じフォルダ内のファイルを示すことになります。

相対パスでは、別のフォルダ を下記のように記述します。

• フォルダ名/ と記述することで、記述した フォルダ名のフォルダ を表す
• ../ と記述することで 親フォルダ を表す

先程 aidata.mbtree などのデータファイルを、marubatsu.ipynb が保存されているフォルダから見て、親フォルダ の中の data フォルダの中に保存することにしたので、aidata.mbtree の 相対パス は ../data/aidata.mbtree と記述します。

ハードディスクを表す C ドライブから順に辿ってファイルのパスを記述する方法を 絶対パス と呼びます。エラーメッセージなどで表示される下記の c:\Users\ys\ai\marubatsu\107\ai.py が絶対パスで、下記の場合は、C ドライブから順に Uses、ys、ai、marubatsu、107 の順で開いたフォルダ内の ai.py という意味を表します。基準となるフォルダが変わると表記が変化する相対パスと異なり、絶対パス は同じファイルは 常に同じパスで記述される という特徴があります。

File c:\Users\ys\ai\marubatsu\107\ai.py:47, in ai_match(ai, params, match_num)

ルールベースの AI が強解決であるかどうかの検証

前回までの記事で、〇×ゲームの 全ての局面に対する最善手の一覧を計算 しました。そのようなデータがあれば、以下のようなアルゴリズムで、任意の AI が強解決の AI であるか どうかを 判定 することができます。

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

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

なお、強解決の AI は、全ての局面で いずれかの最善手を選択できれば良い ので、手順 2 では AI が着手する可能性のある合法手の一覧と、その局面の最善手の一覧が 完全に一致する必要はありません。

以前の記事で作成したルールベースの AI である ai14s は、ランダムな AI である ai2s との対戦による検証 を行った結果、弱解決の性質を持つ可能性が高い ことを以前の記事で確認しましたが、本当に弱解決の AI であるかどうかの証明まではできませんでした。

また、弱解決の AI は、その AI がゲーム開始時の局面から着手を行った際に 出現しない局面 に対しては 最善手を選択するとは限らない という点が 強解決の AI と異なります。ランダムな AI との対戦による検証では、それらの出現しない局面に対して最善手を着手するかどうかの検証を行うことはできなかったので、もしかるすると ai14s が強解決の AI である という 可能性があります。

そこで、上記のアルゴリズムを利用して ai14s が強解決の AI であるかどうかを検証することにします。

AI の関数の修正

上記のアルゴリズムの手順 1 を行うためには、AI の関数が その局面で選択する可能性がある着手の一覧を返す ことができるようにする必要があります。最初に評価値を利用した AI の中で最も単純なランダムな着手を選択する ai2s に対して修正を行い、その後で ai14s の修正を行うことにします。

下記は ai2s の定義です。ai2 では、局面の評価値を計算する eval_func を、常に 0 を返すように定義する事で、全ての合法手の局面の評価値が同じ 0 になるため、ランダムな着手が選択されます。

def ai2s(mb, debug=False):
    def eval_func(mb):
        return 0
        
    return ai_by_score(mb, eval_func, debug=debug)

また、この関数の返り値は、ai_by_score の返り値 になっているので、下記に ai_by_score の定義の中で、返り値を返す処理 の部分を抜粋します。

def ai_by_score(mb_orig, eval_func, debug=False, rand=True):
省略
    if rand:   
        return choice(best_moves)
    else:
        return best_moves[0]

上記から、ai_by_score は、仮引数 rand に True が代入されている場合は、最善手の一覧が代入されている best_moves の中からランダムに 1 つを選択して返し、False が代入されている場合は、best_moves の最初の要素を返すように定義されていることがわかります。

ai_by_score が計算した その AI にとっての最善手の一覧¹は best_moves に代入されているので、ai_by_score が best_moves をそのまま返す ことができるように修正することで、AI がその局面で選択する可能性がある着手の一覧を返すことができるようになります。

ai_by_score の修正

そこで、下記のプログラムのように、ai_by_score に True が代入されていた場合は 着手の候補（candidate） を返すという意味を持つ、仮引数 candidate を追加 することにします。

• 5 行目：互換性を考慮して、デフォルト値を False とした仮引数 candidate を追加する
• 6、7 行目：candidate が True の場合に best_moves を返すようにする

 1  from ai import dprint
 2  from copy import deepcopy
 3  from random import choice
 4
 5  def ai_by_score(mb_orig, eval_func, debug=False, rand=True, candidate=False):  
元と同じなので省略
 6      if candidate:
 7          return best_moves
 8      elif rand:   
 9          return choice(best_moves)
10      else:
11          return best_moves[0]

行番号のないプログラム

from ai import dprint
from copy import deepcopy
from random import choice

def ai_by_score(mb_orig, eval_func, debug=False, rand=True, candidate=False):   
    dprint(debug, "Start ai_by_score")
    dprint(debug, mb_orig)
    legal_moves = mb_orig.calc_legal_moves()
    dprint(debug, "legal_moves", legal_moves)
    best_score = float("-inf")
    best_moves = []
    for move in legal_moves:
        dprint(debug, "=" * 20)
        dprint(debug, "move", move)
        mb = deepcopy(mb_orig)
        x, y = move
        mb.move(x, y)
        dprint(debug, mb)
        
        score = eval_func(mb)
        dprint(debug, "score", score, "best score", best_score)
        
        if best_score < score:
            best_score = score
            best_moves = [move]
            dprint(debug, "UPDATE")
            dprint(debug, "  best score", best_score)
            dprint(debug, "  best moves", best_moves)
        elif best_score == score:
            best_moves.append(move)
            dprint(debug, "APPEND")
            dprint(debug, "  best moves", best_moves)

    dprint(debug, "=" * 20)
    dprint(debug, "Finished")
    dprint(debug, "best score", best_score)
    dprint(debug, "best moves", best_moves)
    if candidate:
        return best_moves
    elif rand:   
        return choice(best_moves)
    else:
        return best_moves[0]

修正箇所

from ai import dprint
from copy import deepcopy
from random import choice

-def ai_by_score(mb_orig, eval_func, debug=False, rand=True):  
+def ai_by_score(mb_orig, eval_func, debug=False, rand=True, candidate=False):  
元と同じなので省略
+   if candidate:
+       return best_moves
+   elif rand:   
-   if rand:   
        return choice(best_moves)
    else:
        return best_moves[0]

ai2s の修正

次に、ai2s を上記の修正にあわせて下記のプログラムのように修正します。

• 1 行目：デフォルト値を False とする仮引数 candidate を追加する
• 5 行目：ai_by_score にキーワード引数 candidate=candidate を追加する

1  def ai2s(mb, debug=False, candidate=False):
2      def eval_func(mb):
3          return 0
4        
5      return ai_by_score(mb, eval_func, debug=debug, candidate=candidate)

行番号のないプログラム

def ai2s(mb, debug=False, candidate=False):
    def eval_func(mb):
        return 0
        
    return ai_by_score(mb, eval_func, debug=debug, candidate=candidate)

修正箇所

-def ai2s(mb, debug=False):
+def ai2s(mb, debug=False, candidate=False):
    def eval_func(mb):
        return 0
        
-   return ai_by_score(mb, eval_func, debug=debug)
+   return ai_by_score(mb, eval_func, debug=debug, candidate=candidate)

上記の修正後に、下記のプログラムでゲーム開始時の局面で ai2s が選択する着手の一覧を表示すると、実行結果から 9 つの全てのマスが表示されることが確認できます。

ai2s(mb, candidate=True)

実行結果

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

ai14s の修正

ai14s は ai2s と同様の方法で下記のプログラムのように修正します。

• 3 行目：デフォルト値を False とする仮引数 candidate を追加する
• 5 行目：ai_by_score にキーワード引数 candidate=candidate を追加する

1  from marubatsu import Markpat
2
3  def ai14s(mb, score_victory=300, score_sure_victory=200, score_defeat=-100, score_special=100, \
             score_201=2, score_102=0.5, score_012=-1, debug=False, candidate=False):       
元と同じなので省略
4
5      return ai_by_score(mb, eval_func, debug=debug, candidate=candidate)

行番号のないプログラム

from marubatsu import Markpat

def ai14s(mb, score_victory=300, score_sure_victory=200, score_defeat=-100, score_special=100, \
          score_201=2, score_102=0.5, score_012=-1, debug=False, candidate=False):       
    def eval_func(mb):         
        # 評価値の合計を計算する変数を 0 で初期化する
        score = 0        

        # 自分が勝利している場合
        if mb.status == mb.last_turn:
            return score_victory

        markpats = mb.count_markpats()
        if debug:
            pprint(markpats)
        # 相手が勝利できる場合は評価値を加算する
        if markpats[Markpat(last_turn=0, turn=2, empty=1)] > 0:
            score = score_defeat * markpats[Markpat(last_turn=0, turn=2, empty=1)]
        # 次の自分の手番で自分が必ず勝利できる場合
        elif markpats[Markpat(last_turn=2, turn=0, empty=1)] >= 2:
            return score_sure_victory
        
        # 斜め方向に 〇×〇 が並び、いずれかの辺の 1 つのマスのみに × が配置されている場合
        if mb.board[1][1] == Marubatsu.CROSS and \
           (mb.board[0][0] == mb.board[2][2] == Marubatsu.CIRCLE or \
            mb.board[2][0] == mb.board[0][2] == Marubatsu.CIRCLE) and \
           (mb.board[1][0] == Marubatsu.CROSS or \
            mb.board[0][1] == Marubatsu.CROSS or \
            mb.board[2][1] == Marubatsu.CROSS or \
            mb.board[1][2] == Marubatsu.CROSS) and \
           mb.move_count == 4:
            return score_special    

        # 次の自分の手番で自分が勝利できる場合は評価値に score_201 を加算する
        if markpats[Markpat(last_turn=2, turn=0, empty=1)] == 1:
            score += score_201
        # 「自 1 敵 0 空 2」1 つあたり score_102 だけ、評価値を加算する
        score += markpats[Markpat(last_turn=1, turn=0, empty=2)] * score_102
        # 「自 0 敵 1 空 2」1 つあたり score_201 だけ、評価値を減算する
        score += markpats[Markpat(last_turn=0, turn=1, empty=2)] * score_012
        
        # 計算した評価値を返す
        return score

    return ai_by_score(mb, eval_func, debug=debug, candidate=candidate)

修正箇所

from marubatsu import Markpat

-def ai14s(mb, score_victory=300, score_sure_victory=200, score_defeat=-100, score_special=100, \
-          score_201=2, score_102=0.5, score_012=-1, debug=False):       
+          score_201=2, score_102=0.5, score_012=-1, debug=False, candidate=False):       
元と同じなので省略

-   return ai_by_score(mb, eval_func, debug=debug)
+   return ai_by_score(mb, eval_func, debug=debug, candidate=candidate)

ai14s はゲーム開始時の局面では真ん中のマスにしか着手を行わないので、下記のプログラムでは (1, 1) に着手した局面に対して ai14s を実行します。その局面では 4 隅のマスが最善手であり、実行結果からその 4 隅のマスを ai14s が選択することが確認できます。

mb.move(1, 1)
ai14s(mb, candidate=True)

実行結果

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

強解決であるかを判定する関数の定義

次に、AI の関数が強解決であるかを判定する下記のような関数を定義する事にします。

名前：強解決（strongly solved）であるかを判定するので is_strongly_solved とする
処理：AI が強解決であるかどうかを判定する
入力：仮引数 ai に判定する AI の関数を代入する
出力：強解決の AI の場合は True、そうでない場合は False を返す

判定に必要となるデータの確認

強解決の AI であるかどうかを判定するためには、任意の局面に対して、下記の手順 1、2 の処理を行う必要があります。

1. その AI が着手する可能性のある合法手の一覧を計算する
2. 手順 1 で計算した合法手の一覧が、その局面の最善手の一覧に完全に含まれているかどうかを判定する

手順 1 は先ほど計算できるようにしました。また、手順 2 のその局面の最善手の一覧は、前回の記事で作成した bestmoves.dat に保存されたデータを利用することで計算できます。

load_bestmoves 関数の定義

下記は、bestmoves.dat からファイルを読み込むプログラムです。

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

毎回このようなプログラムを記述するのは面倒なので、bestmoves.dat を読み込む下記のような関数を定義する事にします。

名前：局面ごとの最善手一覧（bestmoves）が記録されたファイルを読み込むので load_bestmoves とする
処理：局面ごとの最善手一覧が記録されたファイルを読み込む
入力：読み込むファイルの名前を仮引数 fname に代入する。省略できるように、デフォルト値を先程説明した相対パスを使って ../data/bestmoves.dat とする
出力：ファイルから読み込んだデータを返り値として返す

下記は、load_bestmoves の定義です。難しい点はないと思いますので説明は省略します。

import pickle
import gzip

def load_bestmoves(fname="../data/bestmoves.dat"):
    with gzip.open(fname, "rb") as f:
        return pickle.load(f)

上記の実行後に、下記のプログラムで bestmoves に bestmoves.dat から読み込んだデータを代入します。

bestmoves = load_bestmoves()

手順 2 の処理に必要となるデータの計算

次に、手順 2 の処理の例として、ゲーム開始後に (1, 1) に着手を行った下記の局面で ai2s と ai14s に対して手順 2 の処理を行うことにします。

print(mb)

実行結果

Turn x
...
.O.
...

そのためには、この局面の最善手の一覧と、この局面で ai2s と ai14s が選択する着手の一覧を計算する必要があります。

下記は、前回の記事で説明した tuple と records 属性を使ってこの局面の最善手の一覧を計算するプログラムです。

bestmove = bestmoves[tuple(mb.records)]
print(bestmove)

実行結果

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

下記はこの局面で ai2s と ai14s が行う着手の一覧を計算するプログラムです。

moves_ai2s = ai2s(mb, candidate=True)
moves_ai14s = ai14s(mb, candidate=True)
print(moves_ai2s)
print(moves_ai14s)

実行結果

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

人間の目で見れば以下の事がわかりますが、この判定をプログラムで行う必要があります。

• ai2s が行う着手の一覧の中に、最善手ではない着手が混じっている
• ai14s が行う着手は全て最善手である

set を利用した包含関係の計算

上記の判定を行うために必要な知識は、実は以前の記事で説明済ですが、忘れた方が多いのではないかと思いますので、簡単に説明します。

合法手の一覧や、AI が選択する着手の一覧のように、重複しないデータを集めたもの を 集合 と呼びます。

手順 2 が行う処理は、AI が選択する着手の一覧の集合 が、最善手の一覧の集合 に 完全に含まれているか どうかを判定することですが、このような、ある集合の要素が別の集合の要素に完全に含まれていることを 包含関係 と呼びます。

Python では、包含関係の判定などの、集合に関する演算 を set という 集合を表すデータ型 で行うことができ、2 つの set が包含関係にあるかどうかは <= という演算子を使って判定することができます。

Python では list のデータを、下記のプログラムのように、組み込み関数 set を使って set に変換 することができます。set を print で表示すると、実行結果のようにその要素が {} で記号で囲まれて表示されます。なお、list を set に変換する際には、その全ての要素がハッシュ可能なデータである必要があります。

print(set(moves_ai2s))

実行結果

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

下記のプログラムのように、set どうしを <= 演算子で包含関係にあるかどうかを判定することで、実行結果から以下の事がわかります。

• ai2s が選択する着手の一覧は、最善手の一覧に 包含されない
• ai14s が選択する着手の一覧は、最善手の一覧に 包含される

print(set(moves_ai2s) <= set(bestmove))
print(set(moves_ai14s) <= set(bestmove))

False
True

逆に、包含関係にないことは、下記のプログラムのように > 演算子を使って判定することができます。

print(set(moves_ai2s) > set(bestmove))
print(set(moves_ai14s) > set(bestmove))

実行結果

True
False

mblist の保存と load_mblist の定義

強解決の AI であるかどうかを判定するためには、〇×ゲームの 決着がついていない全ての局面 に対して処理を行う必要があり、決着がついていない全ての局面は、前回の記事で下記のようなプログラムで計算しました。

from tree import Mbtree

mbtree = Mbtree.load("../data/aidata")
mblist = []
for node in mbtree.nodelist:
    if node.mb.status == Marubatsu.PLAYING:
        mblist.append(node.mb)

ただし、毎回このような処理を記述するのは面倒なので、下記のプログラムで mblist のデータを ../data/mblist.dat というパスのファイルに保存することにします。

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

次に、load_bestmoves と同様の方法で、このファイルを読み込んで返り値として返す load_mblist を下記のプログラムのように定義します。

def load_mblist(fname="../data/mblist.dat"):
    with gzip.open(fname, "rb") as f:
        return pickle.load(f)

is_strongly_solved の定義

下記の is_strongly_solved にはバグがある ことが判明しました。次回の記事でバグを説明するために、あえて間違いのまま説明を進めます。バグの詳細については次回の記事で説明します。

強解決の AI であるかを判定する方法と、計算するために必要なデータを得る手段がが揃ったので、is_strongly_solved は、以下のようなプログラムで定義できます。

• 3 行目：判定を行う AI の関数を代入する仮引数 ai を記述する
• 4 行目：各局面の最善手の一覧を表すデータをファイルから読み込む
• 5 行目：決着がついていない局面の一覧を表すデータをファイルから読み込む
• 6 行目：決着がついていない全ての局面に対する繰り返し処理を行う。局面の数が多いので、tqdm を使ってプログレスバーを表示するようにする
• 7 行目：先ほど説明した方法を使って、mb の局面に対して ai が行う着手の一覧が、最善手の一覧に対して 包含関係にない ことを判定する
• 8 行目：包含関係にない場合は、強解決の AI ではない ので、False を返して終了する
• 9 行目：繰り返し処理が完了 した場合は、全ての局面が包含関係 なので True を返す

1  from tqdm import tqdm
2
3  def is_strongly_solved(ai):
4      bestmoves = load_bestmoves()
5      mblist = load_mblist()
6      for mb in tqdm(mblist):
7          if set(ai(mb, candidate=True)) > set(bestmoves[tuple(mb.records)]):
8              return False
9      return True

行番号のないプログラム

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

ai2s と ai14s の判定

まず、下記のプログラムで ai2s が強解決の AI であるかを判定すると、実行結果のように False が表示されるので強解決の AI ではないことがわかりました。ai2s はランダムな着手を行うので当然の結果でしょう。なお、繰り返しの途中で処理が終了 したので、プログレスバーは 0% で表示が止まります。

is_strongly_solved(ai2s)

実行結果

  0%|          | 1/294778 [00:00<?, ?it/s]
False

次に、下記のプログラムで ai14s が強解決の AI であるかを判定すると、実行結果のように True が表示されるので強解決の AI であることがわかりました。このことから、ルール 14 が実は 強解決の AI を作成するルールであった ことがわかりました。

is_strongly_solved にはバグがあるため、ai14s が強解決の AI であるという判定は間違いである ことが判明しました。詳細については次回の記事で説明します。

is_strongly_solved(ai14s)

実行結果

100%|██████████| 294778/294778 [00:46<00:00, 6373.50it/s]
True

is_strongly_solved の改良

is_strongly_solved には、いくつかの改良点があるので改良することにします。

データファイルの読み込みの問題の修正

is_strongly_solved では 毎回 load_bestmoves と load_movelist で ファイルからデータを読み込むため、is_strongly_solved を実行してからプログレスバーが表示されるまでに少し時間がかかります。

何度も is_strongly_solved を実行する場合 に 毎回同じファイルを読み込むのは無駄 なので、一度 is_strongly_solved を実行した後では、読み込んだデータをとっておき、次回からは それらのファイルを 読み込まないようにする ように修正することにします。

そのような処理を行う方法の一つに、is_strongly_solved を クラスのメソッドとして定義 し、ファイルから読み込んだ bestmoves と movelist をその クラス属性に代入する という方法が考えられます。その理由は、クラスの定義の中で記述 された クラス属性への代入処理 は、クラスの定義を実行した際に一度だけ実行される からです。

また、そのクラス はこれまでの記事で定義してきたクラスのようにインスタンスを作成して利用するのではなく²、インスタンスを介さずに クラスから is_strongly_solved メソッドを 直接呼び出して利用 します。そのため、is_strongly_solved は インスタンスの情報を利用しない、静的メソッド として定義します。また、インスタンスを作成しないので、 __init__ メソッドを定義する必要はありません。

クラスの名前は、AI が解決されているか（solved）どうかを判定（check）する処理を行うので、Check_solved という名前にし、下記のプログラムのように定義します。

• 2、3 行目：クラス属性 bestmoves と mblist にファイルから読み込んだデータを代入する。クラス属性に値を代入する処理は以前の記事で説明したようにメソッドの定義の前に記述し、この処理はクラスの定義を実行した際に 1 度だけ実行される
• 5 ~ 10 行目：このクラスはインスタンスを作成して利用しないので、@staticmethod を記述して静的メソッドとして is_strongly_solved を定義する。メソッドの中でクラス属性を利用する際には、クラス名.クラス属性名 と記述する必要がある点に注意する事

 1  class Check_solved:
 2      bestmoves = load_bestmoves()
 3      mblist = load_mblist()
 4   
 5      @staticmethod
 6      def is_strongly_solved(ai):
 7          for mb in tqdm(Check_solved.mblist):
 8              if set(ai(mb, candidate=True)) > set(Check_solved.bestmoves[tuple(mb.records)]):
 9                  return False
10          return True

行番号のないプログラム

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

上記を実行すると、2、3 行目の処理が実行されて、ファイルからデータが読み込まれるので、処理の完了までに少し時間がかかります。

is_storngly_solved は、下記のプログラムのように Check_solved のインスタンスを作成せずに 静的メソッドを直接呼び出す ことで実行します。その際に bestmoves などをファイルから読み込むという 無駄な処理は行われません。なお、実行結果は先ほどと同様です。

Check_solved.is_strongly_solved(ai14s)

実行結果

100%|██████████| 294778/294778 [00:53<00:00, 5468.21it/s]
True

包含関係にない局面の数を表示する

ai2s に対して is_strongly_solved メソッドを実行すると False だけが表示されるのが物足りないと思った人はいないでしょうか。そこで、局面の中で 包含関係にある数を数えて表示 することで、全ての局面の中で どのくらいの割合で最善手を着手する局面があるか を表示するように改良することにします。

下記は、そのように is_strongly_solved メソッドを改良したプログラムです。

• 3 行目：包含関係を満たす局面の数を数える count を 0 で初期化する
• 5、6 行目：包含関係にある場合に、count を 1 増やす。元は包含関係にないことを判定していたが、ここでは 包含関係があることを判定 している点に注意する事
• 7 行目：局面の数（Check_solved.mblist の要素の数に等しい）を計算する
• 8 行目：「包含関係にある局面の数/全局面の数」と「包含関係にある局面の数の割合」を表示する
• 9 行目：強解決の AI の場合は、包含関係にある局面の数と全局面の数が等しい ので、それを計算して返り値として返す

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

行番号のないプログラム

@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

Check_solved.is_strongly_solved = is_strongly_solved

修正箇所

@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)]):
+       if set(ai(mb, candidate=True)) <= set(Check_solved.bestmoves[tuple(mb.records)]):
-           return False
+           count += 1
-   return True
+   nodenum = len(Check_solved.mblist)
+   print(f"{count}/{nodenum} {count/nodenum*100:.2f}%")
+   return count == nodenum

Check_solved.is_strongly_solved = is_strongly_solved

上記の修正後に、下記のプログラムを実行すると、実行結果より ai2s が最善手のみを選択する局面が全体の約 60 % もある事がわかります。これは、深さが深いノードの数が多く、深さが深いノードは 合法手の数が少ない ので、全ての合法手が最善手になる局面が多い ことが原因だと思われます。例えば、深さが 8 のノードは合法手が最大でも 1 つしかないので、全ての合法手が必ず最善手になります。

Check_solved.is_strongly_solved(ai2s)

実行結果

100%|██████████| 294778/294778 [00:43<00:00, 6851.92it/s]
173985/294778 59.02%
False

本記事では行いませんが、興味がある方は、ai1s ~ ai13s を最善手の一覧を返すことができるように修正し、is_strongly_solved を実行してみて下さい。

今回の記事のまとめ

今回の記事では、AI が強解決の AI であるかを判定する方法を紹介しました。また、その方法で判定を行った結果、ai14s が強解決の AI であることが判明しました。

is_strongly_solved にはバグがあるため、ai14s が強解決の AI であるという判定は間違いである ことが判明しました。詳細については次回の記事で説明します。

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

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

リンク	説明
marubatsu.ipynb	本記事で入力して実行した JupyterLab のファイル
ai_new.py	今回の記事で更新した ai.py
util_new.py	今回の記事で更新した util.py
mblist.dat	決着がついていない局面の一覧を保存するファイル

次回の記事

更新日時	更新内容
2024/8/25	is_strongly_solved にバグがあり、ai14s が強解決の AI であるという判定が間違っていたことを追記しました

1. ここでいう最善手とは、仮引数 eval_func に渡された関数によって計算された局面の評価値が、最も高くなるような合法手の一覧です。従って、この best_moves はその AI が最善と考えた合法手の一覧にすぎないので、本当の最善手とは異なる点に注意して下さい ↩

2. インスタンスを作成することは可能ですが、作成しても意味はありません。 ↩