正規表現でチェスを指す。
この一文だけでもう十分に変です。しかも、ただのネタではなく、実際に有効な手を返すチェスエンジンとして動くのがこの話のすごいところ。作者のNicholas Carlini氏は、84,688個のregular expressionsを順番に実行することで、盤面に対して1手を決める仕組みを作りました。
もちろん、強いわけではありません。記事のタイトルにもある通り、2-ply minimaxです。これは「自分の手を1回選び、その後の相手の反応も1回だけ見る」ような、かなり浅い探索です。チェスAIとしてはかなり素朴。でも、そこは問題ではないのです。重要なのは、正規表現だけでここまでやれるのかという驚きだと思います。
正直、こういう「役に立つかは知らないけど技術の限界をちょっと押す」遊びは大好きです。実用性は薄くても、発想の筋トレとしてはかなり強い。
記事の中心アイデアは、正規表現を単なる文字列検索ではなく、命令を実行する道具として扱うことです。
作者は、正規表現で動くbranch-freeでconditional-executionな、しかもSIMDっぽい命令セットを設計します。
ざっくり言うと、
という、ちょっとGPUやARMっぽい雰囲気の仕組みです。もちろん本物のCPUよりはるかに遅い。でも、遅さよりも「正規表現を命令に変える」発想が主役です。
この仕組みの面白いところは、コンピュータの状態を1本の文字列で持つことです。たとえばこんな形式です。
%%
#stack:
top item on stack
second item on stack
...
#variable1: value 1
#variable2: value 2
...
#stack: 以下がスタック#foo: value のように変数を置くつまり、「メモリ」っぽいものも「スタック」も、全部ただのテキストです。
私はここがかなり好きです。普通、プログラムの状態はメモリの中に隠れていますが、ここでは状態そのものが見えるテキストになっている。だから、正規表現で「文字列を書き換える」ことが、そのまま「計算する」ことになるわけです。発想としてかなり美しいです。
まずは基本中の基本、スタック操作です。
push("hello") は、#stack: の直後に hello を挿入します。
正規表現でヘッダ部分を捕まえて、置換でその後ろに値を足すだけ。
要するに、文字列の先頭付近を書き換えることでスタックに積むわけです。
pop() はスタックの先頭要素を消します。
#stack: の次の1行を見つけて、それを消す置換をします。
これ、言葉で言うと単純ですが、正規表現の置換でやっていると思うとちょっと気持ち悪くて、そして面白い。
「データ構造を正規表現で実装する」という時点でだいぶ遊んでいます。
次に変数です。
lookup("bar") は、#bar: の値を見つけて、それをスタックの上にコピーします。
元の変数は残るので、読み取り専用っぽく使えます。
ここで作者は、[^%]* のようなパターンを使って「プログラム部分のどこにある変数でも見つける」ようにしています。少し技巧的ですが、やっていることは「変数の値を探して持ってくる」です。
変数への代入は少し難しいです。
なぜなら、その変数がすでにあるかもしれないし、ないかもしれないからです。
そこで作者は、複数の正規表現を順番に試して、
という流れにしています。
この「先にあるケース」「なければ別ルート」という構成は、プログラムの中でもよくある考え方ですが、正規表現だけでやるのが妙です。かなり職人芸です。
記事の途中でeq()、つまり等しいかどうかを判定する命令が出てきます。
ここでも正規表現は、単に「一致する／しない」を見るだけでは終わりません。
一致したときは True を積み、不一致なら False を積む、というように条件付きで結果を残すわけです。
つまり、正規表現そのものがif文ではないのに、if文っぽい動きを作っている。
このへんがまさに「正規表現CPU」の本丸です。
ここまでで作った正規表現CPUの上で、作者はチェスを動かします。
やることはざっくりこうです。
つまり、チェスのルールそのものをかなり細かく文字列処理に落としているわけです。
この「ルールをプログラムでなく文字列変換の連鎖として表現する」というのは、読んでいて頭がふわっとします。普通の開発の発想からかなり離れているので、そこが楽しい。
個人的に一番インパクトがあるのは、やっぱり84,688個のregular expressionsという数字です。
多い。とにかく多い。
「正規表現で書きました」と聞くと、普通は「数本の巨大なregexを頑張って書いたのかな」と思います。でもこれはそうではなく、大量の正規表現を順番に流すことで機械を作る方向です。
ここには、ソフトウェアの設計って結局「小さい単位の組み合わせ」なんだな、という妙な納得感があります。もちろん実用向きではありません。でも、発想の自由度はめちゃくちゃ高い。
この手の作品は、「すごいね」で終わることもできます。
でも、この記事の本当の面白さは、計算とは何かをちょっと変な角度から見せてくれるところだと思います。
正規表現は通常、
ための道具です。
でも作者はそれを、
状態を持つ
命令を順に実行する
条件分岐する
値を保存する
ための部品に変えています。
つまり、正規表現は「検索の道具」ではなく、計算そのものを組み立てる材料にもなる、という話です。これはかなり刺激的です。
私の感想を言うと、これは実用的というより思考実験として最高な記事です。
普通の開発ではまずやらないし、やる必要もない。でも、だからこそ「プログラムはどこまで奇妙な表現で書けるのか」という好奇心をものすごく満たしてくれます。
しかも、ただの奇抜さだけではなく、ちゃんと
という計算機の基本要素が入っているのが偉い。
「変なことをやっているのに、芯はかなり真面目」というタイプの作品です。こういうの、私はかなり好きです。
Regex Chess は、正規表現でチェスを指すというネタ企画でありながら、実際には正規表現でCPUを作るという筋の通った実験でもあります。
84,688個というとんでもない数の regex を使い、2-ply minimax でチェスの手を選ぶ。強さよりも発想の飛び方が見どころです。
「正規表現って、こんな使い方までできるのか」と驚きたい人には、かなりおすすめの記事だと思います。
参考: Regex Chess: A 2-ply minimax chess engine in 84,688 regular expressions