リグザ・チェス：約 8 万 4688 個の正規表現で実装された、深度 2 のミニマックス法を用いたチェスエンジンです。

チェス played（進行）することは、正規表現で可能でしょうか？はい、可能です。チェスを「正規表現」を用いて遊ぶことができます。

休暇中に、「何も意味をなさないことをする」という活動に長い間取り組んでいないことに気づき、決心しました。さっそくですが、ご紹介します…… Regex Chess です。これは、84,688 つの正規表現のシーケンスから成り立ち、チェスの盤面（入力）を受け取った際に順次実行することで、有効かつ（決してひどいわけではない）一手を指すようにプログラムされたものです。以下ではその仕組みを実演してみます。

現在実行中の正規表現はここに表示されます……

具体的には、対戦相手对你 against you に対して一手を指すプログラムの全体像です（冗談ではありません。確かにこれだけで完結します）：

let regex_list = [/* ここに非常に長いリストの正規表現が入る */]
let board = "rnbqkbnr / pppppppp / 8 / 8 / 8 / 8 / PPPPPPPP / RNBQKBNR w KQkq - 0 1";

for (regex of regex_list) {
    board = re.replace(regex.pattern, regex.target)
}
display(board)

この投稿を終える頃には、なぜこのような正規表現のシーケンスが可能なのか、そして個々の正規表現がどのような役割を果たしているのか（願わくば）ご理解いただけることを願っております。

（もし過去 six ヶ月以内に当ブログを購読され、「本気な」「重要な」話題を書かれる私になじみのある方であれば、ここでは MY WEBSITE（私のウェブサイト）であり、ルールは私が定めます。したがって、好きなものであれ嫌いなものであれ、今日は RegexChess を学んでいただくことになりますので、そのようにお考えください。）

通例同様、このプロジェクトのコードは GitHub で公開されています。

---

スタート：正規表現 CPU

では、どのようにして正規表現を使ってチェスを指すことができるのでしょうか？もちろん、「正規表現を用いたコンピュータ」を作成することでです！具体的には、「分岐なし（Branch-Free）」「条件付き実行（Conditional-Execution）」「単一命令・複数データ（SIMD）」の命令セットを設計し、それらを解釈する正規表現のシーケンスを作るのです（GPU の命令セットや ARM アーキテクチャーにちょっと似た概念です。ただし、ずっと低速です）。そして、この新しいコンピュータを使ってチェスをプレイするプログラムを書くことができます。では、スタートです。

（「奇妙なコンピュータを作り込むことへの病的な興味が強い」と言う人もいますが、彼らは大げさであり、平凡なものや普通なものへの異常な執着に陥っているだけです。）

コンピュータの設計

まずは、このコンピュータが操作するデータをどのように整理するかを説明しましょう。正規表現を用いるため、コンピュータの状態は「プログラムスタック」と「すべての変数」を含む単一の文字列として表現されます。以下のような形式です：

%%
#stack:
スタック上の最上位要素
2 番目の要素
...
#variable1: value 1
#variable2: value 2
...
#variablek: value k

各命令は、スタック上のいくつかの変数を操作するか、または指定された変数を読み書きします。以下に基本的な命令を見てみましょう。

スタックの基本操作

Push 命令

スタックの頂部に値を追加する

push

コマンドの実装です：

def push(const):
    return [(r"(%%\n#stack:\n)",
              r"\g<1>"+const+r"\n")]

これらの関数の戻り値は、タプルのリストとして解釈してください。各タプルは適用する正規表現の変換を表しており、左側の要素が一致パターンスて右側の要素が置換文字列です。

簡潔な正規表現のリマインダーとして：このリスト内の各タプルの 2 つの部分（正規表現と置換文字列）について説明します。正規表現は、対象となる文字列（ここでは「状態」）から部分文字列を検出できれば一致すると考えられます。大部分の文字は自身と一致しますが、括弧

()

は後で参照できるようになったり得る「捕捉グループ」を作成します。

第 2 の引数には置換文字列が入ります。ここでも大部分の文字は「この文字で置き換える」という意味ですが、

\g<1>

のような特殊な配列は、以前に捕捉されたグループへの後方参照（back-reference）です。本件の場合は、

\g<1>

は最初のカプチャグループ（最初の括弧の中で匹配された部分）を参照しており、これには

%%\n#stack:\n

というヘッダーが含まれています。

つまり、この操作がスタックに適用されると、「%%\n#stack:\n」の出現位置を見つけ、その直下（つまりスタックの頂部）に定数値を挿入します。

実践を見てみましょう。まず空のスタックから始めます：

%%
#stack:

push("hello")

を実行すると、正規表現は以下のようになります：

• スタートの状態冒頭の

  %%\n#stack:\n

  パターンと一致する。
