sorting legal moves to optimaze alpha-beta pruning

2 files changed, 47 insertions, 25 deletions

diff --git a/src/bot.cpp b/src/bot.cpp
index 90c834a..02b9452 100644
--- a/src/bot.cpp
+++ b/src/bot.cpp
@@ -4,15 +4,19 @@
 #include <algorithm>
 #include <cassert>
 #include <cmath>
+#include <cstdlib>
 #include <iostream>
+#include <vector>
 
-int PAWN_VALUE = 100;
-int KNIGHT_VALUE = 320;
-int BISHOP_VALUE = 330;
-int ROOK_VALUE = 500;
-int QUEEN_VALUE = 900;
-int CHECK = 10;
-int MATE = 10000;
+const int SEARCH_DEPTH = 4;
+
+const int PAWN_VALUE = 100;
+const int KNIGHT_VALUE = 320;
+const int BISHOP_VALUE = 330;
+const int ROOK_VALUE = 500;
+const int QUEEN_VALUE = 900;
+const int CHECK = 10;
+const int MATE = 10000;
 
 const int PAWN_TABLE[64] = {
     0,  0,  0,   0,   0,   0,   0,  0,  // last rank promotes to a quuen
@@ -57,33 +61,52 @@ int ROOK_TABLE[64] = {
     5,  10, 10, 10, 10, 10, 10, 5,  //
     0,  0,  5,  10, 10, 5,  0,  0,  //
 };
+int ScoreMove(const Game *board, const Move &move) {
+  int score = 0;
+
+  Piece moving = board->pieces[PositionToIndex(move.From)];
+  Piece captured = board->pieces[PositionToIndex(move.To)];
+
+  // Captures (MVV-LVA)
+  if (captured.type != NONE) {
+    static const int pieceValue[] = {
+        0,     // NONE
+        20000, // KING (should never happen)
+        900,   // QUEEN
+        500,   // ROOK
+        330,   // BISHOP
+        320,   // KNIGHT
+        100    // PAWN
+    };
+
+    score += 10000;
+    score += pieceValue[captured.type] * 10;
+    score -= pieceValue[moving.type];
+  }
 
-const int SEARCH_DEPTH = 5;
-
-#include <fstream>
-
-void LogMove(const Move &move) {
-  std::ofstream file("moves.txt", std::ios::app);
-
-  if (!file.is_open())
-    return;
-
-  file << static_cast<char>('a' + move.From.file)
-       << static_cast<char>('8' - move.From.rank)
-       << static_cast<char>('a' + move.To.file)
-       << static_cast<char>('8' - move.To.rank);
+  // Promotions
+  if (move.promotion != NONE) {
+    score += 8000;
+  }
 
-  file << '\n';
+  return score;
 }
+
 Move EngineGetBestMove(Game *b) {
   auto moves = GetLegalMoves(b);
   if (moves.size() == 0) {
+    std::cout << "Expected a position with legal moves";
     assert(false && "Unhanled error zero legal moves for bot");
+    exit(1);
   }
+
+  // sort legal moves
+  std::sort(moves.begin(), moves.end(), [&](const Move &a, const Move &c) {
+    return ScoreMove(b, a) > ScoreMove(b, c);
+  });
   Move bestMove = moves[0];
   float BestEval = (b->turn ? -INFINITY : INFINITY);
   for (Move move : moves) {
-    LogMove(move);
     UndoMove undo = MakeMove(move, b);
     float alpha = -INFINITY;
     float beta = INFINITY;
diff --git a/src/bot.hpp b/src/bot.hpp
index 0b92292..b95822f 100644
--- a/src/bot.hpp
+++ b/src/bot.hpp
@@ -5,6 +5,5 @@
 Move EngineGetBestMove(Game *b);
 float EvaluateBoardForWhite(Game *b, int depth);
 float minimax(int depth, Game *b, float alpha, float beta);
-void LogMove(const Move &move);
-
+int ScoreMove(const Game *board, const Move &move);
 #endif /* SRC_BOT_H_ */