Debugging a transposition table

[xr_a_y]

When incheck you extend depth + 1, but in the depth var itself, this means that if you store a position in hash it gets depth+1 in the hash instead of depth

That's something I also do and with a lot of extensions so that depth shall be +2 or +3. What you mean is that when depth is extended during search the further insertion in TT shall only take initial depth into account ? What about reduction ? I don't understand how it is better to use initial depth, can you write a little more on the subject please ?

So you should wait with storing the bestmove in hash until all moves are searched. If you have new bestmove you store it in hash as EXACT, otherwise you store the position with UPPER( like you do already) If a fail high occurs you store it directly in hash with LOWER and return the score, but you do that already.

This is also confusing for me. Let's look at CPW implementation

Code: Select all

         // loop on move
		if (val > alpha) {

			bestmove = movelist[i].id;
			move_to_make = movelist[i];

			if (val > beta) {
				tt_save(depth, beta, TT_BETA, bestmove);
				info_pv(beta);
				return beta;
			}

			alpha = val;
			tt_save(depth, alpha, TT_ALPHA, bestmove);

			info_pv(val);
		} 
	} // end loop on move
	tt_save(depth, alpha, TT_EXACT, bestmove);
	return alpha;
	

TT is updated each time val > alpha but with the TT_ALPHA flag. Only at the end of the move loop, something is store (if no cut-off occurred) as TT_EXACT. It that what you meant ?

[Joost Buijs]

From the code snippet you show here the CPW implementation looks weird indeed. Why does it store an upperbound each time when (val > alpha and val < beta) ?, storing an exact value at the end of the move loop without knowing whether alpha improved or not seems wrong too.

Normally you would do something like this:

Code: Select all

int oldalpha = alpha, bestmove = nomove;

while (move)
{
	do(move);
	int val = -search(-beta, -alpha, depth - 1);
	undo(move);	

	if (val > alpha)
	{
		alpha = val;
		bestmove = move;
		if (alpha >= beta)
		{
			tt_save(depth, alpha, TT_BETA, bestmove);
			return alpha;
		}
	}
}

if (alpha > oldalpha)
	tt_save(depth, alpha, TT_EXACT, bestmove);
else
	tt_save(depth, alpha, TT_ALPHA, bestmove);

return alpha;

When in check, increasing the depth by one and storing that increased depth in the TT doesn't seem wrong to me, at least I always do it like this and I never found a problem with it.

My current engine, on a single thread, needs 24 ply to find the Fine70 move a1-b1, it takes 51 milliseconds to reach 24 ply, and then it slows down, probably because there are Queens getting on the board. What strikes me is that ToppleChess seems to have a bad branching factor at Fine70, so yes... it can very well be that there is a problem with the TT or with move ordering in general.

[hgm]

The CPW code seems to store the opposite bound from what it should, but it is very unlikely this would matter much. For one, it only ever does this in PV nodes, so very rarely. And reaching the position again would mean a repetition, and would assign a draw score rather than the TT score.

In my latest engines I store the TT only at the end of the node. This cause problems when the search is aborted, however, as it always would be in analysis mode. The root position is then never stored. For that reason it would be better to store after every iteration.

As to the extension problem, it does not matter what depth you store, as long as probing and storing are consistent. I.e. if you store the extended depth in the table, you must also use the extended depth on probing, to test whether the stored depth is sufficient for a hash cutoff.

[Joost Buijs]

At the root my engine stores every-PV move and every fail-high, and does this for every iteration. For the remaining part of the tree it only stores at the end of a node.

Aborting the search in combination with the TT has always been a bit tricky, usually you will set an abort-flag and roll back the stack. When rolling back you have to avoid storing anything in the TT, otherwise the TT gets polluted with wrong information. Especially in a multithreaded search where you have to abort parts of the tree on every beta cutoff this can create havoc. In my latest engines I use a throw/catch mechanism to avoid checking the abort flag on each store, which works better than expected, even in a multithreaded environment. And, as a bonus, the code gets somewhat cleaner.

[hgm]

The problem is that I never use a separate routine for the root and other nodes. And only storing at the end of an iteration does not work in cut-nodes, as these would jump out of the IID loop (because I use self-deepening of cut-moves). So I would need to duplicate the code for storing. And that code is not entirely trivial, as it also implements the replacement scheme. And it has to access a lot of the variables in Search, which all would have to be passed to it if I make it a subroutine.

None of that is a real problem, even performance-wise. It is just that the solutions give ugly code, which I hate. Best solution would probably be to always put all local variables of Search() in a struct, so that you can pass a single pointer to give tasks that you deligate to subroutines read an write access to everything. I can then even pass that pointer to Search() itself, to give that access to all variables of the parent node. The compiler can probably inline the subroutines. Having to write f.xxx or f->xxx all the time instead of xxx makes me err quite often while coding, but this is probably just a matter of getting used to it. (And the compiler always catches it immediately.)

[flok]

At the root my engine stores every-PV move and every fail-high, and does this for every iteration. For the remaining part of the tree it only stores at the end of a node.

What is the advange of that?
I did a quick test with my program and it showed a -32 elo with that.

[xr_a_y]

At the root my engine stores every-PV move and every fail-high, and does this for every iteration. For the remaining part of the tree it only stores at the end of a node.

What is the advange of that?
I did a quick test with my program and it showed a -32 elo with that.

Just did the same last night (the opposite situation in fact). At root I was doing as CPW (update TT each time val>alpha) and switch to Joost advice (only update at the end of move loop checking whether alpha was raised or not) and it was a +40elo. (even more with 4 threads)

[hgm]

Isn't that very suspect? How can it make the slightest difference what you store in the TT during an iteration? It should be overwritten by what you store when you leave the node. And up to that point it should never have been probed, as any visits to the node during that period should have been repetitions.

[Joost Buijs]

At the root my engine stores every-PV move and every fail-high, and does this for every iteration. For the remaining part of the tree it only stores at the end of a node.

What is the advange of that?
I did a quick test with my program and it showed a -32 elo with that.

There is no special advantage at all, it just seems the natural way of doing this. That your engine degrades 32 Elo just by changing the way you store the TT entries at the root is strange, or do you mean storing the entries only at the end of each node?

Anyway, it is difficult to compare these concepts between different engines, what for engine 'A' is better can be worse for engine 'B'. In practice it is better to rely on the outcome of automated tests. A gauntlet between your engine and a bunch of other engines of approx. the same strength works best.

[Joost Buijs]

Isn't that very suspect? How can it make the slightest difference what you store in the TT during an iteration? It should be overwritten by what you store when you leave the node. And up to that point it should never have been probed, as any visits to the node during that period should have been repetitions.

It should not have any impact on a single threaded search, but storing entries usually is a very slow process and doing all these redundant stores is not something you would like, and in a multi threaded search it will certainly have an impact on your search as well.