Transposition Table , and search result ?
Moderators: hgm, Rebel, chrisw
-
MahmoudUthman
- Posts: 234
- Joined: Sat Jan 17, 2015 11:54 pm
Transposition Table , and search result ?
how much does(should) a transposition table affect the search result, before implementing the TT ,the search was perfectly stable ,after implementing it (With fail hard normal alpha beta),the program play's different(&bad) moves from the version without TT at the same depth, could this be a TT error, even though the ttentry is checked using the full (64Bit) zobrist key, and the move it contains is checked against all the legal moves' of the position being searched ?
-
Henk
- Posts: 7218
- Joined: Mon May 27, 2013 10:31 am
Re: Transposition Table , and search result ?
Did you already try using alpha in the research step of PVS ?
-
MahmoudUthman
- Posts: 234
- Joined: Sat Jan 17, 2015 11:54 pm
Re: Transposition Table , and search result ?
I'm not using PVS yet I'm just using normal AlphaBeta:
Code: Select all
int alphaBeta( int alpha, int beta, int depthleft ) {
if( depthleft == 0 ) return quiesce( alpha, beta );
for ( all moves) {
score = -alphaBeta( -beta, -alpha, depthleft - 1 );
if( score >= beta )
return beta; // fail hard beta-cutoff
if( score > alpha )
alpha = score; // alpha acts like max in MiniMax
}
return alpha;
}-
Henk
- Posts: 7218
- Joined: Mon May 27, 2013 10:31 am
Re: Transposition Table , and search result ?
Just disable all pruning, reductions, quiescence search.
Or go back to most simple search.
If it is still giving errors then it must be Transposition table.
Or go back to most simple search.
If it is still giving errors then it must be Transposition table.
-
bob
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: Transposition Table , and search result ?
Ttable should NOT introduce errors if it is working correctly. If it is broken, of course, all bets are off.MahmoudUthman wrote:how much does(should) a transposition table affect the search result, before implementing the TT ,the search was perfectly stable ,after implementing it (With fail hard normal alpha beta),the program play's different(&bad) moves from the version without TT at the same depth, could this be a TT error, even though the ttentry is checked using the full (64Bit) zobrist key, and the move it contains is checked against all the legal moves' of the position being searched ?
Best way to debug is to find the shallowest search that will produce something that looks wrong, and dump the tree with and without ttable and find out what is going wrong. Sometimes a pencil and paper are the only way to do this. I have created so many tree dumps over the years I could not begin to count them.
-
MahmoudUthman
- Posts: 234
- Joined: Sat Jan 17, 2015 11:54 pm
Re: Transposition Table , and search result ?
Henk van den Belt, Robert Hyatt , thanks.
the TT was indeed broken, after fixing it the search is close to normal , but the TT version is always behind the non TT version when playing against other engines , I have identified the code responsible for this but I don't understand why is this happening (if I use a score from the hash table for the current position at greater search depth shouldn't that enhance the engine not the opposite) ?
the TT was indeed broken, after fixing it the search is close to normal , but the TT version is always behind the non TT version when playing against other engines , I have identified the code responsible for this but I don't understand why is this happening (if I use a score from the hash table for the current position at greater search depth shouldn't that enhance the engine not the opposite) ?
Code: Select all
static int AlphaBetaT(int alpha, int beta, int depthleft)
{
if (depthleft == 0) return qSearchFree(alpha, beta);
for (int i = 0, J = HalfMoveCounter - 2; i < HalfMoveClock; i += 2)
{
if (Positionkey == GameHistory[J])
return 0;
J -= 2;
}
NodesSearched++;
ExtMove LocalBestMove;
TTEntry ttEntry;
bool FoundTTEntry = TTLookUp(ttEntry);
LocalBestMove.M = ttEntry.BestMove.M & 0x3ffffULL;//Masking Relevant bits(18)
ExtMove Available[218];
U64 InCheck;
U32 CapturesCount = 0, QuietCount = 0;
//Generat Ordered Moves MVV/LVA
if (STM) Move::GenLegalMoves<W, 218>(Available, InCheck, CapturesCount, QuietCount);
else Move::GenLegalMoves<B, 218>(Available, InCheck, CapturesCount, QuietCount);
//Perform Complete Legality Check
bool tvalid =FoundTTEntry&& Move::IsValid(LocalBestMove,Available);
//This Line is the cause if i replace ">=" with "==" in : (ttEntry.BestMove.Depth >= depthleft)
//the Engine plays as good as the non hashed version "Fixed depth games"
if (tvalid && (ttEntry.BestMove.Depth >= depthleft))
{
if (ttEntry.BestMove.boundType == BoundType::Exact) return ttEntry.Score;
if ((ttEntry.BestMove.boundType == BoundType::Upper) & (ttEntry.Score >= beta)) return beta;
if ((ttEntry.BestMove.boundType == BoundType::Lower) & (ttEntry.Score <= alpha)) return alpha;
}
BoundType BT=BoundType::::Lower;
if (tvalid)
{
Move::MakeMoveSearch(LocalBestMove);
auto sScore = -AlphaBetaT(-beta, -alpha, depthleft - 1);
Move::UnMakeSearch(LocalBestMove);
if (sScore >= beta)
{
if ((TypeBoard[LocalBestMove.To] == 0) && (LocalBestMove.M != Killers[ply][0].M))//NonCapture:UpdateKillers
{
Killers[ply][1] = Killers[ply][0]; Killers[ply][0] = LocalBestMove;
}
TTAdd(LocalBestMove, depthleft, BoundType::Upper, beta);
return beta;
}
if (sScore > alpha)
{
alpha = sScore;
BT=BoundType::Exact;
}
}
ExtMove ttMove = LocalBestMove;
for (unsigned int i = 0; i < CapturesCount; i++)
{
if (Available[i].M == ttMove.M) continue;//Skip TTMove
Move::MakeMoveSearch(Available[i]);
auto score = -AlphaBetaT(-beta, -alpha, depthleft - 1);
Move::UnMakeSearch(Available[i]);
if (score >= beta)
{
TTAdd(Available[i], depthleft, BoundType::Upper, beta);//Beta instead
return beta;
}
if (score > alpha)
{
alpha = score;
BT=BoundType::Exact;
}
}
//Similar Loop For Quiets
//Mate/Stale
if ((CapturesCount + QuietCount) == 0)
{
auto Score=InCheck?--INT_MAX + ply:0;
TTAdd(ExtMove(), depthleft, BoundType::Exact, Score);
return Score;
}
TTAdd(LocalBestMove, depthleft, BT, alpha);
return alpha;
}-
Sven
- Posts: 4052
- Joined: Thu May 15, 2008 9:57 pm
- Location: Berlin, Germany
- Full name: Sven Schüle
Re: Transposition Table , and search result ?
I think you are mixing Upper and Lower here. "Upper" means "upper bound", so the actual value is <= the TT score. The opposite for "Lower". You can only return beta if you are sure that the TT score is >= beta, which requires the bound type to be "lower bound".MahmoudUthman wrote:Henk van den Belt, Robert Hyatt , thanks.
the TT was indeed broken, after fixing it the search is close to normal , but the TT version is always behind the non TT version when playing against other engines , I have identified the code responsible for this but I don't understand why is this happening (if I use a score from the hash table for the current position at greater search depth shouldn't that enhance the engine not the opposite) ?
Code: Select all
if ((ttEntry.BestMove.boundType == BoundType::Upper) & (ttEntry.Score >= beta)) return beta; if ((ttEntry.BestMove.boundType == BoundType::Lower) & (ttEntry.Score <= alpha)) return alpha;
-
op12no2
- Posts: 490
- Joined: Tue Feb 04, 2014 12:25 pm
- Full name: Colin Jenkins
Re: Transposition Table , and search result ?
Should the &s not be &&s in the lines Sven quoted...?
You don't seem to fiddle with mate TT values, so you could also try disabling the TT save for mate/stalemate for now; it may be causing some weirdness.
You don't seem to fiddle with mate TT values, so you could also try disabling the TT save for mate/stalemate for now; it may be causing some weirdness.
-
MahmoudUthman
- Posts: 234
- Joined: Sat Jan 17, 2015 11:54 pm
Re: Transposition Table , and search result ?
Sven Schüle wrote:
http://web.archive.org/web/200711120942 ... ashing.htm
with :
BoundType::Exact--->hashfEXACT
BoundType::Lower--->hashfALPHA
BoundType::Upper--->hashfBETA
Colin Jenkins wrote:
both sides are Boolean with no side effects so there shouldn't be any difference.
*seems like disabling the TT for Mate Scores changes the result ,I will try to identify the problem and test.[/quote]
I don't use BoundType enumeration any where/way else so even if it was wrongly named it shouldn't affect the result since I'm using "Bound::Upper" to refer to beta cutoff's everywhere , and Bound::lower to refer to alpha's, for example my routine is identical to thisI think you are mixing Upper and Lower here. "Upper" means "upper bound", so the actual value is <= the TT score. The opposite for "Lower". You can only return beta if you are sure that the TT score is >= beta, which requires the bound type to be "lower bound".
http://web.archive.org/web/200711120942 ... ashing.htm
with :
BoundType::Exact--->hashfEXACT
BoundType::Lower--->hashfALPHA
BoundType::Upper--->hashfBETA
Colin Jenkins wrote:
Code: Select all
Should the &s not be &&s in the lines Sven quoted...?
You don't seem to fiddle with mate TT values, so you could also try disabling the TT save for mate/stalemate for now; it may be causing some weirdness.
*seems like disabling the TT for Mate Scores changes the result ,I will try to identify the problem and test.[/quote]
-
MahmoudUthman
- Posts: 234
- Joined: Sat Jan 17, 2015 11:54 pm
Re: Transposition Table , and search result ?
Sven Schüle,Colin Jenkins ,Thanks
The error was caused by implicit conversion(C++) ,the max ply def was (unsigned int) which caused the matedinmaxply def to be of type (unsigned int) resulting in the code adjusting matescores for the TT to modify non mate scores, anyway how many games do I need to put the engine through to measure changes to it's strength accurately :for example ,this is the result of 700 games (8 engines ,round robin , 25 rounds):
and the result of the matching:
the non hashed version is ChessEngineX , the hashed version is ChessEngine,the hashed version performed better against most engines but it's performance dropped significantly playing against Chess_Cpu and SOS ,is this normal or does this indicate a bug (the engines are restarted after every game so there is no hash table entries from previous games searches ) ?
The error was caused by implicit conversion(C++) ,the max ply def was (unsigned int) which caused the matedinmaxply def to be of type (unsigned int) resulting in the code adjusting matescores for the TT to modify non mate scores, anyway how many games do I need to put the engine through to measure changes to it's strength accurately :for example ,this is the result of 700 games (8 engines ,round robin , 25 rounds):
Code: Select all
3/28/2015 7:15:40 AM :
Program Elo + - Games Score Av.Op. Draws
1 Ruffian 1.0.5 : 2736 90 82 175 90.9 % 2337 3.4 %
2 SOS 5.1 for Arena : 2574 61 59 175 77.4 % 2360 5.1 %
3 Spike 1.4 : 2380 50 50 175 48.9 % 2388 8.6 %
4 ChessEngine : 2338 51 51 175 42.0 % 2394 5.1 %
5 AnMon 5.75 : 2336 49 50 175 41.7 % 2394 10.3 %
6 ChessEngineX : 2325 50 51 175 40.0 % 2396 8.0 %
7 Chess_cpu : 2266 52 54 175 31.1 % 2404 8.6 %
8 Hermann 2.8 64 bit : 2243 54 55 175 28.0 % 2408 9.1 %
Code: Select all
-----------------AnMon 5.75-----------------
AnMon 5.75 - Chess_cpu : 14.5/25 12-8-5 (==10=1=01011110110001=011) 58% +56
AnMon 5.75 - ChessEngine : 11.0/25 11-14-0 (1110100010000000011111001) 44% -42
AnMon 5.75 - ChessEngineX : 14.0/25 13-10-2 (110101011111010=1=0100010) 56% +42
AnMon 5.75 - Hermann 2.8 64 bit : 15.0/25 12-7-6 (00=0010111=111==10=1110=1) 60% +70
AnMon 5.75 - Ruffian 1.0.5 : 1.5/25 1-23-1 (000000000001000000000000=) 6% -478
AnMon 5.75 - SOS 5.1 for Arena : 5.0/25 4-19-2 (000000000011000000==10010) 20% -241
AnMon 5.75 - Spike 1.4 : 12.0/25 11-12-2 (=010111000=00101010011110) 48% -14
-----------------Chess_cpu-----------------
Chess_cpu - AnMon 5.75 : 10.5/25 8-12-5 (==01=0=10100001001110=100) 42% -56
Chess_cpu - ChessEngine : 10.5/25 10-14-1 (01010100=1010101010110000) 42% -56
Chess_cpu - ChessEngineX : 8.0/25 6-15-4 (101=100=00=000=0001010001) 32% -131
Chess_cpu - Hermann 2.8 64 bit : 17.5/25 17-7-1 (00000011=1111111110111111) 70% +147
Chess_cpu - Ruffian 1.0.5 : 2.0/25 1-22-2 (0000000010000000=000000=0) 8% -424
Chess_cpu - SOS 5.1 for Arena : 1.5/25 1-23-1 (000000001000000=000000000) 6% -478
Chess_cpu - Spike 1.4 : 4.5/25 4-20-1 (0100=00000000100000000011) 18% -263
-----------------ChessEngine-----------------
ChessEngine - AnMon 5.75 : 14.0/25 14-11-0 (0001011101111111100000110) 56% +42
ChessEngine - Chess_cpu : 14.5/25 14-10-1 (10101011=0101010101001111) 58% +56
ChessEngine - ChessEngineX : 13.0/25 13-12-0 (1010101010101010101010101) 52% +14
ChessEngine - Hermann 2.8 64 bit : 16.5/25 15-7-3 (0=00101011101=11=11111101) 66% +115
ChessEngine - Ruffian 1.0.5 : 2.0/25 2-23-0 (0000000000000000001000100) 8% -424
ChessEngine - SOS 5.1 for Arena : 1.5/25 1-23-1 (00000000000=0000000100000) 6% -478
ChessEngine - Spike 1.4 : 12.0/25 10-11-4 (0101=10100=10101010101==0) 48% -14
-----------------ChessEngineX-----------------
ChessEngineX - AnMon 5.75 : 11.0/25 10-13-2 (001010100000101=0=1011101) 44% -42
ChessEngineX - Chess_cpu : 17.0/25 15-6-4 (010=011=11=111=1110101110) 68% +131
ChessEngineX - ChessEngine : 12.0/25 12-13-0 (0101010101010101010101010) 48% -14
ChessEngineX - Hermann 2.8 64 bit : 12.0/25 11-12-2 (0000=000110011101=1010111) 48% -14
ChessEngineX - Ruffian 1.0.5 : 3.0/25 2-21-2 (0100000001000000000=000=0) 12% -346
ChessEngineX - SOS 5.1 for Arena : 8.0/25 8-17-0 (0100000101010001001100010) 32% -131
ChessEngineX - Spike 1.4 : 7.0/25 5-16-4 (0000100000100=000=101=0=1) 28% -164
-----------------Hermann 2.8 64 bit-----------------
Hermann 2.8 64 bit - AnMon 5.75 : 10.0/25 7-12-6 (11=1101000=000==01=0001=0) 40% -70
Hermann 2.8 64 bit - Chess_cpu : 7.5/25 7-17-1 (11111100=0000000001000000) 30% -147
Hermann 2.8 64 bit - ChessEngine : 8.5/25 7-15-3 (1=11010100010=00=00000010) 34% -115
Hermann 2.8 64 bit - ChessEngineX : 13.0/25 12-11-2 (1111=111001100010=0101000) 52% +14
Hermann 2.8 64 bit - Ruffian 1.0.5 : 0.0/25 0-25-0 (0000000000000000000000000) 0% -1200
Hermann 2.8 64 bit - SOS 5.1 for Arena : 2.0/25 1-22-2 (00100=000=000000000000000) 8% -424
Hermann 2.8 64 bit - Spike 1.4 : 8.0/25 7-16-2 (0111110=001000=0000000010) 32% -131
-----------------Ruffian 1.0.5-----------------
Ruffian 1.0.5 - AnMon 5.75 : 23.5/25 23-1-1 (111111111110111111111111=) 94% +478
Ruffian 1.0.5 - Chess_cpu : 23.0/25 22-1-2 (1111111101111111=111111=1) 92% +424
Ruffian 1.0.5 - ChessEngine : 23.0/25 23-2-0 (1111111111111111110111011) 92% +424
Ruffian 1.0.5 - ChessEngineX : 22.0/25 21-2-2 (1011111110111111111=111=1) 88% +346
Ruffian 1.0.5 - Hermann 2.8 64 bit : 25.0/25 25-0-0 (1111111111111111111111111) 100% +1200
Ruffian 1.0.5 - SOS 5.1 for Arena : 18.5/25 18-6-1 (10011101=1111111100111101) 74% +182
Ruffian 1.0.5 - Spike 1.4 : 24.0/25 24-1-0 (1110111111111111111111111) 96% +552
-----------------SOS 5.1 for Arena-----------------
SOS 5.1 for Arena - AnMon 5.75 : 20.0/25 19-4-2 (111111111100111111==01101) 80% +241
SOS 5.1 for Arena - Chess_cpu : 23.5/25 23-1-1 (111111110111111=111111111) 94% +478
SOS 5.1 for Arena - ChessEngine : 23.5/25 23-1-1 (11111111111=1111111011111) 94% +478
SOS 5.1 for Arena - ChessEngineX : 17.0/25 17-8-0 (1011111010101110110011101) 68% +131
SOS 5.1 for Arena - Hermann 2.8 64 bit : 23.0/25 22-1-2 (11011=111=111111111111111) 92% +424
SOS 5.1 for Arena - Ruffian 1.0.5 : 6.5/25 6-18-1 (01100010=0000000011000010) 26% -182
SOS 5.1 for Arena - Spike 1.4 : 22.0/25 21-2-2 (10111111111111110=11=1111) 88% +346
-----------------Spike 1.4-----------------
Spike 1.4 - AnMon 5.75 : 13.0/25 12-11-2 (=101000111=11010101100001) 52% +14
Spike 1.4 - Chess_cpu : 20.5/25 20-4-1 (1011=11111111011111111100) 82% +263
Spike 1.4 - ChessEngine : 13.0/25 11-10-4 (1010=01011=01010101010==1) 52% +14
Spike 1.4 - ChessEngineX : 18.0/25 16-5-4 (1111011111011=111=010=1=0) 72% +164
Spike 1.4 - Hermann 2.8 64 bit : 17.0/25 16-7-2 (1000001=110111=1111111101) 68% +131
Spike 1.4 - Ruffian 1.0.5 : 1.0/25 1-24-0 (0001000000000000000000000) 4% -552
Spike 1.4 - SOS 5.1 for Arena : 3.0/25 2-21-2 (01000000000000001=00=0000) 12% -346