• このヘッダーをグループ 1 に捕捉する（パターン内の括弧がこの捕捉グループを作る）。
• これを置換文字列

  \g<1>

  で置き換え、その後に定数 "hello" と改行コードを追加する。

これにより以下を得ます：

%%
#stack:
hello

次に

push("world")

を実行すると、同様のプロセスが繰り返され、以下を得ます：

%%
#stack:
world
hello

正規表現は常にスタック領域の頂部で一致するため、新しい要素は既存の内容を保持したままその上に追加されます。

Pop 命令

pop

命令はスタックの上位要素を削除します：

def pop():
    return [(r"(%%\n#stack:\n)([^\n]*)\n",
              r"\1")]

ここで、正規表現の強力さをもたらすいくつかの特殊なオペレーターが見えてきます。

[^\n]

は「改行ではないあらゆる文字」という意味で、

*

は「これらのゼロ個以上」という意味です。つまり、全体として、「%%\n#stack:\n」で始まる行を探し、次の改行までの零または複数の文字（つまり一行全体）をマッチさせるようにしています。置換は第 1 の行のみであり、これにより 2 番目の行が削除され、スタックの頂部要素がポップされます。

実践での挙動を見てみましょう。以下のスタックから始めます：

%%
#stack:
world
hello

pop()

を実行すると、正規表現は以下のようになります：

• %%\n#stack:\n

  で始まるパターンをグループ 1 に捕捉する。
• 次の改行までの任意の文字（つまり「world」）をグループ 2 に捕捉する。
• マッチした全内容を単にグループ 1（ヘッダー）だけで置換し、上位要素を実際に削除する。

これにより以下を得ます：

%%
#stack:
hello

各

pop

操作はスタックの頂部から正確に 1 つの要素を削除し、残りの要素は保持されます。

変数 <-> スタックの命令

変数の参照（Lookup）

変数の内容をスタックの頂部に読み込む命令です：

def lookup(variable):
    # 変数の値を見つけ、スタックの頂部にプッシュする
    return [(r"(%%\n#stack:)([^%]*\n#"+variable+": )([^\n]*)\n",
              r"\1\n\3\2\3\n")]

この正規表現は以前のものより少し複雑です。以下に分解して説明します：

• [^\%]*

  は基本的に任意の文字をマッチさせます（

  \%

  はプログラム冒頭のみに現れるため）。これにより、プログラムのどこかの変数を探せるようになります。

• [^\n]*

  は変数の値をマッチさせ、行末まで捕捉します。
• 置換では、値のコピーを作成し、それをスタックの頂部に置きます。

実践を見てみましょう。以下の状態から始めます：

%%
#stack:
#foo: hello
#bar: world
#baz: 42

lookup("bar")

を実行すると、正規表現は以下を行います：

• グループ 1 でスタックヘッダーをマッチする。

• [^%]*\n#[^\n]#+variable+: 

  の部分で、グループ 2 に "world" まで含めた部分を読み込む。
• グループ 3 で "world" をマッチする。
• これらのグループを使って、値のコピーをスタックの頂部に持つ状態で状態を再構築する。

置換を実行すると、以下の状態になります：

%%
#stack:
world
#foo: hello
#bar: world
#baz: 42

lookup

操作は元の変数とその値を保ったまま、その値のコピーをスタックの頂部にも置くことができました。これにより、変数の値を読む際にそれを変更せずに済みます。

変数の割り当て（Assignment）

変数への割り当てには興味深い課題があります：その変数がすでに存在するかどうかはわかりません。既存の変数を更新するか、新規に作成するかの両方のケースを処理する必要があります。

以下に実装を示し、後でケースバイケースの説明に行きます。

def assign_pop(varname):
    return [
        (r"(%%)\n#stack:\n([^\n]*)\n" +
         "([^%]*#" + varname + r": )[^\n]*",
         r"\1`\n#stack:\n\3\2"),

        (r"(%%)([^`]\n?#stack:\n)([^\n%]*)\n([^%]*)",
         r"\1`\2\4#" + varname + r": \3\n"),

        (r"%%`",
         r"%%")
    ]

まずは、変数がすでに存在する場合を仮定してみましょう。つまり、スタックは以下のように始められており、

assign_pop("bar")

を呼び出しているとします：

%%
#stack:
world
#foo: hello
#bar: something
#othervar: othervalue

この正規表現リストを実行すると、以下の捕捉グループが作成されます：

%%
#stack:
world
#foo: hello
#bar: something
#othervar: othervalue

置換操作後、以下の出力を得ます：

