Codexはゲームボーイで
どこまで強い将棋を作れるか

71万局面を数える

合法手生成の回帰基準にはperftを使った。² 初期局面から全合法手を再帰的に指し、指定した深さの葉局面数を数える試験である。 この実装では、深さ1から4までが順に30、900、25,470、719,731となる。

なかでも perft 4 = 719731 を、以後の変更で維持する基準にした。 探索を速くする変更が評価値や手順を変えても、合法手の集合まで変えていないことを約72万局面で検査できる。 make/unmake後に盤面、持駒、玉位置、局面指紋が元へ戻ることもテストした。

さらにFairy-Stockfish 11.1へ同じ局面を渡し、初期局面、駒打ち、王手回避、任意成り、強制成り、左右非対称局面の合法手集合を比較した。 これらは一致したが、打ち歩詰め局面だけは同版の go perft が反則手を一手含めた。 外部実装を無条件に正解とせず、本実装側の単体テストと将棋定義を確認して、この一手を既知差分として固定した。

ホスト版にはUSIも実装した。 これにより、局面設定、着手列、探索指示を標準的なプロトコルで送り、自作エンジン同士や外部エンジンとの対局を自動化できた。 ゲームボーイ版を速くする候補も、まずホスト上で合法性と対局結果を調べられるようになった。

何を走査しないか

SM83では、盤面の升番号から筋と段を求める9による除算と剰余が、合法手生成の内側で大きな費用になった。 そこで81要素の筋表と段表をROMに置き、表引きへ置き換えた。 盤上81升を行き先候補として総当たりする方式もやめ、歩、桂、飛車といった駒種ごとの移動ベクトルだけをたどるようにした。 この変更だけで、PC上の初期局面perft depth 4も約0.28秒から0.14秒へ短縮した。

王手判定にも盤面全体の走査が残っていた。 両玉の位置を局面へ1バイトずつキャッシュし、玉から8方向へ最初の駒までたどり、桂馬の二方向だけを別に調べる方式へ変えた。 初期局面のように玉の周囲が埋まった局面では、ほぼ隣接升を見るだけで判定が終わる。 この変更でゲームボーイ上の計測値は、5秒で45から66ノード、60秒で425から729ノードへ増えた。

局面の16ビット指紋も、着手のたびに81升と全持駒を数え直すのをやめた。 移動元、移動先、増減した持駒、手番に対応するZobrist値だけを排他的論理和で更新する。 最初に試した単純な線形式は、駒を入れ替えた局面で衝突しやすく、対局でも8局中7敗したため捨てた。 採用品は固定seedから生成した約6KBのZobrist表であり、再計算した指紋との一致をテストしている。

4KBを置換表へ渡す

探索済み局面を再利用する置換表には、ワークRAMの半分を割り当てた。 一項目は16ビットの局面鍵、最善手、評価値、深さ、境界種別を合わせた8バイトで、512項目、計4,096バイトである。 残りのRAMには局面、探索状態、描画用の領域などを置く。

ROMとRAMの全体配分

完成版のリンク結果を機能別に分けると、ROMの約62%を将棋本体が占める。 RAMは置換表だけで半分を使い、静的に確保した領域の合計は4,416バイトである。

将棋本体20,265バイトの内訳には、局面とルール、評価関数、探索に加え、Zobrist表6,208バイトと指し手方向表648バイトが含まれる。 定跡3,901バイトは、局面と候補手のデータ3,072バイトと照合処理829バイトに分かれる。 画面タイル4,928バイトの大半は、盤と駒に使う4,096バイトである。

RAMの「実行時スタックと静的未割当」は、常に3,776バイトが空いているという意味ではない。 局面を読む再帰呼び出し、指し手生成器、着手を戻すための一時データが、実行中にこの領域を上端から使う。

駒得から軽量位置評価へ

評価関数は、手番側にとって局面がどれだけ良いかを整数で返す。 最初の項目は駒得であり、歩を100点として、香300、桂320、銀450、金520、角650、飛750とした。 盤上の駒と持駒を同じ価値で合計し、成駒には別の値を与える。

ゲームボーイ版は、駒得へ三種類の軽量な位置評価を足す。 小駒の前進度、大駒の簡易機動力、玉に隣接する守備駒である。 盤全体の利きや王手の危険度を数えるのではなく、81升を一度走査するあいだに求められる特徴へ絞った。

static const int piece_value[] = {
    0,100,300,320,450,520,650,750,20000,
    520,520,520,520,850,950
};

if (base == PAWN) v += advancement * SHOGI_PAWN_ADVANCE;
else if (base == LANCE) v += advancement * SHOGI_LANCE_ADVANCE;
else if (base == KNIGHT || base == SILVER)
    v += advancement * SHOGI_MINOR_ADVANCE;

