Transposition table problem

[Desperado]

Repetition detection is strongly recommended for searching any endgame position.

yes it is, and not only for endgame positions.
All i wanted to say is, that building an engine step by step, there is a
good chance doing everything well, but not being comparable with
already _full featured_ engines. (because of missing elements like repetition draw detection,
move ordering and many other things).
So i just wanted to avoid _misleading_ Marika, that this standard testposition for working TTs should be solved in 1s,
otherwise sth would be wrong. It _could_ be simply the phase of development which avoids solving it.

On the other hand i agree totally, that an engine,
full equipped with _basic_ features should pass such tests easily within a second (seconds).

And we all know, later in a more advanced engine there will occur new stumbling blocks,
like nullmove in pawnendgames (if someone likes...),
which may lead to a completly new task regarding this testposition for example.

just my thoughts...

cheers, Michael

[Sven]

Have you checked, for instance, that your hash key generated incrementally after each move is 100% identical to the hash key calculated from scratch?

Perhaps I don't understand here. Do you mean that the hash codes should be identical when I play a sequence of moves with or without searching?

I mean a simple consistency check for debugging which you can apply after each makeMove (during search or game). The hash key is usually calculated incrementally: you have a key for the current board, then update it when making a move, and update it again after unmaking that move. But it can also be calculated from scratch by starting with 0 for the empty board, then updating it for each piece and for everything else influencing the hash key (side to move, castling flags, ...). This is very slow but you could use it for a debug-only version to compare the incremental with the non-incremental hash key after each makeMove. The values must be identical due to the XORing principle of zobrist keys.

Sven

[Sven]

Well, I expected that my wrong expectations were caused by some bug. But now I starting to thing more and more, that it is not necessary.

You could to the following temporary test: modify your TT lookup such that you only prune a subtree if a TT entry is found with exactly the same draft as the remaining depth at the current node, not ">=". This is not meant for the productive version, of course.

a) If the problem persists then I would say that it is very likely that you have a bug.

b) If it disappears then the problem was probably related to wrong expectations. As Onno pointed out, if you search a node to remaining depth D and find a TT hit with draft TTD > D then the value will sometimes differ from the value of searching to depth D only. This can happen with transpositions at different levels in the tree, usually when moves are played in a different order. The proposed test should make this effect disappear so that the TT is now nothing more than a slight speedup while "searching" exactly the same tree.

Even in case of b) I would propose not to stop looking for a bug, at least I would continue to implement all "standard" testing and debugging to verify your TT implementation. Some have been mentioned here.

One more question: is there any random influence on your search? E.g., are you using fixed zobrist keys or do you generate different (random) keys at each program startup? Having the ability to get an exactly reproducible search can help a lot in debugging, and a non-reproducible search could sometimes explain a part of your problems.

The "Fine #70" test is definitely worth trying, even though you should not care too much about the time to find the solution. If your TT is broken then I'd think that your program would struggle to make any progress at all since it would search a huge number of nodes again and again and would not reach an acceptable depth. To solve this position it is necessary to reach a depth far beyond 20 within reasonable time.

Of course you might fail to solve this position even with a correct TT implementation, for instance with inefficient move ordering or if you do not implement repetition detection. Also I am not sure whether the lack of quiescence search can have a negative impact on solving this kind of positions.

Sven

[Desperado]

Even in case of b) I would propose not to stop looking for a bug, ....

@Sven: again , very good points...

@Marika:

Yes, _never_ stop looking for bugs.

Because Sven,Onno and other people are giving very good advices to
debug and finally getting a proper implementation of TTs,
i just want to give you an alernative point of view (for a very good reason,which follows!)

While i was reading the last post of Sven, who again suggested to test the standard test position,
i thought why to hell doesnt anybody suggest sth. more simple like KpK, or any other _3Men,_4Men
where the TT should have significantly effect on the search depth (independant of any solution).
In such cases you get a feeling what TT is able to do,
and you can watch your progress because of significant differences on depth within the same time.

So, before posting my proposal, i thought to be on the safe side, i setup
again an AB-Frame (which already was cleaned up since yesterday) to proove if my suggestion make sense.

Now the _big_ no.... _BIG_ suprise!

- AB-Frame
- no move ordering (beside my rootNode, and capturesLists)
- only TT-cuts
- no repetition detection
- no extensions,reductions,prunings.
- evaluation include pawns,pst,material

The result was _shocking_, because if there was a gain from TT this would
have to be measured, but i was waiting for a significant depth increasment
using TT.

So, i strongly recommend to introduce at least a temporarily moveordering scheme, maybe based on pst-values.
Done this, you should test positions where TT has eye-catching influence,
like 3Men positions.

My suggestion should _not_ exclude Sven's proposals, or any other general good advice giving in this thread.

just try it...

Michael

[marion]

I tried this position and my engine played Kb1 in about 3 seconds...

[Alessandro Damiani]

Hi Marika,

I think you run into the same issue as I did after refactoring my code. The score of a move determined by

Code: Select all

	value = -alfabeta(board, depth - 1, -beta, -alpha, -color);

within the loop is unknown when time expires. Therefore the search should terminate without updating the transposition table. In your code the highest static eval score of the moves is stored in the transposition table when time expires. This wrong score can be propagated to the root affecting the move played in the game. One solution looks like this (pseudo code, without details):