%%`
#stack:
#foo: hello
#bar: world
#othervar: othervalue

次に次の命令に移りますが、プログラム開始の

%%

の後にバックスラッシュ付きのタ（back-tick）が存在する場合、2 番目の正規表現は一致しなくなるため何も起こりません。最後に、3 つ目の正規表現で片付けを行います。

存在しない変数の処理：

変数がすでに存在しない場合を考えてみましょう。また

assign_pop("bar")

を呼び出しているとします：

%%
#stack:
world
#foo: hello
#othervar: othervalue

1 番目の正規表現はマッチを試みますが、"#bar" がどこにもないため失敗し、何も起こりません。次に 2 つ目の正規表現が試みられ、成功します。これにより以下の捕捉グループが作成されます：

%%
#stack:
world
#foo: hello
#othervar: othervalue

ここから書き換えを行い、以下を得ます：

%%
#stack:
#foo: hello
#othervar: othervalue
#bar: world

最後に 3 つ目の正規表現が適用され、何も起こりません。

この「トリック」を使って、望まない順序で処理を適用しないようにする命令がたくさんあります。例えば、「等しいか」という判断を行う命令の仕組みを理解してみましょう（演習問題として）：

def eq():
    return [
        (r"(%%\n#stack:\n)([^\n]*)\n\2\n",
         r"\1`True\n"),

        (r"(%%\n#stack:\n)([^`][^\n]*)\n([^\n]*)\n",
         r"\1False\n")
    ]

（分岐なしの）条件分岐（Conditionals）

プログラミング言語が面白く機能するには、ある種の制御構造が必要です。「if 文」を使ってプログラムを書くのは非常に難しいものです。では、どうやってこの制御を実現するでしょうか？（お役立ちのために、同じ「条件付き実行のトリック」を使うことを願います。）以下に条件命令の実装を示します：

def cond(tag):
    return [(r"%(%\n#stack:\nTrue)",
              r"%\1`"),
            (r"%(\n#stack:\nFalse)",
             tag+r"\1`"),
            (r"\n(True|False)`\n",
             "\n")]

以下に、スタックの頂部が

False

の場合の動作を追って説明します。

%%
#stack:
False
#variable: value

最初にあるいは最初の正規表現はマッチしませんが、2 番目の正規表現はマッチし、対応する捕捉グループを作成します。

置換を適用すると、以下のようになります：

