Pythonで〇×ゲームのAIを一から作成する　その202　ゲーム盤を表すハッシュ可能なデータの計算

Last updated at 2025-11-09Posted at 2025-11-09

目次と前回の記事

Python のバージョンとこれまでに作成したモジュール

本記事のプログラムは Python のバージョン 3.13 で実行しています。また、numpy のバージョンは 2.3.5 です。

以下のリンクから、これまでに作成したモジュールを見ることができます。本文で説明しますが、下記の ai.py は前回のファイルから修正を行っています。

リンク	説明
marubatsu.py	Marubatsu、Marubatsu_GUI クラスの定義
ai.py	AI に関する関数
mbtest.py	テストに関する関数
util.py	ユーティリティ関数の定義
tree.py	ゲーム木に関する Node、Mbtree クラスなどの定義
gui.py	GUI に関する処理を行う基底クラスとなる GUI クラスの定義

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

`ai_match` の修正

前回の記事では 整数型 のデータで 手番とマスを表現する NpIntBoard クラスを定義しましたが、その際に ai_match の表示がおかしくなる という問題が発生することに気が付きましたので、その修正を最初に行うことにします。

下記は、NpIntBoard を利用した場合の ai2 VS ai2 の対戦を ai_match で行う プログラムです。処理がすぐに終わるように対戦回数は 100 回としました。実行結果のように 対戦成績 の 〇と × を表す部分に 1 と 2 が表示 されるという問題があることがわかります。この問題の原因について少し考えてみて下さい。

from marubatsu import NpIntBoard
from ai import ai_match, ai2

ai_match(ai=[ai2, ai2], mbparams={"boardclass": NpIntBoard}, match_num=100)

実行結果

ai2 VS ai2
100%|██████████| 100/100 [00:00<00:00, 4662.41it/s]
count     win    lose    draw
    1      55      33      12
    2      31      57      12
total      86      90      24

ratio     win    lose    draw
    1   55.0%   33.0%   12.0%
    2   31.0%   57.0%   12.0%
total   43.0%   45.0%   12.0%

この問題が発生する原因は、NpIntBoard では 〇の手番を 1、× の手番を 2 という整数型のデータで表現し、ai_match では手番を表示する場所に 手番を表すデータをそのまま表示 しているからです。従って、この問題は下記のプログラムの 7 行目のように対戦成績の各行の先頭に表示する 手番を表す文字列のリスト の中で、〇と × の手番を表す文字列 を 手番を表すデータとその文字列の対応表を利用して計算 することで解決することができます。

1  from marubatsu import Marubatsu
2  from collections import defaultdict
3  from tqdm import tqdm
4  
5  def ai_match(ai, params=[{}, {}], match_num=10000, mbparams={}):
元と同じなので省略
6      # 各行の先頭に表示する文字列のリスト
7      item_text_list = [ mb.board.MARK_TABLE[mb.CIRCLE], mb.board.MARK_TABLE[mb.CROSS], 
8                         "total" ]
元と同じなので省略

行番号のないプログラム

