Hash move ordering vs. Hash cuts: savings in number of nodes visited

[mvanthoor]

That's not correct. Hopefully this is just a matter of terminology. But I'll state the idea explicitly just in case it affects your implementation...

In my implementation, the best move in the move list is by definition a PV move, as it is put into the PV: Is this not correct?

Code: Select all

if eval_score > alpha {
	// Save our better evaluation score.
	alpha = eval_score;
	best_move = current_move.to_hash_move();

	// This is an exact score
	hash_flag = HashFlag::EXACT;

	// Update the Principal Variation.
	pv.clear();
	pv.push(current_move);
	pv.append(&mut node_pv);
}

"best_move = current_move.to_hash_move();" is used to cut down the move to only the parts needed to actually move a piece; there is some extra search information in there, such as the move order score, which isn't needed in the TT. Just before alpha is returned, a hash entry is saved with either the alpha flag (alpha was not raised) or the Exact flag (when alpha was raised).

But yes, when beating beta, the best move up to that point (which was just beaten by beta) is also saved:

Code: Select all

if eval_score >= beta {
	refs.tt.lock().expect(ErrFatal::LOCK).insert(
		refs.board.game_state.zobrist_key,
		SearchData::create(
			depth,
			refs.search_info.ply,
			HashFlag::BETA,
			beta,
			best_move,
		),
	);
	return beta;
}

Should I be saving NOT the best_move up to that point, but the CURRENT move that caused beta to be beaten in the hash table? I've been majorily confused sometimes by some of the older examples in pseudo-code that pull things like "depth", "ply", "best move" and "current move" seemingly out of nowhere, and sometimes seem to conflate them.

I wouldn't be surprised if I should be saving the move that beat beta, instead of the best move up to that point.

edit: in the Ruy Lopez position above, saving the CURRENT MOVE (the one that beat beta) into the hash table instead of the best_move so far, saved half the time on depth 9...

Code: Select all

info score cp 15 depth 1 seldepth 11 time 0 nodes 237 nps 0 pv c1g5
info score cp 15 depth 2 seldepth 15 time 0 nodes 2643 nps 0 pv d4d5 c6b8
info score cp 20 depth 3 seldepth 15 time 0 nodes 5243 nps 0 pv d4d5 c6a5 c1d2 a5b3 a2b3
info score cp 15 depth 4 seldepth 19 time 4 nodes 31853 nps 7963250 pv d4d5 c6b8 c1d2 c8g4
info score cp 20 depth 5 seldepth 19 time 11 nodes 100694 nps 9154000 hashfull 1 pv d4d5 c6a5 c1d2 a5b3 a2b3
info score cp 10 depth 6 seldepth 31 time 101 nodes 883504 nps 8747564 hashfull 10 pv c1e3 c8g4 d4d5 c6a5 b1c3 a5b3 a2b3
info score cp 15 depth 7 seldepth 31 time 313 nodes 2777792 nps 8874735 hashfull 38 pv b3d5 c8d7 c2c3 a8a7 d4e5 d6e5 c1e3
info score cp 10 depth 8 seldepth 33 time 1256 nodes 10360368 nps 8248701 hashfull 186 pv b3d5 f6d5 e4d5 c6d4 f3d4 e5d4 d1d4 c8f5
info score cp 10 depth 9 seldepth 33 time 4330 nodes 37740147 nps 8715969 hashfull 531 pv b3d5 c8d7 c2c3 d8e8 d5c6 d7c6 d1c2 f6e4 e1e4 c6e4

[mar]

I wouldn't be surprised if I should be saving the move that beat beta, instead of the best move up to that point.

edit: in the Ruy Lopez position above, saving the CURRENT MOVE (the one that beat beta) into the hash table instead of the best_move so far, saved half the time on depth 9...

