84,688個の正規表現で実装した2-plyミニマックス・チェスエンジン
(nicholas.carlini.com)- Regex Chessは、84,688個の正規表現置換だけを順番に実行し、チェス盤上で合法かつ「完全にひどいわけではない」手を選ぶ2-plyミニマックスエンジン
- 状態は1つの文字列の中にスタックと変数を一緒に入れ、
push、pop、変数の参照・代入のような命令を正規表現置換で処理する - 条件分岐はアクティブ状態を示す
%%マーカーを変える方式で模倣し、グローバル置換のおかげで複数の状態を一度に処理するSIMD式の並列実行が可能になる - エンジンはすべての合法手を並列状態として作り、相手の応手まで評価するが、相手の応手の合法性まで完全に検証するdepth-3探索は行わない
- 当初は1手への応答に約30分かかっていたが、中間変数の削除、マッチング最適化、特殊目的命令、並列化により、最終実装では局面に応じて1〜10秒程度まで短縮された
Regex Chessの基本構造
- Regex Chessは、チェスエンジン全体を84,688個の正規表現リストで構成する
- 実行構造は単純
- 正規表現リストを順番に巡回する
- 現在のチェス盤状態文字列に各パターンと置換文字列を適用する
- 最後の状態を画面に表示する
- 入力はPGNではなく、
e2e4のように出発マスと到着マスをつなげて書く座標形式 - プロジェクトのコードはGitHubで公開されている
正規表現CPU
- チェスのルールを正規表現で直接書くのではなく、まず正規表現で動作する小さなコンピュータを作る
- このコンピュータは、分岐のない条件実行、単一命令複数データ実行、スタックと変数操作を備えた命令セットを使う
- 現在状態は1つの文字列で表現される
%%はアクティブな実行状態の開始を表す#stack:の下にはスタック項目が積まれる#variable: valueの形式で変数が保存される
-
スタックと変数操作
pushは%%\n#stack:\nヘッダーを探し、その下に値を挿入してスタック最上段に載せるpopは#stack:直下の1行を削除し、スタック最上段の値を取り除く- 変数参照は、状態文字列内で
#変数名:を探して値をコピーし、スタック最上段に追加する - 変数代入は、変数がすでにある場合とない場合の両方を処理する
- すでに存在する場合は既存の変数値をスタック値で置き換える
- なければ変数行を新しく追加する
- バッククォートのような一時マーカーを使い、同じ命令が誤った順序で再適用されないようにする
分岐のない条件実行とループ制限
- 条件実行は
cond(tag)とreactivate(tag)で実装される - スタック最上段が
Falseなら、アクティブマーカー%%が%tagの形に変わり、以降の命令がその状態に適用されなくなる - 後で
reactivate(tag)が%tagを再び%%に戻し、その状態をアクティブ化する - この方式により、明示的な分岐なしに条件付き実行を模倣する
- プログラムは正規表現の逐次リストなので、ループを直接実行することはできない
- チューリング完全な計算はできない
- ただし、チェスの次の手の計算のように境界のある計算は、ループを展開して処理できる
グローバル置換を使った並列実行
- 正規表現置換が文字列全体にグローバルに適用されるため、1つの状態文字列内に複数の
%%実行状態を置くと、同じ命令が複数の状態に同時に適用される - 例えば2つのスタックにそれぞれ整数が2つあるときに
binary_add()を実行すると、2つの加算が同時に実行される fork_inactive(tag)は現在のアクティブ状態を複製し、複製を非アクティブなタグ状態にしておくfork_bool(variable)は1つの状態を、True値とFalse値を持つ2つの状態に分ける- この構造は、チェスで可能な複数の盤面状態を1つずつ反復処理せず、同時に評価するために使われる
マクロアセンブラとシンボリック実行
- エンジンは正規表現だけを手で直接書くのではなく、Python風のプログラムを小さな命令シーケンスに変換するマクロアセンブラを使う
fib()のようなPython風コードは、push、lookup、binary_add、assign_popのような命令リストに変換される- 従来のパーサとコード生成の代わりに**シンボリック実行（symbolic execution）**を使う
- 変数オブジェクトは実際の辞書ではなく、実行された演算を記録する特殊なオブジェクト
a = b + 1はlookup('b')、push(1)、binary_add()、assign_pop('a')として記録される
if文は条件が真の経路と偽の経路を両方記録したあと、再びマージする- 条件分岐に出会うと、呼び出しツリーに2つの経路を作る
- 複数回トレースしながら、訪問回数の少ない分岐を選んで両方の経路を埋める
- マージ地点は
reactivate命令に変換される
チェスの手の生成方法
- チェスエンジンを書くこと自体は一般的な言語のチェスエンジンと似ているが、複数状態を並列に処理する点が核心
- ポーンの移動生成は次の流れで構成される
- すべての白ポーンの位置を探す
- 各ポーンごとに並列状態を作る
- 元のメイン状態を止め、ポーンごとの状態をアクティブ化する
- 1マス前進、2マス前進、斜め取りの候補をすべてのポーン状態で同時に検査する
- 各状態の候補手リストを再び結合する
- 説明用の例ではFEN文字列を直接扱うが、実際の実装ではチェス盤を64マス別の変数に展開して読み書きする
- ビショップ、ルーク、クイーンのようなスライディング駒や、キャスリング、アンパッサンも別途実装されている
- 詳細な実装はchess_engine.pyにある
1ターンの処理と手の検証
- 1ターンは人間の入力手を読み、その手が合法か検証したうえで、コンピュータの応手を生成する順序で進む
from_pretty_utf8_to_fen()はUnicodeのチェス盤表示をFEN表記に変換し、入力の出発・到着マスを抽出する- 人間の手の合法性は、別のルール検査コードではなく、すべての合法な次盤面を生成して比較する方式で検証する
make_moveが入力手を適用した盤面を作るcompute_legal_boardsが現在局面から可能なすべての合法盤面を生成するfork_on_listが各盤面を並列状態に分離する- 入力手の適用結果と異なる状態は
destroy_active_thread()で削除される
- 合法手がなければ、全体の出力がハードコードされた
"Illegal Move"テキストに変わる - コンピュータの応手は、可能な黒の応手盤面とスコアを作ったあと、
keep_best_scoring_board(score)で最も良いスコアの盤面だけを残す
2-plyミニマックスと意図的な単純化
compute_and_score_legal_boardsがdepth-2ミニマックス探索の中核的な役割を担う- まずコンピュータが指せる候補手を生成し、続いて相手が応答できる手を作り、キングが取られ得るかを確認する
- チェック状態の検証のため相手の応手まで生成するので、すでにdepth-2探索構造が作られている
- 各候補局面は、相手が最善の応手をしたときのスコアで評価される
- 完全なdepth-2ミニマックスではない
- 相手の応手が自分のキングをチェックにさらす違法手かどうかまでは検証しない
- これを完全に処理するにはdepth-3探索が必要で、コストが大きく増える
- コンピュータが生成する応手自体は違法手ではないが、一部の場合には相手が指せない手を考慮し、実際より弱い応手を選ぶことがある
性能最適化
- 初期実装では、人間の1手に対する応答を生成するのに約30分かかった
- 最終実装では、作者のマシン基準で局面に応じて1〜10秒ほどかかる
- 約100倍の高速化は、複数の最適化の結果
-
中間変数の削除
- 変数参照は状態文字列全体から変数値を探す必要があるため、**O(n)**コストがかかる
- 実行状態をフォークするとき、変数も一緒にコピーされるためメモリ使用量が大きくなる
- もう不要な変数を積極的に削除し、変数名を再利用して時間とメモリを削減する
- 1手評価の内部状態は、最適化前の10GBから約300MBに減少した
-
正規表現マッチング最適化
- 条件命令のクリーンアップ用正規表現で先頭側の改行文字を含めるだけで、その命令の効率が約2倍良くなる
- 状態内には
TrueとFalse文字列が多く出てくるため、スタック最上段の値だけを素早く見つけるようにパターンを制限する必要がある - 不要な候補マッチングを減らす小さなパターン差が、全体の実行時間に影響する
-
特殊目的命令と並列化
- 駒の位置を探すループのような遅い部分は、既存命令を組み合わせる代わりに、1つの特殊な正規表現命令にまとめる
- ルークの移動生成では、各方向を逐次検査せず、複数の並列状態を作って一度に処理する
- 局面評価も候補盤面ごとに並列状態を作って同時に実行する
- 駒の価値計算のように、同じ演算が複数状態で繰り返される作業では、並列実行が特に効果的
ソースに含まれる追加実装
- ソースには本文で深く掘り下げられていない実装要素も含まれる
- ビショップ、ルーク、クイーンのようなスライディング駒の並列手生成
- キャスリングのための「そのマスは攻撃されているか」手順
- FENチェス盤とマス別変数表現の間の変換
- キングとルークの位置追跡によるキャスリング権の検出
- アンパッサンの検出と追跡
- 数千ゲームにわたってエンジンの正確性を検証する約2000行のテスト
- こうした目的のないプロジェクトが、自分の分野外にある複数のコンピュータサイエンスのトピックを学ばせてくれる、という言葉で締めくくられている
- 関連プロジェクトとして、Cの
printfで三目並べを行うprintf-tac-toeと13kB JavaScript Doomクローンもあわせて言及されている
1件のコメント
Hacker News のコメント
これは printf() がチューリング完全であることを示し、13kB の JavaScriptで一人称シューティングゲームを作った人の仕事です
https://github.com/HexHive/printbf
https://github.com/carlini/js13k2019-yet-another-doom-clone
コンテストの完成期間は1か月でしたが、既存コードは再利用できたようです
作業自体はかなり楽しそうで、今は家族と仕事のせいで、こういうことに使える 1か月分の自由時間は絶対に捻出できそうになく、少し寂しいです
この時点で、この取り組みは狂ったような面白さを超えて、完全に並外れたものになったと感じました。あり得る複数の局面計算がすべて 並列に起こり、増えていく状態・変数の集合、つまりスレッドの上で正規表現を走らせる方式でした
「ここからが、私たちの作った言語で私が一番好きな部分です。正規表現の魔法と、文字列全体にグローバル置換を実行するという事実のおかげで、複数のスレッドを同時に実行できます！」
結論も良かったです。「こういうブログ記事の結論に何を期待していますか？ 特に結論はありません。ただ、もっと多くの人がこういう完全に役に立たないことをやってくれたらいいと思います。本当に楽しいし、終わらせるのにどれだけ時間がかかっても誰も気にせず、動いても動かなくても誰も気にせず、おまけに自分の分野外のコンピュータサイエンスのさまざまな領域について、望んでいた以上に学ぶことになります。」
本当に素晴らしい 姿勢です
ここで得られるのは、座って一つのことに精神を集中したときにどこまでできるかわからないという力であり、同時に著者が間違いなく非常に 才能があり、熟練した創造的な人だという点です
どこかにバグがあるようです。以下の対局は違法手ではないのに「Illegal move, you lose」で終わります
Illegal Move
You Lose.
Game over.
上の対局の FEN:
1nbqkbnr/2pp1ppp/8/8/3QP3/P4N2/P1P2PPP/R1B1KB1R b KQk - 0 8
しかしどちらも合法手なので、間違いなく バグです
84,688個の正規表現でチェスを指す人は怖くありませんが、正規表現1つでチェスを指す人は怖いです
助けて、ナードスナイピングされています
すぐに思い浮かぶ潜在的な問題は 後方参照です
正規表現は非常に長くなるでしょうが、実質的にはチェスエンジンをエンコードしているわけなので…
こういうものを見ると、帽子を脱ぎ、人類の真の英雄たちに厳粛な感謝を捧げたくなります
aファイル移動バグが修正されました: https://github.com/carlini/regex-chess/issues/1
以前の事例: sed で書かれたチェス https://news.ycombinator.com/item?id=6261314
もちろん sed 版は sed の 制御フロー命令を使っており、おそらく1手先しか探索しないので、その点でこのバージョンとはかなり異なります
これはチェスエンジンであるだけでなく、コンピュータとアセンブリ言語を正規表現だけで作ったものでもあります
普通は a2a4 で始めたからといって、こんなに早く負けることはないのに！
これも比較する価値があります: https://codegolf.stackexchange.com/q/3503/32575