Weird mating behavior

[MOBMAT]

I am testing a new move generator and threw together some search and TT code to run some tests.

The move generation code checks out with exhaustive perft testing.
The TT is very basic, implementing an always replace scheme with mate score adjustments .
the search is off the shelf PVS with calls to the TT in the usual places.
Evaluation is disabled (always returns 0).
QSearch disabled.
No Null move or any other reductions/pruning

Barebones iterative deepening with PVS search.

I was testing some simple mate-N tests and got weird results. Positive mates (mate in N by the side moving) seems to work fine, but if i test mated in N (moving side is losing) positions, strange results.

The tests are shown in heavy debug mode, so ignore the times...

Example 1. A simple mate in -1.

fen 1q6/8/8/8/8/2k5/8/K7 w - - 0 34

Here is what happens with hash disabled...
-----------------------------------------
PLY NODES TIME SCORE PV
-----------------------------------------
1 1 :00 +0.00 a1a2
2 3 :00 +0.00 a1a2 b8b3
3 33 :00 -M1 a1a2 b8b2
4 88 :00 -M1 a1a2 b8b2
5 809 :00 -M1 a1a2 b8b2
6 2128 :00 -M1 a1a2 b8b2
7 19704 :00 -M1 a1a2 b8b2
8 52217 :02 -M1 a1a2 b8b2

As expected, search a couple of plies and find the result and report that for each additional ply.

Same test with hash enabled...
---------------------------------------------------
PLY NODES TIME SCORE PV
---------------------------------------------------
1 1 :00 +0.00 a1a2
2 3 :00 +0.00 a1a2 b8b3
3 31 :00 -M1 a1a2 b8b2
4 84 :00 +0.00 a1a2 b8b3 a2a1 b3c2
5 462 :00 -M1 a1a2 b8b2
6 1126 :00 -M2 a1a2 b8b3 a2a1 b3b2
7 4297 :00 -M1 a1a2 b8b2
8 9321 :00 -M2 a1a2 b8b4 a2a1 b4b2

Example 2, another mate in -1:
fen 6k1/1pp3pp/2n5/1P3p2/p2p4/P1qP1P2/Kr3P1P/1Rb5 w - - 0 34
No hash...
----------------------------------------
PLY NODES TIME SCORE PV
----------------------------------------
1 1 :00 +0.00 b1b2
2 4 :00 +0.00 b1b2 c1b2
3 46 :00 -M1 b1b2 c3b2
4 129 :00 -M1 b1b2 c3b2
5 1273 :00 -M1 b1b2 c3b2
6 3487 :00 -M1 b1b2 c3b2
7 34217 :00 -M1 b1b2 c3b2
8 93237 :03 -M1 b1b2 c3b2
9 715475 :19 -M1 b1b2 c3b2

With hash...
-------------------------------------------------------
PLY NODES TIME SCORE PV
-------------------------------------------------------
1 1 :00 +0.00 b1b2
2 4 :00 +0.00 b1b2 c1b2
3 46 :00 -M1 b1b2 c3b2
4 121 :00 +0.00 b1b2 c1b2 b5c6 b7c6
5 1080 :00 -M1 b1b2 c3b2
6 2702 :00 +0.00 b1b2 c1b2 b5c6 b7c6 f3f4 b2a3
7 21789 :00 -M1 b1b2 c3b2
8 60699 :02 +0.00 b1b2 c1b2 b5c6 b7c6 f3f4 b2a3 f2f3 c3d3
9 342347 :10 -M1 b1b2 c3b2

The even plies seem to be missing the solution.

I've been debugging this for way too long.
I'm hoping someone has seen a similar pattern and knows where to point me.

I'll post some code if needed.

[jdart]

It can be very helpful for debugging if you are able to dump out a full trace of all nodes searched, and what the score at each node was, whether from hash or from search, and where the PV is updated.

That said, one of the things you want to be careful about is adjusting mate scores in the hash table based on the current depth. Mates should always get a score that is relative to how far from the root node you are. If you fetch a mate score from the hash, though, it could have been from a transposition that is closer or father from the root than the current node is.

--Jon

[Ras]

It seems that mostly, the engine with hash and with even depth re-uses the move that it had already at depth 2.

1) when you have a hash hit, you you check that the depth draft of your hash hit is sufficient four your remaining search depth? If this isn't the case, what do you do?
2) do you put the mating move into the hash table, in this case the root move that is backup up with depth 3?
3) what is your move sorting with regard to following the PV from the previous depth iteration?

[MOBMAT]

1) when you have a hash hit, you you check that the depth draft of your hash hit is sufficient four your remaining search depth? If this isn't the case, what do you do?

ere is the hash probe. I check the stored hash depth to make sure it is as deep as the probing depth. I'm implementing "fail soft".... in case that question comes up.

Code: Select all

bool MainHash::ProbeHash(Position* p, I8 depth, MSCORE alpha, MSCORE beta, MSCORE *score, MOVE* move)
	{
	if (!m_NumHashEntries){
		*move = NOMOVE;
		return false;
		}

	U32 index = GetHashIndex(p->PosKey);
	TTMAIN *ptt = &m_Hash[index];	// points to the hash entry
	bool ret = false;

	if (ptt->key == p->PosKey){
		*move = ptt->Move;	// we return the move, if the keys match
		if (ptt->Depth >= depth)	{
			*score = ptt->Value;

			switch (ptt->Flag)	{
				case TT_NONE:	break;

				case TT_ALPHA:
					if (*score <= alpha) {
						*score = alpha;
						ret = true;
						}
					break;

				case TT_BETA:
					if (*score >= beta) {
						*score = beta;
						ret = true;
						}
					break;

				case TT_EXACT:	ret = true;	break;

				default:	assert(1==0);
				}
			}
		}
	return ret;
	}

