Add Transposition Table and Quiescence Search

[chitty]

Initial implementation of Quiescence Search. And implementation of Transposition Table to reuse positions that were already calculated.

This PR does the quiesce for an additional level of depth only. It may need to be improved to allow 2 or 3 more levels.

[healeycodes]

Looks like this is heading in a good direction @chitty!

Some points:

• How do we measure that this makes the engine stronger?
• How can we test this?
• Is it possible to achieve this without requiring numpy? I like that the engine currently requires one dependancy. But perhaps there's a performance implication.

Otherwise, the general code design/structure is 💯

[chitty]

You're right, I'll find the cases where the engine blunders and add tests showing that this PR solves some of them. That should take care of the first 2 points. I'll look deeper into the last point to see what makes the most sense.

Thanks for the feedback @healeycodes

[Varsius]

@chitty could you please explain to me why you are using the following line in your quiescence search implementation: score = quiesce(board, alpha, beta, depth - 1) # Line 106

In the pseudo code from the Chessprogramming wiki (https://www.chessprogramming.org/Quiescence_Search) the line goes: score = -Quiesce( -beta, -alpha );

The second thing: Is there a reason you chose the quiescence search depth to be only 1? Wouldn't it make more sense to look a couple more moves ahead (for example 5). Since we are only evaluation capturing moves, there should not be that much possibilites.

[chitty]

This PR should have been marked as a draft, I apologize, I just did that.

At the moment I thought I'd have the bandwidth to complete it, but I didn't, and I probably won't for at least a couple more weeks.

I still think that implementing Quiescence Search will be a great improvement to the engine, feel free to take this PR and update it if you find it useful @Varsius @healeycodes. If not, I'll finish it once I have the availability.

Cheers!

[LouieMartin]

@chitty can't you implement the Transposition Table like this?

TABLE_SIZE = 1048583

class Entry:
    def __init__(
        self,
        evaluation: float,
        depth: int,
        age: int,
        zobrist: int,
    ):
        self.evaluation = evaluation
        self.zobrist = zobrist
        self.depth = depth
        self.age = age

class TranspositionTable:
    def __init__(self):
        self.table = [None] * TABLE_SIZE
    
    def replace(self, entry: Entry):
        index = entry.zobrist % TABLE_SIZE
        stored_entry = self.table[index]
        if not stored_entry or stored_entry.age < entry.age or stored_entry.depth < entry.depth:
            self.table[index] = entry
    
    def get(self, zobrist: int, depth: int) -> Entry | None:
        index = zobrist % TABLE_SIZE
        stored_entry = self.table[index]
        if stored_entry and stored_entry.depth >= depth and stored_entry.zobrist == zobrist:
            return stored_entry

[chitty]

Thanks @LouieMartin, Feel free to complete the PR or open your own, I no longer have the cycles to work on it. I'll just close it.