bound type in PVS ?

[MahmoudUthman]

In the following code I'm not sure what the bound type of the entry in nonPV search should be for mate and stalemate case :

Code: Select all

int searchNonPV(int alpha, int depth)/*beta=alpha+1*/
{
	if (insufficentMaterial) return 0;
	if (depth == 0) return qsearch<NonPV>(alpha, alpha + 1);
	int bestValue = -Value_Infinite, value;
	if (NMoves == 0)
	{
		TTStore(Move(), depth, BoundType::Exact, bestValue);
		bestValue = InCheck ? -Value_Mate + ply : Value_Draw;
	}
	Move mBest = Move();
	BoundType bound = BoundType::Upper;
	for (size_t i = 0; i < NMoves; i++)
	{
		Position::MakeMove(Available[i]);
		value = -searchNonPV(-(alpha + 1), depth - 1, true);
		Position::UnMakeMove(Available[i]);
		if (value > bestValue)
		{
			bestValue = value;
			if (value > alpha)
			{
				mBest = Available[i];
				bound = BoundType::Lower;
				if ((TypeBoard[Available[i].To] == 0)) UpdateKillersAndHistory(Available[i], depth);
				break;// Fail high:>=beta=alpha+1
			}
		}
	}
	TTStore(mBest, depth, bound, bestValue);
	return bestValue;
}

int searchPV(int alpha, int beta, int depth)
{
	if (insufficentMaterial) return 0;
	if (depth == 0) return qsearch<PV>(alpha, beta);
	int bestValue = -Value_Infinite, value;
	if (NMoves == 0)
	{
		TTStore(Move(), depth, BoundType::Exact, bestValue);
		bestValue = InCheck ? -Value_Mate + ply : Value_Draw;
	}
	Move mBest = Move();
	BoundType bound = BoundType::Upper;
	for (size_t i = 0; i < NMoves; i++)
	{
		Position::MakeMove(Available[i]);
		if (i > 0) value = -searchNonPV(-(alpha + 1), depth - 1, true);
		if (i == 0 || (value > alpha && (value < beta))) value = -searchPV(-beta, -alpha, depth - 1);
		Position::UnMakeMove(Available[i]);
		if (value > bestValue)
		{
			bestValue = value;
			if (value > alpha)
			{
				if (value < beta) alpha = value;
				else
				{
					mBest = Available[i];
					bound = BoundType::Lower;
					if ((TypeBoard[Available[i].To] == 0)) UpdateKillersAndHistory(Available[i], depth);
					break; // Fail high
				}
			}
		}
	}
	TTStore(mBest, depth, bound, bestValue);
	return bestValue;
}

is it right to store mate scores (checkmate , stalemate ) score as exact ? and why don't most/all engines store the draw score of insufficient material before returning a draw score ?

[Pio]

I guess that they do not save the entry of insufficient material because it takes time to save and read from the tt. Why not check for insufficent material before reading from the tt?

[Sven]

In the following code I'm not sure what the bound type of the entry in nonPV search should be for mate and stalemate case :
[...]
is it right to store mate scores (checkmate , stalemate ) score as exact ? and why don't most/all engines store the draw score of insufficient material before returning a draw score ?

The right bound type would of course be "exact" for all kinds of terminal positions. But I would not store anything at all for these (and I do not do so in Jumbo and did not do so in all my previous engines). The main purpose of the TT is 1) to improve move ordering by trying the TT move first, and 2) to save time by not searching a node again if the TT already contains a score with sufficient depth and matching bounds. Both do not apply for terminal positions, and storing information about these can be seen as a kind of "TT pollution" since you lose space for nodes with more valuable information.

In contrast to that, storing "mate(d) in N" for N > 0 can be beneficial, of course. But your example was about terminal positions (mated, draw by insufficient material, stalemate).

[mjlef]

Accessing transposition tables is actually pretty slow on modern, big memory machines. Although processors have reached higher speeds, main memory is actually very slow in comparison (once the hash table(s_ are bigger than the processor caches. So it is worthwhile testing various options to see what is best to store and what entries to replace. If it is faster to say call a draw for lack of material, then probing the transposition table, then go with the time saver, assuming the extra condition really is faster than the probe.

Mate and Stalemate can be stored as exact score, but you must modify them when reading and store to account for the distance to mate and ply from the root you are currently at. You can check out some public domain chess engines to see how to do that.

Mark