I've no idea what you mean.
if a move beats alpha, it becomes the best move, if it also beats beta, it causes a beta cutoff. in that case bestmove=current move
typically you check for a beta cutoff inside the if (score > alpha) condition, you can have a separate condition if (score >= beta) after that (but why waste a potential extra if), but you definitely should check for a beta cutoff inside the move loop

[emadsen]

Should I be saving NOT the best_move up to that point, but the CURRENT move that caused beta to be beaten in the hash table?

Yes. Try that. I expect it will add a lot of ELO!

[mvanthoor]

I've no idea what you mean.
if a move beats alpha, it becomes the best move, if it also beats beta, it causes a beta cutoff. in that case bestmove=current move
typically you check for a beta cutoff inside the if (score > alpha) condition, you can have a separate condition if (score >= beta) after that (but why waste a potential extra if), but you definitely should check for a beta cutoff inside the move loop

I now have the following.

This is what I've understood of the explanations:
- If score >= beta, you can return beta, and save the best move
- If score > alpha, you found a better move. You raise alpha, and save the move as EXACT; if you never raised alpha, you save the best move with the alpha flag (which I do just before i return alpha).

So in my case, when saving a TT entry in "if score >= beta", I save the best move up to that point in the loop, because every explanation I've read is saving "the best move". The code is:

Code: Select all

if eval_score >= beta {
	refs.tt.lock().expect(ErrFatal::LOCK).insert(
		refs.board.game_state.zobrist_key,
		SearchData::create(
			depth,
			refs.search_info.ply,
			HashFlag::BETA,
			beta,
			best_move,
		),
	);
	return beta;
}

// We found a better move for us.
if eval_score > alpha {
	// Save our better evaluation score.
	alpha = eval_score;
	best_move = current_move.to_hash_move();

	// This is an exact score
	hash_flag = HashFlag::EXACT;

	// Update the Principal Variation.
	pv.clear();
	pv.push(current_move);
	pv.append(&mut node_pv);
}

However, I get a better result in the position above when I don't save the best_move as set by the last raise of alpha, but when I save the current move that is beating beta. From your explanation, I understand this:

Code: Select all

if eval_score > alpha {
	
	best_move = current_move.to_hash_move();
	if eval_score >= beta {
		refs.tt.lock().expect(ErrFatal::LOCK).insert(
			refs.board.game_state.zobrist_key,
			SearchData::create(
				depth,
				refs.search_info.ply,
				HashFlag::BETA,
				beta,
				best_move,
			),
		);
		return beta;
	}

	alpha = eval_score;
	hash_flag = HashFlag::EXACT;

	pv.clear();
	pv.push(current_move);
	pv.append(&mut node_pv);
}

If _THAT_ is the correct implementation, then in my implementation, I'm saving the wrong "best move" when doing a beta cutoff; In the first piece of code, I save the last move that raised alpha when doing the beta cutoff. In the second example, I'm saving the current move that is beating beta.

[mvanthoor]

Yes. Try that. I expect it will add a lot of ELO!

Damn. That's why I keep hammering on stuff like that if I'm not one hundred percent sure. mar's explanation also points to that direction. When I changed that, it instantly improved (at least) the ruy lopez position I tested above. It cut down the number of nodes by 50%!

To be honest, one of the hardest things in chess programming is finding out what "the truth" actually is. Many different explanations, many different ways of implementing things, and mixups of terminology. Because so many people were saving the "best move", I was doing so as well... but you can only do it like that if you have the implementation I just posted, with the beta part inside the alpha part... in that case, "best move" is always the current move in the loop, and NOT the last one that raised alpha.

@^%^$%@#%!@$%

Retracting the release I just made... and retesting... tomorrow.

[mar]

I now have the following.

This is what I've understood of the explanations:
- If score >= beta, you can return beta, and save the best move
- If score > alpha, you found a better move. You raise alpha, and save the move as EXACT; if you never raised alpha, you save the best move with the alpha flag (which I do just before i return alpha).

but this is wrong, because you then save the wrong move, not the one that cause the beta cutoff. so yes, you can swap the conditions,
but then you have to either set best move to current move or save current move

