Transposition tables are very frustrating, I think I understand what is going on but then engine does something crazy
I first implemented it according to Bruce's website and following along Maksims Youtube tutorials. Then I changed to an approach similar to Leorik and Cosette for the store/read but kept the search store/read places as before.
All seems fine and it plays as before implementing the tables, but with a reduced node count of around half. All good I thought.. Then I got to the endgame and saw some really strange behaviors, when it was finding/not finding mates which makes me think something is wrong with how I store these scores. Since I followed all tutorials and have checked the code for a around a week without finding what can be wrong I am now hoping someone here is able to point me in the right direction.
Given this position it finds the mate in 4 with Bc4 at depth 8 and onwards.
[fen]k7/4P3/3B4/8/1p2p3/pP2P1P1/P1P1B1P1/4K3 w - - 0 1[/fen]
The moves in PV looks a bit strange though and it looks like it thinks white plays twice in a row:
Code: Select all
1 00:00 24 8 +13,69 e7-e8Q+
2 00:00 103 8 +14,13 e7-e8Q+ Ka8-b7
3 00:00 318 8 +14,13 e7-e8Q+ Ka8-b7 Bd6xb4
4 00:00 560 560k +18,53 Bd6xb4 Ka8-b8 e7-e8Q+ Kb8-b7
5 00:00 3k 481k +15,83 Be2-a6 Ka8-a7 Bd6xb4 Ka7xa6 e7-e8Q
6 00:00 9k 429k +18,63 Be2-c4 Ka8-a7 e7-e8Q Ka7-b7 Bd6xb4 Kb7-a7
7 00:00 56k 607k +18,90 Bd6xb4 Ka8-b8 e7-e8Q+ Kb8-a7 Bb4xa3 Ka7-b7
8 00:00 148k 449k +M4 Be2-c4 Ka8-b7 e7-e8Q Kb7-b6 Kb6-c6
9 00:02 1 441k 643k +M4 Be2-c4 Ka8-b7 e7-e8Q Kb7-b6 Kb6-a5
10 00:03 1 823k 574k +M4 Be2-c4 Ka8-a7 e7-e8Q Ka7-b7 Kb7-c6
11 00:07 4 631k 629k +M4 Be2-c4 Ka8-a7 e7-e8Q Ka7-b7 Kb7-c6
Then if I play Ka7 it suddenly forgets the mate and print a completely nonsense PV line for the depths:
Code: Select all
1 00:00 24 8 +13,59 e7-e8Q
2 00:00 113 8 +18,05 e7-e8Q Ka7-b7
3 00:00 379 190k +18,05 e7-e8Q Ka7-b7 Bd6xb4
4 00:00 1k 274k +18,59 Bc4-d5 Ka7-a6 e7-e8Q Ka6-a7
5 00:00 4k 366k +18,63 e7-e8Q Ka7-b7 Bd6xb4 Kb7-a7 Bb4xa3
6 00:00 12k 349k +16,13 Bc4-a6 Ka7xa6 e7-e8Q Ka6-a5 Ka5-b5
7 00:00 37k 410k +M3 e7-e8Q Ka7-b7 Kb7-c6
8 00:00 60k 409k +19,33 Bd6xb4 Ka7-b7 Bb4xa3 Kb7-b8 e7-e8Q+ Kb8-a7 Bc4-f7 Ka7-b7
9 00:00 163k 488k +19,50 Bd6xb4 Ka7-a8 e7-e8Q+ Ka8-b7 Bb4xa3 Kb7-b6 Kb6-a7 e4xe8
10 00:00 316k 435k +20,01 Bd6xb4 Ka7-b8 Bb4xa3 Kb8-a8 e7-e8Q+ Ka8-a7 Bc4-d5 Ka7-b6 Ba3-d6 Kb6-a7
11 00:01 688k 494k +M5 Bd6xb4 Ka7-a8 Bb4-d6 Ka8-a7 e7-e8Q Ka7-b7 Kb7-a8 Bc4-d5+
NEGAMAX code (with some storing and other things cleaned for simplicity of reading:
Code: Select all
private int Negamax(int depth, int ply, int alpha, int beta)
{
// Find if it is a draw
if (boardState.CheckForDraw()) return 0;
// Init variables
int score;
bool foundPV = false;
bool isPV = (beta - alpha) > 1;
// Check transpositions (not in PV nodes, not when ply == 0 and not when we don't have an entry)
if (Transpositions.ReadTT(boardState.ZobristKey, depth, ply, alpha, beta, out Move _bestMove, out int _score))
{
if (!isPV && ply != 0)
{
return _score;
}
}
// Check if we reached depth 0 and go into Quiscence search
if (depth == 0)
{
score = QuiescenceSearch(ply, alpha, beta);
Transpositions.WriteTT(boardState.ZobristKey, depth, ply, alpha, beta, score, bestMove);
return score;
}
// Init PV capturing tables
pvTable[ply][ply] = new Move();
pvLength[ply] = 0;
// Check if we are in check
bool isInCheck = boardState.IsSquareAttacked(boardState.ColorToMove, ownKingIndex);
// Get legal moves
Move[] children = boardState.GetAllMoves();
SortMoves(ply, children);
// Init number of legal moves and moves searched
int legalMoves = 0;
// Negamax loop
foreach (Move move in children)
{
// Break if finding illegal move
if (move == new Move()) break;
// Try if move is legal
if (boardState.MakeMove(move))
{
// Increase legal moves and node count
legalMoves++;
// Search and unmake move
score = -Negamax(depth - 1, ply + 1, -beta, -alpha);
boardState.UnmakeMove(move);
// Found a better move
if (score > alpha)
{
foundPV = true;
alpha = score;
// Write PV move to PV table for the given ply
pvTable[ply][ply] = move;
// Loop over the next ply
for (int j = 0; j < pvLength[ply + 1]; j++)
{
// Copy move from deeper ply into current ply's line
pvTable[ply][ply + 1 + j] = pvTable[ply + 1][ply + 1 + j];
}
// Adjust PV lenght
pvLength[ply] = 1 + pvLength[ply + 1];
// Fail hard beta cutoff (node fails high)
if (score >= beta)
{
// Store transposition tabel entry
Transpositions.WriteTT(boardState.ZobristKey, depth, ply, alpha, beta, score, bestMove); ;
return beta;
}
}
}
}
// If we don't have any legal moves in the position, check if it is mate or stalemate
if (legalMoves == 0)
{
// If checkmate, return the mate value, else stalemate value
if (isInCheck) return -SearchConstants.mateValue + ply;
else return 0;
}
// Write to transposition table wih score = alpha
Transpositions.WriteTT(boardState.ZobristKey, depth, ply, alpha, beta, alpha, bestMove);
// Node fails low
return alpha;
}
Code: Select all
public static bool ReadTT(ulong zobristHash, int depth, int ply, int alpha, int beta, out Move bestMove, out int score)
{
bestMove = default;
score = 0;
if (!Index(zobristHash, out int index))
return false;
ref HashEntry entry = ref hashTable[index];
bestMove = entry.BestMove;
if (entry.Depth < depth)
return false;
score = AdjustMateDistance(entry.Score, -ply);
//1.) score is exact and within window
if (entry.Flag == (byte)Flag.Exact)
return true;
//2.) score is below floor
if (entry.Flag == (byte)Flag.Alpha && score <= alpha)
return true; //failLow
//3.) score is above ceiling
if (entry.Flag == (byte)Flag.Beta && score >= beta)
return true; //failHigh
return false;
}
Code: Select all
public static void WriteTT(ulong zobristHash, int depth, int ply, int alpha, int beta, int score, Move bestMove)
{
ref HashEntry entry = ref hashTable[Index(zobristHash)];
// Don't overwrite a bestmove with 'default' unless it's a new position
if (entry.Key != zobristHash || bestMove != default)
entry.BestMove = bestMove;
entry.Key = zobristHash;
entry.Depth = depth < 0 ? default : (byte)depth;
entry.Age = 0;
if (score >= beta)
{
entry.Flag = (byte)Flag.Beta;
entry.Score = AdjustMateDistance(beta, ply);
}
else if (score <= alpha)
{
entry.Flag = (byte)Flag.Alpha;
entry.Score = AdjustMateDistance(alpha, ply);
}
else
{
entry.Flag = (byte)Flag.Exact;
entry.Score = AdjustMateDistance(score, ply);
}
}
Code: Select all
public static short AdjustMateDistance(int score, int ply)
{
if (Math.Abs(score) > SearchConstants.mateScore)
return (short)(score + Math.Sign(score) * ply);
else
return (short)score;
}
I only know the standard minimax/negamax framework and how things work there.