feat: naively sort moves to improve branch pruning

2 files changed, 79 insertions, 31 deletions

diff --git a/src/config.h b/src/config.h
index 67c9b0b..9273f0e 100644
--- a/src/config.h
+++ b/src/config.h
@@ -1,5 +1,6 @@
 #define BOARD_SIZE 8
 #define DEFAULT_FEN "rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1"
 #define MAX_DEPTH 4
+#define MAX_AVAILABLE_MOVES 64 * 64
 #define INFINITY 1000000
 #define PLAYER WHITE
diff --git a/src/main.c b/src/main.c
index a8f7038..100a80a 100644
--- a/src/main.c
+++ b/src/main.c
@@ -407,6 +407,64 @@ int compute_score(int* board) {
   return compute_material_advantage(board, WHITE)* 3 + coverage_score;
 }
 
+int list_available_moves(Move moves[MAX_AVAILABLE_MOVES], int* board, int color) {
+  int moves_count = 0;
+
+  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;
+            Move move = { index, index_destination, 0 };
+            if (validate_move(move, color, board) >= 0) {
+              moves[moves_count] = move;
+              moves_count++;
+            }
+          }
+        }
+      }
+    }
+  }
+
+  return moves_count;
+}
+
+int get_piece_raw_value(int piece) {
+  switch (piece & NO_COLOR) {
+    case KNIGHT:
+      return 3;
+    case BISHOP:
+      return 3;
+    case ROOK:
+      return 5;
+    case QUEEN:
+      return 9;
+    case KING:
+      return INFINITY;
+    case PAWN:
+      return 1;
+    default:
+      return 0;
+  }
+}
+
+int compare_moves(const void* a, const void* b) {
+  return ((Move*)a)->value - ((Move*)b)->value;
+}
+
+void sort_moves(Move moves[MAX_AVAILABLE_MOVES], int moves_count, int* board) {
+  for (int i = 0; i < moves_count; i++) {
+    int origin_value = get_piece_raw_value(board[moves[i].origin]);
+    int destination_value = get_piece_raw_value(board[moves[i].destination]);
+    moves[i].value = destination_value - origin_value;
+  }
+
+  qsort(moves, moves_count, sizeof(Move), compare_moves);
+}
+
 /*
  * Alpha-beta pruning
  * Value here is white material advantage over black
@@ -419,43 +477,32 @@ Move find_best_move(int* board, int color, int depth, int alpha, int beta, int*
   Move best_move;
   best_move.value = is_maximizer ? -INFINITY : INFINITY;
 
-  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;
-            Move move = { index, index_destination };
-
-            if (validate_move(move, color, board) >= 0) {
-              *metrics += 1;
+  Move available_moves[MAX_AVAILABLE_MOVES];
+  int availabel_moves_count = list_available_moves(available_moves, board, color);
+  sort_moves(available_moves, availabel_moves_count, board);
+  if (depth == 0 && available_moves[0].value == 0) printf("Sort did not help or was wrong!");
 
-              int captured_piece = apply_move(move, board);
+  for (int i = 0; i < availabel_moves_count; i++) {
+    *metrics += 1;
+    Move move = available_moves[i];
 
-              move.value = depth < MAX_DEPTH
-                ? find_best_move(board, 1 - color, depth + 1, alpha, beta, metrics).value
-                : compute_score(board);
+    int captured_piece = apply_move(move, board);
 
-              reverse_move(move, captured_piece, board);
+    move.value = depth < MAX_DEPTH
+      ? find_best_move(board, 1 - color, depth + 1, alpha, beta, metrics).value
+      : compute_score(board);
 
-              if (is_maximizer) {
-                if (move.value > best_move.value) best_move = move;
-                alpha = MAX(best_move.value, alpha);
-              } else {
-                if (move.value < best_move.value) best_move = move;
-                beta = MIN(best_move.value, beta);
-              }
+    reverse_move(move, captured_piece, board);
 
-              if (beta <= alpha) {
-                return best_move;
-              }
-            }
-          }
-        }
-      }
+    if (is_maximizer) {
+      if (move.value > best_move.value) best_move = move;
+      alpha = MAX(best_move.value, alpha);
+    } else {
+      if (move.value < best_move.value) best_move = move;
+      beta = MIN(best_move.value, beta);
     }
+
+    if (beta <= alpha) break;
   }
 
   return best_move;