%tag
#stack:
False`
#variable: value

（最後に、同じクリーンアップトリックを使って、使用済みマーカーを削除します。）

ここで行われたことは何でしょうか？プログラムは

%%

で始らなくなったため、すべての命令がマッチしなくなります。それらは常にプログラムが

%%

で始まるように設計されているからです。つまり、何も起こりません…… until we reactivate it later with the following simple instruction:

def reactivate(tag):
    return [(r"%"+tag+r"\n([^%]*)",
            r"%%\n\1")]

次に条件の

True

側に戻ってみましょう。これは簡単なケースです：実際には何も行いません。2 つ目の正規表現でスタックを

True

に置換し、3 つ目でこの行を削除するだけです。

これは、コードが実際には「分岐なし（branch-free）」であることを意味します。なぜなら、すべての命令が条件命令だからです。（ARM のプレディケート実行に似ています。ほとんどの命令は明示的な分岐命令を使用せず、ステータスフラグに基づいて条件付きで実行可能です。）

ループ（不可能）

プログラムが単なる正規表現のシーケンスのみであるため、ループは完全に不可能です！つまり、理論上、ターリング完全性を持つことはできません。しかし、ループを展開することで、有界な計算であれば何でも行うことができます。幸いなことに、チェスの局面から次の手を計算するのは有界な計算であるため、これを行うことができます。

単一命令・複数データ（SIMD）

ここで、私たちが開発した言語の絶対的なお気に入り部分に到着します。正規表現の魔法（文字列全体に対してグローバル置換を行うこと）と、その事実によって、複数のスレッドを同時に実行できます！

つまり、状態文字列を以下のように書けば：

%%
#stack:
int0000101010
int0001011100
%%
#stack:
int0000001101
int0110000000

binary_add()

を呼び出すと、両方の加算が同時に実行されます！実行後：

%%
#stack:
int0010001110
%%
#stack:
int0110001101

これはなぜ起こるのでしょうか？正規表現のマッチングはグローバルに機能するためです。「スレッド開始」オペレーター（

%%

）を 2 回マッチさせると、両方のスレッド同时对に操作を行うことができます。

では、この機能をどう実際に利用するのでしょうか？スレッドを作成および管理するのに役立つ命令を見てみましょう。

Fork 命令

現在のすべての実行中のスレッドを 2 つに分岐し、そのうち一方は与えられたタグで不活性状態からスタートする、単純な

fork

命令です：

def fork_inactive(tag):
    return [(r"%%\n([^%]*)",
            r"%%\n\1" + "%"+tag+r"\n\1")]

例えば、ブール値に対して

fork()

を行うこともできます。これにより、一方のスレッドが

True

のケース、他方が

False

のケースを得ます。（これは McCarthy の Amb オペレーターに似ています。）

def fork_bool(variable):
    return [(r"%%\n([^%]*)",
            r"%%\n\1#"+variable+r": True\n%%\n\1#"+variable+r": False\n")]

複数の

fork

を適用するとどうなるか見てみましょう。単純な状態から始めます：

%%
#stack:
somevalue
#x: 10

fork_bool("condition")

を呼び出すと、以下を得ます：

%%
#stack:
somevalue
#x: 10
#condition: True
%%
#stack:
somevalue
#x: 10
#condition: False

その後

fork_bool("c2")

を呼び出すと、既存のスレッドのそれぞれがさらに分岐します：

%%
#stack:
somevalue
#x: 10
#condition: True
#c2: True
%%
#stack:
somevalue
#x: 10
#condition: True
#c2: False
%%
#stack:
somevalue
#x: 10
#condition: False
#c2: True
%%
#stack:
somevalue
#x: 10
#condition: False
#c2: False

これで、4 つの同時実行パスができ上がり、ブール条件のすべての組み合わせを同時に検討できるようになりました。これはチェスにとって特に有用です。なぜなら、複数の可能性のある盤面状態を同時に考慮し（例えば）評価して最適なものを見つけたい場合があるからです。ループで全局面を回す代わりに、一度だけ行うふりをして、すべて同時に行えるようにします。

独自の言語へのコンパイル

CPU エミュレータができあがったので、新しいアセンブリ言語をターゲットとするコンパイラを作ることができます。

「待ってください、この投稿はコンパイラの授業のためには来ていません！」というあなたへの答え：その通りです。また、私はこのプロジェクトでコンパイラを作ることを目指して始めたわけではありません。代わりに、マクロアッサーのようなものです。これは、Python 風のプログラムを以下のように変換します：

def fib():
    a = 1
    b = 2
    for _ in range(10):
        next = a + b
        a = b
        b = next

命令のシーケンスに変換します：

push(1)
assign_pop('a')
push(2)
assign_pop('b')
lookup('a')
lookup('b')
binary_add()
assign_pop('next')
lookup('b')
assign_pop('a')
lookup('next')
assign_pop('b')
[... 8 回繰り返される...]

記号実行によるコンパイル

伝統的な解析とコード生成フェーズを持つコンパイラを書く代わりに、異例なアプローチを採用しました：「記号実行（symbolic execution）」です。重要な洞察は、Python コードを特殊な方法で「実行」することで、実際に動作させるのではなく何が起こるべきか記録できることです。

以下が仕組みです：

variables

引数は実際には辞書ではなく、操作履歴を記録する特別のオブジェクトです。これを「トレース」と呼んでいます。以下のように書いた場合：

a = b + 1

トレーサーオブジェクトは以下の 4 つの操作を記録します：

• 変数 'b' の参照
• 定数 1 のプッシュ
• ビナリー・アド
• 変数 'a' への割り当て

制御流の処理

このアプローチで最も難しい部分は、分岐制御構造（

if

文など）を処理することです。ループはどうでしょうか？我々にはありませんので、使用しません。ループは定数のみしか持てません。すべての実行パスを捕捉する必要があります。以下が方法です：

条件に達したとき、トレース内に「真」と「偽」の 2 つの分岐を作成します。各パスは独自の操作シーケンスを記録し、後でこれらを再結合します。

例えば、この Python コード：

if x > 0:
    y = 1
else:
    y = 2

以下のトレース構造を生み出します：

lookup('x')      # x の値を取得
push(0)          # 0 をプッシュ
greater_than()   # 比較
cond('tag1')     # 結果に基づいて分岐
  # 真のパス:
  push(1)
  assign_pop('y')
pause('tag2')
reactivate('tag1')
  # 偽のパス:
  push(2)
  assign_pop('y')
reactivate('tag2')

コンパイラの魔法は、分岐による制御流をどのように処理するかにあります。もう少し詳しく説明しましょう。

コンパイルが最初に行われると、CallTree に単一の直線的な命令パスを維持します。各命令は順次追加されます。リストは完全に直線に見えます。条件文に達したときは、ここで面白いことが起こります。

上記の

x > 0

のような条件に達すると、それを検出し、ツリー内で 2 つのパスを表す分岐を作成します。その後、「この条件は真」と仮定して、ツリーの真のケースを埋めていきます。プログラム終了までに行われたコンパイルは不完全です。

次にくるのは賢明な部分です。コンパイルする際、プログラムを一度だけトレースするのではなく、多次にトレースします。各トレースでは、条件分岐が最も少なく使用された分岐の方へ行かれるように整えます。このようにして、2 回目のトレースで偽のパスの命令も記録されます。

最後に、条件終了を検出し、2 つのパスを再結合します。この分岐と再結合のメカニズムは単なるトリックではなく、正規表現ベースの CPU が実際に動作する上で本質的です。ツリーから命令に変換する際、各分岐は

cond

命令を用いた条件式正規表現操作に翻訳され、プログラムの状態の一部を有選択的に活性化/不活性化するようになります。結合点は正しいパスで継続を実行することを保証する

reactivate

命令になります。

チェスエンジンの作成

さて、いよいよこの投稿で実際にチェスエンジンを書ける部分に達しました。（エミュレータ設計の決断がなぜ合理的か理解できる部分です。）

大部分は非常にシンプルであり、他のプログラミング言語でチェスエンジニアリングを行う方法とほぼ同じです。ただし、SIMD による分岐処理が、高速化をもたらします。

以下の（簡略化した）プログラムを見てみましょう。これにより、すべての有効な歩兵の手順を計算します。

def pawn_moves(initial_board):
    # ステップ 1: すべての歩兵を見つけ、その位置のリストを作成
    pawnpos_list = find_all_pawns(initial_board)

    # ステップ 2: 各歩兵のための並列状態を作成（最大 8）
    MAX_PAWNS = 8
    for iteration in range(MAX_PAWNS):
        if not pawn_list.is_empty():
            pawn_pos = pawnpos_lst.remove_first()
            fork_inactive("waiting")

    # ステップ 3: 並列状態への処理に切り替える
    pause("main")
    reactivate("inactive")

    # ステップ 4: すべての歩兵の移動を同時に生成
    candidate_moves = []
    if initial_board[pawn_pos + (0, 1)].is_empty():
        candidate_moves.append(pawn_pos + (0, 1))
        if pawn_pos.y == 2:
            if initial_board[pawn_pos + (0, 2)].is_empty():
                candidate_moves.append(pawn_pos + (0, 2))

    if initial_board[pawn_pos + (1, 1)].has_opponent():
        candidate_moves.append(pawn_pos + (1, 1))
    if initial_board[pawn_pos + (-1, 1)].has_opponent():
        candidate_moves.append(pawn_pos + (-1, 1))

    # ステップ 5: 結果を再結合して統合
    pause("inactive")
    reactivate("main")
    candidate_moves = merge_variables_from_threads("inactive")

ステップ 1：歩兵の発見

find_all_pawns()

関数は盤面の表現を走査し、FEN 文字列内の 'P' で表される白い歩兵を探します。各歩兵の位置のリストを返します。例えば、d2, e2, f2 に 3 つの歩兵がある局面でプログラムを実行すると、

pawnpos_lst

変数にセミコロン区切りのリストを作成します：

%%
#stack:
#board: 4k3/8/8/8/8/8/3PPP2/4K3
#pawnpos_lst: d2;e2;f2;

ステップ 2：状態の作成

ここで重要な部分です。前述の

fork_inactive

命令は、プログラムの状態を完全に複製します。各実行時、現在の実行中のスレッドの正確なコピーを作成し、新しいコピーには

%waiting

を使用してマークします（これは

%

からではなく、命令がそのスレッドに適用されないことを意味します）。同時に、

pawnpos_lst

から一つ位置を取り出し、それを複製された状態への新しい変数

pawnpos

に割り当てます。

ループが 3 回実行されると、各

fork_inactive

操作は並列宇宙の一つを切り離し、別の歩兵を処理します。このコピーを行う正規表現操作は、既存の変数をすべて保持したまま、新しい

pawnpos

変数に特定の位置を追加します。

%%
#stack:
#board: 4k3/8/8/8/8/8/3PPP2/4K3
#pawnpos_lst: 

%waiting
#stack:
#board: 4k3/8/8/8/8/8/3PPP2/4K3
#pawnpos: d2

%waiting
#stack:
#board: 4k3/8/8/8/8/8/3PPP2/4K3
#pawnpos: e2

%waiting
#stack:
#board: 4k3/8/8/8/8/8/3PPP2/4K3
#pawnpos: f2

ステップ 3：アクティブ化の切り替え

pause

および

reactivate

操作は、どの状態がアクティブであるかを示す

%%

マーカーを操作することで機能します。

pause("main")

は元の

%%

を

%main

に変更し、実質的にそれを不活性にします。その後

reactivate("inactive")

が

%waiting

でマークされたすべての状態を見つけ、それらを

%%

に変換して新しいアクティブ状態とします。

ステップ 4：並列な移動生成

ここで SIMD の魔法が現れます。各可能な移動のチェック（前方 1 マス、前方 2 マス、斜めによる捕獲）は、すべてのアクティブ状態に対して同時に行われます。前方のマスが空かどうかを確認する際、実際には d3, e3, f3 を一つの操作で確認しています。有効な移動それぞれについて、それを

candidate_moves

リストに追加します。

（ここでは可視化の目的のためにプログラムを大幅に簡略化しました。実際には FEN 文字列自体を直接使用せず、各マスのための独立した変数 64 に展開して直接読み書きしています。これにより盤面状態の処理がはるかに容易になります。ただし、このブログ投稿では FEN 文字列だけで動作しているように視覚的に示す方が簡単です。）

%main
#stack:
#board: 4k3/8/8/8/8/8/3PPP2/4K3
#pawnpos_lst: 

%%
#stack:
#board: 4k3/8/8/8/8/8/3PPP2/4K3
#pawnpos: d2
#candidate_moves: d3;d4

%%
#stack:
#board: 4k3/8/8/8/8/8/3PPP2/4K3
#pawnpos: e2
#candidate_moves: e3;e4

%%
#stack:
#board: 4k3/8/8/8/8/8/3PPP2/4K3
#pawnpos: f2
#candidate_moves: f3;f4

ステップ 5：結果の再結合

最終的な再結合操作は、並列状態からのすべての

candidate_moves

リストを組み合わせます。まず

pause

および

reactivate

を使用してアクティブ化をメイン状態に戻します。その後、

merge_variables_from_threads

（これは可視化の目的のために私が発明した疑似命令です。実際には私のマシンでは約 10 つの異なる命令が必要です）が、不活性状態間ですべての

candidate_moves

リストをマッチし、それらを連結します。

これは、書いたコードは一度に一つ歩兵だけ処理しているように見えるにも関わらず、正規表現エンジンの複数の状態処理能力により、実際には全歩兵を同時に処理していることを意味します。空マスのチェックから移動リストの構築まで、すべての操作がアクティブな状態すべてに対して並列で行われます。

これがすべての駒操作の仕組みです。この投稿はすでにかなり長くなっていますので、各駒を一つずつ説明する予定はありませんが、詳しく知りたい場合はぜひ

chess-engine.py

をご覧ください。

一手の進行（Playing a Turn）

次に、すべてを処理するゲームループ全体を見てみましょう。

def play_turn():
    # ステップ 1: 入力から人間が指した手を取得
    board_before_move, src, dst = from_pretty_utf8_to_fen()

    # ステップ 2: その手が進法かどうかをチェック
    after_move = board_before_move.make_move(src, dst)
    next_boards = compute_legal_boards(board_before_move)
    next_board = fork_on_list(next_boards)
    if after_move != next_board:
        destroy_active_thread()

    # ステップ 3: コンピュータの応手を生成
    candidate_boards = compute_and_score_legal_boards(after_move)
    candidate_board = fork_on_list(candidate_boards)

    keep_best_scoring_board(score)
    from_fen_to_pretty_utf8(candidate_board)

ゲームの初手で、人間が「e2e4」（王の歩兵によるオープンング）を入力したと仮定します。コードはこのように処理します：

ステップ 1：手の読み取り

最初、

from_pretty_utf8_to_fen()

関数はUnicode チェス駒で表された漂亮な盤面を FEN 表記に戻し、入力からソースと destinations マスを抽出します：

%%
#stack:
#board: rnbqkbnr/pppppppp/8/8/4P3/8/PPPP1PPP/RNBQKBNR
#src: e2
#dst: e4

ステップ 2：手の有効性確認

次に、これが有効な手かどうかをチェックする必要があります。明示的に手を法的にチェックするための全く新しいコードを書く代わりに、並列処理能力を再度使用します。プロセスは 3 つの段階で行われます：

• まず、

  make_move

  が人間の手の結果を作成して新しい盤面状態を作ります：

%%
#stack:
#board: rnbqkbnr/pppppppp/8/8/4P3/8/PPPP1PPP/RNBQKBNR
#after_move: rnbqkbnr/pppppppp/8/8/4P3/8/PPPP1PPP/RNBQKBNR

• 次に、

  compute_legal_boards

  が開始局面からすべての可能な有効な手を生成し、以下のようなリストを作成します：

%%
#stack:
#next_boards: rnbqkbnr/pppppppp/8/8/4P3/8/PPPP1PPP/RNBQKBNR;
              rnbqkbnr/pppppppp/8/8/8/3P4/PPP1PPPP/RNBQKBNR;
              rnbqkbnr/pppppppp/8/8/8/4P3/PPPP1PPP/RNBQKBNR;
              ...

• 最後に、

  fork_on_list

  が各法的な盤面状態に対して並列状態を作成します：

%%
#stack:
#board: rnbqkbnr/pppppppp/8/8/4P3/8/PPPP1PPP/RNBQKBNR
%%
#stack:
#board: rnbqkbnr/pppppppp/8/8/8/3P4/PPP1PPPP/RNBQKBNR
%%
#stack:
#board: rnbqkbnr/pppppppp/8/8/8/4P3/PPPP1PPP/RNBQKBNR

destroy_active_thread()

呼び出しは、

after_move

と一致しないすべてのスレッドを削除します。この場合、e2-e4 の位置のみが生き残り、これが合法的な手であることを確認します。（有効な手が指されない場合、特別な正規表現を使って出力全体をハードコードされたテキスト"Illegal Move"に置換します。）

ステップ 3：コンピュータの応手

次に、同様のプロセスを繰り返し、最適応手を調べます。まず

compute_and_score_legal_boards

がすべての可能な黒手の応手を生成します。この関数は少し魔法を行い、返される次の盤面のそれぞれについて、白が次に出す最善手後にその局面の評価（スコア）を含みます。以下でこの仕組みを説明しますが、とりあえずの結論として、この関数が返すのは

compute_legal_boards

と同様可能な位置ですが、同時に局面のスコアも含んでいます。（ここでミニマックスが発生します。スコアはプレイヤー視点から、彼らが最善応手をした後の各局面の評価です。）

したがって、この関数を実行すると以下のような出力を得ます：

%%
#stack:
#board: rnbqkbnr/pppp1ppp/8/4p3/4P3/8/PPPP1PPP/RNBQKBNR
#score: 100

%%
#stack:
#board: rnbqkbnr/ppppp1pp/8/5p2/4P3/8/PPPP1PPP/RNBQKBNR
#score: 102

%%
#stack:
#board: rnbqkb1r/pppppppp/5n2/8/4P3/8/PPPP1PPP/RNBQKBNR
#score: 98

keep_best_scoring_board(score)

はこれらの並列状態を圧縮し、この回には黒の視点から最も高スコアを持つ位置のみを残します（例では f7-f5 の応手）。（これはミニマックス探索の第 2 段階です。 opponents が最初に選択したすべてのオプションを検討した後、我々がこれらの中で最も良いものを選びます。）最後に

from_fen_to_pretty_utf8

はこの局面を漂亮的な Unicode 表示形式に戻します。その結果、明示的な検索アルゴリズムや位置のリスト格納のための特別なコードを書く必要はありませんでした。並列処理がすべて処理します。

（無料で）ミニマックス検索

このプロセスで最終的に欠けている部分は

compute_and_score_legal_boards

を深さ 2 のミニマックス検索を得る方法に実装することです。ここで私は多く cheat（不正行為）します。

疑似合法的な手を生成するのは比較的簡単です—that is、基本的に合法だが王を将死させる可能性のある手です。チェスではこれは許可されていません（一手終了時に王を将死させてはいけません）。したがって、2 つ目の必要があるのは、王を将死させるすべての手を削除することです。

この方法は、再度全ての可能な opponents 応手を生成し、それらが王を「捕獲」するかどうかを確認します。もしそうなら、その局面は不合法であり、それがチェックの定義だからです。しかし、これは我々がすでに深さ 2 の検索をしていることを意味します。初期盤面状態を持っています。深さ 1 で、コンピュータが指すすべての可能な手を生成します。次に深さ 2 で、 opponents が指す全ての可能な手を生成し、我々自身をチェックにさらされないようにします。

これで私がしなければならないことは、これらの opponents 生成された各手を評価し、候補位置のスコアを返すことです（相手の視点から）。その後、これらの最良スコアを持つもの（コンピュータの視点から）を選びます。

ただし、ここには少し問題があります。実際のチェスエンジンがこのようにしない理由です。それは技術的にこれは完全な深さ 2 のミニマックス検索ではなく、 opponents が生成した応手が不合法になり得るためです（彼らの王を将死させる可能性があります）。これを完全に正しく行うには、深さ 3 の検索が必要であり、それは検索コストを大幅に増加させます。したがって、私はそれをやらないだけです。

重要なのは、コンピュータは決して不合法な応手を生成しないということです。これは、一部のケースでは、完全な深さ 2 のミニマックス検索を行わなかった場合よりも、応手が少し弱いことを意味します。なぜなら、それは opponents が不合法な手を指すことができることを想定する可能性があるためです。

その他の事項

このプログラムには他にも多くの要素があります。興味があれば GitHub のソースコードを読み込むことをお勧めします。ここで話さないが特に興味深いと考えられるもの：

• 象、ローク、クイーンなどのスライドピースの移動生成を完全に同時に並列化する方法
• 特殊な「このマスは攻撃を受けているか」手続きを使った王車成りの実装方法
• FEN チェス盤を単一変数ごとにマスを持つ形式に、およびその逆に変換する方法
• 王とロークの位置を追跡して王車成りの権利を検出する方法
• エン・パスントキャプチャーの検出と追跡の実装
• チェスエンジンの正しさを数千のゲームで検証する広範な 2000 行のテスト

パフォーマンスのためのトリック

最後になりましたが、いくつかの面白いパフォーマンス向上方法を紹介します。私の初期コードでは、人間の手を一つ生成するのに約 30 分かかりました——チェス・バイメールには最適ですが、ブラウザによるチェスにはそれほど最適ではありません。最終的なコードは私のマシン上で、局面によって 1〜10 秒かかります。したがって、すべての詳細を適切にするにより、約 100 倍の速度向上を実現しました。

（既に私のお気に入りのパフォーマンストリック（並列処理）を見せたはずです。ここではいくつか追加を紹介します。）

中間変数の削除

初期実装での最大の性能キラーは、不要な中間変数を維持し続けたことです。各変数参照には、状態文字列全体をスキャンして変数の値を探す必要があります——O(n) 操作です。さらに、実行状態フォークする際には、これらの変数すべてを複製する必要があり、メモリ使用量が大幅に膨らみます。

必要なくなった変数を積極的かつ早々に削除し、可能な限り変数名を再利用することで、計算時間とメモリ使用量を劇的に削減できました。単一手の評価では内部状態で約 300MB になり、非最適化バージョンの 10GB から減少しました。

高速な正規表現マッチング

以前定義した条件演算子を見てみましょう：

def cond(tag):
    return [(r"%(%\n#stack:\nTrue)",
              r"%\1`"),
            (r"%(\n#stack:\nFalse)",
             tag+r"\1`"),
            (r"\n(True|False)`\n",
             "\n")]

