compact heath
I have a simple web app chess game https://seftontycho.github.io/webchess/ with a computer opponent.
I have implemented a few known computer search algorithms.
However my implementation for Negamax with Alpha-Beta Pruning seems very slow.
It takes a few seconds to search only 7 moves ahead.
I feel like it should be faster and want to know how I could improve it.
Full code can be found at https://github.com/seftontycho/webchess/tree/master.
The relevant parts can be found in src/algorithm/
I will post most of the relevant bits below
pub struct AlphaBetaNegamax {
depth: usize,
}
impl AlphaBetaNegamax {
pub fn new(depth: usize) -> Self {
Self { depth }
}
fn negamax(
score_fn: Rc<dyn ScoreFunction>,
board: Board,
depth: usize,
alpha: f64,
beta: f64,
negative: bool,
) -> f64 {
if depth == 0 {
return match negative {
true => -score_fn.score(&board),
false => score_fn.score(&board),
};
};
let side = board.side_to_move();
match board.status() {
GameStatus::Drawn => return 0.0,
GameStatus::Won => {
return match negative {
true => -1.0,
false => 1.0,
} * match side {
Color::White => -1000.0,
Color::Black => 1000.0,
};
}
GameStatus::Ongoing => {}
};
let mut best_score = f64::NEG_INFINITY;
let mut alpha = alpha;
for mov in get_sorted_moves(&board, &side) {
let mut temp_board = board.clone();
temp_board.play(mov);
best_score = best_score.max(-Self::negamax(
score_fn.clone(),
temp_board,
depth - 1,
-beta,
-alpha,
!negative,
));
alpha = alpha.max(best_score);
if alpha >= beta {
break;
};
}
best_score
}
}``` let mut checkers = Vec::with_capacity(4);
let mut promotions = Vec::with_capacity(4);
let mut captures = Vec::with_capacity(20);
let mut moves = Vec::with_capacity(24);
board.generate_moves_for(board.checkers(), |piece_moves| {
checkers.extend(piece_moves);
false
});
board.generate_moves_for(board.colors(*side), |piece_moves| {
for mov in piece_moves {
if mov.promotion.is_some() {
promotions.push(mov);
} else if board.color_on(mov.to).is_some_and(|color| color != *side) {
captures.push(mov);
} else if !checkers.contains(&mov) {
moves.push(mov);
}
}
false
});
checkers
.into_iter()
.chain(promotions)
.chain(captures)
.chain(moves)
.collect()
}```
dire walrus
Without even reading any of the code yet: did you compile it in release mode?
Also, this is more of a code style question, but why are you matching on a bool?
stray aurora
its been a while since I've used minimax, but the algorithm looks fine. you're using data structures efficiently. I think you're just running into the limitations of minimax for such a complex game. There's a ridiculous number of moves at depth 7. Last time I coded minimax, it took several seconds beyond depth 3 in python.
compact heath
Without even reading any of the code yet: did you compile it in release mode?
Yes I did
compact heath
Also, this is more of a code style question, but why are you matching on a bool?
I had something more complicated there before and haven’t changed it to an if-else yet
compact heath
its been a while since I've used minimax, but the algorithm looks fine. you're u...
Ok, yeah I just did the maths and at ~30 valid move per turn thats ~21 billion moves to check
Are there any obvious ways I could eel out any more performance though?
stray aurora
what is the checkers vec supposed to represent? if it's always going to be the same 4 elements, use an enum or hashmap instead of doing a linear search with contains() every time
oh that doesn't make sense now that I read the code properly
compact heath
Its the moves you can make that place the enemy in check
I am applying a naive move ordering to try and help the Alpha-Beta pruning by showing it potentially better moves first
sacred jolt
Frankly my chess engine was about the same speed at depth of seven when my search function looked like that. Your next step is to look into pruning heuristics, not really what you already have. Fyi though, most engines use a method that calls itself with a negative sign to do the negation rather than the parameter youre using atm
Not something you need to change necessarily, but personally i find it a bit easier to follow
wise slate