前進度は、自陣最下段から相手陣へ何段進んだかである。 5秒設定では一段につき歩3点、香1点、桂と銀2点を加える。 60秒設定では歩3点、香3点、桂と銀1点となり、香の前進をやや強く評価する。 いずれも歩100点に対して小さい値であり、駒損を埋めるほどではない。

飛、角、馬、龍の簡易機動力は、各方向の隣接一升だけを見る。 空升または敵駒なら動ける方向として加点し、その先の長い射線は調べない。 角系では中央へ向かう一升を高くして、初期局面で角道を開ける手と端歩を区別する。

uint8_t to = ray_next[square][direction];
int8_t target = p->board[to];
if (!target || owner_of(target) != side) {
    if (type == BISHOP || type == HORSE) {
        int f = square_file[to];
        int edge_distance = f > 4 ? f - 4 : 4 - f;
        mobility += 5 - edge_distance;
    } else ++mobility;
}

玉の評価も、囲いの名称や玉の位置を知らない。 玉に隣接する金、銀、と金などの自駒を一枚ずつ数え、5秒設定では4点、60秒設定では10点を加える。 このため「玉を安全な場所へ移す」ことと「居玉の周囲へ金銀を集める」ことを区別できない。 後者を選びやすい棋譜は、実装した特徴をそのまま反映している。

if (base == KING) for (int d = 0; d < 8; ++d) {
    uint8_t guard_square = ray_next[i][d];
    if (guard_square >= 81) continue;
    int8_t guard = p->board[guard_square];
    if (king_guard_owner[guard + 14] == side)
        v += SHOGI_LOW_KING_GUARD;
}

5秒設定と60秒設定の評価処理は別の関数として生成した。 一つのループ内で設定を何度も分岐すると5秒設定が遅くなったため、ROMを使ってコードを二重化した。 評価を呼ぶたびに静止探索の深さで関数を一度選び、駒ごとのループ内では分岐しない。 位置評価を増やした結果を「駒得より賢い」とはみなさず、係数ごとに対局で比較した。

葉で取り合いを止めない

アルファベータ法が所定の深さへ達した瞬間に評価関数を呼ぶと、駒を取った直後だけを見て高得点にする場合がある。 次の一手で取り返される局面まで読むかどうかが探索深さの偶然で決まる現象を、水平線効果という。

この偏りを減らすため、通常探索の葉から静止探索（quiescence search）へ入る。 王手でなければ現在局面を評価し、その値を基準に捕獲と成りだけを追加で読む。 王手中は静かな合駒や玉の移動も必要なので、全合法手を生成する。

if (!checked) {
    stand = search_evaluate(p, s);
    if (stand >= beta) return beta;
    if (stand > alpha) alpha = stand;
    if (!qdepth) return alpha;
}
while (checked ? next_legal_do(p, &g, &m, &u)
               : next_tactical_legal_do(p, &g, &m, &u)) {
    int score = -quiesce(p, -beta, -alpha,
                         qdepth - (qdepth != 0), s);
    /* alphaとbetaの更新 */
}

5秒設定は捕獲と成りを原則1手、60秒設定は2手まで読む。 PC版と同じ4手へ戻すと、5秒で13ノードしか進まなかった初期問題が再発するためである。 1手の静止探索を導入したときはノード数が減ったが、32局の予備対局で5秒設定は12勝16分4敗、60秒設定は23勝7分2敗となり、直前版を上回った。

60秒設定の静止探索ではdelta pruningも使う。 ある捕獲や成りで得られる最大の材料点を現在評価へ足してもalphaへ届かないなら、その手を読まない。 将棋では取った駒が持駒になるため、盤上から消す駒と手に入る不成駒の価値を両方数え、成りの増分も加える。 王手には材料点で測れない価値があるので省略しない。

良さそうな手から先に読む

アルファベータ法は、良い手を先に読むほどalphaとbetaの範囲が早く狭まり、後続の枝を多く捨てられる。 そこで本実装は、置換表に保存された最善手、捕獲と成り、その他の静かな手という三段階で生成する。 全手を点数順に並べる配列は作らず、逐次生成器を段階ごとに走査する。

for (int phase = tt_move ? 0 : 1; phase < 3; ++phase) {
    MoveGen g; movegen_init(&g);
    while (phase == 1 ? next_tactical_legal_do(p, &g, &m, &u)
                      : next_legal_do(p, &g, &m, &u)) {
        /* phase 0: 置換表手、1: 捕獲と成り、2: 静かな手 */
    }
}

置換表には評価値だけでなく、その値が正確か、下限か、上限かを記録する。 同じ局面へ別の手順から到達したとき、保存深さが足りれば探索を終え、足りなくても保存手を最初に読む。 512項目しかないため衝突は多いが、8KBのRAMで手順序と枝刈りの両方に使える。