from marubatsu import Marubatsu
from collections import defaultdict
from tqdm import tqdm

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

    # 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][mb.CIRCLE],
            "lose": count_list[0][mb.CROSS],
            "draw": count_list[0][mb.DRAW],
        },
        # ai[1] VS ai[0] の場合の、ai[0] から見た通算成績
        { 
            "win": count_list[1][mb.CROSS],
            "lose": count_list[1][mb.CIRCLE],
            "draw": count_list[1][mb.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 = [ mb.board.MARK_TABLE[mb.CIRCLE], mb.board.MARK_TABLE[mb.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()
        
    return diff_list

修正箇所

from marubatsu import Marubatsu
from collections import defaultdict
from tqdm import tqdm

def ai_match(ai, params=[{}, {}], match_num=10000, mbparams={}):
元と同じなので省略
    # 各行の先頭に表示する文字列のリスト
-   item_text_list = [ mb.CIRCLE, mb.CROSS, "total" ] 
+   item_text_list = [ mb.board.MARK_TABLE[mb.CIRCLE], mb.board.MARK_TABLE[mb.CROSS], "total" ]  元と同じなので省略

上記の修正後に下記の先程と同じプログラムを実行すると、実行結果のように 〇と × の手番が正しく表示 されるようになったことが確認できます。

ai_match(ai=[ai2, ai2], mbparams={"boardclass": NpIntBoard}, match_num=100)

実行結果

ai2 VS ai2
100%|██████████| 100/100 [00:00<00:00, 3923.72it/s]
count     win    lose    draw
o          60      28      12
x          28      59      13
total      88      87      25

ratio     win    lose    draw
o       60.0%   28.0%   12.0%
x       28.0%   59.0%   13.0%
total   44.0%   43.5%   12.5%

ゲーム盤を表すハッシュ可能なデータの計算

前回の記事で NpIntBoard を利用した場合の board_to_str の処理速度 が、NpBoard を利用した場合よりも 遅くなるという問題が発生する ことを示しました。

下記は NpIntBoard クラスと NpBoard クラスの board_to_str メソッドの定義です。

1  # NpIntBoard クラスの場合
2  def board_to_str(self):
3      numlist = self.board.flatten().tolist()
4      strlist = [self.MARK_TABLE[mark] for mark in numlist]
5      return "".join(strlist)
6
7  # NpBoard クラスの場合
8  def board_to_str(self):
9      return "".join(self.board.flatten().tolist())

NpIntBoard では 数値型のデータでマスを表現 するため、上記の 4 行目で 数値型 で表現されたマスのデータを 文字列型のデータに変換 するという処理が必要となり、その分だけ処理速度が遅く なります。

`board_to_str` の目的

本記事で board_to_str を定義した 最初の目的 は、以前の記事で説明したように、局面と最善手の対応表 のデータを、下記のような dict で表現できるようにする ためでした。

dict のキーが局面を表す
dict のキーの値がキーの局面の最善手を表す

以前の記事や下記の Python の公式ドキュメントにもで説明されているように、dict のキーとして利用できる のは ハッシュ可能（hashable）なデータ です。

また、下記の Python の公式ドキュメントに記述されているように、Python では 数値型、文字列型、tuple などの イミュータブル¹な組み込みデータ型は ハッシュ可能 なデータで、list や dict などの ミュータブル な組み込みデータ型は ハッシュ可能なデータではありません。ただし tuple のように 他のオブジェクトを要素として持つ データは、その すべての要素がイミュータブル なデータの場合に ハッシュ可能なデータ となります。

ゲーム盤を表現する 2 次元の list は ハッシュ可能なデータではない ので dict の キーとして利用することはできません。そこで、ゲーム盤を表すデータを ハッシュ可能な文字列型のデータに変換 する board_to_str メソッドを定義し、それを利用して 局面と最善手の対応表のデータを作成 しました。また、board_to_str は ai_abs_dls などの AI の関数 の中で局面と評価値の 置換表を表す dict を作成する際でも利用 されています。

局面と最善手の対応表や、置換表で利用するために ゲーム盤を表すデータ を ハッシュ可能なデータに変換する際 には、ゲーム盤のデータ と 変換後のデータ が 1 対 1 に対応する必要 があります。例えば、異なる 2 つの局面のデータが board_to_str によって同じ文字列に変換された場合は、その 2 つの局面の最善手を dict のキーで区別して記録することができないからです。そのことは明らかだと思いますので証明は省略しますが、board_to_str のように、各マスを表す文字列を結合して変換するという処理はその条件を満たします。

ndarray をハッシュ可能なデータに変換する方法

ゲーム盤を表すデータ を 文字列型のデータに変換した理由 は、文字列を要素として持つ 2 次元の list の要素を結合 して文字列型のデータに 変換する処理 を "".join を利用することで 簡潔に記述できる からです。

別の方法で、より簡潔 にゲーム盤を表すデータを ハッシュ可能なデータに変換 することができれば、その方法を利用してもかまいません。そこで、2 次元の ndarray を ハッシュ可能なデータに変換する方法 をいくつか紹介します。

tuple を利用する方法

一つ目の方法は イミュータブル なデータ型である tuple に変換 するというものです。ただし、下記のプログラムのように 2 次元の ndarray をそのまま tuple に変換 し、その tuple をキーとした dict を作成 しようとすると実行結果のように エラーが発生 します。なお、キーの値には何を代入してもエラーが発生するので下記のプログラムでは 0 を代入しました。

mb = Marubatsu(boardclass=NpIntBoard)
t = tuple(mb.board.board)
print(t)
print({t: 0})

実行結果

---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
Cell In[4], line 4
      2 t = tuple(mb.board.board)
      3 print(t)
----> 4 print({t: 0})

TypeError: unhashable type: 'numpy.ndarray'

実行結果の 最初の行に表示 されるように、2 次元の ndarray を tuple に変換 すると 1 次元の ndarray を要素 として持つ tuple に変換 されます。ndarray はその 要素を後から変更することができる ため ミュータブル なデータなので ハッシュ可能なデータではありません。そのためその tuple をキーとする dict を作成しようとすると上記のように unhashable type: 'numpy.ndarray' というエラーメッセージが表示されます。

この問題は下記のプログラムのように ndarray の flatten メソッドを利用して 1 次元の ndarray に変換 してから tuple に変換 することで解決することができます。実行結果の 1 行目から、変換した tuple の要素 には np.int64(0) という値が代入されていることがわかります。この np.int64(0) は numpy で定義 されている イミュータブルな整数型の 0 であることを表します。従って、変換した tuple のすべての要素はイミュータブル なデータなので ハッシュ可能なデータ となり、dict のキーとして利用 しても エラーは発生しません。

t = tuple(mb.board.board.flatten())
print(t)
print({t: 0})

実行結果

(np.int64(0), np.int64(0), np.int64(0), np.int64(0), np.int64(0), np.int64(0), np.int64(0), np.int64(0), np.int64(0))
{(np.int64(0), np.int64(0), np.int64(0), np.int64(0), np.int64(0), np.int64(0), np.int64(0), np.int64(0), np.int64(0)): 0}

np.int64 は 64 ビット（8 バイト）の 整数型のデータ を表します。整数を何ビットのデータで表現するか によって 表現できる整数の範囲が異なり、np.int64 の場合は $2^{64}$ = 約 1850 京（約 $2 × 10^{19}$)種類の整数を表現することができます。他にも np.int8 や np.int16 などがあり、np.int8 は $2^8$ = 256 種類の整数を表現することができます。

numpy で定義 された np.int64 などの 整数型 のデータは、Python の整数型のデータと同じように 加算や乗算などの 数値計算を行う ことができます。以後の記事では基本的に numpy の整数型 のデータを Python の整数型と区別せずに表記 することにします。

下記は 同じ局面 に対して board_to_str メソッドと上記の tuple で ハッシュ可能な値に変換 する処理の 処理速度を計測 するプログラムです。実行結果からわかるように ndarray を tuple に変換する際 は tolist で list に変換してから行う ことで board_to_str の 約 2 倍の処理速度 になることが確認できます。

%timeit mb.board_to_str()
%timeit tuple(mb.board.board.flatten())
%timeit tuple(mb.board.board.flatten().tolist())

実行結果

1.52 μs ± 27.4 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
1.62 μs ± 28.2 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
743 ns ± 18.2 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)

bytes への変換

ndarray にはデータを Python の組み込みデータ型である bytes に変換 する tobytes メソッドがあり、それを利用して ハッシュ可能なデータに変換 できます。

bytes とは何か

下記の説明は完全に理解しなくても大きな問題はありませんが、bytes が イミュータブルでハッシュ可能 なデータ型であることだけは理解しておいてください。

bytes は tuple とよく似たデータ型 で、下記のような性質を持ちます。

tuple と同様に 複数の要素 を持つ
それぞれの要素は 0 からはじまる整数のインデックスで 参照する
tuple と同様に後から要素の値を変更したり、要素の数を増やすことはできない
従って、bytes は イミュータブル で ハッシュ可能 なデータ型である
bytes の要素には 1 バイト（byte）のデータのみを格納 できる点が tuple と異なる

bytes のデータ tuple と同様に list から作成 することができます。具体的には下記のプログラムのように 1 バイト（= 8 ビット = 2 進数 8 桁）で表現できる 0 ~ 255 の範囲 の 256 種類（$=2^8$）の いずれかの整数を要素として持つ list から作成 できます。

また、下記のプログラムの 3 行目のように bytes は list や tuple と同様 に 0 からはじまる整数のインデックスで個別の要素を参照 することができます。

b = bytes([1, 2, 3])
print(b)
print(b[0])

実行結果

b'\x01\x02\x03'
1

bytes を print で表示 すると上記の実行結果のように b' と ' で囲まれた中 に bytes の 要素が並べて表示 されます。それぞれの要素は \x01 のように表示 されますが、この 先頭の \x² は その後ろの 2 文字が 16 進数で表現される 1 バイトの整数 であることを表します。b'\x01\x02\x03' は先頭から順に 1、2、3 の 3 つの要素を持つ ことを表します。

16 進数の表記方法について説明すると長くなるので、下記の Wikipedia の 16 進数の記事などを参考にして下さい。

コンピューターでは 1 バイトのデータを 16 進数で表示することがよくありますが、これは 16 進数で表記することで、1 バイトのデータを必ず 2 文字で簡潔に表記できるからです。それに対して 1 バイトのデータを 2 進数で表記すると 00001101 のように 8 文字が必要となります。

下記のプログラムのように 0 ~ 255 の範囲外の値 を要素として持つ list を記述して bytes を作成 しようとすると、bytes の要素は 0 以上 256 未満の値でなければならないということを表す bytes must be in range(0, 256) という エラーが発生 します。

bytes([300])

実行結果

---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
Cell In[8], line 1
----> 1 bytes([300])

ValueError: bytes must be in range(0, 256)

また、bytes は イミュータブル なデータなので、下記のプログラムのように 要素に値を代入 しようとすると bytes には値を代入（assignment）できないことを表す 'bytes' object does not support item assignment という エラーが発生 します。

b[0] = 5

実行結果

---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
Cell In[9], line 1
----> 1 b[0] = 5

TypeError: 'bytes' object does not support item assignment

bytes はイミュータブルで ハッシュ可能なデータ なので、下記のプログラムのように dict のキーとして利用 することができます。

print({b: 0})

実行結果

{b'\x01\x02\x03': 0}

他の方法で bytes を作成することもできます。また、今回の記事では利用しませんが bytes と同様の性質を持つ bytesarray というミュータブルな組み込みデータ型もあります。詳細は下記のリンク先を参照して下さい。

ndarray の `tobytes` メソッドの利用法

ndarray は データを コンピュータの 連続したメモリに記録 しており、tobytes メソッドは そのデータをコピーしたものを bytes 型のデータとして返す という処理を行います。

以前の記事で説明したように、list や tuple の要素はオブジェクトなので、そのデータは連続したメモリに記録されていません。そのため、list や tuple には tobytes メソッドはありません。なお、Python の組み込みデータ型である array はデータを連続したメモリに記録しているので tobytes メソッドがあります。

array の tobytes メソッドについては下記のリンク先を参照して下さい。

これまでに紹介した "".join による 文字列の結合 や tuple への変換 は、ゲーム盤を表すデータを 異なるデータ型に変換 するという処理を行っていましたが、ndarray の tobytes メソッドが行う処理は、ndarray が メモリに連続して記録するデータをそのまま取り出す という処理を行っているので、高速に処理を行う ことができます。また、ndarray が内部で記録しているデータを そのまま取り出している ので、ゲーム盤を表すデータ と取り出した bytes のデータは 1 対 1 に対応 します。

下記は、先程の NpIntBoard を利用した ゲーム盤を表す ndarray に対して tobytes メソッドを呼び出すことで、ゲーム盤を表す bytes のデータを表示 するプログラムです。また、3 行目では取り出した bytes のデータをキーとする dict を作成 していますが、bytes のデータは ハッシュ可能なデータ なので エラーは発生しません。

b = mb.board.board.tobytes()
print(b)
print({b: 0})

実行結果

b'\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00'
{b'\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00': 0}

ndarray 内の ゲーム盤のマスを表すデータ は先ほど示したように np.int64 という 64 ビット = 8 バイトのデータで表現 されるので、上記の \x00\x00\x00\x00\x00\x00\x00\x00 の 8 バイト分のデータ が 1 つのマスを表す 整数のデータ です。8 バイトすべてが 0 であることからこのデータは 空のマスを表す整数の 0 を表します。

下記は tobytes の処理時間を計測 するプログラムです。実行結果の 90.1 ns は先ほどの tuple による変換処理 の処理時間である 743 ns の 約 8 分の 1 の時間なので、この方法で ハッシュ可能なデータへの変換処理 を 高速に行うことができる ことが確認できました。

%timeit mb.board.board.tobytes()

実行結果

90.1 ns ± 3.6 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)

そこで、本記事ではこの方法で ndarray で表現されたゲーム盤のデータをハッシュ可能なデータに変換するようにプログラムを修正することにします。

`board_to_hashable` メソッドの定義

下記の理由から、これまで利用してきた board_to_str メソッドはそのまま残す ことにし、ゲーム盤のデータをハッシュ可能なデータに変換する board_to_hashable メソッドを新たに定義 することにします。

後述するように、ai_gt6 などの 一部の AI の関数 や、gui_play などで board_to_str を利用して作成した 文字列をキーとした dict を利用 している
AI の関数以外 で利用されている board_to_str の処理は、GUI で対戦を行う場合など、処理速度が多少遅くても 人間にとっては そのことが感知できない ため board_to_str をそのまま利用し続けても大きな問題は発生しない

board_to_hashable メソッドはゲーム盤を表すクラスの基底クラスである Board クラスの抽象メソッド とし、それぞれのクラスで定義 することにします。

下記はそのように board_to_hashable メソッドを定義するプログラムです。

4 ~ 8 行目：Board クラスの抽象メソッドとして定義する
10 ~ 13 行目：ListBoard クラスの board_to_hashable が行う処理は board_to_str と変わらないので board_to_str の返り値を返すように定義する。List1dBoard と ArrayBoard クラスも同様で、それらのクラスは ListBoard クラスを継承して定義しているので board_to_hashable をそれらのクラスに定義する必要はない
15 ~ 19 行目：NpBoard とクラスの board_to_hashable を tobytes を利用して計算するように定義する。上記と同様の理由で NpIntBoard クラスでは定義する必要はない

 1  from abc import abstractmethod
 2  from marubatsu import Board, ListBoard, NpBoard
 3  
 4  @abstractmethod
 5  def board_to_hashable(self):
 6      pass
 7  
 8  Board.board_to_hashable = board_to_hashable
 9  
10  def board_to_hashable(self):
11      return self.board_to_str()
12  
13  ListBoard.board_to_hashable = board_to_hashable
14  
15  def board_to_hashable(self):
16      return self.board.tobytes()
17  
18  NpBoard.board_to_hashable = board_to_hashable

行番号のないプログラム

from abc import abstractmethod
from marubatsu import Board, ListBoard, NpBoard

@abstractmethod
def board_to_hashable(self):
    pass

Board.board_to_hashable = board_to_hashable

def board_to_hashable(self):
    return self.board_to_str()

ListBoard.board_to_hashable = board_to_hashable

def board_to_hashable(self):
    return self.board.tobytes()

NpBoard.board_to_hashable = board_to_hashable
NpIntBoard.board_to_hashable = board_to_hashable

board_to_str は、Marubatsu クラスのメソッドとしても定義 しているので、board_to_hashable も下記のプログラムのように Marubatsu クラスのメソッドとして定義 することにします。

def board_to_hashable(self):
    return self.board.board_to_hashable()

Marubatsu.board_to_hashable = board_to_hashable

`calc_same_boardtexts` メソッドの修正

ai_abs_dls などの 置換表を利用する AI の関数 では、calc_same_boardtexts メソッドで 同一局面を表す文字列型のデータを計算 することで、同一局面の評価値を置換表に登録 するという処理を行っています。そのため、calc_same_boardtexts 内の board_to_str を board_to_hashable に修正 する必要があります。

また、board_to_hashable が計算する値は 文字列型のデータとは限らない ので、そのように修正すると メソッドの名前と行う処理が異なってしまう ようになります。そこで、メソッドの名前を calc_same_hashables に修正 することにします。

下記はそのように ListBoard クラスの calc_same_hashables を修正したプログラムです。なお、List1dBoard と ArrayBoard クラスの calc_same_hashables が 行う処理は同じ で、ListBoard を継承して利用できるので 定義する必要はありません。

3 行目：メソッドの名前を calc_same_hashables に修正した
12、14、21、25、26 行目：boardtxts を hashables に修正した
12、14 行目：self.board_to_str を self.board_to_hashable に修正した

 1  import numpy as np
 2  
 3  def calc_same_hashables(self, move=None):
 4      data = [ [ 0,  0,  1, 1, -1,  0,  1,  0, -1, 0,  1,  0],
 5              [ 1, -1,  0, 1,  0, -1] * 2,
 6              [ 1,  0, -1, 0,  1,  0,  0,  0,  1, 1, -1,  0],
 7              [ 1, -1,  0, 0,  0,  1] * 2,
 8              [ 0,  1,  0, 1,  0, -1] * 2,
 9              [ 1,  0, -1, 1, -1,  0] * 2,
10              [ 0,  0,  1, 0,  1,  0] * 2, ]
11      if move is None:
12          hashables = set([self.board_to_hashable()])
13      else:
14          hashables = { self.board_to_hashable(): move }
15      for xa, xb, xc, ya, yb, yc, xa2, xb2, xc2, ya2, yb2, yc2 in data:
16          txt = ""
17          for x in range(self.BOARD_SIZE):
18              for y in range(self.BOARD_SIZE):
19                  txt += self.getmark(xa * (self.BOARD_SIZE - 1) + xb * x + xc * y, ya * (self.BOARD_SIZE - 1) + yb * x + yc * y)
20          if move is None:
21              hashables.add(txt)
22          else:
23              x, y = self.move_to_xy(move)
24              x, y = xa2 * (self.BOARD_SIZE - 1) + xb2 * x + xc2 * y, ya2 * (self.BOARD_SIZE - 1) + yb2 * x + yc2 * y
25              hashables[txt] = self.xy_to_move(x, y)
26      return hashables     
27  
28  ListBoard.calc_same_hashables = calc_same_hashables

行番号のないプログラム

import numpy as np

def calc_same_hashables(self, move=None):
    data = [ [ 0,  0,  1, 1, -1,  0,  1,  0, -1, 0,  1,  0],
            [ 1, -1,  0, 1,  0, -1] * 2,
            [ 1,  0, -1, 0,  1,  0,  0,  0,  1, 1, -1,  0],
            [ 1, -1,  0, 0,  0,  1] * 2,
            [ 0,  1,  0, 1,  0, -1] * 2,
            [ 1,  0, -1, 1, -1,  0] * 2,
            [ 0,  0,  1, 0,  1,  0] * 2, ]
    if move is None:
        hashables = set([self.board_to_hashable()])
    else:
        hashables = { self.board_to_hashable(): move }
    for xa, xb, xc, ya, yb, yc, xa2, xb2, xc2, ya2, yb2, yc2 in data:
        txt = ""
        for x in range(self.BOARD_SIZE):
            for y in range(self.BOARD_SIZE):
                txt += self.getmark(xa * (self.BOARD_SIZE - 1) + xb * x + xc * y, ya * (self.BOARD_SIZE - 1) + yb * x + yc * y)
        if move is None:
            hashables.add(txt)
        else:
            x, y = self.move_to_xy(move)
            x, y = xa2 * (self.BOARD_SIZE - 1) + xb2 * x + xc2 * y, ya2 * (self.BOARD_SIZE - 1) + yb2 * x + yc2 * y
            hashables[txt] = self.xy_to_move(x, y)
    return hashables     

ListBoard.calc_same_hashables = calc_same_hashables

修正箇所

import numpy as np

-def calc_same_boardtexts(self, move=None):
+def calc_same_hashables(self, move=None):
    data = [ [ 0,  0,  1, 1, -1,  0,  1,  0, -1, 0,  1,  0],
            [ 1, -1,  0, 1,  0, -1] * 2,
            [ 1,  0, -1, 0,  1,  0,  0,  0,  1, 1, -1,  0],
            [ 1, -1,  0, 0,  0,  1] * 2,
            [ 0,  1,  0, 1,  0, -1] * 2,
            [ 1,  0, -1, 1, -1,  0] * 2,
            [ 0,  0,  1, 0,  1,  0] * 2, ]
    if move is None:
-       boardtexts = set([self.board_to_str()])
+       hashables = set([self.board_to_hashable()])
    else:
-       boardtexts = { self.board_to_str(): move }
+       hashables = { self.board_to_hashable(): move }
    for xa, xb, xc, ya, yb, yc, xa2, xb2, xc2, ya2, yb2, yc2 in data:
        txt = ""
        for x in range(self.BOARD_SIZE):
            for y in range(self.BOARD_SIZE):
                txt += self.getmark(xa * (self.BOARD_SIZE - 1) + xb * x + xc * y, ya * (self.BOARD_SIZE - 1) + yb * x + yc * y)
        if move is None:
-           boardtexts.add(txt)
+           hashables.add(txt)
        else:
            x, y = self.move_to_xy(move)
            x, y = xa2 * (self.BOARD_SIZE - 1) + xb2 * x + xc2 * y, ya2 * (self.BOARD_SIZE - 1) + yb2 * x + yc2 * y
-           boardtexts[txt] = self.xy_to_move(x, y)
+           hashables[txt] = self.xy_to_move(x, y)
-   return boardtexts     
+   return hashables     

ListBoard.calc_same_hashables = calc_same_hashables

下記はそのように NpBoard クラスの calc_same_hashables を修正したプログラムです。なお、NpIntBoard クラスの calc_same_hashables が 行う処理は同じ で、NpBoard を継承して利用できるので 定義する必要はありません。

1 行目：メソッドの名前を calc_same_hashables に修正した
3、5、16、22、24 行目：boardtxts を hashables に修正した
3、5、14 行目：self.board_to_str を self.board_to_hashable に修正した
14、16、22 行目：txt を hashable に修正した

 1  def calc_same_hashables(self, move=None):
 2      if move is None:
 3          hashables = set([self.board_to_hashable()])
 4      else:
 5          hashables = { self.board_to_hashable(): move }
 6      boardorig = self.board
 7      if move is not None:
 8          x, y = self.move_to_xy(move)
 9      for i in range(7):
10          if i != 3:
11              self.board = np.rot90(self.board)
12          else:
13              self.board = np.fliplr(self.board)
14          hashable = self.board_to_hashable()
15          if move is None:
16              hashables.add(hashable)
17          else:
18              if i == 3:
19                  y = self.BOARD_SIZE - y - 1
20              else:
21                  x, y = self.BOARD_SIZE - y - 1, x
22              hashables[hashable] = self.xy_to_move(x, y)
23      self.board = boardorig
24      return hashables
25  
26  NpBoard.calc_same_hashables = calc_same_hashables

行番号のないプログラム

def calc_same_hashables(self, move=None):
    if move is None:
        hashables = set([self.board_to_hashable()])
    else:
        hashables = { self.board_to_hashable(): move }
    boardorig = self.board
    if move is not None:
        x, y = self.move_to_xy(move)
    for i in range(7):
        if i != 3:
            self.board = np.rot90(self.board)
        else:
            self.board = np.fliplr(self.board)
        hashable = self.board_to_hashable()
        if move is None:
            hashables.add(hashable)
        else:
            if i == 3:
                y = self.BOARD_SIZE - y - 1
            else:
                x, y = self.BOARD_SIZE - y - 1, x
            hashables[hashable] = self.xy_to_move(x, y)
    self.board = boardorig
    return hashables

NpBoard.calc_same_hashables = calc_same_hashables

修正箇所

-def calc_same_boardtexts(self, move=None):
+def calc_same_hashables(self, move=None):
    if move is None:
-       boardtexts = set([self.board_to_str()])
+       hashables = set([self.board_to_hashable()])
    else:
-       boardtexts = { self.board_to_str(): move }
+       hashables = { self.board_to_hashable(): move }
    boardorig = self.board
    if move is not None:
        x, y = self.move_to_xy(move)
    for i in range(7):
        if i != 3:
            self.board = np.rot90(self.board)
        else:
            self.board = np.fliplr(self.board)
-       txt = self.board_to_str()
+       hashable = self.board_to_hashable()
        if move is None:
-           boardtexts.add(txt)
+           hashables.add(hashable)
        else:
            if i == 3:
                y = self.BOARD_SIZE - y - 1
            else:
                x, y = self.BOARD_SIZE - y - 1, x
-           boardtexts[txt] = self.xy_to_move(x, y)
+           hashables[hashable] = self.xy_to_move(x, y)
    self.board = boardorig
-   return boardtexts
+   return hashables

NpBoard.calc_same_hashables = calc_same_hashables

tree.py 内で util.py 内で定義された calc_same_boardtexts が呼び出されている部分があることに気が付いたのですが、修正しなくてもプログラムは正しく動作するので修正しないことにします。気になる方は修正して下さい。

ai.py の修正

ai.py 内で board_to_str と calc_same_boardtexts を呼び出している部分を 修正する必要 があります。主な修正内容は下記の通りですが、修正箇所が多いため プログラムを記述して実行するのではなく、今回の記事では ai.py の方に修正 しておきました。

board_to_str を board_to_hashable に修正する
board_to_str を代入する変数名を boardtxt から hashable に修正する
calc_same_boardtexts を calc_same_hashables に修正する
calc_same_hashables を代入する変数名を boardtxtlist から hashables に修正する

ただし、下記の board_to_str は、board_to_str を利用して作成した 文字列をキーとした dict を利用 しているため、修正してはいけない 点に注意が必要です。

# ai_gt6 内の下記の部分
    return bestmoves_by_board[mb.board_to_str()]

#ai_gt7 内の下記の 2 箇所
    candidate = bestmoves_and_score_by_board[mborig.board_to_str()]["bestmoves"]

    score_by_move[move] = bestmoves_and_score_by_board[mb.board_to_str()]["score"]

プログラムの修正箇所

具体的なプログラムの修正箇所は以下の通りです。

ai_by_mmscore

-boardtxt = mb.board_to_str()
+hashable = mb.board_to_hashable()
-if boardtxt in tt:
+if hashable in tt:
-    _, _, bestmove = tt[boardtxt]
+    _, _, bestmove = tt[hashable]

ai_mmdfs

-boardtxt = mborig.board_to_str()
+hashable = mborig.board_to_hashable()
-if boardtxt in tt:
+if hashable in tt:
-    return tt[boardtxt]
+    return tt[hashable]

-boardtxtlist = mborig.board.calc_same_boardtexts()
+hashables = mborig.board.calc_same_hashables()
-for boardtxt in boardtxtlist:
+for hashable in hashables:
-    tt[hashable] = score
+    tt[boardtxt] = score

ai_abs_tt

-boardtxt = mborig.board_to_str()
+hashable = mborig.board_to_hashable()
-key = (boardtxt, alpha, beta)
+key = (hashable, alpha, beta)

-boardtxtlist = mborig.board.calc_same_boardtexts()
+hashables = mborig.board.calc_same_hashables()
_, alpha, beta = key
-for boardtxt in boardtxtlist:
+for hashable in hashables:
-    tt[(boardtxt, alpha, beta)] = score
+    tt[(hashable, alpha, beta)] = score

ai_abs_tt2、ai_abs_tt3、ai_abs_tt4、ai_nws_3score、ai_abs_all、ai_scout、ai_mtdf

-boardtxt = mborig.board_to_str()
+hashable = mborig.board_to_hashable()
-if boardtxt in tt:
+if hashable in tt:
-    lower_bound, upper_bound = tt[boardtxt]
+    lower_bound, upper_bound = tt[hashable]

-boardtxtlist = mborig.board.calc_same_boardtexts()
+hashables = mborig.board.calc_same_hashables()
略
-for boardtxt in boardtxtlist:
+for hashable in hashables:
-    tt[boardtxt] = (lower_bound, upper_bound)
+    tt[hashable] = (lower_bound, upper_bound)

ai_mmdfs_all

-boardtxt = mborig.board_to_str()
+hashable = mborig.board_to_hashable()
-if use_tt and boardtxt in tt:
+if use_tt and hashable in tt:
-    return tt[boardtxt]
+    return tt[hashable]

if use_tt:
-    boardtxtlist = mborig.board.calc_same_boardtexts()
+    hashables = mborig.board.calc_same_hashables()
-    for boardtxt in boardtxtlist:
+    for hashable in hashables:
-        tt[boardtxt] = score
+        tt[hashable] = score

ai_abs_dls

if use_tt:
-    boardtxt = mborig.board_to_str()
+    hashable = mborig.board_to_hashable()
-    if boardtxt in tt:
+    if hashable in tt:
-        lower_bound, upper_bound, _ = tt[boardtxt]
+        lower_bound, upper_bound, _ = tt[hashable]

if not use_tt:
-    boardtxt = mborig.board_to_str()
+    hashable = mborig.board_to_hashable()	
-        if boardtxt in tt_for_mo:
+        if hashable in tt_for_mo:
-            _, _, bestmove = tt_for_mo[boardtxt]
+            _, _, bestmove = tt_for_mo[hashable]

if use_tt:
-    boardtxtlist = mborig.board.calc_same_boardtexts(bestmove)
+    hashables = mborig.board.calc_same_hashables(bestmove)
略
-    for boardtxt, move in boardtxtlist.items():
+    for hashable, move in hashables.items():
-        tt[boardtxt] = (lower_bound, upper_bound, move)
+        tt[hashable] = (lower_bound, upper_bound, move)

ai_pvs_dls

-boardtxt = mborig.board_to_str()
+hashable = mborig.board_to_hashable()
-if boardtxt in tt:
+if hashable in tt:	
+    lower_bound, upper_bound, _ = tt[boardtxt]
-    lower_bound, upper_bound, _ = tt[hashable]

if tt_for_mo is not None:
-    if boardtxt in tt_for_mo:
+    if hashable in tt_for_mo:
-        _, _, bestmove = tt_for_mo[boardtxt]
+        _, _, bestmove = tt_for_mo[hashable]

-boardtxtlist = mborig.board.calc_same_boardtexts(bestmove)
+hashables = mborig.board.calc_same_hashables(bestmove)
略
-for boardtxt, move in boardtxtlist.items():
+for hashable, move in hashables.items():
-    tt[boardtxt] = (lower_bound, upper_bound, move)
+    tt[hashable] = (lower_bound, upper_bound, move)

処理速度の比較

上記の修正を行った ai_abs_dls に対して、下記のプログラムで これまでのベンチマークと同じ条件 で 処理時間を計測 することにします。なお、ai2 と ai14s では今回の記事で修正を行った board_to_hashable と cals_same_hashables を利用していない ので ai2 VS ai2 と ai14s VS ai2 のベンチマークは行わないことにします。

from marubatsu import  List1dBoard, ArrayBoard
from ai import ai14s, ai_abs_dls

for boardclass in [ListBoard, List1dBoard, ArrayBoard, NpBoard, NpIntBoard]:
    for count_linemark in [False, True]:
        print(f"boardclass: {boardclass.__name__}, count_linemark {count_linemark}")
        mb = Marubatsu(boardclass=boardclass, count_linemark=count_linemark)
        eval_params = {"minimax": True}
        %timeit ai_abs_dls(mb, eval_func=ai14s, eval_params=eval_params, use_tt=True, maxdepth=8)

実行結果

boardclass: ListBoard, count_linemark False
18 ms ± 255 μs per loop (mean ± std. dev. of 7 runs, 100 loops each)
boardclass: ListBoard, count_linemark True
17 ms ± 313 μs per loop (mean ± std. dev. of 7 runs, 100 loops each)
boardclass: List1dBoard, count_linemark False
18.2 ms ± 1.6 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
boardclass: List1dBoard, count_linemark True
16.7 ms ± 300 μs per loop (mean ± std. dev. of 7 runs, 100 loops each)
boardclass: ArrayBoard, count_linemark False
18.8 ms ± 390 μs per loop (mean ± std. dev. of 7 runs, 100 loops each)
boardclass: ArrayBoard, count_linemark True
18.1 ms ± 233 μs per loop (mean ± std. dev. of 7 runs, 100 loops each)
boardclass: NpBoard, count_linemark False
45.7 ms ± 2.28 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
boardclass: NpBoard, count_linemark True
40.3 ms ± 2.52 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
boardclass: NpIntBoard, count_linemark False
43.8 ms ± 2.21 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
boardclass: NpIntBoard, count_linemark True
40 ms ± 1.42 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

下記は以前の記事と前回の記事の ai_abs_dls のベンチマークの結果 に上記の実行結果を加えた表です。下段が上記の実行結果 を表します。

boardclass	count_linemark	`ai_abs_dls`
ListBoard	`False`	17.9 ms 18.0 ms
ListBoard	`True`	18.0 ms 17.0 ms
List1dBoard	`False`	17.0 ms 18.2 ms
List1dBoard	`True`	17.7 ms 16.7 ms
ArrayBoard	`False`	18.3 ms 18.8 ms
ArrayBoard	`True`	18.5 ms 18.1 ms
NpBoard	`False`	50.4 ms 45.7 ms
NpBoard	`True`	45.0 ms 40.3 ms
NpIntBoard	`False`	51.7 ms 43.8 ms
NpIntBoard	`True`	48.9 ms 40.0 ms

上記の表から今回の修正の 影響を受けない ListBoard、List1dBoard、ArrayBoard の 処理速度はほとんど変化しません が、今回の 修正の影響を受ける NpBoard と NpIntBoard の 処理速度が改善 したことが確認できます。また、修正前 は NpBoard のほうが NpIntBoard よりも 処理速度が高速 でしたが、calc_same_hashable が同じ tobytes で計算を行う ことになったことで両者の 処理速度がほぼ同じになる ことが確認できました。

下記は前回の記事の NpBoard と NpIntBoard のベンチマークの結果の表の ai_abs_dls の処理速度を上記の結果で修正したものです。この表から 数値型 のデータで手番とマスを表現する NpIntBoard を利用したほうが 文字列型 で手番とマスを表現する NpBoard を利用する よりも処理速度が同じか速くなる ことが確認できました。

boardclass	count_linemark	`ai2` VS `ai2`	`ai14s` VS `ai2`	`ai_abs_dls`
NpBoard	`False`	5972.04 回/秒	692.95 回/秒	44.1 ms
NpIntBoard	`False`	7185.05 回/秒	723.75 回/秒	43.5 ms
NpBoard	`True`	7478.88 回/秒	1894.42 回/秒	39.8 ms
NpIntBoard	`True`	9820.80 回/秒	2030.51 回/秒	38.5 ms

ListBoard などに対する tuple の利用

ndarray と異なり、ListBoard のように list を利用してゲーム盤を表現 する場合は bytes に変換することはできませんが、tuple に変換 することで "".join よりも高速 に ハッシュ可能な値に変換 することができます。ListBoard の場合は下記のプログラムのように 2 次元の list から 1 次元の list を作成してから tuple に変換 する必要があります。

mb = Marubatsu(boardclass=ListBoard)
l = []
for col in mb.board.board:
    l += col
t = tuple(l)
print(t)

実行結果

('.', '.', '.', '.', '.', '.', '.', '.', '.')

下記は board_to_str と 上記の処理速度を計測 するプログラムです。

%timeit mb.board_to_str()

実行結果

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

%%timeit

l = []
for col in mb.board.board:
    l += col
t = tuple(l)

実行結果

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

実行結果から tuple に変換 したほうが 処理速度が約 2 倍になる ことが確認できました。

ただし、残念ながら ListBoard クラスの board_to_hashable の処理を下記のプログラムのように 修正して ai_abs_dls の処理速度を計測 すると、実行結果のように 先程の 18 ms と比較して約 5 倍も処理速度遅く なってしまいます。

def board_to_hashable(self):
    l = []
    for col in self.board:
        l += col
    return tuple(l)

ListBoard.board_to_hashable = board_to_hashable

boardclass = ListBoard
for count_linemark in [False, True]:
    print(f"boardclass: {boardclass.__name__}, count_linemark {count_linemark}")
    mb = Marubatsu(boardclass=boardclass, count_linemark=count_linemark)
    eval_params = {"minimax": True}
    %timeit ai_abs_dls(mb, eval_func=ai14s, eval_params=eval_params, use_tt=True, maxdepth=8)

実行結果

boardclass: ListBoard, count_linemark False
113 ms ± 3.85 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
boardclass: ListBoard, count_linemark True
105 ms ± 1.12 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

このようなことが起きる原因は、tuple をキー とした場合の dict の要素の参照速度 にあります。下記は__以下のキーを 100 個ずつ持つ dict__ を作成し、それぞれの場合のキーの値を参照 する処理の 処理時間を計測 するプログラムです。下記で 文字列の文字の数 と tuple と bytes の 要素の数を 9 としたのは、〇× ゲーム の board_to_str と board_to_hashable で 作成されるデータ だからです。

2 行目：数値型のデータ
4 ~ 6 行目：文字数が 1、9、100 の文字列型データ
7 ~ 9 行目：文字列型の要素の数が 1、9、100 の tuple
10 ~ 12 行目：要素の数が 1、9、100 の bytes
14 ~ 20 行目：それぞれのデータ型のキーを要素として持つ list を作成し、繰り返し処理によってデータ型のキーの参照の処理速度を計測して表示する

 1  t = {}
 2  for i in range(100):
 3      t[i] = 0
 4      t[str(i)] = 0
 5      t[str(i) * 9] = 0
 6      t[str(i) * 100] = 0
 7      t[tuple([str(i)])] = 0
 8      t[tuple([str(i)] * 9)] = 0
 9      t[tuple([str(i)] * 100)] = 0
10      t[bytes([i])] = 0
11      t[bytes([i] * 9)] = 0
12      t[bytes([i] * 100)] = 0
13  
14  keylist = [0, "0", "0" * 9, "0" * 100, 
15             tuple(["0"]), tuple(["0"] * 9), tuple(["0"] * 100),
16             bytes([0]), bytes([0] * 9), bytes([0] * 100)]
17  
18  for key in keylist:
19      print(f"key = {key}")
20      %timeit t[key]

行番号のないプログラム

t = {}
for i in range(100):
    t[i] = 0
    t[str(i)] = 0
    t[str(i) * 9] = 0
    t[str(i) * 100] = 0
    t[tuple([str(i)])] = 0
    t[tuple([str(i)] * 9)] = 0
    t[tuple([str(i)] * 100)] = 0
    t[bytes([i])] = 0
    t[bytes([i] * 9)] = 0
    t[bytes([i] * 100)] = 0

keylist = [0, "0", "0" * 9, "0" * 100, 
           tuple(["0"]), tuple(["0"] * 9), tuple(["0"] * 100),
           bytes([0]), bytes([0] * 9), bytes([0] * 100)]

for key in keylist:
    print(f"key = {key}")
    %timeit t[key]

実行結果

key = 0
33.8 ns ± 1.09 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
key = 0
44.3 ns ± 1.26 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
key = 000000000
46.8 ns ± 1.75 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
key = 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
48.9 ns ± 1.91 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
key = ('0',)
63.7 ns ± 2.08 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
key = ('0', '0', '0', '0', '0', '0', '0', '0', '0')
186 ns ± 12.7 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
key = ('0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0')
1.46 μs ± 17.9 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
key = b'\x00'
33.5 ns ± 1.23 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
key = b'\x00\x00\x00\x00\x00\x00\x00\x00\x00'
46.9 ns ± 0.392 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
key = b'\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00'
50.8 ns ± 1.34 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)

