Pythonで〇×ゲームのAIを一から作成する その111 同一局面の計算と同一局面を考慮した強解決の AI の判定

目次と前回の記事

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

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

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

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

強解決の AI であるかを判定する局面の数の削減

前回の記事では、〇×ゲームのゲーム盤を表す board 属性の値を文字列型のデータに変換 し、それを利用することで〇×ゲームのゲーム盤の種類が 5478 種類であることを示しました。これは、ゲーム木のノードの数が 549946 であるのに対して約 1/100 になっているため、局面と最善手の対応表を表すデータも約 1/100 の大きさに減らすことができました。

また、その中から決着がついている局面を除いた局面の種類は 4520 種類であることを示し、それを利用して強解決の AI であるかを判定するように Check_solved クラスを修正しました。実は、強解決の AI であるか を判定するために 必要な局面の種類をさらに減らす ことができます。どのようにして減らすことができるかについて少し考えてみて下さい。

合法手に最善手しか存在しない局面の削減

強解決の AI であるかを判定するためには、局面に対して AI が最善手以外の着手を選択するか どうかを判定する必要があります。局面の中には すべての合法手が最善手 になっている局面があり、そのような局面では すべての AI が最善手のみを選択 します。従って、それらの局面を強解決の AI であるかを判定する 局面の一覧から削除 することができます。

局面の一覧の計算

下記は、前回の記事で記述した board 属性の値が異なり、なおかつ決着がついていない局面の一覧を計算して mblist_by_board に代入するプログラムです。

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 からそれらの局面を除いた局面の一覧は、下記のプログラムで計算することができます。

• 10 行目：mblist_by_board に局面を加える条件に、合法手の数を表す子ノードの数と最善手の数が一致しないという条件を加える

 1  from marubatsu import Marubatsu
 2  from tree import Mbtree
 3
 4  mbtree = Mbtree.load("../data/aidata")
 5  bestmoves_by_board = {}
 6  mblist_by_board = []
 7  for node in mbtree.nodelist:
 8      txt = node.mb.board_to_str()
 9      if not txt in bestmoves_by_board.keys():
10          bestmoves_by_board[txt] = node.bestmoves
11          if node.mb.status == Marubatsu.PLAYING and len(node.children) != len(node.bestmoves):
12              mblist_by_board.append(node.mb)

行番号のないプログラム

from marubatsu import Marubatsu
from tree import Mbtree

mbtree = Mbtree.load("../data/aidata")
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 and len(node.children) != len(node.bestmoves):
            mblist_by_board.append(node.mb)

修正箇所

from marubatsu import Marubatsu
from tree import Mbtree

mbtree = Mbtree.load("../data/aidata")
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:
+       if node.mb.status == Marubatsu.PLAYING and len(node.children) != len(node.bestmoves):
            mblist_by_board.append(node.mb)

上記の修正後に下記のプログラム実行して mblist_by_board の要素の数を表示すると、実行結果から 強解決の AI であることを判定するために必要な局面の数が 3191 であることが判明しました。

print(len(mblist_by_board))

実行結果

3191

プログラムの改良

上記のプログラムでは node.mb と同じ局面が mblist_by_board に登録されているかどうかを 判定するために bestmoves_by_board を計算 していますが、その判定を行うために わざわざ bestmoves_by_board を計算する必要はない ので、その点を改良することにします。

具体的には、下記のプログラムのように mblist_by_board に node.mb が 登録済（registerd）であるかを表す registered_boards という list を bestmoves_by_board の代わりに計算するように修正します。

• 1 行目：mblist_by_board に mb が登録済であるかを表す registered_boards を空の list で初期化する
• 5 行目：board 属性の値を変換した文字列を表す txt が registered_boards の要素に存在するかを判定するように修正する
• 6 行目：registered_boards の要素に txt を追加する

1  registered_boards = []
2  mblist_by_board = []
3  for node in mbtree.nodelist:
4     txt = node.mb.board_to_str()
5     if not txt in registered_boards:
6         registered_boards.append(txt)
7         if node.mb.status == Marubatsu.PLAYING and len(node.children) != len(node.bestmoves):
8             mblist_by_board.append(node.mb)

行番号のないプログラム

registered_boards = []
mblist_by_board = []
for node in mbtree.nodelist:
    txt = node.mb.board_to_str()
    if not txt in registered_boards:
        registered_boards.append(txt)
        if node.mb.status == Marubatsu.PLAYING and len(node.children) != len(node.bestmoves):
            mblist_by_board.append(node.mb)

修正箇所

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

上記の修正後に下記のプログラムを実行すると、修正前と同じの数の mblist_by_board が計算できたことが確認できます。

print(len(mblist_by_board))

