big commit adding bot

1 files changed, 111 insertions, 69 deletions

diff --git a/src/bot.cpp b/src/bot.cpp
index 8889156..e3a39f2 100644
--- a/src/bot.cpp
+++ b/src/bot.cpp
@@ -1,103 +1,145 @@
 #include "bot.hpp"
 #include "board.hpp"
 #include "moves.hpp"
+#include <algorithm>
+#include <cassert>
 #include <cmath>
-#include <ctime>
+#include <iostream>
 
 int PAWN_VALUE = 100;
 int KNIGHT_VALUE = 200;
 int BISHOP_VALUE = 300;
 int ROOK_VALUE = 400;
 int QUEEN_VALUE = 900;
+int MATE = 10000;
+
+const int SEARCH_DEPTH = 3;
+
+int positions_consider = 0;
 
 Move EngineGetBestMove(Board *b) {
   auto moves = GetLegalMoves(b);
-  std::srand(std::time(0)); // use current time as seed for random generator
-  int random_pos = std::rand() % moves.size();
-  Move move = moves[random_pos];
-  return move;
+  if (moves.size() == 0) {
+    assert(false && "Unhanled error zero legal moves for bot");
+  }
+  Move bestMove = moves[0];
+  float BestEval = (b->turn ? -INFINITY : INFINITY);
+  for (Move move : moves) {
+    Board TestBoard = *b;
+    PlayMove(move, &TestBoard);
+    float alpha = -INFINITY;
+    float beta = INFINITY;
+
+    float eval = minimax(SEARCH_DEPTH - 1, &TestBoard, alpha, beta);
+    if (b->turn) {
+      if (eval > BestEval) {
+        BestEval = eval;
+        bestMove = move;
+      }
+    } else {
+      if (eval < BestEval) {
+        BestEval = eval;
+        bestMove = move;
+      }
+    }
+  }
+  std::cout << "\nConsider: " << positions_consider << "\n";
+  return bestMove;
+}
+float minimax(int depth, Board *b, float alpha, float beta) {
+  if (depth == 0) {
+    return EvaluateBoardForWhite(b);
+  }
+  auto moves = GetLegalMoves(b);
+  if (moves.size() == 0) {
+    return EvaluateBoardForWhite(b);
+  }
+  if (b->turn) {
+    float bestEval = -INFINITY;
+
+    for (Move move : moves) {
+      Board next = *b;
+      PlayMove(move, &next);
+
+      float eval = minimax(depth - 1, &next, alpha, beta);
+      bestEval = std::max(bestEval, eval);
+
+      alpha = std::max(alpha, bestEval);
+
+      if (alpha >= beta) {
+        break;
+      }
+    }
+
+    return bestEval;
+  } else {
+    float BestEval = INFINITY;
+
+    for (Move move : moves) {
+      Board next = *b;
+      PlayMove(move, &next);
+
+      float eval = minimax(depth - 1, &next, alpha, beta);
+
+      BestEval = std::min(BestEval, eval);
+
+      beta = std::min(beta, BestEval);
+      if (alpha >= beta) {
+        break; // *snips*
+      }
+    }
+    return BestEval;
+  }
 }
 
-float EvaluateBoard(Board *b) {
+float EvaluateBoardForWhite(Board *b) {
+  positions_consider++;
   float score = 0;
-  Board BoardCopy = *b;
 
   bool isStaleMate = false;
 
-  auto legalMoves = GetLegalMoves(&BoardCopy);
+  GetLegalMoves(b);
   if (b->state == WHITE_WON) {
-    score = INFINITY;
+    return MATE;
   }
   if (b->state == BLACK_WON) {
-    score = INFINITY * -1;
+    return -MATE;
   }
   if (b->state == STALEMATE || b->state == DRAW) {
     isStaleMate = true;
   }
-  int white_pawn_count = 0;
-  int white_knight_count = 0;
-  int white_bishop_count = 0;
-  int white_rook_count = 0;
-  int white_queen_count = 0;
-
-  int black_pawn_count = 0;
-  int black_knight_count = 0;
-  int black_bishop_count = 0;
-  int black_rook_count = 0;
-  int black_queen_count = 0;
+
   for (Piece piece : b->pieces) {
-    if (piece.type == NONE) {
+    if (piece.type == NONE)
       continue;
-    }
-    if (piece.color) {
-      // white
-      if (piece.type == PAWN) {
-        white_pawn_count++;
-      }
-      if (piece.type == KNIGHT) {
-        white_knight_count++;
-      }
-      if (piece.type == BISHOP) {
-        white_bishop_count++;
-      }
-      if (piece.type == ROOK) {
-        white_rook_count++;
-      }
-      if (piece.type == QUEEN) {
-        white_queen_count++;
-      }
-      continue;
-    }
 
-    // black
-    if (piece.type == PAWN) {
-      black_pawn_count++;
-    }
-    if (piece.type == KNIGHT) {
-      black_knight_count++;
-    }
-    if (piece.type == BISHOP) {
-      black_bishop_count++;
-    }
-    if (piece.type == ROOK) {
-      black_rook_count++;
-    }
-    if (piece.type == QUEEN) {
-      black_queen_count++;
+    int value = 0;
+
+    switch (piece.type) {
+    case PAWN:
+      value = PAWN_VALUE;
+      break;
+    case KNIGHT:
+      value = KNIGHT_VALUE;
+      break;
+    case BISHOP:
+      value = BISHOP_VALUE;
+      break;
+    case ROOK:
+      value = ROOK_VALUE;
+      break;
+    case QUEEN:
+      value = QUEEN_VALUE;
+      break;
+    default:
+      break;
     }
-  }
 
-  score += white_pawn_count * PAWN_VALUE;
-  score += white_knight_count * KNIGHT_VALUE;
-  score += white_bishop_count * BISHOP_VALUE;
-  score += white_rook_count * ROOK;
-  score += white_queen_count * QUEEN_VALUE;
-
-  score -= black_pawn_count * PAWN_VALUE;
-  score -= black_knight_count * KNIGHT_VALUE;
-  score -= black_bishop_count * BISHOP_VALUE;
-  score -= black_rook_count * ROOK;
-  score -= black_queen_count * QUEEN_VALUE;
+    if (piece.color)
+      score += value;
+    else
+      score -= value;
+  }
   if (isStaleMate) {
     return 0;
   }