0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@sen-ltd

Rust のオセロを 3.7 KB の wasm にして、ビットボードで合法手を 7 行で生成する

0
Posted at

オセロの合法手生成を 7 行 で書けることを、知ってるとびっくりする人が多いです。私もそのひとりでした。

Rust の u64 で盤面を持ち、ビットシフトと AND を積み重ねるだけで 8 方向全部の合法手が出る。コードは短いし、出来上がった wasm も 3.7 KB。wasm-bindgen を入れると 50 KB 超えするところを、raw な WebAssembly.instantiate で呼ぶと本当に小さい。

Rust/WASM Reversi の UI。8×8 の濃い緑の盤、中央 4 石の初期配置、合法手の 4 箇所に金色のヒント、画面上に黒 2 白 2 のスコアと『黒の番』

🔗 Demo: https://sen.ltd/portfolio/reversi-wasm/
📦 GitHub: https://github.com/sen-ltd/reversi-wasm

作ったもの

  • Rust で書いた Reversi エンジン（no_std、ヒープ割当ゼロ）
  • raw WebAssembly にコンパイル。wasm-bindgen 不使用
  • UI は vanilla JS + HTML + CSS で WASM の関数を直接呼ぶ
  • AI は α-β 剪定の negamax、深さ 1〜5 から選べる
  • 最終 wasm サイズ: 3,717 バイト（リリースビルド）

ビットボード

盤面を 2 本の u64 で持ちます:

static mut BLACK: u64 = 0;
static mut WHITE: u64 = 0;

bit = row * 8 + col で各マスに対応。bit 0 = a1（左上）、bit 63 = h8（右下）。初期配置:

const INIT_WHITE: u64 = (1u64 << 27) | (1u64 << 36); // d4, e5
const INIT_BLACK: u64 = (1u64 << 28) | (1u64 << 35); // e4, d5

これで 状態 17 バイト。勝敗判定、合法手生成、評価関数、すべてこの 2 本に対するビット演算で書けます。

方向シフト

オセロの 8 方向を u64 のシフトで表現します。列がはみ出さないよう、シフトする前 にマスクで端の列を落とすのがミソ:

const NOT_A_FILE: u64 = 0xFEFEFEFEFEFEFEFE; // bit 0 は「col != 0」
const NOT_H_FILE: u64 = 0x7F7F7F7F7F7F7F7F; // bit 0 は「col != 7」

fn n(x: u64) -> u64  { x >> 8 }                        // 北 (上)
fn s(x: u64) -> u64  { x << 8 }                        // 南 (下)
fn e(x: u64) -> u64  { (x & NOT_H_FILE) << 1 }         // 東
fn w(x: u64) -> u64  { (x & NOT_A_FILE) >> 1 }         // 西
fn ne(x: u64) -> u64 { (x & NOT_H_FILE) >> 7 }         // 北東
fn nw(x: u64) -> u64 { (x & NOT_A_FILE) >> 9 }         // 北西
fn se(x: u64) -> u64 { (x & NOT_H_FILE) << 9 }         // 南東
fn sw(x: u64) -> u64 { (x & NOT_A_FILE) << 7 }         // 南西

行方向の端（bit 0..7 や bit 56..63）はシフトでそのままはみ出るので、マスクは列だけで十分です。

合法手生成 — 7 行

オセロの合法手とは:

自分の石から見て、ある方向に相手の石が 1 個以上連続し、その先が空きマスになっているマス（のうちの空きマス側）

これをビットボードで書くと:

fn legal_moves_dir(me: u64, opp: u64, empty: u64, shift: Shift) -> u64 {
    let mut run = shift(me) & opp;         // 自分の隣にある相手
    run |= shift(run) & opp;                // さらに隣の相手
    run |= shift(run) & opp;
    run |= shift(run) & opp;                // 最大 6 個連続し得る
    run |= shift(run) & opp;
    run |= shift(run) & opp;
    shift(run) & empty                      // その先が空きマス = 合法手
}

これを 8 方向それぞれに呼んで OR する:

fn legal_moves(me: u64, opp: u64) -> u64 {
    let empty = !(me | opp);
    let mut moves = 0u64;
    for shift in DIRECTIONS {
        moves |= legal_moves_dir(me, opp, empty, shift);
    }
    moves
}

これで legal_moves は 64 ビット中、合法手マスだけが 1 の u64 を返します。JS 側はこの値をもらってハイライトに使うだけ。

着手処理 — ひっくり返しも同じパターン

「pos に着手したとき、ひっくり返る敵石」の計算:

fn flips_dir(pos: u64, me: u64, opp: u64, shift: Shift) -> u64 {
    let mut run = shift(pos) & opp;
    run |= shift(run) & opp;
    run |= shift(run) & opp;
    run |= shift(run) & opp;
    run |= shift(run) & opp;
    run |= shift(run) & opp;
    // run の先が me なら挟み込み成立 → run が flip 対象
    if shift(run) & me != 0 { run } else { 0 }
}

先ほどと違うのは「run の先が empty か me か」の判定だけ。8 方向全部 OR して flips_total を得たら:

let new_me = me | pos | flips;
let new_opp = opp & !flips;

これだけ。分岐も配列もなし。

AI — negamax + α-β

オセロは決定論的な 2 人零和ゲームなので、教科書通りの negamax で行けます。

