search or transposition table bug?

[OliverUwira]

Hmm your engine sees that Kd7 is losing since ply 9. Even if my engine would see it at ply 12 it's still too late. My evalfn is probably to blame, who knows... It drives the search and most pruning so it's still far from perfect... but even then the search should see it... why should I need 3 or even 5 more plies? ... I'm sure I've a bug somewhere...

I don't think your eval is the culprit.

PS the 1-meg version scored 65% against a 128-meg TT version in 40 test games (1 game in 1 minute) so that's quite a difference...

Ok but that doesn't explain why a 1-meg TT version is 100 elo stronger. So I suppose I have a serious bug somewhere.

This seem to be a better clue. It's quite likely that your TT does something incorrectly.

Maybe you could post your hash probing code here.

btw. insane nps I get only 33% and the search takes much longer (14x) to reach more time to reach 14 plies

There's always room for improvement. I also have a long way in front of me. The changes I made between last year's version of Kurt (271009), which were mostly bugfixes and some search enhancements, resulted in a huge NPS speedup. The eval is still thick like a brick, though, and speed is just part of the story (-:

[mar]

There is a simple way to find out if you have a TT bug.
1. Write a second hash calculator that computes the entire hash from scratch.
Then when you incrementally update your Zobrist hash in debug mode, also update the full hash.
Compare both hash values. If they do not agree, then you have a hash calculation bug.

2. Make a hash table that holds the Epd position as one of its elements if it is compiled in debug mode. When you have a hash hit, then check the Epd position you are analyzing with the stored Epd position. If the hash matches and the EPD values don't match, and it happens frequently, there is a problem. This is better than storing the whole 64 bit hash instead, but that is also a good idea.

So if you have a hash formation bug or a hash storage bug or a hash retrieval bug this will catch it. You probably have most of the code already written (e.g. just call the routine you will call when someone gives you an EPD or FEN string to create the hash against the whole position).

Most hash computation bugs I have seen are from:
1. e.p. problem
2. null move problem
3. castle rights problem
Other problems happen too, but are more rare.

If you have a fancy pants hash that chains long lists of equal hash values or otherwise stores multiple values for a single hash number, you might try simplifying to a single value lookup to see if that fixes it. Sometimes the alternative lookups in the hash table get muddled.

Thanks. I already check the incremental hash value against hash from scratch in debug mode so I'm pretty sure it's ok. I also tried to store
the whole board in TT and compare so I'm sure there're no hash collisions either
I have a very simple hash table where I cluster 4 values in one and do a linear search for 64-bit hash signature.
So I think I might have a bug in search... or maybe some nasty bug in repetition detection... hard to say, there can be 1000 reasons for that...

[OliverUwira]

So I think I might have a bug in search... or maybe some nasty bug in repetition detection... hard to say, there can be 1000 reasons for that...

Don't forget that the repetition draw curiously ends up as the root PV. This could point to some error with the way your hash store and hash probe handles the bounds and remaining depth.

[mar]

Ok here's my hash probing code:

Code: Select all

const BitTransEntry *te = trans.entry( h );
if ( te )
{
	if ( (te->type & 3) && te->depth >= depth	)
	{
		// potential trans_table hit!
		i32 val = te->getValue( ply );
		switch( te->type & 3 )
		{
		case bttFull:
			se.move.packed = te->move.packed;
			return CLAMP_AB(val);
		case bttAlpha:
			if ( val <= alpha )
			&#123;
				se.move.packed = te->move.packed;
				return CLAMP_AB&#40;val&#41;;//alpha;
			&#125;
			break;
		case bttBeta&#58;
			if ( val >= beta )
			&#123;
				se.move.packed = te->move.packed;
				return CLAMP_AB&#40; val );
			&#125;
			break;
		&#125;
		hashmv.packed = te->move.packed;
	&#125;
	else
	&#123;
		if ( te->type & 3 )
			hashmv.packed = te->move.packed;
	&#125;
&#125;

To clarify some things:
bttFull corresponds to exact
bttAlpha corresponds to upperbound
bttBeta corresponds to lowerbound
se = current search stack ref (current ply)

CLAMP_AB(x) is a macro that currently does nothing (returns x)

[mar]

So I think I might have a bug in search... or maybe some nasty bug in repetition detection... hard to say, there can be 1000 reasons for that...

Don't forget that the repetition draw curiously ends up as the root PV. This could point to some error with the way your hash store and hash probe handles the bounds and remaining depth.

hmm I don't handle remaining depth at all... I mean if I search at depth 10 and I hit a repetition at depth 9 and it is the best move then I would store depth 10 value 0 (maybe even EXACT) with rep move... Is that what you mean? Now I'm a bit lost...

[OliverUwira]

So I think I might have a bug in search... or maybe some nasty bug in repetition detection... hard to say, there can be 1000 reasons for that...

Don't forget that the repetition draw curiously ends up as the root PV. This could point to some error with the way your hash store and hash probe handles the bounds and remaining depth.

hmm I don't handle remaining depth at all... I mean if I search at depth 10 and I hit a repetition at depth 9 and it is the best move then I would store depth 10 value 0 (maybe even EXACT) with rep move... Is that what you mean? Now I'm a bit lost...

If your iteration depth is 10 and you want to store a value into the TT at ply 9, you should store it with depth = 1 because you searched that position only one ply deep.

If you would really store depth = 10 in this scenario, it is no wonder that your engine does not find the win earlier, because a one ply search result would cause hash hits even if the search is to be to larger depths.

By the way, it seems that you do not increase alpha to val in case of an exact hit. This will make your search tree larger with no benefit. Could be that you do that once your probing function returns, though.

[mar]

If your iteration depth is 10 and you want to store a value into the TT at ply 9, you should store it with depth = 1 because you searched that position only one ply deep.

If you would really store depth = 10 in this scenario, it is no wonder that your engine does not find the win earlier, because a one ply search result would cause hash hits even if the search is to be to larger depths.

By the way, it seems that you do not increase alpha to val in case of an exact hit. This will make your search tree larger with no benefit. Could be that you do that once your probing function returns, though.

1) Well if I detect repetition at depth 9 I return 0. Then the search at depth 10 continues. IF it doesn't find a better move then it stores 0 with depth 10 (+the move that leads to repetition). How do I know that I searched the position only one ply deep? do you store something like selective depth for that node - root depth?! that seems crazy or maybe I don't get it. Never heard of anything like that. I get the same problem even if I don't use TT cutoff in PV nodes.

2) When I cutoff using TT (and type is EXACT) then I simply return the TT value. That should be ok I think. Or do you mean that I should raise that to alpha if alpha > tt_exact_val?
EDIT: sorry ok that's not a probing function but a code fragment directly from search. (so "probing function" inlined, which is ugly I know)

[OliverUwira]

If your iteration depth is 10 and you want to store a value into the TT at ply 9, you should store it with depth = 1 because you searched that position only one ply deep.

If you would really store depth = 10 in this scenario, it is no wonder that your engine does not find the win earlier, because a one ply search result would cause hash hits even if the search is to be to larger depths.

By the way, it seems that you do not increase alpha to val in case of an exact hit. This will make your search tree larger with no benefit. Could be that you do that once your probing function returns, though.

1) Well if I detect repetition at depth 9 I return 0. Then the search at depth 10 continues. IF it doesn't find a better move then it stores 0 with depth 10 (+the move that leads to repetition). How do I know that I searched the position only one ply deep? do you store something like selective depth for that node - root depth?! that seems crazy or maybe I don't get it. Never heard of anything like that. I get the same problem even if I don't use TT cutoff in PV nodes.

2) When I cutoff using TT (and type is EXACT) then I simply return the TT value. That should be ok I think. Or do you mean that I should raise that to alpha if alpha > tt_exact_val?
EDIT: sorry ok that's not a probing function but a code fragment directly from search. (so "probing function" inlined, which is ugly I know)