下記は上記の結果をまとめた表です。

	処理時間
数値型	33.8 ns
1 文字の文字列	44.3 ns
9 文字の文字列	46.8 ns
100 文字の文字列	48.9 ns
要素が 1 つの tuple	63.7 ns
要素が 9 つの tuple	186.0 ns
要素が 100 の tuple	1460.0 ns
要素が 1 つの bytes	33.5 ns
要素が 9 つの bytes	46.9 ns
要素が 100 の bytes	50.8 ns

実行結果から以下の事がわかります。

キーのデータの 要素の数が 1 の場合³は、dict の要素の参照の処理時間は「整数型 = bytes < 文字列型 < tuple」のようになる
文字列型 の場合は文字数が多いほうが若干処理速度が遅くなるが、大きくは変わらない
tuple の場合は 要素の数が多いほうが 参照の処理速度が 大きく遅くなる
bytes の場合は 要素の数が多いほうが 参照の処理速度が 若干遅くなる
〇× ゲームの場合に対応する 要素が 9 の文字列、tuple、bytes の場合は、文字列と bytes がほぼ同じ 処理速度で、tuple の場合は処理速度がそれらと比べて 約 4 倍ほど遅い

このことから、ゲーム盤のデータ を tuple に変換 する処理は "".join で 文字列に変換するよりも高速 になりますが、9 文字の文字列をキー とする dict を参照 した場合よりも、9 つの要素を持つ tuple をキー とする dict を参照するほうが 処理速度がかなり遅くなる ため、全体として ai_abs_dls の処理速度が 大幅に遅くなります。

