正規表現で実装されたミニマックス・チェスエンジン

 (nicholas.carlini.com)
4 ポイント 投稿者 GN⁺ 2025-01-08 | 1件のコメント | WhatsAppで共有

2重ミニマックス・チェス・エンジン

  • チェスと正規表現: 著者は正規表現だけを使ってチェスを指すプログラムを作成した。 このプログラムは、チェス盤を入力として受け取り、有効手を生成する84,688個の正規表現で構成されている。

  • 正規表現CPUの設計: 正規表現を用いて分岐なし実行とSIMD（Single Instruction Multiple Data）命令セットを設計した。これにより、チェスを指すプログラムを作成できる。

  • データ構造: コンピュータの現在の状態は、プログラム「スタック」とすべての変数を含む1つの文字列として表現される。各命令は、スタック上の変数を操作するか、特定の変数に対して読み取り/書き込み操作を行う。

  • 基本スタック操作:

    • プッシュ命令: スタックの先頭に値を追加する。
    • ポップ命令: スタックの先頭要素を削除する。

  • 変数↔スタック命令:

    • 変数参照: 変数の内容をスタックの先頭に読み込む。
    • 変数代入: 変数へ値を代入し、変数が存在するかどうかに応じて更新または新規作成する。

  • 条件文: 条件文によってプログラムのフローを制御する。条件に基づいてプログラムの特定部分を有効化または無効化する。

  • ループ不可能性: 正規表現だけではループを実装できないため、すべての反復計算は事前に展開しておく必要がある。

  • マルチスレッド実行: 正規表現のグローバル置換機能を利用して、複数のスレッドを同時に実行できる。

  • チェスエンジンの実装: チェスエンジンは他のプログラミング言語での記述と同様に作成でき、並列処理によって高速に動作する。

  • ターンプレイ:

    • プレイヤーの手の読み取り: 入力された手を読み込み、妥当性を検証する。
    • コンピュータの応答生成: 可能なすべての応答を生成し、最適な手を選ぶ。

  • ミニマックス探索: 深さ2のミニマックス探索を通じて最適な手を選択する。この過程は並列処理によって効率的に行われる。

このプロジェクトは、正規表現の独創的な利用によってチェスエンジンを実装した例であり、正規表現の強力さと創造的なコンピュータ設計を示している。

関連記事

1件のコメント

 
GN⁺ 2025-01-08
Hacker News の意見

  • この開発者は、printf() がチューリング完全であることを示し、13kB の JavaScript で一人称シューティングゲームを作成した人物だ

  • このプロジェクトが特異なのは、複数の候補手の計算が並列で実行される点だ

    • 正規表現を使って複数スレッドを同時に実行できる

  • ブログ記事の結論について特にコメントしたいことはないが、このような無意味なプロジェクトをもっと多くの人が試してほしい

    • ただ楽しく、完了までの時間や成功するかどうかの負担がないため、コンピューターサイエンスのさまざまな分野について多くのことを学べる

  • チェスゲームで「不正な手、敗北」というバグが発生している

    • サンプルゲームでは不正な手ではないのにゲームが終了してしまう

  • 84,688 個の正規表現でチェスをする人より、1 つの正規表現でチェスをする人のほうがより恐ろしく思える

  • この種のプロジェクトを見ていると、敬意を表したくなる

  • a-ファイル移動に関するバグが修正された

  • このプロジェクトはチェスエンジンであるだけでなく、正規表現だけで構築されたコンピューターおよびアセンブリ言語でもある

  • 以前には sed で書かれたチェスのプロジェクトがあった

    • sed 版は制御フロー命令を使い、1ply だけを探索する

  • a2a4 で始めると、これほど早く負けることはない

  • 明確な「生産的」な目標を持たずに何かを試してみることは、新しい方法を見つけ、イノベーションをもたらすことができる

    • エンジンは序盤で駒を落とす
    • 大文字を入力すると「不正な手」と表示される

  • 革新を試み、もっと生産的になろうとする取り組みは続行中だ