1
Irgendwelche Idee oder Pseudocode für einen nicht-rekursiven, iterativ basierten Negamax-Algorithmus?Benötigen Sie einen nicht-rekursiven, iterativ basierten Negamax-Algorithmus für eine Schach-AI
Ich benutze Negamax als Suchkern meiner Schach-KI.
Meine Engine ist in JavaScript geschrieben und kann laut Literatur 4fach nutzen, wenn Iteration über Rekursion verwendet wurde.
Die JavaScript zu C Strafe ist etwa 3x langsamer in Bezug auf die Knotentiefe. Dieser eine Tweak könnte das Spielfeld nivellieren, aber beide Faktoren mit einem Körnchen Salz nehmen :)
Anstelle des längeren Negamax-Codes. Ähnlicher rekursiven Code ist mein "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;
}
Die Veröffentlichung Ihres aktuellen Codes würde Ihnen helfen, eine bessere Lösung zu finden. – Chris
Ich habe kürzlich eine generische nicht-rekursive Negamax-Routine geschrieben, die ein einfaches Array von Objekten verwendet. Die Bibliothek [easyAI] (http://zulko.github.io/easyAI/) wird eher in Python als in Javascript geschrieben. aber Sie könnten den Code sicherlich mit wenig Problem konvertieren. Die spezifische Quelldatei ist unter: https://github.com/Zulko/easyAI/blob/master/easyAI/AI/NonRecursiveNegamax.py – JohnAD