なぜ 3 つ目の正規表現がこのように書かれているのでしょうか？以下のようにすると短くないですか：

def cond(tag):
    return [(r"%(%\n#stack:\nTrue)",
              r"%\1`"),
            (r"%(\n#stack:\nFalse)",
             tag+r"\1`"),
            (r"(True|False)`\n",
             "")]

注意してください。

\n

がなくなっています。

実際には、最初のバージョンはこの命令の効率を 2 倍に改善します！たった一つの文字を変えるだけで！この理由は正規表現がどのように機能し、マッチされるかの詳細にあります。

コード中に True/False の文字列が多くあります。しかし、ほとんどは変数の一部であり、スタック上の最上位要素ではありません。パターンに先行する

\n

および "#stack:\n" プレフィックスを要求することで、正規表現エンジンが変数名や値の中に現れるすべての True/False 文字列を素早くスキップできるようになります。これにより、試行マッチ回数が大幅に減少します。

特殊目的命令の書式設定

既存のものを組み合わせるのではなく、専用命令を書くことに価値がある場合があります。例えば、初期実装の最も遅い部分は、各マスをスキャンして与えられたタイプのすべてのピースを見つけるループでした。これは多くの条件分岐を必要とし、各分岐内で多くのスタック操作が必要でした。しかし、ループ本体全体を一つの正規表現命令に押し込めることができます：

