Optimizing Rust Borrowing Patterns in a Chess Engine

[mathmoi]

Hi everyone,

As a Rust beginner (about two months in), I've been developing a chess engine to learn the language. I have substantial experience implementing chess engines in other languages like C++, but I'm committed to finding truly idiomatic Rust solutions rather than just translating my C++ approach.

I've hit a challenging design problem involving Rust's borrowing rules, and I'm looking for guidance on the most elegant solution.

Current Structure

My engine has two key components:

• A Position struct that represents the chess board state
• A Search struct that contains a mutable reference to this position

The search method works recursively: it plays a move, calls itself recursively to explore deeper positions, then undoes the move when returning. This ensures that despite mutations, the position always reverts to its original state after each recursive call completes.

The Problem

I need a MoveGenerator struct that:

1. Efficiently generates legal moves from a position
2. Generates moves lazily (in stages) for performance reasons
3. Needs to reference the Position object when its next() method is called

The MoveGenerator works correctly as long as the position is in the same state when next() is called as it was during the generator's creation. My search algorithm guarantees this invariant, but Rust's borrowing rules prevent this design because the position is being mutated between calls.

Cloning the position is not an option due to performance requirements.

Solutions I've Considered

1. Using Rc<RefCell<Position>>: This appears to be the idiomatic solution, but it:

• Complicates the search function with explicit borrowing/dropping
• Causes a 3% performance penalty (significant for chess engines where every bit of speed matters)

2. Passing a position reference to next(): Instead of storing the reference in MoveGenerator, I could pass it each time. This seems inefficient since the reference is usually unnecessary after initial move generation.
3. Using UnsafeCell: This might offer zero overhead but introduces unsafe code, which I'd prefer to avoid if there's a better solution.

My Question

Is there an idiomatic Rust pattern I'm missing that would maintain both safety and performance? How would experienced Rust developers approach this problem without compromising on either aspect?

Any insights would be greatly appreciated!

[kpreid]

It's hard to follow exactly what your current situation is, when described like this. In particular, it’s unclear how Search fits in — you explain search() but not Search. Can you please post code, including at least the following?

• The definitions of all structs that have lifetime parameters.
• The signatures (including enclosing impl block signatures) of all the functions involved.

Compilable code (even if the actual algorithms are stubbed out with unimplemented!()) will especially help because it lets us test out proposed solutions.

[mathmoi]

Hi, thanks for your answer. The code is complexe and I have not implemented MoveGenerator yet, that's why I did not provide code.

But here is a simplified version of what I'm trying to do.

struct MoveGenerator<'a> {
    position: &'a Position,
    // other fields
}

impl <'a> MoveGenerator<'a> {
    fn new(position: &'a Position) -> Self {
        MoveGenerator { position }
    }

    fn next(&mut self) -> Option<Move> {
        // Logic to generate the next move, sometimes need to read self.position
    }
    
}

struct search {
    position: Position,
    depth: u16,
}

impl search {
    fn new(position: Position, depth: u16) -> Self {
        search { position, depth }
    }

    pub fn search(&mut self, depth: u16) -> i32 {
        if depth == 0 {
            return evaluate(&self.position);
        }

        let move_generator = MoveGenerator::new(&self.position); // This is not allowed

        let mut best = i32::MIN;
        let mut move = move_generator.next();
        while move.is_some() {
            let mv = move.unwrap();

            self.position.make(mv);
            let score = -self.search(depth - 1);
            self.position.unmake(mv);

            if score > best {
                best = score;
            }
            
            move = move_generator.next();
        }
        return score;
    }
}

[kpreid]

You said that Search would contain a mutable reference to Position but here it owns a Position. Is that correct? Those are very different.

Thinking about the structure of the recursion, I see two straightforward approaches:

1. Avoid using &mut self in the recursive search function; pass the Position in use separately from the depth. Replace self.position.make(mv) with move_generator.position.make(mv).

2. Get rid of all mutable references, and store a Cell<Position> instead of a Position, which you can mutate through &. (If your Position type isn't Copy, then it should be. You're using bitboards, right?) This way, you can mutate in patterns that aren't expressible by mutable borrows, and there is no overhead of RefCell checking.

[tczajka]

@mathmoi

Passing a position reference to next(): Instead of storing the reference in MoveGenerator, I could pass it each time. This seems inefficient since the reference is usually unnecessary after initial move generation.

This shouldn't really be inefficient and from your description it feels like the natural solution.

[mathmoi]

Search has a reference to a Position in the real code. That being said here it would be acceptable for search to own a clone of the position.

Position is not copyable. Make/Unmake is more performant than copying the position.

[mathmoi]

@kpreid

Avoid using &mut self in the recursive search function; pass the Position in use separately from the depth. Replace self.position.make(mv) with move_generator.position.make(mv).

If I understand correctly, you propose that the position is passed to search() as a reference and that reference is used to create the move_generator. However if the move generator keeps a reference to the position for its lifetime can I still make a recursive call to search and passing a refernce to the position?

My goal is to have only one position (no copy/clone) and at each depth of the recusives call to search a move_generator also has a reference to the same position.

Again, thanks for you answers.

[mathmoi]

I will test it. If the overhead is minimal this will be my solution even if it is not completely clean. Or maybe it is an elagant solution and I don't realise it because I'm used to other languages.

[kpreid]

@mathmoi

Position is not copyable.

So, what is your actual definition of Position? This is one of the things that will be very important to performance.

@mathmoi

However if the move generator keeps a reference to the position for its lifetime can I still make a recursive call to search and passing a refernce to the position?

You can pass a reborrow of the reference that move_generator has, instead of the original reference.

[tczajka]

@mathmoi

        let mut move = move_generator.next();
        while move.is_some() {
            let mv = move.unwrap();
            ...
            move = move_generator.next();
        }

Small improvement of this:

while let Some(mv) = move_generator.next() {
    ...
}

[curoli]

Two things that I would consider:

It is possible to express a position using an array of only 32 bytes (i.e. four bits per square), which should be not too expensive to clone.

Alternatively, a position can be expressed using a reference to the previous position plus the last move. This way, you can traverse the search tree while cheaply creating new positions and discarding them as you return.

[Jesper]

@mathmoi

Generates moves lazily (in stages) for performance reasons

It is difficult to do that efficiently - better to calculate all the pseudo legal moves in one go even if you end up not needing all of them. That way you can also sort the moves by value which will help the search (pruning).

[sw2wolf]

Maybe you can obtain insights from
a chess engine

Regards!