実行結果

3191

set による処理の高速化

上記のプログラム を実行すると筆者のパソコンでは 約 17 秒 の時間がかかりましたが、修正前のプログラムでは 1 秒以内 で処理が完了しました。処理時間が大幅に増えた理由 は、list に対して要素の中にデータが存在するか どうかを判定する処理は、dict のキーの中にデータが存在するか どうかを判定する処理と比較して 処理の効率が大幅に悪いから です。

同じデータが重複して存在しない ようなデータの中に、特定のデータが存在するかどうかを判定 する場合は、list ではなく、set を利用することで高速に処理を行う ことができます。下記は、先程のプログラムを set を使うように修正したプログラムです。

• 1 行目：registered_boards を 空の set で初期化 するように修正する
• データが要素に含まれているかどうかの 判定は list と set で同じ なので、5 行目のプログラムを 修正する必要はない
• 6 行目：set に要素を追加するのは append ではなく add なのでそのように修正する

1  registered_boards = set()
2  mblist_by_board = []
3  for node in mbtree.nodelist:
4      txt = node.mb.board_to_str()
5      if not txt in registered_boards:
6          registered_boards.add(txt)
7          if node.mb.status == Marubatsu.PLAYING and len(node.children) != len(node.bestmoves):
8              mblist_by_board.append(node.mb)

行番号のないプログラム

registered_boards = set()
mblist_by_board = []
for node in mbtree.nodelist:
    txt = node.mb.board_to_str()
    if not txt in registered_boards:
        registered_boards.add(txt)
        if node.mb.status == Marubatsu.PLAYING and len(node.children) != len(node.bestmoves):
            mblist_by_board.append(node.mb)

修正箇所

-registered_boards = []
+registered_boards = set()
mblist_by_board = []
for node in mbtree.nodelist:
    txt = node.mb.board_to_str()
    if not txt in registered_boards:
-       registered_boards.append(txt)
+       registered_boards.add(txt)
        if node.mb.status == Marubatsu.PLAYING and len(node.children) != len(node.bestmoves):
            mblist_by_board.append(node.mb)

上記の修正後に下記のプログラムを実行すると、実行結果は同じになりますが、処理時間が 1 秒未満になることが確認できます。

print(len(mblist_by_board))

実行結果

3191

dict のキーが、set の要素と同様に同じ名前のキーが重複せず、ハッシュ可能なデータしか利用できないのは dict のキーと set が同じ仕組みで管理されているからです。そのため、最初の bestmoves_by_board のキーで判定を行っていたプログラムと上記のプログラムの処理速度はほとんど変わりません。

なお、データを追加する処理に関しては list と set で大きな違いはありません。

データの保存と is_strongly_soved の修正と確認

データが作成できたので、下記のプログラムでファイルに保存します。ファイル名は良い名前が思いつかなかったので、mblist_by_board2.dat としました。

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

作成された ファイルサイズは 30 KB で、mblist_by_board.dat の 38 KB よりもさらにサイズが小さくなります。

次に、このデータで正しく強解決の AI であるかを判定できるかを確認するために、Check_solved クラスの is_strongly_solved を下記のプログラムのように修正します。なお、修正箇所は 9 行目で読み込むファイルを mblist_by_board2.dat に変えただけです。

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

行番号のないプログラム

from util import Check_solved, load_bestmoves, load_mblist
from tqdm import tqdm

@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_board2.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

Check_solved.is_strongly_solved = is_strongly_solved

修正箇所

from util import Check_solved, load_bestmoves, load_mblist
from tqdm import tqdm

@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")
+       Check_solved.mblist_by_board = load_mblist("../data/mblist_by_board2.dat")
元と同じなので省略

Check_solved.is_strongly_solved = is_strongly_solved

上記の修正後に、下記のプログラムで強解決でない ai2s、ai14s と強解決の ai_gt6 を is_strongly_solved で判定できるかどうかを確認します。

下記の実行結果のように ai2s が強解決の AI でないことを正しく判定できます。また、ai2s は 全ての合法手の中からランダムに着手を選択する ので、最善手でない合法手が必ず混じっている局面を集めた mblist_by_board2.dat のデータに対してチェックを行うと、実行結果のように 0 % が表示 されます。

from ai import ai2s, ai14s, ai_gt6
result, incorrectlist = Check_solved.is_strongly_solved(ai2s)
print(result)

実行結果

100%|██████████| 3191/3191 [00:00<00:00, 4117.52it/s]
0/3191 0.00%
False

下記の実行結果のように ai14s が強解決の AI でないことが正しく判定できます。また、正しく判定できない局面の数は 3191 - 3139 = 52 種類であることがわかります。

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

