Debugging a transposition table

[konsolas]

I've recently started writing my own chess engine, and I've been trying to implement all of the basics so I can get on to trying out some other ideas.

I'm currently having trouble writing a working transposition table. From what I understand, Fine#70 https://chessprogramming.wikispaces.com ... m+Position should be solved quite easily by any engine with a transposition table used for pruning, but my engine slows down a lot past depth 17, and doesn't seem to get the winning move of a1b1:

Code: Select all

position fen 8/k7/3p4/p2P1p2/P2P1P2/8/8/K7 w - -
go infinite
info depth 1 score cp 126 time 0 nodes 7 nps 7000 pv a1b2
info depth 2 score cp 80 time 0 nodes 31 nps 31000 pv a1b2 a7b7
info depth 3 score cp 100 time 1 nodes 171 nps 85000 pv a1b2 a7b7 b2c3
info depth 4 score cp 95 time 1 nodes 521 nps 260000 pv a1b2 a7b7 b2c3 b7c8
info depth 5 score cp 95 time 2 nodes 2171 nps 723000 pv a1b2 a7b7 b2b3 b7c8 b3c3
info depth 6 score cp 95 time 4 nodes 4374 nps 874000 pv a1b2 a7a6 b2b3 a6b7 b3c3 b7c8
info depth 7 score cp 100 time 5 nodes 9540 nps 1590000 pv a1b2 a7a6 b2c3 a6b7 c3d3 b7c8 d3e2
info depth 8 score cp 100 time 7 nodes 17728 nps 2216000 pv a1b2 a7a6 b2c3 a6b6 c3c4 b6a6 c4c3 a6b7
info depth 9 score cp 105 time 12 nodes 40761 nps 3135000 pv a1b2 a7a6 b2c3 a6b6 c3c4 b6a6 c4d3 a6b7 d3e2
info depth 10 score cp 100 time 23 nodes 100474 nps 4186000 pv a1b2 a7a6 b2c3 a6b6 c3c4 b6a6 c4d3 a6b7 d3e2 b7c8
info depth 11 score cp 105 time 53 nodes 297384 nps 5507000 pv a1b2 a7a6 b2c3 a6b6 c3d3 b6a6 d3c4 a6b6 c4d3 b6b7 d3e2
info depth 12 score cp 100 time 126 nodes 774376 nps 6097000 pv a1b2 a7a6 b2c3 a6b6 c3c4 b6a6 c4d3 a6b6 d3c4 b6a6 c4c3 a
6b7
info depth 13 score cp 105 time 312 nodes 2137414 nps 6828000 pv a1b2 a7a6 b2c3 a6b6 c3c4 b6a6 c4d3 a6b6 d3c4 b6a6 c4d3
a6b7 d3e2
info depth 14 score cp 100 time 836 nodes 5429043 nps 6486000 pv a1b2 a7a6 b2c3 a6b6 c3c4 b6a6 c4d3 a6b6 d3c4 b6a6 c4d3
a6b7 d3e2 b7c8
info depth 15 score cp 105 time 2199 nodes 15383429 nps 6992000 pv a1b2 a7a6 b2c3 a6b6 c3c4 b6a6 c4d3 a6b6 d3c3 b6a6 c3c
4 a6b6 c4d3 b6b7 d3e2
info depth 16 score cp 100 time 6016 nodes 40508273 nps 6732000 pv a1b2 a7a6 b2c3 a6b6 c3c4 b6a6 c4d3 a6b6 d3c4 b6a6 c4d
3 a6b6 d3e3 b6b7 e3e2 b7c8
info depth 17 score cp 105 time 16471 nodes 118124519 nps 7171000 pv a1b2 a7a6 b2c3 a6b6 c3c4 b6a6 c4d3 a6b6 d3c3 b6a6 c
3b3 a6b6 b3c4 b6a6 c4d3 a6b7 d3e2
info depth 18 score cp 100 time 41306 nodes 274092549 nps 6635000 pv a1b2 a7a6 b2c3 a6b6 c3c4 b6a6 c4d3 a6b6 d3c4 b6a6 c
4d3 a6b6 d3e3 b6a7 e3f3 a7b7 f3e2 b7c8
info depth 19 score cp 105 time 105701 nodes 753390765 nps 7127000 pv a1b2 a7a6 b2c3 a6b6 c3c4 b6a6 c4d3 a6b6 d3e3 b6c7
e3d2 c7b6 d2d3 b6a6 d3c4 a6b6 c4d3 b6b7 d3e2

What's the typical issue for an engine to not be able to solve this position? I would greatly appreciate it if anyone could nudge me in the right direction.

For reference, the source code of my engine is at https://github.com/konsolas/ToppleChess
The transposition table is an extremely basic always-replace table, in hash.(h/cpp), and the search is in search.(h/cpp)

[Ronald]

I took a quick look at your code and I noticed 2 things in your search function:

- 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

- Every time you find a new bestmove (score > alfa) you store the new bestmove in hash, this is however an intermediary result because you have not searched all the moves in the position yet, there might still be a better move or a fail high ahead. Because you already stored the position hash it influences the way later transpositions of the same position in the tree are evaluated and thus the evaluation of the position itself. 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.

Maybe this will solve your problem.

[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.