国际象棋AI的递归迭代式negamax算法
非递归迭代的negamax算法的任何想法或伪代码？
我使用negamax作为我的国际象棋AI的搜索核心。
我的引擎是用JavaScript编写的，根据文献，如果递归使用迭代，则可以获得4倍的收益。
JavaScript到C的惩罚在节点深度方面慢了大约3倍。 这一个调整可以平衡比赛场地，但同时考虑到两个因素：
而不是更长的negamax代码。 类似的递归代码是我的“静态交换评估”（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;
}您可以使用堆栈将递归算法转换为迭代算法。 通常，您在堆栈上推送的对象将与递归调用的参数相同。
我在EasyAI python库中编写了一个非递归Negamax例程作为选项。 具体的源代码位于：
https://github.com/Zulko/easyAI/blob/master/easyAI/AI/NonRecursiveNegamax.py
它使用一个简单的循环和固定的对象数组（大小由目标深度决定）以有序的方式在树上上下移动。 对于我使用它的特定项目，它比递归版本快六倍。 但我相信每场比赛都会有不同的回应。
没有办法否认这是一些密集而复杂的代码，并且转换为Javascript将是......具有挑战性的。 这几乎只是边界情况。 :)
如果你把它转换成Javascript，我很乐意看到结果。 在评论中放置一个链接？
链接地址: http://www.djcxy.com/p/84679.html上一篇: recursive, iterative based negamax algorithm for a chess AI