Page 1 of 2

TT Mate scores

Posted: Wed Feb 10, 2016 5:30 pm
by rgoomes
I'm having some trouble understanding how I can store and then retrieve the mate scores from the transposition table. I couldn't find in the website chessprogramming.wikispaces.com any useful info about this matter.

For example in this test position:
3k4/1R3p2/2p3pp/8/8/pR6/p7/4K3 w - - 0 1
There's mate in 6, and my engine finds it with no problem without TT. Using TT, instead my engine thinks there's mate in 5 somehow.

Another position, this one from the testing positions of chessprogramming.wikispaces.com:
5B2/6P1/1p6/8/1N6/kP6/2K5/8 w - -
Again, mate in 3 without TT, but mate in 2 with TT, and if I let it reach higher depth it starts to say there's is mate in -1... :D
What I have implemented: Alpha beta pruning with negamax, Storing the mate scores: -MATE + ply. Then if I can prune I just return the score from the table.

What I'm doing wrong?

Re: TT Mate scores

Posted: Wed Feb 10, 2016 10:59 pm
by hyatt
rgoomes wrote:I'm having some trouble understanding how I can store and then retrieve the mate scores from the transposition table. I couldn't find in the website chessprogramming.wikispaces.com any useful info about this matter.

For example in this test position:
3k4/1R3p2/2p3pp/8/8/pR6/p7/4K3 w - - 0 1
There's mate in 6, and my engine finds it with no problem without TT. Using TT, instead my engine thinks there's mate in 5 somehow.

Another position, this one from the testing positions of chessprogramming.wikispaces.com:
5B2/6P1/1p6/8/1N6/kP6/2K5/8 w - -
Again, mate in 3 without TT, but mate in 2 with TT, and if I let it reach higher depth it starts to say there's is mate in -1... :D
What I have implemented: Alpha beta pruning with negamax, Storing the mate scores: -MATE + ply. Then if I can prune I just return the score from the table.

What I'm doing wrong?

Mate scores are special. They represent mate in N move from the ROOT position. When you store a mate score internally inside the tree, you have to adjust it to mate in N minus something from the current position. Simple example.

the mate sequence looks like this:

P1 - P2 - P3 - P4 - P5 <mate in 3 moves>

At depth P1 you can safely store mate in 3, as when you look up the position, it really is a mate in 3. But at position P3, you store mate in 2 moves, since after P3 and P5 the opponent is mated.

That's step 1. Then when you look up the position and notice it is a mate-in-N (or mated-in-N) score, you have to do the inverse. Add the current ply to the score since if we are currently at depth=5, and found a mate in 3, it is really a mate in 9 plies (or mate in 5 moves) from the ROOT to the current position. And obviously all scores have to be relative to distance from the root.

Re: TT Mate scores

Posted: Sat Feb 13, 2016 1:01 am
by rgoomes
hyatt wrote:Mate scores are special. They represent mate in N move from the ROOT position. When you store a mate score internally inside the tree, you have to adjust it to mate in N minus something from the current position. Simple example.

the mate sequence looks like this:

P1 - P2 - P3 - P4 - P5 <mate in 3 moves>

At depth P1 you can safely store mate in 3, as when you look up the position, it really is a mate in 3. But at position P3, you store mate in 2 moves, since after P3 and P5 the opponent is mated.

That's step 1. Then when you look up the position and notice it is a mate-in-N (or mated-in-N) score, you have to do the inverse. Add the current ply to the score since if we are currently at depth=5, and found a mate in 3, it is really a mate in 9 plies (or mate in 5 moves) from the ROOT to the current position. And obviously all scores have to be relative to distance from the root.
I think I now understand that the mate scores need to be adjusted because we can find the position in different distances to the root. I tried to fix this in my own way but it failed completely.. In Stockfish they adjust the scores more or less like this:

Code: Select all

int value_to_tt(int score, int ply){
	if(score >= MATE - MAX_PLY)
		return score + ply;
	else if(score <= -MATE + MAX_PLY)
		return score - ply;
	else
		return score;
}