2) do you put the mating move into the hash table, in this case the root move that is backup up with depth 3?
3) what is your move sorting with regard to following the PV from the previous depth iteration?

Here is the main search. I have it stripped down for testing this problem.
I probe at the top of the search (answers 3) and return if a cutoff or exact value. I am testing a stripped down version. I have special root code which i'm not using for this test which also does additional move ordering. for this test, move ordering shouldn't make a difference. The mating move should be found or calculated somewhere.
i save beta cutoff and save the result of the search at the bottom

the only "different" thing I do is carry a var in my position call "Mate" which is the current mate score. this is initialized at he root and decremented in CopyBoard() as we descend. I got this idea from something Bruce Moreland wrote, but let's not argue the merits of that right now. It avoids all the mate score fixing confusion coming/going from the hash. I know that works (non hash code is working fine). it is returned when a mate is discovered.

Code: Select all

MSCORE ABTTFS(Position* p, I8 depth, MSCORE alpha, MSCORE beta, PVLINE *pPV, bool DoNull)
	{
	if (p->IsDraw())return _DRAWSCORE;
	if (IsTimeOut())return _DRAWSCORE;

	MSCORE v;
	MOVE hmove;		// move from the hash table
	// if we get an exact or cutoff score, return
	if (g.TTMain.ProbeHash(p, depth, alpha, beta, &v, &hmove))
		return v;

	if (depth <= 0)		// call QSearch (eval for testing
		{
		if (pPV) pPV->NumMoves = 0;
		v = Evaluate(p);
		//v = QSearch(p, alpha, beta, _QS_CHKCNTMAX);
		return v;
		}

	if (TooDeep(p->Ply))	return Evaluate(p);		// rodent uses beta, some use Evaluate(p)

	g.Nodes++;		// increment any time we have gone deeper

	bool InCheck = p->IsSTMInCheck();
	bool IsPV = (alpha != (beta - 1));

	Position p1;
	MOVE m;
	Moves ml;
	MOVE BestMove = NOMOVE;
	MSCORE BestScore = -_INF;
	PVLINE pv;

	ml.Init(p, hmove);	// save the hash
	
	while (ml.GetNextMove(&m)){		// generating legal moves right now

		CopyBoard(&p1, p);	// copy the board so we can make the move onto it
		p1.MakeMove(m);		// make the move onto the copy of the board

		// PVS
		if (BestScore == -_INF)		// haven't searched yet, so do full width search
			v = -ABTTFS(&p1, depth - 1, -beta, -alpha, &pv, NULL_OK);
		else {
			v = -ABTTFS(&p1, depth - 1, -alpha - 1, -alpha, &pv, NULL_OK);
			if (g.TimeOver)	return _DRAWSCORE;

			if ((v > alpha) && (v < beta))
				v = -ABTTFS(&p1, depth - 1, -beta, -alpha, &pv, NULL_OK);
			}

		if (g.TimeOver)	return _DRAWSCORE;

		if (v >= beta) {
			g.TTMain.SaveHash(p, depth, v, TT_BETA, m);
			return v;
			}

		if (v > BestScore){
			BestScore = v;
			if (v > alpha){
				alpha = v;
				BestMove = m;
				AddPVMove(pPV, &pv, m);
				}
			}
	} // end of move loop

	// check if mate  
	if (BestScore == -_INF)	{	// were there any  moves played
		if (pPV) pPV->NumMoves = 0;	// no PV in this situation
		return InCheck ? -p->Mate : _DRAWSCORE;
		}

	// store to the hash based on the values
	if (BestMove.Move())
		g.TTMain.SaveHash(p, depth, BestScore, TTTYPE::TT_EXACT, BestMove);
	else
		g.TTMain.SaveHash(p, depth, BestScore, TTTYPE::TT_ALPHA, NOMOVE);

	return BestScore;

}

The Hash Save is pretty simple...always overwrite.

Code: Select all

void MainHash::SaveHash(Position *p, I8 depth, MSCORE score, TTTYPE flag, MOVE move)
	{
	if (!m_NumHashEntries) return;

	U32 index = GetHashIndex(p->PosKey);	
	TTMAIN *ptt = &m_Hash[index];

	if (ptt->key == 0)
		m_HashNewWrites++;	// for UCI stats
	else
		m_HashOverWrites++;

	// overwrite the entry
	ptt->Depth = depth;
	ptt->Flag = flag;
	ptt->key = p->PosKey;
	ptt->Value = score;
	ptt->Move = move.Move();
	}

[Ras]

Hm, the only thing that I do differently is taking care of the pPV in case of a hash hit. That gets either length 1 and the hash move or length 0 if the hash hit doesn't give a hash move.

When saving hash with beta cutoff, I think it should be TTTYPE::TT_BETA and not just TT_BETA, but that's probably cosmetics.

But I guess you'll have to make a full dump at each depth level to figure out what's going on, as Jon suggested.

[MOBMAT]

Mystery solved.

It wasn't the Hash code, it wasn't the search code.
It was two issues.

a minor problem in the pseudo legal move checking code (for hash and killers) that missed some otherwise good queen moves, and a problem in the GetNextMove() ignoring the hash move in certain situations.

thanks for taking a look.