一方、ゲーム盤のデータ を bytes に変換 する処理は "".join で 文字列に変換するよりも高速 になり、9 文字の文字列をキーとする dict を参照した場合と 9 つの要素を持つ bytes をキー とする dict を参照する 処理速度がほぼ同じ であるため、全体として ai_abs_dls の処理速度が 若干速くなります。

上記の結果から、ListBoard クラスなどの board_to_hashable の処理は board_to_str を呼び出す処理のままにすることにします。

ハッシュ値を利用した置換表

今回の記事では、ゲーム盤を表すデータ と 1 対 1 に対応 する ハッシュ可能なデータ を利用する方法を紹介しましたが、この方法では ゲーム盤のサイズが大きくなる と ハッシュ可能なデータ の データサイズが大きくなる という問題が発生します。

例えば〇× ゲームのような 3 × 3 のゲーム盤 の場合は マスの数が 9 ですが、囲碁のような 19 × 19 のゲーム盤の場合は マスの数が 19 × 19 = 361 となるため、ハッシュ可能なデータ のデータサイズも 約 40 倍 になります。このように、ハッシュ可能なデータ のデータ サイズが大きくなるとメモリに多くのデータが入りきらなくなる という問題が発生します。そのため、ゲーム盤を表すデータ を 1 対 1 に変換するのではなく、特定の大きさのデータに変換 することでデータサイズを小さく済ますのが一般的です。

