HN 日本語サマリー

← 一覧へ戻る
プログラミング

AttoChess、278バイトで実現した16ビットx86 DOS向けの完全でプレイ可能なチェスプログラム

AttoChess, a complete, playable chess program for 16-bit x86 DOS in 278 bytes (nicholas-afk.github.io)

13 pointsby SeenNotHeard4 コメント

要約

AttoChessは、16ビットx86 DOS環境で動作する、わずか278バイトの非常にコンパクトなチェスプログラムです。このプログラムは、従来のチェスプログラムが使用していたレンダリングバッファ、BIOSモード設定、複雑な入力デコーダー、スタックからの深さ再読み込み、複雑な駒の移動ロジックなどを排除または簡略化することで、驚異的なコードサイズを実現しています。特に、画面描画を直接コンソールに出力する高速化や、ポインタ演算による入力処理の統合が特徴です。

全文翻訳

Proof-carrying sizecoding · 記録: 272バイト

AttoChess

16ビットx86 DOS向けに、272バイトで実現した完全なプレイアブルチェスプログラムです。盤面を描画し、指し手を読み込み、4手先まで探索し、応手を返します。そして、それがファイル全体のサイズです。

GitHubでソースコードを見る 272バイトのCOMファイルをダウンロード

サイズ

272バイト

ターゲット

x86 DOS .COM

探索

4-ply(4手先まで)

ライセンス

MIT

作者

Nicholas Tanner

年

2026

01 lineage

AttoChessは、LeanChessをサイズ最適化した後継プログラムです。同じゲーム、同じ環境、同じパディングされた盤面と再帰的な駒の探索を持ちながら、272バイトにアセンブルされます。これは、以前は最小の動作するチェスエンジンの記録を保持していた288バイトのプログラムよりも16バイト少ない値です。

1K ZX Chess 672バイト 1982年 · David Horne · Sinclair ZX81

BootChess 487バイト 2015年 · Olivier Poudade · x86ブートセクタ

Toledo Atomchess 352バイト 2015年 · Óscar Toledo G. · x86 DOS (.COM)

LeanChess 288バイト 2019年 · Dmitry Shechtman · x86 DOS (.COM)

AttoChess 272バイト 2026年 · Nicholas Tanner · x86 DOS (.COM)

注記

AttoChessは、単に盤面を表示するだけのバイト数競争のスタントではありません。起動し、局面を描画し、キーボードからあなたの指し手を読み込み、再帰的に4手先まで探索し、応手を選択し、ループします。272バイトは、それらすべてのアセンブルされたサイズであり、生成された.COMファイルで測定されています。

02 AttoChessをプレイする

272バイトのプログラムをエミュレートされたDOSマシンにロードします。あなたは白番です。

あなたの指し手

開始前 K N B P Q R 白  ·  k n b p q r 黒

03 先行研究

ここにあるアイデアのほとんどは新しいものではありません。ほとんどは、他の人々のアイデアをさらに一歩進めたものであり、その連鎖を書き出す価値があります。

LeanChess, Dmitry Shechtman, 2019

これが重要なものです。487バイトのブートセクタから288バイトのDOS .COMへと記録を更新し、それを真に読める設計で行いました。パディングされた0x88盤面、駒のエンコーディングが自身のムーブ生成インデックスとしても機能する点、そして指し手を生成し最善の応手を見つける両方の役割を果たす単一の再帰ルーチンです。AttoChessは派生作品であり、Shechtmanの著作権とMITライセンスをそのまま引き継いでいます。もしこのいずれかに興味があれば、私のソースを読む前に彼のソースを読んでください。

Toledo Atomchess, Óscar Toledo G., 2015

BootChessとLeanChessの間にDOS .COMの記録を保持し、数年かけて352バイト(ブート可能なセクタとしては356バイト、剥ぎ取られた「HACK」ビルドでは326バイト)まで洗練されました。このサイズではすべてそうであるように、AttoChessもキャスリング、アンパッサン、プロモーションは省略しています。この記録に関する記述は、しばしば487バイトから288バイトへと直接飛び、これをスキップします。GitHubのソース。

BootChess, Olivier Poudade, 2015

チェスゲームを512バイトのブートセクタに収め、そのうち487バイトがコードでした。これは現代のコンテストの始まりに近い場所です。Poudadeのページには今もホストされています。

1K ZX Chess, David Horne, 1982

Sinclair ZX81で672バイトにプレイ可能なゲームを詰め込み、30年以上記録を保持しました。

04 サイズの検証

再現できないサイズ記録はあまり価値がありません。ソースをアセンブルし、自分で出力を測定してください。

