algorithm - Alpha-Beta search truncating my principal variation -

i have implemented alpha-beta search adds results transposition table. then, extracting principal variation transposition table.

this appears work alright analysis @ shallow depths. however, when ask analysis @ depth of 7 plies, this:

7 [+1.00] 1.b1c3 a7a6 2.g1f3 a6a5 3.a6a5  

at end, move repeated. final move placed in table result of pruning, not legal move white. obviously, there less 7 plies printed.

is misunderstanding in alpha-beta search code?

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);     (int = 0; < 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);     (int = 0; < 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; } 

this interesting part of evaluation printing function:

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); 

no move in principal variation should ever pruned, right?

i answering own question save future chess authors several hours of grief.

there trivial bug in which, when cutoff occurs, unapply move late.

however, more interesting problem described here: chess: extracting principal variation transposition table