diff options
| -rw-r--r-- | src/config.h | 2 | ||||
| -rw-r--r-- | src/main.c | 101 |
2 files changed, 81 insertions, 22 deletions
diff --git a/src/config.h b/src/config.h index 60d60c3..5da6a21 100644 --- a/src/config.h +++ b/src/config.h @@ -1,2 +1,4 @@ #define BOARD_SIZE 8 #define DEFAULT_FEN "rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1" +#define MAX_DEPTH 5 +#define INFINITY 1000000 @@ -5,6 +5,9 @@ #include "config.h" #include "pieces.h" +#define MAX(x, y) (((x) > (y)) ? (x) : (y)) +#define MIN(x, y) (((x) < (y)) ? (x) : (y)) + void print_board(int board[128]) { for (int rank = 7; rank >= 0; rank--) { @@ -150,12 +153,12 @@ int validate_move(int move[2], int color, int* board) { int target_piece = board[square]; if (square == destination) { - if (target_piece & color) return -4; + if (target_piece != EMPTY && target_piece % 2 == color) return -4; return target_piece; } if (target_piece != EMPTY) break; - if ((piece & NO_COLOR) == PAWN || (piece & NO_COLOR) == KNIGHT || piece == KING) break; + if ((piece & NO_COLOR) == PAWN || (piece & NO_COLOR) == KNIGHT || (piece & NO_COLOR) == KING) break; } legal_move++; } @@ -187,7 +190,35 @@ int apply_move(int move[2], int* board) { return board[destination]; } -int compute_advantage(int* board, int color) { + +int evaluate_pawn(int piece, int rank) { + int color = piece % 2; + if (color == 0) { + switch (rank) { + case 7: + return 9; + case 6: + return 5; + case 5: + return 3; + default: + return 1; + } + } else { + switch (rank) { + case 0: + return 9; + case 1: + return 5; + case 2: + return 3; + default: + return 1; + } + } +} + +int compute_material_advantage(int* board, int color) { int counter = 0; for (int rank = 7; rank >= 0; rank--) { for (int file = 0; file < 8; file++) { @@ -195,6 +226,12 @@ int compute_advantage(int* board, int color) { if (piece != EMPTY) { int sign = (piece % 2 == color) ? 1 : -1; switch (piece & NO_COLOR) { + case KING: + counter += 1000 * sign; + break; + case PAWN: + counter += evaluate_pawn(piece, rank) * sign; + break; case KNIGHT: counter += 3 * sign; break; @@ -217,10 +254,15 @@ int compute_advantage(int* board, int color) { return counter; } -void find_best_move(int best_move[2], int* board, int color, int depth) { +// Alpha-beta pruning +// Value here is white material advantage over black +// Alpha is the best value for maximizer (white) +// Beta is the best value for minimizer (black) +int find_best_move(int* board, int color, int depth, int alpha, int beta) { + int best_move[2]; int fake_board[128]; - int best_advantage = -10000; - + int is_maximizer = (color == 0); + int best_value = is_maximizer ? -INFINITY : INFINITY; for (int rank = 7; rank >= 0; rank--) { for (int file = 0; file < 8; file++) { @@ -231,6 +273,7 @@ void find_best_move(int best_move[2], int* board, int color, int depth) { for (int file_destination = 0; file_destination < 8; file_destination++) { int index_destination = rank_destination * 16 + file_destination; int move[2] = { index, index_destination }; + if (validate_move(move, color, board) >= 0) { // Generate fake board for (int r = 7; r >= 0; r--) { @@ -239,20 +282,31 @@ void find_best_move(int best_move[2], int* board, int color, int depth) { } } + apply_move(move, fake_board); - // Try finding a response - if (depth) { - int response_move[2]; - find_best_move(response_move, fake_board, color ^ 1, depth - 1); - apply_move(response_move, fake_board); + int value = depth < MAX_DEPTH + ? find_best_move(fake_board, 1 - color, depth + 1, alpha, beta) + : compute_material_advantage(fake_board, 0); // Always for maximizer (white) + + if (is_maximizer) { + if (value > best_value) { + best_value = value; + best_move[0] = move[0]; + best_move[1] = move[1]; + } + alpha = MAX(best_value, alpha); + } else { + if (value < best_value) { + best_value = value; + best_move[0] = move[0]; + best_move[1] = move[1]; + } + beta = MIN(best_value, beta); } - int advantage = compute_advantage(fake_board, color); - if (advantage > best_advantage) { - best_advantage = advantage; - best_move[0] = move[0]; - best_move[1] = move[1]; + if (beta <= alpha) { + return best_value; } } } @@ -261,10 +315,13 @@ void find_best_move(int best_move[2], int* board, int color, int depth) { } } - char move_in_notation[] = "xy XY"; - index_to_notation(best_move[0], move_in_notation); - index_to_notation(best_move[1], move_in_notation + 3); - if (depth == 3) printf("Best move for %i is %s with score %i\n", color, move_in_notation, best_advantage); + if (depth == 0) { + char move_in_notation[] = "xy XY"; + index_to_notation(best_move[0], move_in_notation); + index_to_notation(best_move[1], move_in_notation + 3); + printf("Best move (validation: %i) for %s is %s with score %i in #%i moves\n", validate_move(best_move, color, board), COLORS[color], move_in_notation, best_value, MAX_DEPTH); + } + return best_value; } int main() { @@ -277,8 +334,8 @@ int main() { int color = 0; while (1) { - printf("Current board advantage is %i\n", compute_advantage(board, color)); - find_best_move(move, board, color, 3); + printf("Current board advantage is %i\n", compute_material_advantage(board, 0)); + find_best_move(board, color, 0, -INFINITY, +INFINITY); printf("Enter a move for %s:\n", COLORS[color]); input_move(move); |