温故知新（2年ぶり，Transposition Table編）

一時期続いていた温故知新シリーズも前回3年ぶり、今回これから２年ぶりになります。

温故知新（3年ぶりNaN回目，gpsfish計測編） - 48's diary

今回は以前よりゆるゆる更新している1fileプログラムの更新をしました。

バージョンナンバーは4-7から4-8で1200くらいから1900くらいまで上がってます。

ちょっとこの辺り対戦相手がいないので大げさな数字になっている感があります。

タイトルにありますがTransposition Tableを実装しました。

Transposition Tableは日本語で置換表と呼ばれたりしましすが、ゲームなど探索系のアルゴリズムで各局面情報をハッシュ値ベースのテーブルで状態保存しておく手法です。

ハッシュ値としてゾブリストハッシュを用いるのが有名でしょうか。

Zobrist Hashing - Chessprogramming wiki

gpt-ossにお願いしたら二十数行のクラス実装と探索部で呼ぶものをつらつらと出していただけました。Stockfishに寄せろというとそういう実装もしてくれましたがPythonの習作ですのでdictionary実装が適当でしょう。

# Transposition Table

from collections import namedtuple

TTEntry = namedtuple('TTEntry', ['depth', 'score', 'flag', 'move'])

class TranspositionTable:

    def __init__(self):

        self.table = {}

    # move を受け取る

    def store(self, key, depth, score, flag, move=None):

        self.table[key] = TTEntry(depth, score, flag, move)

    # 返却時に TTEntry 全体を渡す

    def lookup(self, key, depth, alpha, beta):

        entry = self.table.get(key)

        if entry and entry.depth >= depth:

            # バウンダリ判定

            if entry.flag == 1:            # EXACT

                return entry

            if entry.flag == 2 and entry.score >= beta:  # LOWERBOUND

                return entry

            if entry.flag == 3 and entry.score <= alpha:  # UPPERBOUND

                return entry

        return None

最初はmoveがなかったのですが追加するよう指示して完成です。

将棋に関してgpt-ossに限らずLLMはあんまり知らないのですが、チェスやチェスAIには詳しいことが分かったので温故知新の教材としてチェスサイトではなくLLMに教わるというのもアリかということになりました。

特に個々の質問に対して結構的確な回答が得られるのが素晴らしいところです。本当にこの分野のテキスト情報を十二分に学習していることが分かります。

今までのシリーズは元々Pythonで探索するのは無理があるので教育目的のコードのつもりでしたが、TT（Transposition Table）実装後は探索速度が向上しておりもしかしたらそこそこ戦えるものになるのかもしれません。