optimization: do not recreate board each time

1 files changed, 68 insertions, 25 deletions

diff --git a/src/main.c b/src/main.c
index f517d06..acfc37e 100644
--- a/src/main.c
+++ b/src/main.c
@@ -195,7 +195,16 @@ int apply_move(int move[2], int* board) {
     // printf("Captured %s\n", pieces[target_piece]);
   }
 
-  return board[destination];
+  return target_piece;
+}
+
+void reverse_move(int move[2], int captured_piece, int* board) {
+  int origin = move[0];
+  int destination = move[1];
+  int piece = board[destination];
+
+  board[origin] = piece;
+  board[destination] = captured_piece;
 }
 
 
@@ -263,30 +272,70 @@ int compute_material_advantage(int* board, int color) {
 }
 
 int compute_coverage(int* board, int color) {
-  int counter = 0;
+  int hit_map[128];
   for (int rank = 7; rank >= 0; rank--) {
     for (int file = 0; file < 8; file++) {
-      int index = rank * 16 + file;
-      int piece = board[index];
-      if (piece != EMPTY && (piece % 2) == color) {
-        for (int rank_destination = 7; rank_destination >= 0; rank_destination--) {
-          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) {
-              counter++;
-            }
+      hit_map[rank * 16 + file] = 0;
+    }
+  }
+
+  for (int rank = 7; rank >= 0; rank--) {
+    for (int file = 0; file < 8; file++) {
+      int origin = rank * 16 + file;
+      int piece = board[origin];
+      if (piece != EMPTY && piece % 2 == color) {
+        int* legal_move;
+        switch (piece & NO_COLOR) {
+          case KNIGHT:
+            legal_move = knightMoves;
+            break;
+          case BISHOP:
+            legal_move = bishopMoves;
+            break;
+          case ROOK:
+            legal_move = rookMoves;
+            break;
+          case QUEEN:
+            legal_move = queenMoves;
+            break;
+          case KING:
+            legal_move = kingMoves;
+            break;
+          case PAWN:
+            if (piece & BLACK) legal_move = blackPawnAttackMoves;
+            else legal_move = pawnAttackMoves;
+            break;
+          default:
+            break;
+        }
+
+        while(*legal_move) {
+          for (int square = origin + *legal_move; !(square & 0x88); square += *legal_move) {
+            hit_map[square] = 1;
+            int target_piece = board[square];
+
+            if (target_piece != EMPTY) break;
+            if ((piece & NO_COLOR) == PAWN || (piece & NO_COLOR) == KNIGHT || (piece & NO_COLOR) == KING) break;
           }
+          legal_move++;
         }
       }
     }
   }
+
+  int counter = 0;
+  for (int rank = 7; rank >= 0; rank--) {
+    for (int file = 0; file < 8; file++) {
+      counter += hit_map[rank * 16 + file];
+    }
+  }
+
   return counter;
 }
 
 int compute_score(int* board) {
   int coverage_score = compute_coverage(board, WHITE) - compute_coverage(board, BLACK);
-  return compute_material_advantage(board, WHITE) * 2 + coverage_score;
+  return compute_material_advantage(board, WHITE)* 3 + coverage_score;
 }
 
 // Alpha-beta pruning
@@ -294,7 +343,6 @@ int compute_score(int* board) {
 // Alpha is the best value for maximizer (white)
 // Beta is the best value for minimizer (black)
 int find_best_move(int best_move[2], int* board, int color, int depth, int alpha, int beta, int* metrics) {
-  int fake_board[128];
   int is_maximizer = (color == 0);
   int best_value = is_maximizer ? -INFINITY : INFINITY;
 
@@ -311,20 +359,14 @@ int find_best_move(int best_move[2], int* board, int color, int depth, int alpha
             if (validate_move(move, color, board) >= 0) {
               *metrics += 1;
 
-              // Generate fake board
-              for (int r = 7; r >= 0; r--) {
-                for (int f = 0; f < 8; f++) {
-                  fake_board[r * 16 + f] = board[r * 16 + f];
-                }
-              }
-
-
-              apply_move(move, fake_board);
+              int captured_piece = apply_move(move, board);
 
               int dummy[2];
               int value = depth < MAX_DEPTH
-                ? find_best_move(dummy, fake_board, 1 - color, depth + 1, alpha, beta, metrics)
-                : compute_score(fake_board);
+                ? find_best_move(dummy, board, 1 - color, depth + 1, alpha, beta, metrics)
+                : compute_score(board);
+
+              reverse_move(move, captured_piece, board);
 
               if (is_maximizer) {
                 if (value > best_value) {
@@ -367,6 +409,7 @@ int main() {
   while (1) {
     if (color == WHITE) {
       printf("Current score is %i\n", compute_score(board));
+      printf("White coverage: %i, black coverage: %i\n", compute_coverage(board, WHITE), compute_coverage(board, BLACK));
       printf("Enter a move for %s:\n", COLORS[color]);
       input_move(move);
     } else {