100%|██████████| 3191/3191 [00:00<00:00, 3317.61it/s]
3139/3191 98.37%
False

下記の実行結果のように ai_gt6 が強解決の AI であることが正しく判定できます。

from util import load_bestmoves
bestmoves = load_bestmoves("../data/bestmoves_by_board.dat")
result, incorrectlist = Check_solved.is_strongly_solved(ai_gt6, params={"bestmoves_by_board": bestmoves})
print(result)

実行結果

100%|██████████| 3191/3191 [00:00<00:00, 265287.59it/s]
3191/3191 100.00%
True

同一局面の削減

以前の記事で〇×ゲームには 回転による同一局面 と、線対称な同一局面 が存在することを説明しました。同一局面に対する最善手は、元の局面の最善手を 同じように回転、反転 させたものに 一致します。

わかりづらいと思いますので、具体例を挙げます。下記の 左の局面 は 次に (2, 2) に 〇 が着手を行うと 〇 が勝利するので 最善手は (2, 2) です。左の局面を 時計回りに 90 度回転 させた 右の局面は同一局面です が、その最善手は 左の局面の最善手 である (2, 2) を同じく 時計回りに 90 度回転させた (0, 2) になります。

o..  .xo
xo.  .o.
...  ...

同一局面に対する着手が一致する AI の定義と性質

AI が選択する着手の一覧 が、同一局面に対しても同じだけ回転、反転した着手の一覧に一致する場合 は、ある局面 に対して AI が最善手のみを着手するかどうかを判定することで、その局面に対する すべての同一局面に対しても判定を行ったことになります。

例えば、そのような AI が上記の左の局面で最善手のみを選択することが確認できれば、右の局面に対する確認を行わなくても、右の局面で最善手のみを選択することがわかります。従って、そのような AI に対しては、強解決の AI であるかを判定する局面の一覧から 同一局面を削除 することができます。

本記事ではそのような性質を持つ AI のことを、同一局面に対する着手が一致する AI と表記することにします。

これまでに作成してきた〇×ゲームの AI は、左上のマスから優先的に着手を行うという ルール 1 で着手を選択する ai1 と ai1s のみがその条件を満たしません。実際に ai1s は上記の 左の局面では (1, 0) を選択 し、右の局面 では (1, 0) を時計回りに 90 度回転させた (2, 1) とは 異なる (0, 0) を選択 します。

ただし、それ以外のルール はいずれもゲーム盤を回転、反転した際に 選択する着手が同様の回転、反転を行うようなルール なので、ai1 と ai1s 以外の AI はすべて同一局面に対する着手が一致する AI です。また、〇×ゲームの性質を考えると、よほど特別なルールでない限りは、同一局面に対する着手が一致する AI になるでしょう。

同一局面を考慮した局面の一覧を計算するアルゴリズム

最初に、同一局面を考慮した場合の〇×ゲームの局面の一覧 を計算することにします。

同一局面を考慮した局面の一覧は、下記のアルゴリズムで計算することができます。

• 局面を登録済であるかどうかを表すデータを空の set で初期化する
• 局面の一覧を表すデータを空の list で初期化する
• ゲーム木の全てのノードの局面に対して下記の処理を行う
• その局面を文字列に変換したデータが、登録済であるかを表す set に存在していなければ、下記の処理を行う。存在している場合は登録済なので何もしない
  • 局面の一覧を表す list にその局面を追加する
  • 局面を登録済であるかどうかを表す set に、その局面を含む、すべての同一局面を文字列に変換したデータを登録する

このアルゴリズムは、以下の点を除けば 先程の mblist_by_board を計算するプログラムと 全く同じ です。

• mb.node だけでなく、mb.node の全ての同一局面を文字列に変換したデータを registerd_borads に追加する
• 決着がついているかどうかと、全ての合法手が最善手であるかの判定を行わず、全ての局面を mblist_by_board に登録する

従って、上記のアルゴリズムは、先程のプログラムを修正した下記のプログラムのように記述できます。6 行目の処理をどのように記述すれば良いかについて少し考えてみて下さい。

1  registered_boards = set()
2  mblist_by_board = []
3  for node in mbtree.nodelist:
4      txt = node.mb.board_to_str()
5      if not txt in registered_boards:
6          # ここに node のすべての同一局面を表す文字列を registerd_boards に追加する処理を記述する
7          mblist_by_board.append(node.mb)

修正箇所

registered_boards = set()
mblist_by_board = []
for node in mbtree.nodelist:
    txt = node.mb.board_to_str()
    if not txt in registered_boards:
-       registered_boards.add(txt)
+       # ここに node のすべての同一局面を表す文字列を registerd_boards に追加する処理を記述する
-       if node.mb.status == Marubatsu.PLAYING and len(node.children) != len(node.bestmoves):
-           mblist_by_board.append(node.mb)
+       mblist_by_board.append(node.mb)

