Ich habe eine Alpha-Beta-Suche implementiert, die ihre Ergebnisse zu einer Transpositionstabelle hinzufügt. Dann entziehe ich die Hauptvariation aus der Transpositionstabelle.Alpha-Beta-Suche trunkiert meine Hauptvariante
Dies scheint für die Analyse in geringen Tiefen gut zu funktionieren. Allerdings, wenn ich für die Analyse in einer Tiefe von 7 Lagen fragen, ich diese:
7 [+1.00] 1.b1c3 a7a6 2.g1f3 a6a5 3.a6a5
Am Ende wird ein Schritt wiederholt. Dieser letzte Zug wird als Ergebnis des Beschneidens in die Tabelle gelegt, ist aber für Weiß nicht einmal ein legaler Zug. Offensichtlich sind weniger als 7 Lagen gedruckt.
Ist das ein Missverständnis in meinem Alpha-Beta-Suchcode?
int ab_max(board *b, int alpha, int beta, int ply) {
if (ply == 0) return evaluate(b);
int num_children;
move chosen_move = no_move;
move *moves = board_moves(b, &num_children);
assert(num_children > 0);
for (int i = 0; i < num_children; i++) {
apply(b, moves[i]);
int score = ab_min(b, alpha, beta, ply - 1);
if (score >= beta) {
tt_put(b, (evaluation){moves[i], score, at_least, ply});
unapply(b, moves[i]);
free(moves);
return beta; // fail-hard
}
if (score > alpha) {
alpha = score;
chosen_move = moves[i];
}
unapply(b, moves[i]);
}
tt_put(b, (evaluation){chosen_move, alpha, exact, ply});
free(moves);
return alpha;
}
int ab_min(board *b, int alpha, int beta, int ply) {
if (ply == 0) return evaluate(b);
int num_children;
move chosen_move = no_move;
move *moves = board_moves(b, &num_children);
assert(num_children > 0);
for (int i = 0; i < num_children; i++) {
apply(b, moves[i]);
int score = ab_max(b, alpha, beta, ply - 1);
if (score <= alpha) {
tt_put(b, (evaluation){moves[i], score, at_most, ply});
unapply(b, moves[i]);
free(moves);
return alpha; // fail-hard
}
if (score < beta) {
beta = score;
chosen_move = moves[i];
}
unapply(b, moves[i]);
}
tt_put(b, (evaluation){chosen_move, beta, exact, ply});
free(moves);
return beta;
}
Dies ist der interessanteste Teil meiner Bewertung Druckfunktion:
do {
if (!b->black_to_move) printf("%d.", moveno++);
char move[6];
printf("%s ", move_to_string(eval->best, move));
apply(b, eval->best);
eval = tt_get(b);
} while (eval != NULL && depth-- > 0);
Keine Bewegung in meiner Hauptvariante je beschnitten werden soll, nicht wahr?