def do_piece_assign(piece_chr, piece, x, y, pos):
    return [(f"%%([^%]*#{pos}: {piece_chr}[^%]*)") +
            f"#{piece}x_lst: ([^\n]*)\n" +
            f"#{piece}y_lst: ([^\n]*)\n" +
            f"#{piece}pos_lst: ([^\n]*)\n",
            fr"%%\1#{piece}x_lst: {x};\2\n" +
            fr"#{piece}y_lst: {y};\3\n" +
            fr"#{piece}pos_lst: {pos};\4\n")]

最終的な主要な最適化は、並列処理できる範囲を最大化することから生まれます。正規表現エンジンが複数の状態を同時に処理できることを思い出してください——つまり、移動を一つずつ生成する代わりに、すべて同時に生成できます。

例えば、ローキの移動生成時に、各方向順次チェックするのではなく、8 つの並列状態を作成できます（それぞれの可能な方向の一つ）。注意してください。「上」と「下」は異なる方向です。）各状態は、その方向でできるだけ遠くまでローキを移動します。これはループを単一の並列操作に変えます。

同様に、位置評価時に、一度に一つ位置ずつスコア付けするのではなく、候補位置それぞれに対して並列状態を作成し、すべて同時に評価します。この並列評価は特に効果的であり、多くの操作（駒値の合計など）がすべての状態において同じように機能するためです。

結論

このようなブログ投稿の結論で何を期待できますか？特に結論つけるほどのものは持っていません。おそらく「こうした全く意味のないことをする人がもっといるべき」と言いたいだけです。それは非常に面白く、いつ完了するか誰も気にせず、成功しているかどうかに関係なく、結果としてあなたの分野以外のコンピュータ科学の多数の領域についてあなたより多くの知識を得られるでしょう。

今年中にこれに似た全く意味のないものをいくつか発表したいと思います。このようなことがお好きな方は、C の

printf

文を使用して井戸戸ゲーム（tic-tac-toe）を遊ぶ方法や、13KB の JavaScript でドームクローンを書いたという私の別の記事も面白く読めるかもしれません。