根では反復深化により、深さ1、2、3と一段ずつ探索する。 一見すると最初から深さ3を読むより余計な仕事が増える。 しかし時間切れ時に直前の完了結果が残り、前回の最善手を次の深さで最初に読めるため、手順序も改善する。

深さを省く条件

捕獲と成りを先に読んだ後、すべての静かな手を同じ深さで調べる余裕はない。 現行ROMは次の手法を、王手中や戦術手を除く条件で使う。

futility pruningは、残り深さ1で静的評価に100点を足してもalphaへ届かない場合、残った静かな手を省く。 歩一枚分の余裕を見ても現在の最善値へ届かないなら、捕獲も成りもしない一手で逆転する可能性は低い、という近似である。 王手回避、捕獲、成り、置換表の手には適用しない。

late move pruningは、手順序の後ろへ来た手そのものを省く。 60秒設定の残り深さ2以下で、置換表手と戦術手を含めて11手を調べた後は、残りの静かな手を生成せず終了する。 lateの意味は実際の対局手数ではなく、その局面で何番目に探索したかである。

if (qdepth > 1 && phase == 2 && depth <= 2 &&
    !checked && move_count >= 11) {
    position_undo(p, m, &u);
    goto moves_done;
}

late move reductionは、後ろの手を完全には捨てず、一段浅く読む。 残り深さ4以上で、7手目以降の静かな非王手だけが対象になる。 浅い探索でalphaを上回った手は元の深さで読み直すため、遅い好手を回収できる余地を残す。

principal variation search（PVS）は、最初の一手でalphaを更新できた後、後続手へ「現在の最善手を本当に上回るか」だけを問う幅1の窓を使う。 principal variationとは、その時点の最善手から続く読み筋である。 上回らなければ安く棄却でき、上回った手だけ通常の窓で読み直す。 60秒設定の内部節点だけで有効にし、根局面では再探索費用が実時間で負けたため使わない。

score = -negamax(p, child_depth, -alpha - 1, -alpha, s);
if (!s->stopped && score > alpha && score < beta)
    score = -negamax(p, child_depth, -beta, -alpha, s);

これらは正解を保つ証明付きの枝刈りではない。 futility pruningとlate move pruningは、条件に合う好手を見落とし得る。 PVSとlate move reductionは必要なら再探索するが、その再探索自体が遅いCPUでは負担になる。 そのため固定問題の正答だけで採らず、実時間相当の対局まで比較した。

反復の途中で時間が切れたら

深さ2を完了した後、深さ3の途中で60秒になった場合、通常は完了済みの深さ2を返せる。 しかし本実装は、深さ3で評価を終えた根候補も条件付きで使う。 前回の最善手より十分高い候補だけを採り、小さな評価差は探索順によるノイズとして無視する。

if (!s.stopped) {
    result->best = best;
    result->completed_depth = depth;
} else if (best != principal &&
           best_score >= principal_score + partial_margin) {
    result->best = best;
}

採用幅は5秒設定が2点、60秒設定が175点である。 5秒設定は深さ1の途中結果も使わなければ指し手の比較材料がほとんど残らない。 60秒設定は静止探索と枝刈りによる評価の振れが大きいため、歩一枚を超える差がある候補だけを採る。

深さ2以降では、前回反復の評価に256点を加えた上限を探索窓に使うaspiration windowも導入した。 評価が上限を超えた場合だけ通常の広い窓で読み直す。 下限は最初から広いままにし、時間切れまでに得た部分結果を保ちやすくした。

完成版の初期局面計測は、5秒設定が88ノード、完了深さ1、60秒設定が1,061ノード、完了深さ3となった。 通常ROMは32,768バイト、静的WRAMは4,416バイトである。 リンク終端からROM末尾までの余裕は142バイトしか残っていない。

小さな起動コードの大きな不具合

別の画面崩れは、Cコードではなく専用の起動コードにあった。 ゲームボーイ用のC処理へ入る前に、アセンブリで初期値付きデータを転送し、ゼロ初期化領域を消去する。 ところがゼロクリアの残量判定に使った論理和の結果がAレジスタへ残り、その非ゼロ値をメモリへ書き続けていた。

この不具合は描画更新件数を19にし、不正なVRAMアドレスを作り、割り込み許可レジスタまで意図しない値に変えた。 ループへ入る前に xor a を加えてゼロを作り直し、静的領域、割り込み、スプライト転送を明示的に初期化した。

人間が見つけたのは、押したキーと違う動作や、画面に残った数ピクセルだった。 Codexはそれを、再現用の設定、長押し列、レジスタ値、録画、回帰試験へ変換した。 この往復がなければ、PyBoyとmGBAだけで動くROMを完成品としていた可能性がある。

