javascript - 国际象棋 AI 需要一个非递归的、基于迭代的 negamax 算法

Question

关于非递归、基于迭代的 negamax 算法的任何想法或伪代码？

我使用 negamax 作为我的国际象棋 AI 的搜索核心。

我的引擎是用 JavaScript 编写的，根据文献，如果使用迭代而不是递归，可以获得 4 倍的 yield 。

就节点深度而言，JavaScript 到 C 的惩罚大约慢了 3 倍。这个调整可以平衡竞争环境，但对这两个因素持保留态度:)

而不是更长的 negamax 代码。类似的递归代码是我的“Static Exchange Eval”(SEE)

function _see(sq, fen, depth, maxDepth, color, chess) {
    "use strict";
    if (chess.fen() !== fen) {
        console.error("s fen/chess sync error");
        chess.load(fen);
    }

    if (chess.in_checkmate() || chess.game_over()) {
        return MATE;
    } else if (chess.in_check()) {
        return 0; // ????
    }

    var value = 0, moves, index, move_score, tfen, foo, bar;

    if (depth < maxDepth) {
        moves = chess.moves({
            square: sq,
            verbose: true
        });
        if (moves.length > 0) {
            counter.seeNodes = counter.seeNodes + 1;
            moves = _.chain(moves)
                //only captures
                .reject(function (e) {
                    return !e.hasOwnProperty('captured');
                })
                //material MVV
                .sortBy(function (s) {
                    return evalPiece(s.piece);
                })
                //captures LVA
                .sortBy(function (s) {
                    return -evalPiece(s.captured);
                })
                .value();
            //counter.sDepth = Math.max(depth, counter.sDepth);
            //counter.maxSDepth = Math.max(maxDepth, counter.maxSDepth);        console.error(JSON.stringify(moves));

            for (index = 0; index < moves.length; index += 1) {
                foo = chess.move(moves[index]);
                if (foo === null) {
                    console.error("see move generated error, aborting loop");
                    break;
                }
                tfen = chess.fen();
                value = Math.max(0, evalPiece(foo.captured) - _see(sq, tfen, depth + 1, maxDepth, -color, chess));
                bar = chess.undo();
                if (bar === null) {
                    console.error("see: bar=null");
                }
            }

        }

    }
    return value;
}

Answer 1

您可以使用堆栈将递归算法转换为迭代算法。通常，您压入堆栈的对象将与您进行递归调用时使用的参数相同。