in non-pv (=all/cut) nodes, which are orders of magnitude more likely than PV nodes, you would save "no move" then, if I understand what you did,
because in zero-width search, beating alpha implies a beta cutoff and you're done.

so you just found a bug that probably cost you plenty of elo, congratulations

[mvanthoor]

I now have the following.

This is what I've understood of the explanations:
- If score >= beta, you can return beta, and save the best move
- If score > alpha, you found a better move. You raise alpha, and save the move as EXACT; if you never raised alpha, you save the best move with the alpha flag (which I do just before i return alpha).

but this is wrong, because you then save the wrong move, not the one that cause the beta cutoff. so yes, you can swap the conditions,
but then you have to either set best move to current move or save current move

in non-pv (=all/cut) nodes, which are orders of magnitude more likely than PV nodes, you would save "no move" then, if I understand what you did,
because in zero-width search, beating alpha implies a beta cutoff and you're done.

so you just found a bug that probably cost you plenty of elo, congratulations

Thanks... I only found it because I kept hammering on this point and asking questions, because I suspected something was wrong with regard to saving moves in the TT, but couldn't actually put my finger on it.

[mar]

Thanks... I only found it because I kept hammering on this point and asking questions, because I suspected something was wrong with regard to saving moves in the TT, but couldn't actually put my finger on it.

oh, one last thing, for nitpicks: I meant cut nodes of course, because in all nodes you don't have a best move

[emadsen]

Yes. Try that. I expect it will add a lot of ELO!

Damn. That's why I keep hammering on stuff like that if I'm not one hundred percent sure. mar's explanation also points to that direction. When I changed that, it instantly improved (at least) the ruy lopez position I tested above. It cut down the number of nodes by 50%!

To be honest, one of the hardest things in chess programming is finding out what "the truth" actually is. Many different explanations, many different ways of implementing things, and mixups of terminology. Because so many people were saving the "best move", I was doing so as well... but you can only do it like that if you have the implementation I just posted, with the beta part inside the alpha part... in that case, "best move" is always the current move in the loop, and NOT the last one that raised alpha.

@^%^$%@#%!@$%

Retracting the release I just made... and retesting... tomorrow.

Running gauntlet tournaments is a great arbiter of the truth. It doesn't inform you of the proper coding technique, proper algorithm, etc. But it's really good at informing you when your code change is a regression, lol.

You really have to internalize the ideas. Just as restating ideas in your own words is valuable when learning a new topic, so is restating chess programming techniques in your own code.

Jargon is tossed around in forum posts with imprecise language, people may use the same term to mean slightly different things, etc. On the negative side, this will not be the last you experience a bug that weakens engine strength without causing any outright failures. On the positive side, you'll gain ELO from this code change. And you'll develop a healthy skepticism of your own code. I wince when someone says, "There are no bugs in my code, this must be an issue that benefits more mature engines..." I don't really take in the second half of such a sentence. Can't get past the dangerous optimism in the first half.

[mvanthoor]

Running gauntlet tournaments is a great arbiter of the truth. It doesn't inform you of the proper coding technique, proper algorithm, etc. But it's really good at informing you when your code change is a regression, lol.

I do run gauntlets (several actual, for this change), and the improvement was +105 Elo; so the TT did work.

However, because of the poor performance of the TT move ordering since the beginning, I had a nagging problem that I was doing something wrong with saving the "best move" to the TT, but didn't know why, because in EVERY explanation I found, after endless googling, was that the "best move" should be saved.

The problem was that the "best move" is open to discussion... is it the "best move" in the move loop so far? Is it the move that last raised alpha? (I took it as such, because Alpha is where you collect the PV), is it the move that causes a beta-cutoff... it actually is the very first: the move with the highest eval_score in the loop, not the one that last raised alpha.

You really have to internalize the ideas. Just as restating ideas in your own words is valuable when learning a new topic, so is restating chess programming techniques in your own code.