同一局面の計算の考え方

上記の 6 行目の処理を記述するためには、任意の局面の同一局面をすべて計算 する必要があります。そのために、同一局面がどのようなものであるかをおさらいします。

以前の記事で説明したように、同一局面には最大で下記の 8 種類が存在します。

同一局面を表す board 属性のデータは、上図の 左のゲーム盤のデータを元 に、残りの 7 つのゲーム盤のデータを計算する 処理を行うことで計算することができます。

左から 2 番目の同一局面の計算方法

まず、一番左のゲーム盤 のデータを、左から 2 番目の同一局面 のゲーム盤のデータに 変換する方法 を考えることにします。このような変換の処理に慣れている人であれば頭の中だけで変換を行う方法を思いつくことができますが、そうではない場合は、最初に 変換後と変換前 のそれぞれの 数字の座標 を下記のように 表にまとめる ことをお勧めします。

数字	変換後の座標	変換前の座標
1	(2, 0)	(0, 0)
2	(2, 1)	(1, 0)
3	(2, 2)	(2, 0)
4	(1, 0)	(0, 1)
5	(1, 1)	(1, 1)
6	(1, 2)	(2, 1)
7	(0, 0)	(0, 2)
8	(0, 1)	(1, 2)
9	(0, 2)	(2, 2)

おそらく、この表をみてもピンとこない人が多いのではないかと思います。そのような場合は、下記の表のように x 座標と y 座標に分けた表 を作成すると良いでしょう。

数字	変換後の x 座標	変換後の y 座標	変換前の x 座標	変換前の y 座標
1	2	0	0	0
2	2	1	1	0
3	2	2	2	0
4	1	0	0	1
5	1	1	1	1
6	1	2	2	1
7	0	0	0	2
8	0	1	1	2
9	0	2	2	2

この表から、以下の事がわかります。

• 変換後の y 座標と、変換前の x 座標が等しい
• 変換後の x 座標と変換前の y 座標は、同じ座標に対して同じ値が対応 している

そこで、変換後の x 座標と変換前の y 座標の対応 をまとめると以下の表のようになります。

変換後の x 座標	変換前の y 座標
2	0
1	1
0	2

この表から「変換後の x 座標 + 変換前の y 座標 = 2」になることがわかるので、変換後の x 座標 は「2 - 変換前の y 座標」という 式で計算できる ことがわかります。

上記から、左から 2 番目 の同一局面の (x, y) のマスの内容 は、一番左の局面の (y, 2 - x) のマスの内容 になることがわかります。

従って、一番左の局面 を表すデータが mb に代入 されている場合に、左から 2 番目 の同一局面を表すゲーム盤のデータは、下記のプログラムで計算 することができます。

• 1 行目：同一局面のゲーム盤を計算する board を空の list で初期化する
• 2 行目：同一局面の各列に対する繰り返し処理を行う
• 3 行目：同一局面の x 列のデータを計算する col を空の list で初期化する
• 4 行目：同一局面の x 列の各マスに対する繰り返し処理を行う
• 5 行目：同一局面の (x, y) のマスを表す、元の局面の (y, 2-x) のマスのデータを col の要素に追加する
• 6 行目：同一局面の x 列のデータを board の要素に追加する

1  board = []
2  for x in range(mb.BOARD_SIZE):
3      col = []
4      for y in range(mb.BOARD_SIZE):
5          col.append(mb.board[y][2 - x])
6      board.append(col)

このプログラムが正しく動作することを、下記のプログラムで下記の図の 一番左と同じ局面を作成 し、左から 2 番目の同一局面を作成できているか どうかで確認することにします。

• 1 ~ 5 行目：上図の一番左の局面のデータを作成してゲーム盤を表示する
• 7 ~ 12 行目：上記のプログラムを記述して左から 2 番目の同一局面のデータを計算する
• 13、14 行目：計算したデータを mb の board 属性に代入して上書きし、print(mb) でその局面を表示する

 1  mb = Marubatsu()
 2  mb.move(1, 1)
 3  mb.move(0, 0)
 4  mb.move(1, 0)
 5  print(mb)
 6
 7  board = []
 8  for x in range(mb.BOARD_SIZE):
 9      col = []
10      for y in range(mb.BOARD_SIZE):
11          col.append(mb.board[y][2 - x])
12      board.append(col)
13  mb.board = board
14  print(mb)

行番号のないプログラム

mb = Marubatsu()
mb.move(1, 1)
mb.move(0, 0)
mb.move(1, 0)
print(mb)

