ハクソク

世界を動かす技術を、日本語で。

Show HN: Sameshi – 約1200 Eloのチェスエンジンで、サイズは2KB以内

100日前原文(github.com)

概要

  • 2KB以内 に収めた最小限のチェスエンジン「sameshi」の紹介
  • Negamax法 と アルファベータ枝刈り による探索アルゴリズム
  • 120セル“mailbox”方式 の盤面表現
  • チェックメイト/ステイルメイト判定 サポート
  • Stockfish との対戦によるEloレーティング評価

sameshi: 2KBチェスエンジンの概要

  • sameshi は、 2KB 以内に収められた極小チェスエンジン
  • Negamax法 と アルファベータ枝刈り による効率的な探索実装
  • 120セルmailbox方式 で盤面を表現し、盤外判定を容易化
  • 合法手判定 （チェック/メイト/ステイルメイト）機能を実装
  • 評価関数 は駒の点数のみを使用し、シンプルな設計
  • キャプチャ優先の指し手順序 による探索効率向上
  • 未対応ルール ：キャスリング、アンパッサン、プロモーション、手数引き分け、三fold repetition
  • Eloレーティング は約1170（95%信頼区間: 1110-1225）と推定
  • Stockfish （Elo 1320-1600）との240局自動対戦による評価
  • 固定探索深さ5、最大60手（plies）までの制限付き対戦

技術的特徴

  • Negamax法 ：MinMax法の変形で、実装を簡潔化
  • アルファベータ枝刈り ：不要な探索を省略し、計算効率を大幅向上
  • 120セルmailbox ：8x8盤面を120セルの1次元配列で管理し、盤外参照時のエラー防止
  • 合法手生成・検証 ：チェック、メイト、ステイルメイトまで対応
  • 素材評価のみ ：局面評価は駒の合計点数のみで判断

パフォーマンス評価

  • Stockfish との自動対戦で実力測定
    • 240局 の対戦データを収集
    • 勝利/引き分け/敗北 のスコアをプールし、標準的なロジスティック式でElo換算
    • 色（白黒） の分布も均等化
    • 95%信頼区間 でElo推定の信頼性を確保

開発者コメント

  • demoscene （コンピュータアートサブカルチャー）へのリスペクトから、極小サイズに挑戦
  • エッジケース を削ることで、チェックメイト/ステイルメイト判定を実装しつつ容量削減
  • Makefile や readableバージョン も提供し、可読性と再現性を重視

まとめ

  • sameshi は、 教育用途 や アルゴリズム学習、 サイズ制約下の開発 に最適
  • フル機能チェスエンジン ではないが、 最小限の実装 で本質を体験可能
  • ソースコード や デモ動画 も公開されており、誰でも試せる環境

Hackerたちの意見

1:1のELOとバイト数を達成するのって可能だと思う？もっと小さくできるけど、賢さは少し落ちるかもね。

└

すごく低いレーティングならあり得るかも？1 ELOあたり1バイトって、ほんの小さな範囲で起こるかもしれないけど、実用的な強さだとすぐに崩れちゃうと思う。

└

これは面白いコードゴルフのチャレンジだね。

https://www.chessprogramming.org/Toledo は、そこそこ強い小さなチェスプログラムのファミリーだよ。

いいプロジェクトだね。GNUチェスのフロントエンドを使って、行数を減らすこともできるし、バックエンドだけ実装するのもアリだよ。バグ報告: a b c d e f g h 8 r n b q k b n r 8 7 . . p p p p p p 7 6 . p . . . . . . 6 5 p . . . . . . . 5 4 P . . P P . . . 4 3 . . . . . . . . 3 2 . P P . . P P P 2 1 R N B Q K B N R 1 a b c d e f g h move: b2b3 ai: b6b4 ポーンは一度動いた後に二マス動くことはできないよ: b6b4はb7b6の後では有効な手じゃない。 （最初に二マス動いて、その後一マス動くのはOKだったけどね。）

└