Code: Select all

	int search(int depth, int alpha, int beta) {
		if (depth <= 0) {
			return evaluate();   // actually a quiescence search is better
		}
		
		if (isTimeExpired) {
			return 0;		// the value doesn't matter, since not used
		}
		
		TTableEntry entry = transpositionTable.get();
		
		// check for hashtable cut-off here.
		
		int initialAlpha = alpha;
		int best = -MATE + ply;
		Move bestMove = NO_MOVE;
		Move move = nextMove();
		
		while (move != NO_MOVE) {
			make(move);
			int value = -search(depth - 1, -beta, -alpha);
			unmake(move);
			
			// don't update the hashtable when time expired:
			if (isTimeExpired) {
				return 0;
			}

			if (value > best) {
				best = value;
				bestMove = move;
					
				if (best >= beta) {
					move = NO_MOVE;
				}
				
				else {
					if (best > alpha) {
						alpha = best;
						
						// update PV here.
					}
			
					move = nextMove();
				}
			}
			
			else {
				move = nextMove();
			}
		}
		
		// check for stale mate here.
		
		int flag;
		
		if (best <= initialAlpha) {
			flag = UPPER_BOUND;
		}
		
		else if (best >= beta) {
			flag = LOWER_BOUND;
		}
		
		else {
			flag = EXACT_SCORE;
		}
		
		transpositionTable.put(best, flag, bestMove);
		return best;
	}

I hope this helps.

Ciao ciao,
Alessandro

[Sven]

Hi Marika,

I think you run into the same issue as I did after refactoring my code. The score of a move determined by

Code: Select all

	value = -alfabeta(board, depth - 1, -beta, -alpha, -color);

within the loop is unknown when time expires. Therefore the search should terminate without updating the transposition table. In your code the highest static eval score of the moves is stored in the transposition table when time expires. This wrong score can be propagated to the root affecting the move played in the game.

Correct and definitely a very good point. But since Marika reported that the divergence between move decisions with vs. without TT occurs in a fixed-depth search, I believe that the timeout scenario does not influence the problem described.

One solution looks like this (pseudo code, without details):

Code: Select all

	int search(int depth, int alpha, int beta) {
		if (depth <= 0) {
			return evaluate();   // actually a quiescence search is better
		}
		
		if (isTimeExpired) {
			return 0;		// the value doesn't matter, since not used
		}
		
		TTableEntry entry = transpositionTable.get();
		
		// check for hashtable cut-off here.
		
		int initialAlpha = alpha;
		int best = -MATE + ply;
		Move bestMove = NO_MOVE;
		Move move = nextMove();
		
		while (move != NO_MOVE) {
			make(move);
			int value = -search(depth - 1, -beta, -alpha);
			unmake(move);
			
			// don't update the hashtable when time expired:
			if (isTimeExpired) {
				return 0;
			}

			if (value > best) {
				best = value;
				bestMove = move;
					
				if (best >= beta) {
					move = NO_MOVE;
				}
				
				else {
					if (best > alpha) {
						alpha = best;
						
						// update PV here.
					}
			
					move = nextMove();
				}
			}
			
			else {
				move = nextMove();
			}
		}
		
		// check for stale mate here.
		
		int flag;
		
		if (best <= initialAlpha) {
			flag = UPPER_BOUND;
		}
		
		else if (best >= beta) {
			flag = LOWER_BOUND;
		}
		
		else {
			flag = EXACT_SCORE;
		}
		
		transpositionTable.put(best, flag, bestMove);
		return best;
	}

The use of "initialAlpha" is of course an essential point that is missed sometimes.

It has been proposed that one should not store a "bestMove" in TT if the "bestValue" (you call it "best") is <= alpha, the reason being that you don't know whether it is really the best move (scores outside the window can't be compared reliably). Also you are using fail-soft while Marika's code is fail-hard, which might make a comparison a bit difficult. I know you wrote it is only pseudocode but for the two reasons I have given a modified version could look like this:

Code: Select all

	int search(int depth, int alpha, int beta) {
		if (depth <= 0) {
			return evaluate();   // actually a quiescence search is better
		}
		
		if (isTimeExpired) {
			return 0;		// the value doesn't matter, since not used
		}
		
		TTableEntry entry = transpositionTable.get();
		
		// check for hashtable cut-off here.
		
		int initialAlpha = alpha;
		Move bestMove = NO_MOVE;
		Move move;
		
		for (move = nextMove(); move != NO_MOVE; move = nextMove()) {
			make(move);
			int value = -search(depth - 1, -beta, -alpha);
			unmake(move);
			
			// don't update the hashtable when time expired:
			if (isTimeExpired) {
				return 0;
			}

			if (value > alpha) {
				alpha = value;
					
				if (value >= beta) {
					break;
				} else {
					bestMove = move;
					// update PV here.
				}
			}
		}
		
		// check for stale mate here.
		
		int flag;
		
		if (alpha <= initialAlpha) {
			flag = UPPER_BOUND;
		}
		
		else if (alpha >= beta) {
			flag = LOWER_BOUND;
		}
		
		else {
			flag = EXACT_SCORE;
		}
		
		transpositionTable.put(alpha, flag, bestMove);
		return alpha;
	}

Sven

[Sven]

I tried this position and my engine played Kb1 in about 3 seconds...

Ok, so your TT seems to work well at least, assuming it also shows a clearly winning score for Kb1. Which depth does your engine reach in that case?

Did you already try the temporary test I proposed, switching from ">=" match for TT cutoff to "exact depth" match just to see what happens? I am curious to read whether it makes the "different move decisions" effect go away or not in your engine (I would expect it does).

Another point, Alessandro has posted pseudocode where also one difference to your code should be noticed: checking for "depth <= 0" before probing the TT which you have in reversed order. Since you don't store anything in TT for depth == 0 you can easily swap the order of these two parts, saving many redundant TT probes at depth == 0 where you will get very few matches only (transposition to a position with depth >= 2). With the version you posted you will frequently do the TT probe and call the evaluation function. It is not a big saving but you get it for free.

Sven