fn negamax(me: u64, opp: u64, depth: u32, mut alpha: i32, beta: i32) -> (i32, u64) {
    if depth == 0 { return (evaluate(me, opp), 0); }

    let moves = legal_moves(me, opp);
    if moves == 0 { /* パス処理、両者パスなら終局 */ }

    let mut best_score = i32::MIN + 1;
    let mut best_move = 0u64;
    let mut bits = moves;
    while bits != 0 {
        let mv = bits & bits.wrapping_neg();     // ← 最下位 1 ビットを抽出
        bits ^= mv;
        let flips = flips_total(mv, me, opp);
        let new_me = me | mv | flips;
        let new_opp = opp & !flips;
        let (s, _) = negamax(new_opp, new_me, depth - 1, -beta, -alpha);
        let score = -s;
        if score > best_score { best_score = score; best_move = mv; }
        if score > alpha { alpha = score; }
        if alpha >= beta { break; }
    }
    (best_score, best_move)
}

ビットボードの嬉しさが最も出るのがこの while bits != 0 のループ。bits & bits.wrapping_neg() は 最下位の 1 ビットだけを抜き出す 標準テクニックで、毎回それを XOR で消しながら合法手を列挙します。配列も Vec も不要。

評価関数はオーソドックスなポジション重み + mobility:

const WEIGHTS: [i32; 64] = [
    100, -25,  10,   5,   5,  10, -25, 100,
    -25, -50,  -1,  -1,  -1,  -1, -50, -25,
     10,  -1,   3,   2,   2,   3,  -1,  10,
      5,  -1,   2,   1,   1,   2,  -1,   5,
      5,  -1,   2,   1,   1,   2,  -1,   5,
     10,  -1,   3,   2,   2,   3,  -1,  10,
    -25, -50,  -1,  -1,  -1,  -1, -50, -25,
    100, -25,  10,   5,   5,  10, -25, 100,
];

角 +100、角の斜め隣（X-square）-50 が効いていて、AI は序盤から「角を狙う／X を避ける」挙動をします。深さ 4 だと 3〜5 秒で手が返ってくる程度の計算量。

wasm-bindgen を使わない理由

wasm-bindgen は便利ですが、文字列や構造体を JS と受け渡しする機能 を提供するライブラリで、それ自体がコード生成される JS グルーを含みます。今回のエクスポートは全部 u32 と u64 という POD だけ:

#[no_mangle]
pub extern "C" fn legal_moves_bits() -> u64 { ... }

#[no_mangle]
pub extern "C" fn apply_move(pos: u32) -> u32 { ... }

#[no_mangle]
pub extern "C" fn ai_choose_move(depth: u32) -> u32 { ... }

JS 側の呼び出しも超シンプル:

const res = await fetch('./assets/reversi.wasm');
const { instance } = await WebAssembly.instantiate(await res.arrayBuffer(), {});
const engine = instance.exports;

engine.reset();
const legal = engine.legal_moves_bits();  // u64 → BigInt が返る
engine.apply_move(pos);
const ai = engine.ai_choose_move(4);

WebAssembly.instantiate が返す exports に直接アクセスするだけ。グルー JS は 0 バイト。結果として最終 wasm が 3.7 KB に収まりました。

no_std + tight release profile

Cargo.toml のリリースプロファイルを絞るのがサイズ削減の主要因:

[profile.release]
opt-level = 3
lto = true
codegen-units = 1
panic = "abort"
strip = true

加えて #![no_std] + #![no_main] にすることで、std のランタイムが丸ごと外れます。パニックハンドラだけは自分で書く:

#[cfg(not(test))]
#[panic_handler]
fn panic(_: &PanicInfo) -> ! { loop {} }

#[cfg(not(test))] で囲むのは、cargo test でネイティブビルドするときに std（test 依存）と衝突するのを避けるため。ここで一度ハマりました。

cargo test も通す

wasm だけ使えればいいなら no_std のまま cargo test も忘れたいところですが、今回はゲームロジックが複雑なので単体テストを書きたい。解決策は上記の #[cfg(not(test))] で panic_handler をテスト時に除外すること:

#![cfg_attr(not(test), no_std)]
#![cfg_attr(not(test), no_main)]

これで cargo test --lib は std 付きでネイティブ実行、cargo build --release --target wasm32-unknown-unknown は std なしで wasm。1 ソースで両方に対応できます。

テストは 7 本書きました:

running 7 tests
test tests::init_has_four_center_disks ... ok
test tests::black_opening_has_four_legal_moves ... ok
test tests::playing_d3_flips_d4 ... ok
test tests::illegal_move_returns_zero ... ok
test tests::ai_at_shallow_depth_returns_a_legal_move ... ok
test tests::ai_takes_corner_on_diagonal_setup ... ok
test tests::apply_pass_only_when_forced ... ok

初期配置、最初の合法手、着手のひっくり返し、不正手の拒否、AI が合法手を返すこと、角を取れる場面で取ること、パスの正当性。ビットボードのバグは初期化か方向シフトに出がちで、この 7 本で十分カバーできます（実装途中で NOT_A_FILE と NOT_H_FILE を取り違えて 1 回詰まった、テストが救いました）。

まとめ

  • オセロの合法手生成は、ビットボード + 8 方向のシフト/AND で 1 方向 7 行 に収まる
  • 着手処理（ひっくり返し）も同じ構造で書ける
  • Rust を no_std + tight release profile + panic = abort にすると、wasm が 3.7 KB になる
  • u32/u64 だけ受け渡す API なら wasm-bindgen も要らず、JS グルーは 0 バイト
  • cargo test との両立は #[cfg(not(test))] で panic_handler を分岐するだけ

リポジトリ: https://github.com/sen-ltd/reversi-wasm

0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?