Python3-8 / rschess

A Rust chess library with the aim to be as feature-rich as possible
https://crates.io/crates/rschess
MIT License
31 stars 4 forks source link

Legal move caching limit #2

Open Python3-8 opened 3 months ago

Python3-8 commented 3 months ago

The below program

use rschess::Board;

fn main() {
    for i in 1..=5 {
        println!("positions after {i} ply: {}", count_positions(Board::default(), i));
    }
}

fn count_positions(board: Board, depth: usize) -> usize {
    if depth == 0 {
        return 1;
    }
    let mut positions = 0;
    for m in board.gen_legal_moves() {
        let mut new = board.clone();
        new.make_move(m).unwrap();
        positions += count_positions(new, depth - 1);
    }
    positions
}

outputs

positions after 1 ply: 20
positions after 2 ply: 400
positions after 3 ply: 8902
positions after 4 ply: 197281
positions after 5 ply: 4865609

as expected. However in the process it uses 1.25 GiB of memory, because of the recently implemented legal move caching. It may be a good idea to set a limit for this cache, and implement a sort of 'garbage collector' which deletes unused cache. Further discussion is needed.