nasm -f bin -w+error -o ATTOCHES.COM AttoChess.asm
wc -c ATTOCHES.COM        ; 272 bytes
shasum -a 256 ATTOCHES.COM

期待されるSHA-256は 02b80d2b11ba3c6bea02b112e7009c318aac35b3e869f8bb823dc2aa6cdd6f8e です。そのイメージには他に何も含まれていません。すべてのバイトは、プログラムが実際に使用するコードまたはテーブルデータです。

05 最適化

276バイトのフェーズは、ディスプレイ、入力、深さのライフタイム、ポーンの方向、アドレッシングの作業において、LeanChessから12バイトを削減しました。現在のリリースは、構成的にチェックされた1バイト削減を4つ追加しています。最終的なページポインタの書き換えは、新しいポーンのundoがBHを解放することに依存しています。

01 · ディスプレイ

ボードは自分で描画する

これが最も多くのバイトを節約します。元のプログラムは、局面を別のバッファにレンダリングします。盤面をウォークし、各マスを印刷可能な文字に変換し、それを格納し、$ターミネータを付加し、DOS関数 09h (int 21h) で文字列全体を印刷します。そのパスは、バッファポインタの設定、コピーループのストア、ターミネータの書き込み、そしてバッファが盤面の後に配置されるため、イメージ内の予約された盤面配列のコストがかかります。

AttoChessはそれらすべてを削除します。盤面の境界列は、LeanChessが使用した 08h フィラーではなく、CR, LF, CR, LF (0Dh, 0Ah, 0Dh, 0Ah) として配置されます。CRとLFはどちらもビット3がセットされているため、すべての既存の境界/カラーマスクテストは以前と同じように機能しますが、生の盤面バイトはすでに印刷可能なフレームになっています。ディスプレイループは、各バイトを直接コンソールに int 29h (DOS高速コンソール出力) でストリームします。境界は改行に、空のマスはNULになり、実際の駒だけがASCII変換を受けます。

main_loop:
    mov si, board_db + 24          ; 行 2 (黒のバックランク), 列 0
    mov cl, 98                     ; 8ランク行 + 最終CR,LF (CH=0)
disp_loop:
    lodsb                          ; マスの内容を読み込む
    test al, 30h                   ; 駒か?
    jz disp_cont                   ;   いいえ: 生のバイトを出力 (CR / LF / NUL)
    inc ax                         ; キングをゼロアライン
    and al, 27h                    ; 駒タイプ + 黒/小文字ビットを分離
    add al, 4Bh                    ; K, N, B, P, Q, R (色によって大文字/小文字)
disp_cont:
    int 29h                        ; ALの高速コンソール出力
    loop disp_loop

これにより、レンダリングバッファ、そのポインタ設定、$ターミネータ、int 21h/09h 文字列印刷、ファイルイメージ内の予約盤面配列が削除されます。

02 · スタートアップ

BIOSモード設定なし

元のプログラムは、BIOSディスプレイモード0を強制するために int 10h で始まります。AttoChessはこれを削除し、2つの実際の開始前提条件を明示的にすることで、全体として小さくなり、プログラムがどのように起動されても正しい動作をします。

start:
    cld                            ; DFはエントリ時にクリアされる保証はない
    mov cx, 13                     ; 行数 (エントリ時のCXは保証されない)

int 29h を介したストリーミングは、どのビデオモードでも機能するため、モード設定は不要です。

03 · 入力

入力デコーダーがすべての定数を1つのベースアドレスに折りたたむ

指し手を読み込むことは、2つの入力文字(ファイルとランク)を盤面アドレスに変換することです。元のプログラムはこれを段階的に行います。ファイル文字を読み込み、それを加算し、ランク文字を読み込み、and al, 0Fh でマスクダウンし、12 を ah にロードし、mul で行オフセットを取得し、減算します。

AttoChessは、ASCIIバイアス定数をベースアドレスに事前に折りたたむことで算術演算を圧縮し、64K moduloのラップアラウンドを16ビットポインタ演算に任せます。正規化ステップと個別の乗算設定の両方が不要になります。

read_sub:
    mov bp, di
    mov di, board_db + 123 + 0CE0h         ; ベースがASCIIオフセットを事前に折りたたむ
    mov ah, 01h
    int 21h                                ; ファイル文字を読み込む
    add di, ax                             ; AX = 0100h + ファイル文字
    int 21h                                ; ランク文字を読み込む
    imul ax, 12                            ; AX = 12 * (0130h + ランク数字)
    sub di, ax                             ; 対象マスに着地

imul ax, 12 (80186の即値形式乗算) は、mov ah,12 + mul ah のペアを置き換え、ラップアラウンドベースは明示的な and al, 0Fh 入力マスクを不要にします。

