Help with transposition table

[eboatwright]

Hello,

I've been writing a Chess engine in Rust over the past 2 months or so, and I'm currently in the process of overhauling most of the codebase for version 3.1.
Over the past few days I've been re-writing the transposition table to use a fixed size instead of the aging system I had before, but it actually performs a decent bit worse than the previous version.

It's not because the aging HashMap was allowed to get too big, when checking the logs I've never seen it above 200 MB, so with the new one's 256 MB hash it should be a decent improvement!

It's probably also important to note, that the engine implements Aspiration Windows, both the old and new versions have it

Any help would be greatly appreciated, here's the main parts of the code that handle the TT (Some stuff is removed for clarity)

Code: Select all

pub fn lookup(&mut self, key: u64, depth_left: u8, depth: u8, alpha: i32, beta: i32) -> (Option<i32>, Option<MoveData>) {
	if let Some(data) = self.table[self.get_index(key)] {
		if data.key == key {
			let mut return_evaluation = None;

			// depth_left is the number of plys left in the current search
			if data.depth_left >= depth_left {
				match data.eval_bound {
					EvalBound::LowerBound =>
						if data.evaluation >= beta {
							return_evaluation = Some(data.evaluation);
						},
					EvalBound::UpperBound =>
						if data.evaluation <= alpha {
							return_evaluation = Some(data.evaluation);
						},
					EvalBound::Exact =>
						return_evaluation = Some(data.evaluation),
				}
			}

			return (return_evaluation, Some(data.best_move));
		}
	}

	(None, None)
}

Code: Select all

// At the top of the Alpha-Beta search function
let (tt_eval, hash_move) = transposition_table.lookup(zobrist_key, depth_left, depth, alpha, beta);

// Depth is the number of plys into the search
if depth > 0 {
	if let Some(tt_eval) = tt_eval {
		return tt_eval;
	}
}

If you need more context, the entire codebase is here: (make sure to switch to the "dev" branch)
https://github.com/eboatwright/maxwell

[eboatwright]

Here are the exact commits as well:
Old version (Aging Hash) https://github.com/eboatwright/Maxwell/ ... d219d7026d
New version (Static sized Hash) https://github.com/eboatwright/Maxwell/ ... 1558570824

[mvanthoor]

Why are you checking on the depth you have still to go until 0? This can change, when you use extensions. You should be checking the hash-table move AT the depth where you are currently at. (I may be understanding this the wrong way.) For reference, this is the get() function in my own hash table:

Code: Select all

    pub fn get(&self, depth: i8, ply: i8, alpha: i16, beta: i16) -> (Option<i16>, ShortMove) {
        // We either do, or don't have a value to return from the TT.
        let mut value: Option<i16> = None;

        if self.depth >= depth {
            match self.flag {
                HashFlag::Exact => {
                    // Get the value from the data. We don't want to change
                    // the value that is in the TT.
                    let mut v = self.value;

                    // Opposite of storing a mate score in the TT...
                    if v > CHECKMATE_THRESHOLD {
                        v -= ply as i16;
                    }

                    if v < -CHECKMATE_THRESHOLD {
                        v += ply as i16;
                    }

                    // This is the value that will be returned.
                    value = Some(v);
                }

                HashFlag::Alpha => {
                    if self.value <= alpha {
                        value = Some(alpha);
                    }
                }

                HashFlag::Beta => {
                    if self.value >= beta {
                        value = Some(beta);
                    }
                }

                HashFlag::Nothing => (),
            }
        }
        (value, self.best_move)
    }