board = []
for x in range(mb.BOARD_SIZE):
    col = []
    for y in range(mb.BOARD_SIZE):
        col.append(mb.board[y][2 - x])
    board.append(col)
mb.board = board
print(mb)

実行結果

Turn x
xO.
.o.
...

Turn x
..x
.oo
...

実行結果から図の一番左と、左から 2 番目と 同じ局面が表示される ので、正しい処理が行われることが確認できました。

同一局面を表す文字列の計算

上記では左から 2 番目の同一局面のデータを計算しましたが、実際に必要になる のはその局面を 文字列に変換したデータ です。そのデータは、下記のプログラムのように、board_to_str メソッドを使って計算できますが、一旦ゲーム盤のデータを作成してから文字列に変換するのは 無駄がある ので、一番左の局面 のデータから 直接同一局面を表す文字列を計算する ことにします。どのように計算すればよいかについて少し考えてみて下さい。

print(mb.board_to_str())

実行結果

'....o.xo.'

そのプログラムは、下記のように元のプログラムと比較してシンプルに記述できます。

• 1 行目：同一局面のゲーム盤の文字列を表す txt を空文字で初期化する
• 4 行目：同一局面の (x, y) のマスを表す、元の局面の (y, 2-x) のマスのデータを + 演算子を使って txt に結合する

1  txt = ""
2  for x in range(mb.BOARD_SIZE):
3      for y in range(mb.BOARD_SIZE):
4          txt += mb.board[y][2 - x]

行番号のないプログラム

txt = ""
for x in range(mb.BOARD_SIZE):
    for y in range(mb.BOARD_SIZE):
        txt += mb.board[y][2 - x]

修正箇所

-board = []
+txt = ""
for x in range(mb.BOARD_SIZE):
-   col = []
    for y in range(mb.BOARD_SIZE):
        txt += mb.board[y][2 - x]
-       col.append(mb.board[y][2-x])
-   board.append(col)

上記のプログラムが正しく動作することは、下記のプログラムで先程 print(mb) で表示した文字列と同じ文字列が表示されることで確認できます。先ほどのプログラムで、mb の board 属性を同一局面のデータに置き換えてしまった ので、下記のプログラムのように mb のデータを作り直す必要がある 点に注意して下さい。

mb = Marubatsu()
mb.move(1, 1)
mb.move(0, 0)
mb.move(1, 0)

txt = ""
for x in range(mb.BOARD_SIZE):
    for y in range(mb.BOARD_SIZE):
        txt += mb.board[y][2 - x]
print(txt)

実行結果

....o.xo.

全ての同一局面を表す文字列の計算

残りの同一局面 は 同様の方法で文字列に変換 することができます。下図のそれぞれの同一局面の (x, y) のマスが、一番左の局面のどのマスの値になるかを考えて下さい。

下記はそれぞれの同一局面の (x, y) のマスと一番左の局面のマスの座標の対応表です。

同一局面	(x, y) に対応する元の局面の座標
2	(y, 2 - x)
3	(2 - x, 2 - y)
4	(2 - y, x)
5	(2 - x, y)
6	(x, 2 - y)
7	(2 - y, 2 - x)
8	(y, x)

上記の 7 つ の同一局面への 変換の処理 を 1 つずつ記述するのは大変 なので、7 つの変換の処理を for 文でまとめて行いたい のですが、その方法について少し考えてみて下さい。

上記それぞれの x 座標と y 座標を表す式 をよく見ると、2、x、-x、y、-y のうちのいくつかを使った式 で表されていることがわかります。そのため、それぞれの x 座標と y 座標は以下の式で表現できます。

$a×2 + bx + cy$、ただし a は 0 または 1、b と c は -1、0、1 のいずれか

例えば、2 つ目の同一局面の座標は、下記の式で表現できます。

(y, 2 - x) = (0 * 2 + 0 * x + 1 * y, 1 * 2 + -1 * x + 0 * y)

下記は、それぞれの同一局面の x 座標と y 座標を上記の式で表現した際の a、b、c の値を表にまとめたものです。

同一局面	(x, y) に対応する元の局面の座標	x 座標			y 座標
		a	b	c	a	b	c
2	(y, 2 - x)	0	0	1	1	-1	0
3	(2 - x, 2 - y)	1	-1	0	1	0	-1
4	(2 - y, x)	1	0	-1	0	1	0
5	(2 - x, y)	1	-1	0	0	0	1
6	(x, 2 - y)	0	1	0	1	0	-1
7	(2 - y, 2 - x)	1	0	-1	1	-1	0
8	(y, x)	0	0	1	0	1	0

