feat: add basic negamax implementation

1 files changed, 60 insertions, 1 deletions

diff --git a/src/board.rs b/src/board.rs
index 7f35e91..3343702 100644
--- a/src/board.rs
+++ b/src/board.rs
@@ -1,4 +1,4 @@
-use crate::{bitboard::{Bitboard, serialize_bitboard, bitscan}, moves::{Move, MoveKind}, attacks::Attacks, square::Square};
+use crate::{bitboard::{Bitboard, serialize_bitboard, bitscan, pop_count}, moves::{Move, MoveKind}, attacks::Attacks, square::Square};
 
 pub enum CastlingSide {
     King,
@@ -114,6 +114,11 @@ impl Board {
         Self::from_FEN(default_fen)
     }
 
+    /// Color to move at this ply
+    fn color(&self) -> Color {
+        Color::from(self.ply as u8 % 2)
+    }
+
     fn update_occupancy(&mut self) {
         self.occupancy = 0;
         // TODO: reduce
@@ -606,6 +611,49 @@ impl Board {
         let square = bitscan(king_bb);
         self.is_square_attacked(square, color.flip())
     }
+
+    fn evaluate(&self) -> f32 {
+        let mut eval = 0f32;
+        let pieces = self.pieces_by_color(self.color());
+        eval += pop_count(pieces[PieceType::Pawn as usize]) as f32;
+        eval += pop_count(pieces[PieceType::Bishop as usize]) as f32 * 3.;
+        eval += pop_count(pieces[PieceType::Knight as usize]) as f32 * 3.;
+        eval += pop_count(pieces[PieceType::Rook as usize]) as f32 * 4.5;
+        eval += pop_count(pieces[PieceType::Queen as usize]) as f32 * 9.;
+        eval
+    }
+
+    fn negamax_search(&mut self, mut alpha: f32, beta: f32, depth_left: u8) -> f32 {
+        let color = Color::from(self.ply as u8 % 2);
+
+        self.print();
+
+        if depth_left == 0 {
+            return self.evaluate();
+        }
+        let moves = self.generate_pseudolegal_moves(color);
+
+        for mov in moves {
+            let ep_target_before = self.ep_target.clone();
+            let castling_rights_before = self.castling_rights.clone();
+            let captured_piece = self.make_move(mov);
+
+            if !self.is_king_in_check(color) {
+                let evaluation = -self.negamax_search(-beta, -alpha, depth_left - 1);
+                self.unmake_move(mov, captured_piece, ep_target_before, castling_rights_before);
+
+                if (evaluation >= beta) {
+                    return beta; // Fail-hard beta-cutoff
+                }
+                if (evaluation > alpha) {
+                    alpha = evaluation
+                }
+            } else {
+                self.unmake_move(mov, captured_piece, ep_target_before, castling_rights_before);
+            }
+        }
+        alpha
+    }
 }
 
 
@@ -634,6 +682,8 @@ impl Color {
 
 #[cfg(test)]
 mod tests {
+    use std::f32::INFINITY;
+
     use super::*;
     use crate::{bitboard::{pop_count, bitscan, print}, square::Square};
 
@@ -777,4 +827,13 @@ mod tests {
         assert_eq!(board.is_square_attacked(Square::E4, Color::White), false);
         assert_eq!(board.is_square_attacked(Square::B6, Color::Black), true);
     }
+
+    #[test]
+    fn negamax_search() {
+        let fen = String::from("r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq - ");
+        let mut board = Board::from_FEN(fen);
+
+        let eval = board.negamax_search(-INFINITY, INFINITY, 4);
+        println!("{}", eval);
+    }
 }