That is precisely what I'm doing, and the reason why the development of my engine is so slow. I'm writing everything from scratch, reading only pseudo-code (and I absolutely avoid old C code, because those engines have LOTS of things in the global space.) Because I really dislike massively nested IF-statements, I now have this, and I believe this is correct:

Code: Select all

// eval_score is better than the best we found so far, so we
// save a new best_move that'll go into the hash table.
if eval_score > best_eval_score {
	best_eval_score = eval_score;
	best_move = current_move.to_hash_move();
}

// Beta cutoff: this move is so good for our opponent, that we
// do not search any further. Insert into TT and return beta.
if eval_score >= beta {
	refs.tt.lock().expect(ErrFatal::LOCK).insert(
		refs.board.game_state.zobrist_key,
		SearchData::create(
			depth,
			refs.search_info.ply,
			HashFlag::BETA,
			beta,
			best_move,
		),
	);
	return beta;
}

// We found a better move for us.
if eval_score > alpha {
	// Save our better evaluation score as alpha.
	alpha = eval_score;

	// This is an exact move score.
	hash_flag = HashFlag::EXACT;

	// Update the Principal Variation.
	pv.clear();
	pv.push(current_move);
	pv.append(&mut node_pv);
}

... after the loop we insert the best_move, either as flag:ALPHA or flag::EXACT ...

It should be the "untangled" version of this:

Code: Select all

// eval_score is better than the best we found so far, so we
// save a new best_move that'll go into the hash table.
if eval_score > best_eval_score {
	best_eval_score = eval_score;
	best_move = current_move.to_hash_move();
	
	// We found a better move...
	if eval_score > alpha {
		// ... for our opponent.
		if eval_score >= beta {
			refs.tt.lock().expect(ErrFatal::LOCK).insert(
				refs.board.game_state.zobrist_key,
				SearchData::create(
					depth,
					refs.search_info.ply,
					HashFlag::BETA,
					beta,
					best_move,
				),
			);
			return beta;
		}

		// ... for us.
		alpha = eval_score;

		// This is an exact move score.
		hash_flag = HashFlag::EXACT;

		// Update the Principal Variation.
		pv.clear();
		pv.push(current_move);
		pv.append(&mut node_pv);
	}	
}

... below the loop we save the best_move as ALPHA or EXACT ...

This may be nitpicking, but I get REALLY confused if there are too many if/else statements (or loops/switch/match) nested into one another. I dislike it with a passion, so I try to prevent it, even if it takes a tiny bit of performance by having to evaluate more if-statements. (The above code is still doable, but yeah... principles.)

Jargon is tossed around in forum posts with imprecise language, people may use the same term to mean slightly different things, etc. On the negative side, this will not be the last you experience a bug that weakens engine strength without causing any outright failures. On the positive side, you'll gain ELO from this code change. And you'll develop a healthy skepticism of your own code. I wince when someone says, "There are no bugs in my code, this must be an issue that benefits more mature engines..." I don't really take in the second half of such a sentence. Can't get past the dangerous optimism in the first half.

The mixup of jargon and terminology is often most confusing.

I hope I was just in time to retract the release and nobody downloaded it already, or I _WOULD_ have had a massive bug in my engine; one I suspected since I finalized the TT, but couldn't put my finger on. That's why the release took so long, and I even posted those two topics AFTER releasing the engine because even after, i couldn't convince myself that everything was 100% correct. I just felt the TT should have given me more benefit, and as far as I can see, it now will.

"I have no bugs in my code" is something I normally don't dare to say; but "my code probably has a lot less bugs than average" is something I'm convinced of. Development of my code is also often much slower, and tested for far longer, than what I see on average. You learn to work that way, if you're doing embedded software and control systems, and (nearly) seriously damaged a €100.000 piece of machinery by making a mistake. Been there, done that; fortunately only once. It was a heart-stopping moment though, seeing a conveyor belt running a pallet into a packaging machine at something like 50 km/h or so