7 種類の同一局面 のそれぞれに対して上記の a, b, c の 6 つのデータを用意 することで、7 つの同一局面を表す文字列を for 文を使ってまとめて計算 することができます。そこで、指定した局面 に対するの 同一局面を表す文字列の一覧を計算 する下記のような関数を定義する事にします。

名前：同一（same）局面のゲーム盤（board）を表す文字列（text）の一覧を計算（calculate）するので、calc_same_boardtexts とする
処理：指定した局面の同一局面を表す文字列の一覧を計算する
入力：計算の対象となる局面のデータを仮引数 mb に代入する
出力：同一局面を表す文字列の一覧を表す set を返り値として返す

返り値を list ではなく set にした理由 は、例えばゲーム開始時の局面のように、7 つの同一局面 の中の いくつかまたは全部 が 全く同じゲーム盤になる場合がある からです。set にすることで、同く同じ文字列を set に登録しても、set の要素が 重複しなくなります。

calc_same_boardtexts は下記のプログラムのように定義できます。

• 1 行目：mb を仮引数とする calc_same_boardtexts を定義する
• 2 ~ 8 行目：上記の表のデータを要素とする、2 次元配列の list を data に代入する。data の 1 つ目のインデックスは 7 つの同一局面の番号を、2 つ目のインデックスは同一局面のマスの値を計算するために必要となる 6 つのデータを表す
• 9 行目：同一局面を表す文字列の集合を計算する boardtexts を初期化する。その際に、mb 自身も同一局面の 1 つなので、mb を文字列に変換したデータを要素として持つ set で初期化する
• 10 行目：7 つの同一局面を表す文字列を順番に計算する繰り返し処理を for 文で記述する。data からは 同一局面のマスの値を計算するために必要となる 6 つのデータを xa ～ yc までの変数に代入する。この変数の名前は、x 座標を計算する a を xa のようにした
• 11 ～ 14 行目：先程記述したプログラムと同様の方法で同一局面を表す文字列を計算する。その際に 14 行目では、xa ～ yc の値を使って (x, y) のマスに対応する mb のゲーム盤のマスの座標を計算する
• 15 行目：計算した同一局面を表す文字列を boardtexts の集合に追加する
• 16 行目：boardtexts を返り値として返す

 1  def calc_same_boardtexts(mb):
 2      data = [ [ 0,  0,  1, 1, -1,  0],
 3               [ 1, -1,  0, 1,  0, -1],
 4               [ 1,  0, -1, 0,  1,  0],
 5               [ 1, -1,  0, 0,  0,  1],
 6               [ 0,  1,  0, 1,  0, -1],
 7               [ 1,  0, -1, 1, -1,  0],
 8               [ 0,  0,  1, 0,  1,  0], ]
 9      boardtexts = set([mb.board_to_str()])
10      for xa, xb, xc, ya, yb, yc in data:
11          txt = ""
12          for x in range(mb.BOARD_SIZE):
13              for y in range(mb.BOARD_SIZE):
14                  txt += mb.board[xa * 2 + xb * x + xc * y][ya * 2 + yb * x + yc * y]
15          boardtexts.add(txt)
16      return boardtexts

行番号のないプログラム

def calc_same_boardtexts(mb):
    data = [ [ 0,  0,  1, 1, -1,  0],
             [ 1, -1,  0, 1,  0, -1],
             [ 1,  0, -1, 0,  1,  0],
             [ 1, -1,  0, 0,  0,  1],
             [ 0,  1,  0, 1,  0, -1],
             [ 1,  0, -1, 1, -1,  0],
             [ 0,  0,  1, 0,  1,  0], ]
    boardtexts = set([mb.board_to_str()])
    for xa, xb, xc, ya, yb, yc in data:
        txt = ""
        for x in range(mb.BOARD_SIZE):
            for y in range(mb.BOARD_SIZE):
                txt += mb.board[xa * 2 + xb * x + xc * y][ya * 2 + yb * x + yc * y]
        boardtexts.add(txt)
    return boardtexts

上記のプログラムを実行した後で、下記のプログラムで先程の図の左の局面に対して、同一局面を表す文字列の一覧を計算します。

print(calc_same_boardtexts(mb))

実行結果（見やすいように、途中で改行ました）

{'...oo.x..', 'xo..o....', '....o..ox', '....o.xo.',
 '.ox.o....', 'x..oo....', '..x.oo...', '....oo..x'}

上記の実行結果と、下記の図を見比べて正しく計算されていることを確認して下さい。なお、x..oo.... は、左から順番 に 0 列目 の 3 マス、1 列目 の 3 マス、2 列目 の 3 マスを表します。横ではなく、 縦方向に順番に並んでいる 点に注意して確認して下さい。

