recursive, iterative based negamax algorithm for a chess AI
Any idea or pseudo code for a Non-recursive, iterative based negamax algorithm?
I use negamax as the search heart of my Chess AI.
My engine is written in JavaScript and according to the literature can benefit 4x if iteration was used over recursion.
The JavaScript to C penalty is about 3x slower in terms of node depth. This one tweak could level the playing field, but take both factors with a grain of salt :)
Instead of the longer negamax code. Similar recursive code is my "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;
}You can translate a recursive algorithm to an iterative one using a stack. In general, the object you push on the stack will be the same as the parameters you make your recursive call with.
I wrote a non-recursive Negamax routine as an option in the EasyAI python library. The specific source code is at:
https://github.com/Zulko/easyAI/blob/master/easyAI/AI/NonRecursiveNegamax.py
It uses a simple loop with a fixed array of objects (size determined by target depth) to move up and down the tree in an ordered fashion. For the particular project I was using it on, it was six times faster than the recursive version. But I'm sure each game would respond differently.
There is no way to deny that this is some dense and complex code and conversion to Javascript will be ... challenging. It is pretty much nothing but border cases. :)
If you convert it to Javascript, I would love to see the results. Place an link in the comment?
链接地址: http://www.djcxy.com/p/84680.html上一篇: 如何并行化negamax算法？