このような、特定の計算方法 によって 任意のデータ を 特定の大きさのデータ変換 したデータのことを ハッシュ値 と呼びます。また、その手順 のことを ハッシュ関数 と呼びます。

将棋や囲碁 などのゲームでは 置換表のデータサイズを小さくするため に、ゲーム盤のデータ を 数バイト程度の大きさのハッシュ値に変換する のが一般的だと思います。

ハッシュ値 は 異なるデータが同じデータであるかどうかを高速に判定 したり、大量のデータの中から特定のデータを検索 する際などで利用されます。例えば Python の dict は キーのハッシュ値を計算 することで、キーの値を高速に参照 しています。また、そのことが dict のキーがハッシュ可能なデータでなければならない理由です。

ハッシュ値のデータサイズが小さい と、異なるデータ に対して計算された ハッシュ値が一致してしまう ことがあり、そのような状況を ハッシュの衝突 と呼びます。本記事の board_to_hashable ではゲーム盤とハッシュ可能なデータが 1 対 1 に対応するように計算したのでハッシュの衝突はおきませんが、ハッシュの衝突が起きる と ハッシュ値から元のデータを区別できなくなる ので、何らかの対策が必要 です。その対策については長くなるので省略しますが興味がある方は調べてみると良いでしょう。

ハッシュ は 大きなものを特定の手順に従って小さなデータに変換する処理 の事を表し、文章でいうと要約 に相当します。ハッシュ はコンピューターで良く使われている重要なものですが、コンピューター以外の場面でも良く使われています。例えば、X などの SNS でつけられている ハッシュタグ は、投稿した文章 を 一言で要約したもの で、ハッシュタグを利用して 大量の投稿記事 の中から 特定の内容の投稿を検索 することができます。また、ハッシュは 暗号の技術と組み合わせる ことで、文章が改ざんされていないかどうかを調べる ためなど、様々な用途で利用されています。