なお、返り値を set にした ことで、下記のプログラムのように、ゲーム開始時の局面のように、同一局面を表すゲーム盤が 1 つしかない場合 は、calc_same_bardtexts の返り値の set の集合が 1 つ になります。

mb.restart() # ゲームをリセットしてゲーム開始時の局面にする
print(calc_same_boardtexts(mb))

実行結果

{'.........'}

同一局面を計算するアルゴリズムには、下記のようなものもあります。興味がある方は実装してみて下さい。

• 時計回りに 90 度回転した局面を計算する関数を定義する
• x = 1 の軸を中心に反転した局面を計算する関数を定義する
• 時計回りに 90 度回転する処理を 3 回繰り返すことで同一局面を 3 つ計算できる
• その後で、局面を反転することで同一局面を 1 つ計算できる
• その後で、時計回りに 90 度回転する処理を 3 回繰り返すことで同一局面を 3 つ計算できる

同一局面を考慮した局面の一覧の計算

同一局面を表す文字列の一覧の計算を行えるようになったので、それを利用することで同一局面を考慮した局面の一覧を下記のプログラムで計算できます。

• 6 行目：node.mb の局面の同一局面を表す文字列の一覧を計算し、registerd_boards の要素に追加する。set に別の set の全ての要素を追加する処理 は、集合の両方の要素を持つ 和集合を計算する | 演算子 を使って行うことができる

1  registered_boards = set()
2  mblist_by_board = []
3  for node in mbtree.nodelist:
4      txt = node.mb.board_to_str()
5      if not txt in registered_boards:
6          registered_boards |= calc_same_boardtexts(node.mb)
7          mblist_by_board.append(node.mb)

行番号のないプログラム

registered_boards = set()
mblist_by_board = []
for node in mbtree.nodelist:
    txt = node.mb.board_to_str()
    if not txt in registered_boards:
        registered_boards |= calc_same_boardtexts(node.mb)
        mblist_by_board.append(node.mb)

上記の実行後に下記のプログラムを実行することで、実行結果から〇×ゲームで 同一局面を考慮した場合の局面の数は 765 種類 であることが確認できました。

print(len(mblist_by_board))

実行結果

765

同一局面を考慮したデータによる強解決の AI であるかどうかの判定

次に、同一局面を考慮した強解決の AI であることを判定するためのデータを作成し、そのデータを使って強解決の AI であるかどうかの判定を行うことにします。

まず、上記のプログラムに下記のプログラムの 7 行目を追加することで、今回の記事の最初で行ったのと同じ方法で、ゲームの決着がついている局面と、合法手と最善手が一致している局面を除いた mblist_by_board を計算します。

1  registered_boards = set()
2  mblist_by_board = []
3  for node in mbtree.nodelist:
4      txt = node.mb.board_to_str()
5      if not txt in registered_boards:
6          registered_boards |= calc_same_boardtexts(node.mb)
7          if node.mb.status == Marubatsu.PLAYING and len(node.children) != len(node.bestmoves):
8              mblist_by_board.append(node.mb)

行番号のないプログラム

registered_boards = set()
mblist_by_board = []
for node in mbtree.nodelist:
    txt = node.mb.board_to_str()
    if not txt in registered_boards:
        registered_boards |= calc_same_boardtexts(node.mb)
        if node.mb.status == Marubatsu.PLAYING and len(node.children) != len(node.bestmoves):
            mblist_by_board.append(node.mb)

修正箇所

registered_boards = set()
mblist_by_board = []
for node in mbtree.nodelist:
    txt = node.mb.board_to_str()
    if not txt in registered_boards:
        registered_boards |= calc_same_boardtexts(node.mb)
-       mblist_by_board.append(node.mb)
+       if node.mb.status == Marubatsu.PLAYING and len(node.children) != len(node.bestmoves):
+           mblist_by_board.append(node.mb)

上記の実行後に下記のプログラムを実行することで、実行結果から 強解決の AI であることを判定するために必要な局面の数は 431 種類 であることがわかりました。最初は 50 万以上の局面を調べていたのと比べて 1/1000 以下になっていることがわかります。

print(len(mblist_by_board))

実行結果

431

データの保存と is_strongly_soved の修正と確認

データが作成できたので、下記のプログラムでファイルに保存します。ファイル名は最小（minimum）の局面数なので mblist_by_board_min としました。

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

作成された ファイルのサイズは 5 KB で、mblist_by_board2.dat の 30 KB よりも さらにサイズが小さくなる ことが確認できました。

次に、このデータで正しく強解決の AI であるかを判定できるかを確認するために、Check_solved クラスの is_strongly_solved を下記のプログラムのように修正します。