int value_from_tt(int score, int ply){
	if(score >= MATE - MAX_PLY)
		return score - ply;
	else if(score <= -MATE + MAX_PLY)
		return score + ply;
	else
		return score;
}
I tried this, but this also fails. If I'm not wrong they basically check if the score is MATE or not. If it isn't just store the TT score, otherwise they add or subtract the current ply based on negative or positive MATE score. Then on the lookup they do the inverse, instead of subtracting the cur ply they add it and vice-versa.. On my understanding this isn't enough, because we need to check if the stored ply of the mate score is greater or not to the current ply. Still, the code doesn't work on my engine..

Re: TT Mate scores

Posted: Sat Feb 13, 2016 5:05 pm
by hyatt
I do exactly the same thing. On storing:

if (value > 32000)
value += ply - 1;
else if (value < -32000)
value -= ply - 1;

In Crafty, any score > 32000 or < -32000 has to be mate, there is no way to have a 320 pawn advantage of deficit.

On probing:

if (val > 32000)
val -= ply - 1;
else if (val < -32000)
val += ply - 1;

Notice they are EXACT opposites. So scores are always corrected to distance to mate from the root before they are actually used.

Re: TT Mate scores

Posted: Mon Feb 15, 2016 10:05 pm
by rgoomes
hyatt wrote:I do exactly the same thing. On storing:

if (value > 32000)
value += ply - 1;
else if (value < -32000)
value -= ply - 1;

In Crafty, any score > 32000 or < -32000 has to be mate, there is no way to have a 320 pawn advantage of deficit.

On probing:

if (val > 32000)
val -= ply - 1;
else if (val < -32000)
val += ply - 1;

Notice they are EXACT opposites. So scores are always corrected to distance to mate from the root before they are actually used.
I think I found the problem. When I disable the check extension everything works fine. Basically when a move gives check I extend the depth by one ply and in this case the alphabeta call is like this: alphabeta(-beta, -alpha, depth (only depth and not depth-1), ply+1). I know that this makes the finding of mates "faster" because it finds a mate one depth earlier but I don't see how this can interfere with the mate scores.

Any idea why this happens?

Thank you for everything.

Re: TT Mate scores

Posted: Mon Feb 15, 2016 11:18 pm
by hyatt
I am hoping you meant

val = - alphabeta(-beta, -alpha, etc)???

If so, that should not be a problem. I would re-factor your code so that you only have one call to alphabet(), not one for in check and one for not in check, which is a good way to introduce bugs that are hard to find...

Re: TT Mate scores

Posted: Tue Feb 16, 2016 12:20 am
by rgoomes
hyatt wrote:I am hoping you meant

val = - alphabeta(-beta, -alpha, etc)???

If so, that should not be a problem. I would re-factor your code so that you only have one call to alphabet(), not one for in check and one for not in check, which is a good way to introduce bugs that are hard to find...
yes, its -alphabeta. I just wanted to show how the arguments were passed in that specific case, and I don't have different alphabeta calls. I also disabled quiescent search in my tests to see if the problem was there, but it wasn't.

Check my code (I did some changes to reduce the line count, hope no typos). It's about 80 lines, you should copy it to some text editor to read it better:

Code: Select all

int mated_in(int ply){ return -MATE+ply; }

int new_depth(Chessboard *b, int depth){
	return depth-1 + is_check(b, b->occ); /* is_check returns 1 if chessboard is in check */
}

int value_to_tt(int score, int ply){
	if(score >= MATE - MAX_PLY)
		return score + ply;
	else if(score <= -MATE + MAX_PLY)
		return score - ply;
	return score;
}

int value_from_tt(int score, int ply){
	if(score >= MATE - MAX_PLY)
		return score - ply;
	else if(score <= -MATE + MAX_PLY)
		return score + ply;
	return score;
}

bool can_tt_prune(table_t *entry, int alpha, int beta, int depth, int ply){
	if(entry == nullptr || entry->depth < depth)
		return false;

	int score = value_from_tt(entry->score, ply);
	if((entry->flag == ALL && score <= alpha) 
	|| (entry->flag == CUT && score >= beta)
	|| (entry->flag == PV))
		return true;

	return false;
}