04 · 探索

ソースループはCXをそのままにするため、深さは再ロードされない

再帰探索内で、元のプログラムはカウントされた loop (mov cl, 92 ... loop src_loop) で候補ソースマスをスキャンします。これはCXをループカウンタとして再利用するため、そこにある探索深度を破壊します。そのため、各再帰呼び出しは、スタックフレームから深さを再度読み込む (mov cx, [si + 32]) 必要があり、その後デクリメントします。

AttoChessは、ポインタを盤面の終端と比較することでソースマスをウォークします。

src_cont:
    inc bp
    cmp bp, board_db + 120         ; 最後のマスを過ぎたか?
    jnz src_loop

CXは決して触られないため、スキャン全体でライブな深度カウンタとして保持されます。再帰呼び出しサイトは、単に dec cx を実行するだけで、深さのスタックリロードは完全に不要になります。

05 · ポーン

ポーンの方向がカラービットに折りたたまれる

元のプログラムのポーンロジックは、ベクトルの符号ビットを分離し、カラービットに揃えるようにシフトし、サイド・トゥ・ムーブとXORし、パリティで分岐します。これはビットシャッフリングの複数の命令を必要とします。AttoChessは、単一の xor al, dh で前方/後方のテストをサイド・トゥ・ムーブカラーのビット5に直接折りたたみ、ベクトルパリティ(奇数オフセットは斜めを意味する)を再利用してキャプチャとプッシュを区別します。

pawn:
    push ax
    xor al, dh          ; ビット5 := ベクトル符号 XOR サイド・トゥ・ムーブ
    test al, 20h        ; 移動するカラーにとって前方か?
    pop ax              ; POPはフラグをそのまま残す
    jz vec_cont         ;   後方: 拒否
    test al, 1          ; 奇数オフセット (+/-11, +/-13) = 斜めか?
    jnz pawn_cont       ;   斜め: キャプチャでなければならない
    xor ah, 30h         ; 直線 (+/-12): 空きマスチェックのためにデスティネーションカラーを反転
pawn_cont:
    test ah, dl
    jz vec_cont

方向テストが絶対符号ではなくサイド・トゥ・ムーブカラーに依存するようになったため、ポーンは1つのコードパスから両方のカラーで正しく移動します。

06 · アドレッシング

駒タイプがBXに保持されるため、ムーブテーブルのアドレスが1つのleaに折りたたまれる

Peter Ferrie氏による寄稿です。

ソースループはマスを読み込み、駒タイプにマスクダウンし、それをムーブベクタメタデータのインデックスとして使用します。そのインデックスをAXに保持すると、BLへの個別のコピーと2命令のアドレス計算が必要になります。

    mov al, [bp]
    and ax, 07h
    mov bl, al                          ; 駒タイプを保存
    mov si, offset moves_knight - 2     ; ベース
    add si, ax                          ; + インデックス

BLに直接読み込むことで、インデックスはスライダーテストで後から必要とされる場所にすでにあり、アドレス計算全体が単一の lea に圧縮されます。

    mov bl, [bp]
    and bx, 07h                         ; BHもゼロにする
    lea si, [bx + moves_knight - 2]
    lodsb
    cbw                                 ; AHはANDによってゼロにされなくなった

1つの微妙な点があります。元の and ax, 07h は二重の役割を果たしていました。AHもクリアしていたため、それに続く add si, ax はロードされたバイトを16ビット値として扱いました。BXをマスクするとAHは変更されないため、1バイトの cbw でその不変条件を回復する必要があります。正味の節約: 2バイト。

07 · プロローグ

ソースをALに交換してからテストする

古いルーチンは、AXをクリアする前に [BP] を CH と比較します。探索深度は0〜4なので、CH=0 です。ソースを最初に AL に交換してからそのバイトをテストすると、継続的な状態が保持されます。空のソースは、意図的な自己ループの前に冪等なゼロストアを受け取ります。

; 前                                ; 後
cmp  [bp], ch                       xor  ax, ax
jz   $
xor  ax, ax                       xchg al, [bp]
xchg al, [bp]                       test al, al

エンコードされた節約: 1バイト。

08 · ポーン述語

PFに占有状態とベクトルパリティをマッピングする

新しい述語は、デスティネーションの占有状態をキャリーに入れ、ベクトルパリティの隣に回転させ、結果の2つの下位ビットをテストします。パリティは、占有状態が斜め/直線移動と一致する場合にのみ偶数になります。POP はPFを変更せずにAXを復元します。

push ax
and  ah, dl
neg  ah
rcl  al, 1
test al, 3
pop  ax
jpo  vec_cont

