I have a humble help request of more like showing me a path rather than a concrete solution, but still I'll describe the issue.
I've created 30+ youtube video series on creating a simple chess engine from scratch.
I thought I'm so cool... until reached the negamax alphabeta search...
While understanding move generation process really clear (as series shows) I've horribly realized that when it came to the search I always copypasted it...
I know it's a shame... So from now on I really really want to master it and looking for a guidance at this point.
Particular technical issue I encounter: mating score and associated move are not always returned correclty, it seems like it depends on search depth somehow, e.g. at depth 5 it doesn't find mate in 1 while at depth 2 it does.
I have a very very basic negamax failhard framework (copypasted numerous times(((( ):
maksimKorzh wrote: ↑Thu Aug 06, 2020 3:44 pm
Dear community
I have a humble help request of more like showing me a path rather than a concrete solution, but still I'll describe the issue.
I've created 30+ youtube video series on creating a simple chess engine from scratch.
I thought I'm so cool... until reached the negamax alphabeta search...
While understanding move generation process really clear (as series shows) I've horribly realized that when it came to the search I always copypasted it...
I know it's a shame... So from now on I really really want to master it and looking for a guidance at this point.
Particular technical issue I encounter: mating score and associated move are not always returned correclty, it seems like it depends on search depth somehow, e.g. at depth 5 it doesn't find mate in 1 while at depth 2 it does.
I have a very very basic negamax failhard framework (copypasted numerous times(((( ):
// search position
int search_position(int alpha, int beta, int depth)
{
// legal moves
int legal_moves = 0;
// best move
int best_so_far = 0;
// old alpha
int old_alpha = alpha;
// escape condition
if (!depth)
// search for calm position before evaluation
return quiescence_search(alpha, beta);
// create move list variable
moves move_list[1];
// generate moves
generate_moves(move_list);
// loop over the generated moves
for (int move_count = 0; move_count < move_list->count; move_count++)
{
// define board state variable copies
int board_copy[128], king_square_copy[2];
int side_copy, enpassant_copy, castle_copy;
// copy board state
memcpy(board_copy, board, 512);
side_copy = side;
enpassant_copy = enpassant;
castle_copy = castle;
memcpy(king_square_copy, king_square,8);
// make only legal moves
if (!make_move(move_list->moves[move_count], all_moves))
// skip illegal move
continue;
// increment legal moves
legal_moves++;
// recursive call
int score = -search_position(-beta, -alpha, depth - 1);
// restore board position
memcpy(board, board_copy, 512);
side = side_copy;
enpassant = enpassant_copy;
castle = castle_copy;
memcpy(king_square, king_square_copy,8);
// fail hard beta-cutoff
if (score >= beta)
return beta;
// alpha acts like max in MiniMax
if (score > alpha)
{
// set alpha score
alpha = score;
// store current best move
best_so_far = move_list->moves[move_count];
}
}
// if no legal moves
if (!legal_moves)
{
// check mate detection
if (is_square_attacked(king_square[side], side ^ 1))
return -49000;
// stalemate detection
else
return 0;
}
// associate best score with best move
if (alpha != old_alpha)
best_move = best_so_far;
// return alpha score
return alpha;
}
Finally, to get an idea of how it behaves you can watch this video:
it has timestamps in the description pointing out where the issue occurs.
I'm not asking for a working solution but I would be very very grateful if you guys kindly point me the right direction. Thanks in advance!
One of the things I notice is that you don't update the best move when there is a beta cut-off, but if everything else is right it should still return the mate score.
Are you sure that the move-generator, the check for illegal moves and the is_square_attacked function are working in the way they should?
maksimKorzh wrote: ↑Thu Aug 06, 2020 3:44 pm
Dear community
I have a humble help request of more like showing me a path rather than a concrete solution, but still I'll describe the issue.
I've created 30+ youtube video series on creating a simple chess engine from scratch.
I thought I'm so cool... until reached the negamax alphabeta search...
While understanding move generation process really clear (as series shows) I've horribly realized that when it came to the search I always copypasted it...
I know it's a shame... So from now on I really really want to master it and looking for a guidance at this point.
Particular technical issue I encounter: mating score and associated move are not always returned correclty, it seems like it depends on search depth somehow, e.g. at depth 5 it doesn't find mate in 1 while at depth 2 it does.
I have a very very basic negamax failhard framework (copypasted numerous times(((( ):
// search position
int search_position(int alpha, int beta, int depth)
{
// legal moves
int legal_moves = 0;
// best move
int best_so_far = 0;
// old alpha
int old_alpha = alpha;
// escape condition
if (!depth)
// search for calm position before evaluation
return quiescence_search(alpha, beta);
// create move list variable
moves move_list[1];
// generate moves
generate_moves(move_list);
// loop over the generated moves
for (int move_count = 0; move_count < move_list->count; move_count++)
{
// define board state variable copies
int board_copy[128], king_square_copy[2];
int side_copy, enpassant_copy, castle_copy;
// copy board state
memcpy(board_copy, board, 512);
side_copy = side;
enpassant_copy = enpassant;
castle_copy = castle;
memcpy(king_square_copy, king_square,8);
// make only legal moves
if (!make_move(move_list->moves[move_count], all_moves))
// skip illegal move
continue;
// increment legal moves
legal_moves++;
// recursive call
int score = -search_position(-beta, -alpha, depth - 1);
// restore board position
memcpy(board, board_copy, 512);
side = side_copy;
enpassant = enpassant_copy;
castle = castle_copy;
memcpy(king_square, king_square_copy,8);
// fail hard beta-cutoff
if (score >= beta)
return beta;
// alpha acts like max in MiniMax
if (score > alpha)
{
// set alpha score
alpha = score;
// store current best move
best_so_far = move_list->moves[move_count];
}
}
// if no legal moves
if (!legal_moves)
{
// check mate detection
if (is_square_attacked(king_square[side], side ^ 1))
return -49000;
// stalemate detection
else
return 0;
}
// associate best score with best move
if (alpha != old_alpha)
best_move = best_so_far;
// return alpha score
return alpha;
}
Finally, to get an idea of how it behaves you can watch this video:
it has timestamps in the description pointing out where the issue occurs.
I'm not asking for a working solution but I would be very very grateful if you guys kindly point me the right direction. Thanks in advance!
One of the things I notice is that you don't update the best move when there is a beta cut-off, but if everything else is right it should still return the mate score.
Are you sure that the move-generator, the check for illegal moves and the is_square_attacked function are working in the way they should?
re: Are you sure that the move-generator, the check for illegal moves and the is_square_attacked function are working in the way they should?
Yes, absolutely because I've passed the perft test.
re: One of the things I notice is that you don't update the best move when there is a beta cut-off
- Should I? Sorry for a dumb question, but my understanding of beta cutoffs is limited like... skip calculating the branch because it gives a loosing score. So I'm not sure what exactly it returns.
// associate best score with best move
if (alpha != old_alpha)
best_move = best_so_far;
Is best_move a global? If yes, then shouldn't we only be setting this at the root of the search? Otherwise this might get set on moves at nearly the leaf of the tree, and should often be suggesting illegal moves.
1) "best_move" is a global variable which you seem to overwrite from everywhere in the tree. This can often lead to random results, not limited to mate scores. So you'd better make "best_move" an output parameter (in C++ "int & best_move" or in C/C++ "int * best_move"). It will be redundant for all depths except the root, though, since you normally only consume the score of the subtree. There are at least two solutions to avoid this redundancy: either have a separate search function for the root (and maintain "best_move" only there), or track the whole principal variation (PV) as a result parameter at each depth. The former is easy to quickly get a working search (if you do not accept the redundancy I mentioned), the latter is the future way to go since you will certainly want to be able to let your search report its progress somehow. Whenever you get a new best score within the alpha-beta window (so > alpha and < beta), you update the PV of the current node by concatenating the current move with the PV that was returned from its subtree.
2) Distance to mate is unknown for your search since you always return "-49000" whenever you detect that the side to move is mated. A typical solution is to simply return "-(49000 - distance_to_root)" instead. This ensures that the moving side will always favor moves leading to a shorter mate, if there is any forced mate available at all. The "distance_to_root" value (often simply called "ply") is an additional parameter of your search_position() function. Obviously you call search_position() with ply=0 at the root, and with ply+1 in the recursive call.
There are some more points to comment on, where none of them is really critical, nor related to your main goal of getting correct mate scores.
- Improve your make/unmake code: Your copy&make approach is fine in general. But I would change two things to improve it:
a) put all board-related variables into one struct (or class) - to get source code that is easier to read,
b) think about saving all board copies on a stack that is maintained outside of "search_position()" and passed in as a parameter, and then simply moving the stack pointer back one level when doing the "unmake" - to avoid a second copying action.
- Avoid redundancy of "best_so_far" and "old_alpha": both variables are not really necessary in this simple implementation of a full-widh fail-hard alpha-beta search. If your move loop terminates then "best_so_far" is already the best move of the current node, the condition "alpha != old_alpha" which you use for assigning "best_move = best_so_far" is always false if no subtree score was sufficient to improve alpha. So in conjunction with my point 1) above you could think about removing "old_alpha" and about melting "best_so_far" and "best_move" into just one variable.
Joost Buijs wrote: ↑Thu Aug 06, 2020 4:46 pm
One of the things I notice is that you don't update the best move when there is a beta cut-off, but if everything else is right it should still return the mate score.
Are you sure that the move-generator, the check for illegal moves and the is_square_attacked function are working in the way they should?
re: Are you sure that the move-generator, the check for illegal moves and the is_square_attacked function are working in the way they should?
Yes, absolutely because I've passed the perft test.
re: One of the things I notice is that you don't update the best move when there is a beta cut-off
- Should I? Sorry for a dumb question, but my understanding of beta cutoffs is limited like... skip calculating the branch because it gives a loosing score. So I'm not sure what exactly it returns.
// fail hard beta-cutoff
if (score >= beta)
{
best_move = best_so_far;
return beta;
}
So can I say that the current version would work in brute force negamax when we associate bestscore (alpha equivalent) with best move?
"best_move" does not need to be updated on a beta cutoff since the parent node will discard the move leading to this subtree (that is the subject of a cutoff) so our "best_move" would not be propagated towards the root, it will never be part of the PV.
Joost Buijs wrote: ↑Thu Aug 06, 2020 4:46 pm
One of the things I notice is that you don't update the best move when there is a beta cut-off, but if everything else is right it should still return the mate score.
Are you sure that the move-generator, the check for illegal moves and the is_square_attacked function are working in the way they should?
re: Are you sure that the move-generator, the check for illegal moves and the is_square_attacked function are working in the way they should?
Yes, absolutely because I've passed the perft test.
re: One of the things I notice is that you don't update the best move when there is a beta cut-off
- Should I? Sorry for a dumb question, but my understanding of beta cutoffs is limited like... skip calculating the branch because it gives a loosing score. So I'm not sure what exactly it returns.
// fail hard beta-cutoff
if (score >= beta)
{
best_move = best_so_far;
return beta;
}
So can I say that the current version would work in brute force negamax when we associate bestscore (alpha equivalent) with best move?
"best_move" does not need to be updated on a beta cutoff since the parent node will discard the move leading to this subtree (that is the subject of a cutoff) so our "best_move" would not be propagated towards the root, it will never be part of the PV.
Joost Buijs wrote: ↑Thu Aug 06, 2020 4:46 pm
One of the things I notice is that you don't update the best move when there is a beta cut-off, but if everything else is right it should still return the mate score.
Are you sure that the move-generator, the check for illegal moves and the is_square_attacked function are working in the way they should?
re: Are you sure that the move-generator, the check for illegal moves and the is_square_attacked function are working in the way they should?
Yes, absolutely because I've passed the perft test.
re: One of the things I notice is that you don't update the best move when there is a beta cut-off
- Should I? Sorry for a dumb question, but my understanding of beta cutoffs is limited like... skip calculating the branch because it gives a loosing score. So I'm not sure what exactly it returns.
// fail hard beta-cutoff
if (score >= beta)
{
best_move = best_so_far;
return beta;
}
So can I say that the current version would work in brute force negamax when we associate bestscore (alpha equivalent) with best move?
"best_move" does not need to be updated on a beta cutoff since the parent node will discard the move leading to this subtree (that is the subject of a cutoff) so our "best_move" would not be propagated towards the root, it will never be part of the PV.
This might be so, but you'll need it if this is the root-node and there is no parent node, which is absolutely not clear from this example.
You can argue that there will never be a beta cutoff at the root, but it solely depends upon how you handle the root.
maksimKorzh wrote: ↑Thu Aug 06, 2020 3:44 pm
Dear community
I have a humble help request of more like showing me a path rather than a concrete solution, but still I'll describe the issue.
I've created 30+ youtube video series on creating a simple chess engine from scratch.
I thought I'm so cool... until reached the negamax alphabeta search...
While understanding move generation process really clear (as series shows) I've horribly realized that when it came to the search I always copypasted it...
I know it's a shame... So from now on I really really want to master it and looking for a guidance at this point.
Particular technical issue I encounter: mating score and associated move are not always returned correclty, it seems like it depends on search depth somehow, e.g. at depth 5 it doesn't find mate in 1 while at depth 2 it does.
I have a very very basic negamax failhard framework (copypasted numerous times(((( ):
// search position
int search_position(int alpha, int beta, int depth)
{
// legal moves
int legal_moves = 0;
// best move
int best_so_far = 0;
// old alpha
int old_alpha = alpha;
// escape condition
if (!depth)
// search for calm position before evaluation
return quiescence_search(alpha, beta);
// create move list variable
moves move_list[1];
// generate moves
generate_moves(move_list);
// loop over the generated moves
for (int move_count = 0; move_count < move_list->count; move_count++)
{
// define board state variable copies
int board_copy[128], king_square_copy[2];
int side_copy, enpassant_copy, castle_copy;
// copy board state
memcpy(board_copy, board, 512);
side_copy = side;
enpassant_copy = enpassant;
castle_copy = castle;
memcpy(king_square_copy, king_square,8);
// make only legal moves
if (!make_move(move_list->moves[move_count], all_moves))
// skip illegal move
continue;
// increment legal moves
legal_moves++;
// recursive call
int score = -search_position(-beta, -alpha, depth - 1);
// restore board position
memcpy(board, board_copy, 512);
side = side_copy;
enpassant = enpassant_copy;
castle = castle_copy;
memcpy(king_square, king_square_copy,8);
// fail hard beta-cutoff
if (score >= beta)
return beta;
// alpha acts like max in MiniMax
if (score > alpha)
{
// set alpha score
alpha = score;
// store current best move
best_so_far = move_list->moves[move_count];
}
}
// if no legal moves
if (!legal_moves)
{
// check mate detection
if (is_square_attacked(king_square[side], side ^ 1))
return -49000;
// stalemate detection
else
return 0;
}
// associate best score with best move
if (alpha != old_alpha)
best_move = best_so_far;
// return alpha score
return alpha;
}
Finally, to get an idea of how it behaves you can watch this video:
it has timestamps in the description pointing out where the issue occurs.
I'm not asking for a working solution but I would be very very grateful if you guys kindly point me the right direction. Thanks in advance!
One of the things I notice is that you don't update the best move when there is a beta cut-off, but if everything else is right it should still return the mate score.
Are you sure that the move-generator, the check for illegal moves and the is_square_attacked function are working in the way they should?
re: Are you sure that the move-generator, the check for illegal moves and the is_square_attacked function are working in the way they should?
Yes, absolutely because I've passed the perft test.
re: One of the things I notice is that you don't update the best move when there is a beta cut-off
- Should I? Sorry for a dumb question, but my understanding of beta cutoffs is limited like... skip calculating the branch because it gives a loosing score. So I'm not sure what exactly it returns.
// fail hard beta-cutoff
if (score >= beta)
{
best_move = best_so_far;
return beta;
}
So can I say that the current version would work in brute force negamax when we associate bestscore (alpha equivalent) with best move?
At fist glance I would say it should work if everything else is correct, and I would update best_sofar also when there is a beta cutoff if you want to store it in a transposition-table in the future.
if (score > alpha)
{
best_sofar = xxx;
if (score >= beta) return score; // or return beta for fail hard
alpha = score;
}
Probably better to introduce a ply counter as well, since you only have to update the best_move at ply 0, I assume best_move is the move that you want to play eventually.