参考までに下記に Wikipedia のハッシュ関数の項目を下記に紹介します。その中にハッシュの様々な用途が記載されているので興味がある方は参考にして下さい。

今回の記事のまとめ

今回の記事では、ゲーム盤を表すデータ を tuple を利用する場合と、ndarray の tobytes メソッドを利用して ハッシュ可能な bytes のデータに高速に変換 する方法を紹介しました。この方法を利用することで AI の関数の中で 置換表を利用する処理速度が高速 になります。

また、今回の記事の修正を行うことで ndarray を利用した場合に、手番とマスを表すデータ を 文字列型から数値型のデータに変更 することで 処理速度が向上する ことを示しました。

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

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

次回の記事

近日公開予定です

ミュータブルなデータはオブジェクトが管理するデータを後から書き換えることができるもの、イミュータブルなデータは書き換えることができないものを表します。忘れた方は以前の記事を復習して下さい ↩
\x のように \ とアルファベット 1 文字で始まる記述をエスケープシーケンスと呼び、特別な意味を持ちます。エスケープシーケンスの詳細については https://docs.python.org/ja/3.14/reference/lexical_analysis.html#escape-sequences を参照して下さい ↩
データが 1 つしかない数値型のデータも含めます ↩

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up

Pythonで〇×ゲームのAIを一から作成する その202 ゲーム盤を表すハッシュ可能なデータの計算

目次と前回の記事

Python のバージョンとこれまでに作成したモジュール

ai_match の修正

ゲーム盤を表すハッシュ可能なデータの計算

board_to_str の目的

ndarray をハッシュ可能なデータに変換する方法

tuple を利用する方法

bytes への変換

bytes とは何か

ndarray の tobytes メソッドの利用法

board_to_hashable メソッドの定義

calc_same_boardtexts メソッドの修正

ai.py の修正

プログラムの修正箇所

処理速度の比較

ListBoard などに対する tuple の利用

ハッシュ値を利用した置換表

今回の記事のまとめ

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

次回の記事

Pythonで〇×ゲームのAIを一から作成する　その202　ゲーム盤を表すハッシュ可能なデータの計算

`ai_match` の修正

`board_to_str` の目的

ndarray の `tobytes` メソッドの利用法

`board_to_hashable` メソッドの定義

`calc_same_boardtexts` メソッドの修正