AHはメモリundoのために利用可能であるため、XCHG AH,[DI] はBHクローンパスを置き換え、MOV BH,AH を削除します。正味の節約: 1バイト。

09 · データオーバーラップ

キング値を隠し境界の初期化に使用する

eval_db[7]=2Eh は init_db[0] でもあります。評価ルックアップは変更されていません。隠されたトップ境界では、古い 09h と新しい 2Eh の両方が両方のカラーマスクをブロックし、それらのバイトはディスプレイ、ソーススキャン、初期化子セルフフィード読み取りの外側にあります。節約: 1バイト。

10 · ページアドレッシング

コモンベクタページをBHに保持する

AHベースのundoはBHを解放します。評価データ、メタデータ、ベクタはすべて実行時ページ 01xx を占有するため、BH=01h はライブのままにできます。6つの絶対低バイトポインタが RET の後の到達不能な島に移動し、disp16 LEAの代わりにdisp8を許可します。

and  bl, 07h
lea  si, [byte bx + 53h]  ; 8D 77 53
lodsb
mov  ah, bh
xchg ax, si

メタデータバイトは E4 EA E9 ED EF ED で、タイプ2〜7のフルポインタ 01E4h, 01EAh, 01E9h, 01EDh, 01EFh, 01EDh を選択します。節約: 1バイト。この削減は、前のポーン/undo書き換えに依存します。

06 検証証拠

正確な272バイトの成果物には、8つのスタンドアロンSMT-LIB不一致クエリが付属しています。Z3 4.16は、すべての義務に対して UNSAT を返しました。ムーブプロローグ、ポーン述語、再帰呼び出しのデッド入力、メモリundo、コンテキストライブ射影、テーブルオーバーラップ、ポインタメタデータ、拒否パス状態です。

バイナリ監査は、正確な80186命令境界、バイト単位で同一の再エンコーディング、2つの実行可能スパン、メタデータ島からの制御フローの除外、ネストされた PUSHA/POPA 全体でのBH=01hの優位性、およびすべての3つの拒否パスでのAH/BHの読み取り前キルも検証しています。

独立したUnicorn 2.1.4ハーネスは、完全なモデル化されたDOSイベントトレースと、すべての20の合法なオープニングおよび3つの2手シーケンスにわたる配置された盤面状態を比較しました。すべて23件が合格しました。標準的なレポートSHA-256は ab632e7a55ed9ce43f26dae4803080e17c0b625b072a7fa23976f30b537b59f3 です。

GitHubで正確なクエリをリプレイし、ネイティブ証明出力を検査する

範囲

これらの数式は、述べられたローカルおよびコンテキスト上の契約を確立します。それらは、すべてのx86バイト文字列間または機械的に構成された無制限の全プログラムビスミュレーションにおけるグローバルな最小性を証明するものではありません。コンテキスト上のポーン定理は、等しい再帰スコアを明示的な構成仮説として使用します。

07 ビルドと実行

AttoChessは、80186をターゲットとするNASM構文で記述されています。

NASMでアセンブルする
nasm -f bin -w+error -o ATTOCHES.COM AttoChess.asm

これにより、272バイトのDOS実行可能ファイルである ATTOCHES.COM が生成されます。

DOSBoxで実行する
dosbox

次に、DOSBoxプロンプトで次のように入力します。

mount c: .
c:
ATTOCHES.COM

プログラムは標準的なDOS int 21h/int 29h 呼び出しのみを使用するため、実際のハードウェアまたはエミュレートされた16ビットDOS環境(DOSBox、PCem、86Box、または実際のハードウェア)で動作します。

プレイ方法

あなたは白番です。コンピューターは黒番で、それ自身の応手を返します。指し手は4文字で、ソースのファイルとランク、次にデスティネーションのファイルとランクを入力します。例: e2e4。各ペアの指し手の後に盤面が再描画されます。AttoChessは4手先まで探索します。

08 範囲と制限

AttoChessは、ゴルフされたプログラムからルールセットを引き継いでいます。実質的にそれは何を意味するかというと:

  • 標準的な駒の動きとキャプチャを、実際の再帰探索でプレイします。
  • このサイズの先行プログラムと同様に、キャスリング、アンパッサン、ポーンプロモーション、完全なチェック/チェックメイト判定は実装されていません。合法な指し手がなく、スコアがゼロ以上の場合、単に停止します。
  • 入力は信頼されます。完全なエンジンが行うような不正な指し手に対する検証は行わず、フォーマットされた座標を期待します。

これらは、1K未満のチェスでは標準的なトレードオフであり、上記のすべてのプログラムがこれらのルールでプレイしています。バイト数は、それらがすべて同じ削減されたルールでプレイしているため、意味のある比較になります。