やねうら王 — 日本将棋AIの探索基盤

Minimax は「自分は評価値を最大化、相手は最小化」と仮定して、 木を末端まで読み、葉ノードの評価値を上に伝播させる：

function minimax(node, depth, maximizing):
    if depth == 0 or node が終局:
        return evaluate(node)
    if maximizing:  // 自分の手番
        best = -∞
        for child in children(node):
            val = minimax(child, depth-1, false)
            best = max(best, val)
        return best
    else:           // 相手の手番
        best = +∞
        for child in children(node):
            val = minimax(child, depth-1, true)
            best = min(best, val)
        return best

問題：将棋は1局面あたり約80手の候補があるので、深さ d 読むと 80^d ノード。 d=10 で約 10¹⁹ ノード。到底読み切れない。

// 自分（max）の手番から探索を開始
function alphaBeta(node, depth, alpha, beta, maximizing) {
    if (depth === 0 || isTerminal(node)) {
        return evaluate(node);  // ← 評価関数を呼ぶのはここ（NNUEなど）
    }

    if (maximizing) {
        let value = -Infinity;
        for (const child of moveOrder(node)) {
            value = Math.max(value, alphaBeta(child, depth-1, alpha, beta, false));
            alpha = Math.max(alpha, value);
            if (alpha >= beta) break;  // ★β枝刈り：これ以上読んでも無駄
        }
        return value;
    } else {
        let value = +Infinity;
        for (const child of moveOrder(node)) {
            value = Math.min(value, alphaBeta(child, depth-1, alpha, beta, true));
            beta = Math.min(beta, value);
            if (alpha >= beta) break;  // ★α枝刈り
        }
        return value;
    }
}

// 反復深化（Iterative Deepening）
function search(root, maxDepth) {
    let best;
    for (let d = 1; d <= maxDepth; d++) {
        best = alphaBeta(root, d, -Infinity, +Infinity, true);
        // ★ 浅い結果を moveOrder のヒントに使う → 枝刈り効率UP
    }
    return best;
}

// 各子ノードを評価するループの中で
for (let i = 0; i < children.length; i++) {
    const child = children[i];
    let reduction = 0;
    if (i >= 3 && depth >= 3 && !isCheck(child)) {
        reduction = 1 + Math.floor(Math.log(i) / Math.log(2));
        // ★ 「i 番目以降」「王手じゃない」「ある程度深い」とき、深さを削る
    }
    let val = -alphaBeta(child, depth - 1 - reduction, -beta, -alpha, !max);
    if (reduction > 0 && val > alpha) {
        // 削った結果が良すぎたら、フルの深さでもう一度読み直す
        val = -alphaBeta(child, depth - 1, -beta, -alpha, !max);
    }
}

function alphaBeta(node, depth, alpha, beta, maximizing) {
    // ... 標準処理 ...

    // ★ Null Move Pruning
    if (depth >= 3 && !inCheck(node) && hasNonPawnMaterial(node)) {
        // 自分の手をパスして相手に渡す
        const nullNode = makeNullMove(node);
        const val = -alphaBeta(nullNode, depth - 3, -beta, -beta + 1, !maximizing);
        if (val >= beta) {
            return beta;  // パスしても勝てる → これ以上読まない
        }
    }

    // ... 通常の子探索 ...
}

const TT = new Map();  // 置換表（実装では巨大な配列＋Zobrist hash）

function alphaBeta(node, depth, alpha, beta, maximizing) {
    const key = zobristHash(node);
    const cached = TT.get(key);
    if (cached && cached.depth >= depth) {
        // ★ 既に十分深く読んだ結果がある → 即返却
        return cached.value;
    }

    // ... 通常の探索 ...

    TT.set(key, { value, depth, bestMove });  // 結果をキャッシュ
    return value;
}

// 概念図：ルート分割並列（Lazy SMP）
function parallelSearch(root, numThreads) {
    const sharedTT = new ConcurrentMap();

    const workers = [];
    for (let t = 0; t < numThreads; t++) {
        workers.push(spawn(() => {
            // 各スレッドが少しずらした深さ・ヒューリスティクスで同じ木を探索
            // 置換表を共有することで知見が伝播する
            alphaBetaWithSharedTT(root, baseDepth + (t % 2), sharedTT);
        }));
    }
    waitAll(workers);
    return sharedTT.get(zobristHash(root)).bestMove;
}

// ===== やねうら王本体（探索部） =====
function alphaBeta(node, depth, alpha, beta, max) {
    if (depth === 0) {
        return evaluate(node);  // ★ ここだけが評価関数とのインターフェース
    }
    // ... α-β の標準処理 ...
}

// ===== 評価関数（差し替え可能） =====
// 起動時に nn.bin を読み込んで evaluator を構築
const evaluator = loadNNUE("suisho10.nn.bin");
// または
const evaluator = loadNNUE("hao.nn.bin");
// または
const evaluator = loadNNUE("tanuki-wcsc33.nn.bin");

function evaluate(node) {
    // node の HalfKP特徴を抽出して、浅いMLPを通すだけ
    return evaluator.forward(node);
}

この 「evaluate() の中身だけ差し替える」設計が、エコシステム全体を可能にしました。

• 探索：α-β ではなく MCTS（モンテカルロ木探索）
• 評価：浅い MLP ではなく 深い CNN + ResNet（dlshogi 系モデル）
• 差し替え可能性：dlshogi の学習済みモデルをそのまま使える
• ハード：GPU 推論が必須

同じ「やねうら王」ブランドの下に NNUE型・DL型の両方が存在する。 ユーザーは用途に応じて使い分けられる。