なお、メソッドの修正箇所は 6 行目で読み込むファイルを mblist_by_board_min.dat に変えた点だけですが、Check_solved クラスの定義を実行し直さない場合 は、mblist_by_board 属性の値 には先程 is_strongly_solved を実行した結果 mblist_by_board2.dat から読み込んだデータが代入されたままになっている ので、9 行目のように その属性に None を代入する必要がある 点に注意して下さい¹。

1  @staticmethod
2  def is_strongly_solved(ai, params=None):
3      if Check_solved.bestmoves_by_board is None:
4          Check_solved.bestmoves_by_board = load_bestmoves("../data/bestmoves_by_board.dat")
5      if Check_solved.mblist_by_board is None:
6          Check_solved.mblist_by_board = load_mblist("../data/mblist_by_board_min.dat")
元と同じなので省略
7
8  Check_solved.is_strongly_solved = is_strongly_solved
9  Check_solved.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_min.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

Check_solved.is_strongly_solved = is_strongly_solved
Check_solved.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_board2.dat")
+       Check_solved.mblist_by_board = load_mblist("../data/mblist_by_board_min.dat")
元と同じなので省略

Check_solved.is_strongly_solved = is_strongly_solved
+Check_solved.mblist_by_board = None

上記の修正後に、下記のプログラムで強解決でない ai2s、ai14s と強解決の ai_gt6 を is_strongly_solved で判定できるかどうかを確認します。

下記の実行結果のように ai2s が強解決の AI でないことを正しく判定できます。また、修正前と同様に実行結果には 0 % が表示されます。

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

実行結果

100%|██████████| 431/431 [00:00<00:00, 3734.25it/s]
0/431 0.00%
False

下記の実行結果のように ai14s が強解決の AI でないことが正しく判定できます。また、正しく判定できない局面の数は 431 - 424 = 7 種類であることがわかります。

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

100%|██████████| 431/431 [00:00<00:00, 2177.32it/s]
424/431 98.38%
False

正しく判定できない局面が 7 種類しかないようなので、せっかくなので下記のプログラムでその局面を表示してみることにします。実行結果から 6 つが真ん中の (1, 1) を、1 つが 四隅の (0, 0) を最善手であると 間違って判断している ことが確認できました。ai14s は初手で真ん中のマスに着手を行う AI であり、いずれの局面も (1, 1) のマスに着手が行われていないことから、いずれも ai14s がゲーム開始時の局面から着手を行った場合には 出現しない局面であり、ai14s が弱解決の AI であることに影響を与えない ことが確認できました。

興味がある方は、それぞれの局面の最善手がどのように間違っているかを確認して下さい。

for mb, candidates, best_moves in incorrectlist:
    print(mb)
    print("candidates", candidates)
    print("best_moves", best_moves)

実行結果

Turn o
o.X
...
...

candidates {(1, 1)}
best_moves {(0, 1), (0, 2), (2, 2)}
Turn x
oOx
...
...

candidates {(1, 1)}
best_moves {(2, 1), (2, 2)}
Turn x
o.x
...
.O.

candidates {(1, 1)}
best_moves {(2, 2)}
Turn x
xo.
..O
...

candidates {(1, 1)}
best_moves {(0, 2)}
Turn x
.o.
x.O
...

candidates {(0, 0)}
best_moves {(2, 0), (2, 2)}
Turn o
.o.
...
X..

candidates {(1, 1)}
best_moves {(0, 0)}
Turn x
.o.
..O
x..

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

下記の実行結果のように ai_gt6 が強解決の AI であることが正しく判定できます。

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

実行結果

100%|██████████| 431/431 [00:00<00:00, 143540.18it/s]
431/431 100.00%
True

今回の記事のまとめ

今回の記事では、同一局面を考慮した局面の一覧を計算する方法を紹介し、〇×ゲームの 同一局面を考慮した局面の種類が 765 種類 しかないことを示しました。

また、同一局面を考慮 した場合に 強解決の AI であるかを判定するために必要な局面が 431 種類 しかないことを示し、その局面の一覧を使って強解決の AI であるかを判定するように is_strongly_solved を修正しました。

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

今回の記事で定義した calc_same_boardtexts は util.py に保存することにします。

リンク	説明
marubatsu.ipynb	本記事で入力して実行した JupyterLab のファイル
util_new.py	今回の記事で更新した util.py
mblist_by_board2.dat	合法手の一覧と最善手が同じ局面を除いた決着がついていない局面の一覧を保存するファイル
mblist_by_board_min.dat	合法手の一覧と最善手が同じ局面と、同一局面を除いた決着がついていない局面の一覧を保存するファイル

次回の記事

1. 筆者も最初はそのことに気づかずに、この後で is_strongly_solved を実行した際に繰り返しの数に 431 ではなく 3191 が表示されてしまい、しばらく原因について悩みました ↩