table_t *tt_probe(Chessboard *b){
	uint64_t pos = b->key % hashblocks;
	return tt_table[pos].key == b->key ? tt_table+pos : NULL;
}

void tt_store(Chessboard *b, int bestscore, int alpha, int beta, int depth){
	uint64_t pos = b->key % hash_blocks;
	int flag = bestscore <= alpha ? ALL : bestscore >= beta ? CUT : PV;
	tt_table[pos] = {b->key, bestscore, depth, flag};
}

int alphabeta(Chessboard *b, int alpha, int beta, int depth, int ply){
	const int orig_alpha = alpha;

	table_t *entry = tt_probe(b);
	if(can_tt_prune(entry, alpha, beta, depth, ply))
		return value_from_tt(entry->score, ply);

	if(depth <= 0)
		return evaluate(b); //quiescent(b, alpha, beta, depth, ply);

	Info info = empty_info;
	Move mlist[MAX_MOVES], *end = gen_moves(b, mlist, &info, false /* true is to generate moves for quiescent, false here because not in quiescent */);

	for(Move *it = mlist; it != end; ++it){
		make_move(b, it);
		int val = -alphabeta(b, -beta, -alpha, new_depth(b, depth), ply+1);
		undo_move(b, it);

		if(val > alpha){
			alpha = val;
			if(val >= beta)
				break;
			update_pv(it, ply);
		}
	}

	if(!moves_left(mlist, end) /* if end - mlist == 0, if this position has no moves */ )
		alpha = info.checkers ? mated_in(ply) : DRAW /* 0 */;

	tt_store(b, value_to_tt(alpha, ply), orig_alpha, beta, depth);
	return alpha;
}

Re: TT Mate scores

Posted: Tue Feb 16, 2016 5:31 am
by hyatt
Note we don't match exactly. Here is mine again:

if (val > 32000)
val -= ply - 1;
else if (val < -32000)
val += ply - 1;

Note the val += ply -1 or val =- ply - 1. Perhaps that -1 is what you are missing?

Re: TT Mate scores

Posted: Tue Feb 16, 2016 12:39 pm
by rgoomes
hyatt wrote:Note we don't match exactly. Here is mine again:

if (val > 32000)
val -= ply - 1;
else if (val < -32000)
val += ply - 1;

Note the val += ply -1 or val =- ply - 1. Perhaps that -1 is what you are missing?
Subtracting one ply doesn't do anything. This is the scores I'm getting for the last test position (only material eval to simplify things):

Code: Select all

info depth 1 score cp 1500 nodes 24 nps 11999 time 2 pv g7g8q 
info depth 2 score cp 1500 nodes 166 nps 33199 time 5 pv g7g8q b6b5 
info depth 3 score cp 1500 nodes 755 nps 83888 time 9 pv g7g8q b6b5 g8f7 
info depth 4 score cp 1600 nodes 4899 nps 489899 time 10 pv b4d5 a3a2 d5b6 a2a1 
info depth 5 score mate 3 nodes 19431 nps 1494692 time 13 pv g7g8n b6b5 g8e7 a3b4 e7c6 
info depth 6 score mate 3 nodes 107651 nps 3844678 time 28 pv g7g8n b6b5 g8e7 a3b4 e7c6 
info depth 7 score mate 3 nodes 477279 nps 4870193 time 98 pv g7g8n b6b5 g8e7 a3b4 e7c6 
info depth 8 score mate 2 nodes 3560236 nps 5751592 time 619 pv c2c3 b6b5 b4c2 
info depth 9 score mate -8 nodes 16158674 nps 5960410 time 2711 pv

Re: TT Mate scores

Posted: Tue Feb 16, 2016 8:05 pm
by hyatt
My point was not that you needed the - 1 or + 1, but that you have to carefully look. For example, why not do this:

when you store a mate score, display the tree and print the actual score and the stored score. When you hit on a position with a mate score, display the position, the table score, and the adjusted mate score. You should quickly see what is going wrong.

You could use a simple mate in 3, searched just deeply enough to see it. Then make the expected move and see what kind of table scores you get back (which ought to be mate in 2). That will be a tiny amount of output with the displays I recommended above.