This is the entire hash table. Note that it uses buckets (to pack more than one value into an entry) and that it also handles hashing for the Perft function. (Using the TT in the Perft function is a good idea to see if the TT works. Note that in Perft, a hash-hit is only valid if it was posted in the table at the EXACT SAME depth at which Perft is probing, or you'll get the wrong leaf node count.)

[eboatwright]

Why are you checking on the depth you have still to go until 0? This can change, when you use extensions. You should be checking the hash-table move AT the depth where you are currently at. (I may be understanding this the wrong way.)

I am, I just use different names for them because it makes more sense to me: what you call "depth" I call "depth_left" because it's the number of plys left in the current search, and what you call "ply" I call "depth" because it's the current depth from the root of the search

I guess I should probably change those around to make it less confusing when I ask questions like this

This is the entire hash table. Note that it uses buckets (to pack more than one value into an entry) and that it also handles hashing for the Perft function. (Using the TT in the Perft function is a good idea to see if the TT works. Note that in Perft, a hash-hit is only valid if it was posted in the table at the EXACT SAME depth at which Perft is probing, or you'll get the wrong leaf node count.)

Speaking of which, how much strength does using buckets provide? I haven't looked into it yet

But anyways, I've used your TT and Weiawaga's as reference, and no matter what I've tried it always loses matches to the previous "aging" method I used.
Where I'm currently at, is I think this may just be a sacrifice I have to make to have the "proper" TT implementation

[mvanthoor]

I am, I just use different names for them because it makes more sense to me: what you call "depth" I call "depth_left" because it's the number of plys left in the search, and what you call "ply" I call "depth" because it's the current depth into the search

Then you're confusing anyone who is going to read your code. Depth is the distance to the horizon which is decreased each time you hit a new node,or extended or reduced because of some condiiton in the search. Ply is the number of half-moves made. It is increased each time a move is made in the search tree.

I guess I should probably change those around to make it less confusing when I ask questions like this

Definitely. In my earlier TT's I had buckets, with 3 entries in each bucket. That seemed logical to me, but the chess engine world does it the other way around, so I changed this.

Speaking of which, how much strength does using buckets provide? I haven't looked into it yet

I would need to test this to make certain. When you double the buckets, you half the number of entries if the TT stays the same size. Your TT will be packed more densly with less overwrites. However, there is a limit; you just can't set the TT to have 500 buckets because searching all the buckets in an entry takes too much time. That's the reason why most chess engines have only 2 or 3 buckets.

But anyways, I've used your TT and Weiawaga's as reference, and no matter what I've tried it always loses matches to the previous "aging" method I used.
Where I'm currently at, is I think this may just be a sacrifice I have to make to have the "proper" TT implementation

If you had aging in the TT before and now you don't, you had less overwrites in your previous TT, so it may have gained you some strength. If your current TT doesn't have aging, you'll have lost some Elo. However, a static TT that doesn't change size can also have aging.

Note that engines that change their TT size or are not able to set their TT size could be prohibited from testing or tournaments, because it can (will) create an advantage for your engine if the TT is large enough.

[eboatwright]

Then you're confusing anyone who is going to read your code. Depth is the distance to the horizon which is decreased each time you hit a new node,or extended or reduced because of some condiiton in the search. Ply is the number of half-moves made. It is increased each time a move is made in the search tree.

Ok I'll change those around

If you had aging in the TT before and now you don't, you had less overwrites in your previous TT, so it may have gained you some strength. If your current TT doesn't have aging, you'll have lost some Elo. However, a static TT that doesn't change size can also have aging.

Ok, I'll try to implement it back in and see if it helps

Note that engines that change their TT size or are not able to set their TT size could be prohibited from testing or tournaments, because it can (will) create an advantage for your engine if the TT is large enough.

Yeah that makes sense

Thanks for the help, I'm currently running some tests and wondering: I've seen Weiawaga only returns the evaluation retrieved from the TT in non-PV nodes, and your engine only returns if you're not in the root node. Is this just an engine specific thing, or is one objectively better than the other?

[mvanthoor]

Thanks for the help, I'm currently running some tests and wondering: I've seen Weiawaga only returns the evaluation retrieved from the TT in non-PV nodes, and your engine only returns if you're not in the root node. Is this just an engine specific thing, or is one objectively better than the other?

There are multiple ways to do things. Some things work better for some engines; other things works better for others. In a non-PV node, there's a big chance that IF there is a move returned from the TT, it may not be relevant for the position the engine is in at the moment, thus it is not possible to do a move sort on the basis of the returned move. It saves a legality check for the move. My engine (at this point in time) swaps already-generated moves around in the move list, and if the TT-move is in there, it'll end up at the beginning. If it isn't, the move is not relevant for the position and nothing will happen.

If I return a TT-cut from the root node and there happens to be no move from the TT, the engine doesn't have a move to make so it will make the illegal move "a1 a1" (because the move is empty). Thus I never return TT cuts from the root node. (There may be a better way, but if so, I haven´t encountered it yet. If I do, at some point, I'll implement it. I try to implement most things by reading and researching, without looking at other/stronger engines too much.)

[eboatwright]

Ok thank you, I've tried only returning from non-root nodes, only returning from non-PV nodes, and just always returning, and I've found the best results with only returning from non-root nodes, so I guess I'll stick with that.

[eboatwright]

Ok final update for this thread.
I implemented a basic replacement scheme: it doesn't overwrite if the stored data has a higher depth than the new data, and if the depths are equal it prefers exact evaluation bounds, and that seems to work! A pretty decent improvement

Thanks for the help

[mvanthoor]

Ok final update for this thread.
I implemented a basic replacement scheme: it doesn't overwrite if the stored data has a higher depth than the new data, and if the depths are equal it prefers exact evaluation bounds, and that seems to work! A pretty decent improvement

Thanks for the help

Very good starting point Run a test: disable the transposition table (remove the calls to it, or make sure it never stores anything; I can do this by setting the size to 0 MB) and and run it against the same engine with the TT enabled. The Elo-difference should be somewhere between 130-160 Elo. If so, you could then implement buckets and aging.