5秒設定対random（ゲームボーイ先手）

5秒設定は、玉を居玉のままにして金銀を近づける。 定跡を外れた後の駒組みとして自然とは言いにくく、玉の安全を周辺の守備駒数だけで測る評価の粗さが表れている。

それでも終盤には、相手玉の周囲へ飛車、龍、馬、金を運び、詰みまで到達した。 randomは局面の目的を持たず、王手や駒得も他の合法手と同じ確率で選ぶ。 ゲームボーイ版の囲いは奇妙でも、駒得、前進、王手を探索する動きには方向がある。

この一局だけから「randomへ何割勝てる」とは言えない。 ただし異なる着手列となった保存40局では37勝しており、全合法手の一様選択より目的のある手を指す段階には達している。

60秒設定対MaterialLv1（ゲームボーイ後手）

60秒設定でも、玉を動かさず金銀を近づける傾向は残った。 探索が深くなっても、評価関数が好む玉周辺の形そのものは変わらない。

紹介する勝ち棋譜では、多くの駒を相手へ渡しながら、最後は龍で詰ませた。 MaterialLv1の静的評価は玉の安全を数えないが、通常探索器の一手詰め判定は働く。 この局面は、ゲームボーイ版が偶然の非合法手で勝ったのではなく、合法な詰みへ到達した例である。

ただし60秒設定の3勝は、すべてこの同じ着手列だった。 三つの異なる勝ち方を見つけたのではなく、同じ定跡分岐から同じ勝ち筋を再生した。

探索の骨格は本体より古い

静止探索の考え方は、ゲームボーイ発売の39年前まで遡る。 Claude Shannonは1950年の論文で、駒交換の途中に評価関数を適用しても意味が薄く、強制的な変化を比較的静かな局面まで進めてから評価する方法を記した。⁴ 本実装が捕獲と成りを追加で読む理由と同じである。

Zobristは1970年の技術報告で、チェス、チェッカー、囲碁を対象に盤面をハッシュ化する方法を示した。⁵ アルファベータ法も、KnuthとMooreが1975年に正しさと計算量を論じている。⁶

PVSの狭い探索窓にも発売前の系譜がある。 Judea Pearlは1980年にScoutを発表し、Alexander Reinefeldは1983年にその改良であるNegaScoutを発表した。⁷ 1986年のレビューは、PVSとaspirationを既存のゲーム木探索手法として比較している。⁸

late move reductionの年代は、一本の発明年へ整理できなかった。 手ごとに探索量を変えるSEX algorithmの論文は1989年3月に発表されており、ゲームボーイ発売より約7週間早い。 一方、アルファベータ法へfutility pruning、null move pruning、late move reductionを組み合わせた将棋での公開評価は2012年である。⁹ 同論文は、生の分岐数が平均約80の将棋終盤で、実効分岐数を2.8まで減らせると報告した。

現ROMのlate move pruningとdelta pruningについては、初出を確認できる一次資料を特定できなかった。 由来が不明な手法を「ゲームボーイ発売後の発明」とは分類しない。

発売後にそろった開発基盤

発売後に登場したのは、ROM内の基本探索よりも、実装、検証、対局を反復するための基盤だった。 次の年は、公式仕様、プロジェクトの履歴、原案、運用記録で公開時期を確認できる。

SDCCは1999年12月に公開開発の場をSourceForgeへ移し、現在はSM83を対象CPUに含む。¹⁰ Gitは2005年に生まれ、このリポジトリでは動く節目と実験の差分を残した。¹¹

USIの初稿は2007年1月24日付で、GUIと将棋エンジンを標準入出力のテキストで分離する目的を明記している。¹² 本プロジェクトはこの分離を使い、ホスト版を対局器へ接続した。 Floodgateの連続対局モードは2008年2月9日に運用を始め、その公開棋譜を定跡と異なる開始局面の両方へ利用した。¹³

C言語自体はゲームボーイより古いが、採用したC11規格の発行は2011年12月である。¹⁴ mGBAは2013年に始まり、ゲームボーイ対応を2016年に追加した。¹⁵ 実機相当のノード数とRAM上の探索結果を自動で読む環境は、このエミュレータのデバッガを前提としている。

Codexのクラウド型ソフトウェア工学エージェントが研究プレビューとして公開されたのは2025年5月16日だった。¹⁶ アルファベータ法や静止探索を発明したのではなく、既存の手法を32KBと8KBへ合わせ、試験と対局を回し、不採用理由までリポジトリへ残す役割を担った。

したがって、このROMを構成する機械語の中心は、1989年の知識でも設計できた可能性がある。 同じ開発過程は再現できない。 標準プロトコル、公開棋譜、デバッガ付きエミュレータ、分散型の履歴管理、コーディングエージェントは、いずれも発売後にそろったためである。