changes

1 files changed, 210 insertions, 265 deletions

diff --git a/src/bot.cpp b/src/bot.cpp
index 982a4a4..71c9277 100644
--- a/src/bot.cpp
+++ b/src/bot.cpp
@@ -1,115 +1,59 @@
 #include "bot.hpp"
 #include "board/board.hpp"
+#include "evaluate.hpp"
 #include "moves.hpp"
 #include "zobrist/zobrist.hpp"
+
 #include <algorithm>
 #include <cassert>
 #include <cmath>
 #include <cstdint>
-#include <cstdlib>
 #include <iostream>
+#include <iterator>
+#include <limits>
 #include <vector>
 
-constexpr int DEFAULT_DEPTH = 4;
-constexpr int Q_DEPTH_LIMIT = 3;
+constexpr int DEFAULT_DEPTH_LIMIT = 4;
+constexpr int Q_DEPTH_LIMIT = 4;
 
-constexpr int PAWN_VALUE = 100;
-constexpr int KNIGHT_VALUE = 320;
-constexpr int BISHOP_VALUE = 400;
-constexpr int ROOK_VALUE = 500;
-constexpr int QUEEN_VALUE = 900;
 constexpr int MATE = 10000;
 
-static int PAWN_TABLE[64] = {
-    0,  0,  0,   0,   0,   0,   0,  0,  // last rank promotes to a quuen
-    50, 50, 50,  50,  50,  50,  50, 50, // comments to stop formating to ruin it
-    10, 10, 20,  35,  35,  20,  10, 10, //
-    5,  5,  10,  30,  30,  10,  5,  5,  //
-    0,  0,  0,   25,  25,  0,   0,  0,  //
-    5,  -5, -10, 0,   0,   -10, -5, 5,  //
-    5,  10, 10,  -20, -20, 10,  10, 5,  //
-    0,  0,  0,   0,   0,   0,   0,  0   //
-};
-
-static int KNIGHT_TABLE[64] = {
-    -50, -40, -30, -30, -30, -30, -40, -50, //
-    -40, -20, 0,   0,   0,   0,   -20, -40, //
-    -30, 0,   10,  15,  15,  10,  0,   -30, //
-    -30, 5,   15,  20,  20,  15,  5,   -30, //
-    -30, 0,   15,  20,  20,  15,  0,   -30, //
-    -30, 5,   10,  15,  15,  10,  5,   -30, //
-    -40, -20, 0,   5,   5,   0,   -20, -40, //
-    -50, -40, -30, -30, -30, -30, -40, -50, //
-};
-
-static int BISHOP_TABLE[64] = {
-    -20, -10, -10, -10, -10, -10, -10, -20, //
-    -10, 5,   0,   0,   0,   0,   5,   -10, //
-    -10, 10,  10,  10,  10,  10,  10,  -10, //
-    -10, 0,   10,  15,  15,  10,  0,   -10, //
-    -10, 5,   5,   10,  10,  5,   5,   -10, //
-    -10, 0,   5,   10,  10,  5,   0,   -10, //
-    -10, 0,   0,   0,   0,   0,   0,   -10, //
-    -20, -10, -10, -10, -10, -10, -10, -20, //
-};
-
-static int ROOK_TABLE[64] = {
-    0,  0,  5,  10, 10, 5,  0,  0,  //
-    5,  10, 10, 10, 10, 10, 10, 5,  //
-    -5, 0,  0,  0,  0,  0,  0,  -5, //
-    -5, 0,  0,  5,  5,  0,  0,  -5, //
-    -5, 0,  0,  5,  5,  0,  0,  -5, //
-    -5, 0,  0,  0,  0,  0,  0,  -5, //
-    5,  10, 10, 10, 10, 10, 10, 5,  //
-    0,  0,  5,  10, 10, 5,  0,  0,  //
-};
-
-static int QUEEN_TABLE[64] = {
-    -20, -10, -10, -5, -5, -10, -10, -20, //
-    -10, 0,   0,   0,  0,  0,   0,   -10, //
-    -10, 0,   5,   5,  5,  5,   0,   -10, //
-    -5,  0,   5,   5,  5,  5,   0,   -5,  //
-    0,   0,   5,   5,  5,  5,   0,   -5,  //
-    -10, 5,   5,   5,  5,  5,   0,   -10, //
-    -10, 0,   5,   0,  0,  0,   0,   -10, //
-    -20, -10, -10, -5, -5, -10, -10, -20, //
-};
-
-static int KING_TABLE_EARLY[64] = {
-    -30, -40, -40, -50, -50, -40, -40, -30, //
-    -30, -40, -40, -50, -50, -40, -40, -30, //
-    -30, -40, -40, -50, -50, -40, -40, -30, //
-    -30, -40, -40, -50, -50, -40, -40, -30, //
-    -20, -30, -30, -40, -40, -30, -30, -20, //
-    -10, -20, -20, -20, -20, -20, -20, -10, //
-    20,  20,  0,   0,   0,   0,   20,  20,  //
-    20,  30,  10,  0,   0,   10,  30,  20,  //
-};
+// Material + PST bonuses can never reach this, so anything at/above it is a
+// forced mate. Used to stop iterative deepening once a mate is found.
+constexpr int MATE_THRESHOLD = MATE - 1000;
+constexpr int INF = 100000000;
+
+static int ScoreMove(const Game *board, const Move &move,
+                     const Move *bestMove) {
+  // Indexed by PieceType (NONE, PAWN, KNIGHT, BISHOP, ROOK, QUEEN, KING).
+  static constexpr int PIECE_VALUES[] = {
+      0,     // NONEPIECE
+      100,   // PAWN
+      320,   // KNIGHT
+      330,   // BISHOP
+      500,   // ROOK
+      900,   // QUEEN
+      20000, // KING (never captured in legal play)
+  };
+  static_assert(std::size(PIECE_VALUES) == KING + 1);
 
-int ScoreMove(const Game *board, const Move &move) {
   int score = 0;
 
+  // Search the previous iteration's best move first (iterative deepening).
+  if (bestMove != nullptr && move == *bestMove) {
+    score += 1000000;
+  }
+
   const Piece moving = board->pieces[PositionToIndex(move.From)];
   const Piece captured = board->pieces[PositionToIndex(move.To)];
 
-  // Captures (MVV-LVA)
+  // MVV-LVA: value the capture by what we win, penalise by what we spend.
   if (captured.type != NONEPIECE) {
-    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];
+    score += PIECE_VALUES[captured.type] * 10;
+    score -= PIECE_VALUES[moving.type];
   }
 
-  // Promotions
   if (move.promotion != NONEPIECE) {
     score += 8000;
   }
@@ -117,260 +61,261 @@ int ScoreMove(const Game *board, const Move &move) {
   return score;
 }
 
-std::vector<Move> GetSortedLegalMoves(Game *g, bool generateQuietMoves) {
+static std::vector<Move> GetSortedLegalMoves(Game *g, bool generateQuietMoves,
+                                             const Move *bestMove) {
   auto moves = GetLegalMoves(g, generateQuietMoves);
-  if (moves.empty()) {
-    return moves;
-  }
   std::ranges::sort(moves, [&](const Move &a, const Move &c) {
-    return ScoreMove(g, a) > ScoreMove(g, c);
+    return ScoreMove(g, a, bestMove) > ScoreMove(g, c, bestMove);
   });
   return moves;
 }
 
-Move EngineGetBestMove(Game *b, const int depth) {
-  const auto moves = GetSortedLegalMoves(b);
-  if (moves.empty()) {
-    std::cout << "Expected a position with legal moves";
-    assert(false && "Error zero legal moves for bot");
-    exit(1);
-  }
-
-  Move bestMove = moves[0];
-  int BestEval = b->turn ? std::numeric_limits<int>::lowest()
-                         : std::numeric_limits<int>::max();
-  for (const Move move : moves) {
-    const UndoMove undo = MakeMove(move, b);
-    const float alpha = -INFINITY;
-    const float beta = INFINITY;
+// Quiescence search: only captures, so the eval isn't blind to hanging pieces.
+// `standPat` lets the side to move decline every capture. Terminal positions
+// are scored with the same `MATE - ply` convention as the main search so that
+// mate distances stay consistent (a mate found inside quiescence must not look
+// faster than a real mate-in-1). White perspective throughout.
+static int quiescenceSearch(Game *b, int qdepth, int alpha, int beta, int ply) {
+  // Runs GetNewGameState internally, so b->state is up to date afterwards.
+  const int standPat = EvaluateBoardForWhite(b);
 
-    const int eval =
-        minimax(depth <= 0 ? DEFAULT_DEPTH : depth, b, alpha, beta);
-
-    UnMakeMove(undo, b);
-    if (b->turn) {
-      if (eval > BestEval) {
-        BestEval = eval;
-        bestMove = move;
-      }
-    } else {
-      if (eval < BestEval) {
-        BestEval = eval;
-        bestMove = move;
-      }
-    }
-  }
-  return bestMove;
-}
-int quiescenceSearch(Game *b, int Qdepth) {
-  int standPat = EvaluateBoardForWhite(b);
-  if (Qdepth >= Q_DEPTH_LIMIT) {
-    return standPat;
+  switch (b->state) {
+  case WHITE_WON:
+    return MATE - ply; // black is mated
+  case BLACK_WON:
+    return -(MATE - ply); // white is mated
+  case DRAW:
+    return 0;
+  case TURN:
+    break;
   }
-  std::vector<Move> attackMoves = GetSortedLegalMoves(b, false);
-  if (attackMoves.empty()) {
+
+  if (qdepth >= Q_DEPTH_LIMIT) {
     return standPat;
   }
 
-  int bestScore = b->turn ? std::numeric_limits<int>::lowest()
-                          : std::numeric_limits<int>::max();
+  auto moves = GetSortedLegalMoves(b, false, nullptr);
 
   if (b->turn) {
-    for (Move move : attackMoves) {
+    if (standPat >= beta) {
+      return beta;
+    }
+    alpha = std::max(alpha, standPat);
+
+    for (Move move : moves) {
       UndoMove undo = MakeMove(move, b);
 
-      int eval = quiescenceSearch(b, Qdepth + 1);
+      int score = quiescenceSearch(b, qdepth + 1, alpha, beta, ply + 1);
 
       UnMakeMove(undo, b);
-      bestScore = std::max(bestScore, eval);
+
+      if (score >= beta) {
+        return beta;
+      }
+      alpha = std::max(alpha, score);
     }
+    return alpha;
   } else {
-    for (Move move : attackMoves) {
+    if (standPat <= alpha) {
+      return alpha;
+    }
+    beta = std::min(beta, standPat);
+
+    for (Move move : moves) {
       UndoMove undo = MakeMove(move, b);
 
-      int eval = quiescenceSearch(b, Qdepth + 1);
+      int score = quiescenceSearch(b, qdepth + 1, alpha, beta, ply + 1);
 
       UnMakeMove(undo, b);
-      bestScore = std::min(bestScore, eval);
+
+      if (score <= alpha) {
+        return alpha;
+      }
+      beta = std::min(beta, score);
     }
+    return beta;
   }
-
-  return bestScore;
 }
+static int minimax(int depth, Game *b, int alpha, int beta, int ply) {
+  const uint64_t gameHash = GenerateZobristKey(b);
 
-int minimax(int depth, Game *b, float alpha, float beta) {
-  uint64_t gameHash = GenerateZobristKey(b);
-
-  if (b->ThreeFoldMap[gameHash] >= 2) {
-    return 0;
+  auto repIt = b->ThreeFoldMap.find(gameHash);
+  if (repIt != b->ThreeFoldMap.end() && repIt->second >= 2) {
+    return 0; // repetition -> draw
   }
-  if (b->Transpositions->contains(gameHash)) {
-    TranspositionsEntry data = b->Transpositions->at(gameHash);
-    if (data.depth >= depth) {
-      return data.Eval;
+
+  TranspositionsEntry *entry = nullptr;
+  if (auto it = b->Transpositions->find(gameHash);
+      it != b->Transpositions->end()) {
+    entry = &it->second;
+    if (entry->depth >= depth) {
+      if (entry->flag == EXACT) {
+        return entry->Eval;
+      }
+      if (entry->flag == LOWERBOUND) {
+        alpha = std::max(alpha, entry->Eval);
+      }
+      if (entry->flag == UPPERBOUND) {
+        beta = std::min(beta, entry->Eval);
+      }
+      if (alpha >= beta) {
+        return entry->Eval;
+      }
     }
   }
 
   if (depth <= 0) {
-    return quiescenceSearch(b, 0);
+    return quiescenceSearch(b, 0, alpha, beta, ply);
   }
-  auto moves = GetSortedLegalMoves(b);
+
+  Move ttBestMove = entry != nullptr ? entry->bestMove : Move{};
+  std::vector<Move> moves = GetSortedLegalMoves(b, true, &ttBestMove);
+
   if (moves.empty()) {
-    return EvaluateBoardForWhite(b);
+    const Position king = FindKing(b, b->turn);
+    if (IsSquareAttacked(b, king, !b->turn)) {
+      return b->turn ? -(MATE - ply) : (MATE - ply); // mated
+    }
+    return 0; // stalemate
   }
 
-  bool shouldStore = true;
+  Move bestMove = moves[0];
+  const int alphaOrig = alpha;
 
-  int bestScore = b->turn ? std::numeric_limits<int>::lowest()
-                          : std::numeric_limits<int>::max();
+  if (b->turn) { // white maximizes
+    int bestScore = std::numeric_limits<int>::lowest();
 
-  if (b->turn) {
     for (Move move : moves) {
       UndoMove undo = MakeMove(move, b);
 
-      int eval = minimax(depth - 1, b, alpha, beta);
+      int score = minimax(depth - 1, b, alpha, beta, ply + 1);
 
       UnMakeMove(undo, b);
-      bestScore = std::max(bestScore, eval);
-
-      alpha = std::max(alpha, static_cast<float>(bestScore));
 
+      if (score > bestScore) {
+        bestScore = score;
+        bestMove = move;
+      }
+      alpha = std::max(alpha, score);
       if (alpha >= beta) {
-        shouldStore = false;
-        break; // *snips*
+        break;
       }
     }
-  } else {
+
+    const Flag flag = bestScore <= alphaOrig ? UPPERBOUND
+                      : bestScore >= beta    ? LOWERBOUND
+                                             : EXACT;
+    (*b->Transpositions)[gameHash] = {
+        .depth = depth, .Eval = bestScore, .flag = flag, .bestMove = bestMove};
+    return bestScore;
+  } else { // black minimizes
+    int bestScore = std::numeric_limits<int>::max();
+
     for (Move move : moves) {
       UndoMove undo = MakeMove(move, b);
 
-      int eval = minimax(depth - 1, b, alpha, beta);
+      int score = minimax(depth - 1, b, alpha, beta, ply + 1);
 
       UnMakeMove(undo, b);
-      bestScore = std::min(bestScore, eval);
 
-      beta = std::min(beta, static_cast<float>(bestScore));
+      if (score < bestScore) {
+        bestScore = score;
+        bestMove = move;
+      }
+      beta = std::min(beta, score);
       if (alpha >= beta) {
-        shouldStore = false;
-        break; // *snips*
+        break;
       }
     }
-  }
 
-  if (shouldStore) {
-    b->Transpositions->operator[](gameHash) = {.depth = depth,
-                                               .Eval = bestScore};
+    const Flag flag = bestScore <= alphaOrig ? UPPERBOUND
+                      : bestScore >= beta    ? LOWERBOUND
+                                             : EXACT;
+    (*b->Transpositions)[gameHash] = {
+        .depth = depth, .Eval = bestScore, .flag = flag, .bestMove = bestMove};
+    return bestScore;
   }
-  return bestScore;
 }
 
-static int PSTIndex(const int square, const bool white) {
-  return white ? square : (56 ^ square);
-}
+struct SearchResult {
+  Move bestMove;
+  int score; // white perspective
+};
 
-static int ForceKingToEdgeBonus(const Position enemyKing,
-                                const Position myKing) {
-  int bonus = 0;
+// Searches every root move to `depth` plies and returns the best one.
+// `previousBest` is the best move from the previous iteration (used for move
+// ordering, the core win of iterative deepening).
+static SearchResult SearchDepth(Game *b, int depth, const Move *previousBest) {
+  auto moves = GetSortedLegalMoves(b, true, previousBest);
 
-  // Push enemy king toward edge
-  const int distToCenter =
-      std::abs(enemyKing.file - 3) + std::abs(enemyKing.rank - 3);
+  if (moves.empty()) {
+    return {{}, EvaluateBoardForWhite(b)};
+  }
 
-  bonus += distToCenter * 10;
+  Move bestMove = moves[0];
+  int bestEval = b->turn ? std::numeric_limits<int>::lowest()
+                         : std::numeric_limits<int>::max();
 
-  // Bring own king closer
-  const int kingDistance = std::abs(myKing.file - enemyKing.file) +
-                           std::abs(myKing.rank - enemyKing.rank);
+  for (Move move : moves) {
+    UndoMove undo = MakeMove(move, b);
 
-  bonus += (14 - kingDistance) * 5;
+    int eval = minimax(depth - 1, b, -INF, INF, 1);
 
-  return bonus;
-}
-static bool IsEndgame(Game *g) {
-  int queens = 0;
-  int rooks = 0;
-
-  for (const Piece &piece : g->pieces) {
-    switch (piece.type) {
-    case QUEEN:
-      queens++;
-      break;
-    case ROOK:
-      rooks++;
-      break;
-    default:
-      break;
+    UnMakeMove(undo, b);
+
+    if (b->turn) {
+      if (eval > bestEval) {
+        bestEval = eval;
+        bestMove = move;
+      }
+    } else {
+      if (eval < bestEval) {
+        bestEval = eval;
+        bestMove = move;
+      }
     }
   }
 
-  return queens == 0 || (queens == 2 && rooks <= 1);
+  return {bestMove, bestEval};
 }
 
-int EvaluateBoardForWhite(Game *g) {
-  int score = 0;
+static void PrintInfo(const int depth, const int engineScore) {
+  if (std::abs(engineScore) >= MATE_THRESHOLD) {
+    int movesToMate = (MATE - std::abs(engineScore) + 1) / 2;
+    if (movesToMate < 1) {
+      movesToMate = 1;
+    }
+    std::cout << "info depth " << depth << " score mate "
+              << (engineScore > 0 ? movesToMate : -movesToMate) << "\n"
+              << std::flush;
+  } else {
+    std::cout << "info depth " << depth << " score cp " << engineScore << "\n"
+              << std::flush;
+  }
+}
 
-  switch (GetNewGameState(g)) {
-  case WHITE_WON:
-    return MATE;
-    break;
-  case BLACK_WON:
-    return -MATE;
-    break;
-  case TURN:
-    break;
-  case DRAW:
-    return 0;
+Move GetBestMove(Game *b, const int maxDepth) {
+  const int depthLimit = maxDepth > 0 ? maxDepth : DEFAULT_DEPTH_LIMIT;
+
+  auto legalMoves = GetSortedLegalMoves(b, true, nullptr);
+  if (legalMoves.empty()) {
+    assert(false && "GetBestMove called with no legal moves");
+    return {};
   }
-  for (int i = 0; i < 64; i++) {
-    const Piece piece = g->pieces[i];
-    if (piece.type == NONEPIECE)
-      continue;
 
-    int value = 0;
+  Move bestMove = legalMoves[0];
 
-    switch (piece.type) {
-    case PAWN:
-      value = PAWN_VALUE;
-      value += PAWN_TABLE[PSTIndex(i, piece.color)];
-      break;
-    case KNIGHT:
-      value = KNIGHT_VALUE;
-      value += KNIGHT_TABLE[PSTIndex(i, piece.color)];
-      break;
-    case BISHOP:
-      value = BISHOP_VALUE;
-      value += BISHOP_TABLE[PSTIndex(i, piece.color)];
-      break;
-    case ROOK:
-      value = ROOK_VALUE;
-      value += ROOK_TABLE[PSTIndex(i, piece.color)];
-      break;
-    case QUEEN:
-      value = QUEEN_VALUE;
-      value += QUEEN_TABLE[PSTIndex(i, piece.color)];
-      break;
-    case KING:
-      value = KING_TABLE_EARLY[PSTIndex(i, piece.color)];
-      break;
-    default:
-      break;
-    }
+  for (int depth = 1; depth <= depthLimit; depth++) {
+    SearchResult result = SearchDepth(b, depth, &bestMove);
+    bestMove = result.bestMove;
 
-    if (piece.color) {
-      score += value;
-    } else {
-      score -= value;
+    PrintInfo(depth, b->turn ? result.score : -result.score);
+
+    // A mate was found; deeper searches can only find a faster one.
+    if (std::abs(result.score) >= MATE_THRESHOLD) {
+      break;
     }
   }
 
-  Position whiteKing = FindKing(g, true);
-  Position blackKing = FindKing(g, false);
-
-  if (IsEndgame(g)) {
-    score +=
-        ForceKingToEdgeBonus(blackKing, whiteKing); // White attacking black
-    score -=
-        ForceKingToEdgeBonus(whiteKing, blackKing); // Black attacking white
-  }
-  return score;
+  return bestMove;
 }