ad 1)

I mean something like the following:

Code: Select all

int search(int alpha, int beta, int depth)
{
     ...

     MakeMove();
     // depth decreases with every recursive call
     value = -search(-beta, -alpha, depth - 1);      
     UnmakeMove();
     ...
     
     HashStore(value, ttflag, depth);

     ...
}

At the root you call search with the current iteration depth - 1, which is decreased with every further recursive call. The depth that you pass to search is what I call "remaining depth", which is what should be used when storing into the TT.

ad 2)

If you have an exact hit, you should check the exact value against your current bounds. If the exact value is greater than alpha, you can narrow the bounds by setting alpha to the retrieved value. If that is now greater than beta, you must not update the PV because you have a beta cutoff.

[mar]

ad 1)

I mean something like the following:

Code: Select all

int search(int alpha, int beta, int depth)
{
     ...

     MakeMove();
     // depth decreases with every recursive call
     value = -search(-beta, -alpha, depth - 1);      
     UnmakeMove();
     ...
     
     HashStore(value, ttflag, depth);

     ...
}

At the root you call search with the current iteration depth - 1, which is decreased with every further recursive call. The depth that you pass to search is what I call "remaining depth", which is what should be used when storing into the TT.

ad 2)

If you have an exact hit, you should check the exact value against your current bounds. If the exact value is greater than alpha, you can narrow the bounds by setting alpha to the retrieved value. If that is now greater than beta, you must not update the PV because you have a beta cutoff.

Ok now I get it.
ad 1) that's exactly what I do
ad 2) I thought that when I get an exact hit I don't have to search any further and simply return the current value. The bound will eventually get narrowed in the parent node so it should be ok I think. But I'll have to look into it, thanks for help!

[OliverUwira]

ad 2) I thought that when I get an exact hit I don't have to search any further and simply return the current value. The bound will eventually get narrowed in the parent node so it should be ok I think. But I'll have to look into it, thanks for help!

Yes, now that I look again, your code should work. I didn't pay enough attention to the fact that your code is part of the search function.

It still must have something to do with your hash framework. I can't imagine an engine without TT being stronger than one that uses a TT.