指摘してくれてありがとう！修正してみるね。テストしてくれて感謝！

ストックフィッシュがキャスリングしたがったせいで、どれだけゲームを捨てなきゃいけなかった？それとも、ストックフィッシュにキャスリングさせないようにしたの？キャスリングってすごく頻繁に出る手だから、それをサポートしていないエンジンの強さについて結論を出すのは難しいよね。

└

キャスリングのためにゲームを捨てることはなかったよ。ストックフィッシュにキャスリングさせないように、合法的な手をフィルタリングして、そのフィルタリングされた手だけをroot_movesで渡すようにしたから、全てのゲームはキャスリングなしのバリアントに留まったんだ。君の言う通り、このレーティングはその制約されたバリアントのもので、フルチェスではないね。

これめっちゃクールだね！持ち駒があるのもいいけど、フルルールセットを実装するのにどれくらいのスペースが必要なんだろう？君が書いてる通り、キャスリング、アンパッサン、昇格、繰り返し、50手ルールは実装されてないけど、これらは現代チェスをプレイするためには必要だよね。小さなエンジンなら繰り返しと50手ルールをスキップするのもありかもしれないけど、キャスリング、アンパッサン、昇格はほぼどんな真剣なプレイにも必要だと思う。https://en.wikipedia.org/wiki/Video_Chess は1980年に4Kでフルルールセットをサポートしてたよね？だから、今現在で最も小さな完全UCI（https://www.chessprogramming.org/UCI）準拠のエンジンは何か知りたいな。フルルールセットをサポートする小さなものを作るのは面白い目標だね。追記：私の最初のチェスコンピュータは1980年代初頭のこれだったよ：https://www.ismenio.com/chess_fidelity_cc3.html - キャスリングとアンパッサンはサポートしてたけど、50手ルールはどうだったかな。

└

ToledoChessには、いくつかの異なる言語での実装があるよ。いくつかのハイライトとしては、キャスリング、エンパッサン、プロモーション、検索、さらにはGUIを含む2KBのJavaScriptとか、特別なルールがないアセンブリで326バイトのものもある。著者はUCI準拠のものは持ってないと思うけど、GUIよりは簡単だと思う。JSのフォークがそれを実現しているかもしれないね。 [0] https://nanochess.org/chess6.html

もし興味がある人がいたら、エンジン開発者の間でELO推定によく使われるツールはcutechessだよ。これがSPRTを使ってるんだ。あとはordoもあるけど、こっちは自分では使ったことないな。 [1] https://cutechess.com/ [2] https://www.chessprogramming.org/Sequential_Probability_Rati... [3] https://github.com/michiguel/Ordo

すごい！最近、全ルールを含むチェスエンジンを約400行（読みやすい）で実装したんだ。最初はJavaで、その後自分のプログラミング言語「Bau」に移植したよ。 [1] これにはターミナルUIも含まれてる。ELOを測るつもりだけど、今までそれを超えられたことはないんだ :-) キャスリングの動きは特に実装が難しいと思う。挑戦が楽しかったよ。 [1] https://github.com/thomasmueller/bau-lang/blob/main/src/test...

└

Bauには符号なしの数値型がないのはどうして？

これはチェスではなく、チェスの駒を動かす何かだね。 > 実装されていない: キャスリング、エンパッサン、プロモーション、繰り返し、50手ルール。

こういう極端な制約の下で作業することには、何か明確なものがあるね。2KBしかないと、チェスの本質的なコアが何なのかを発見せざるを得ない — どの駒が最も重要か、どの評価ヒューリスティックが圧縮に耐えられるか、実装しなくてもいいものは何か。確かにキャスリングやエンパッサン、プロモーションは欠けてるけど、「チェスエンジンが合理的なチェスをプレイするために実際に必要なものは何か」という研究としては、これは興味深いね。答えは驚くほど少ないことが分かった。どこにその2KBが使われているのかの内訳を見てみたいな。手の生成、評価、検索のどれがどれくらい使われてるのか。