ok, i think i found a bug that might have caused the strange behavior. its that when value returned equals alpha i used to store it as exact value, not an upperbound.
something like:
if ( BestEval < Alpha ) then store(Depth, Node, hfUpperBound);
else store(Depth, Node, hfExactScore);
which should be:
if ( BestEval <= Alpha ) then store(Depth, Node, hfUpperBound);
else store(Depth, Node, hfExactScore);
i am gonna start benchmarking all-over again.
[Edited by - zaidgs on August 24, 2004 7:48:21 AM]
Advices for implementing transposition tables needed
Yep, you've got to be very careful. Luckily for you that was an easy bug to fix. :)
You can't really test a full hash-table implementation on just one position, since problems typically occure one the table starts gettting full. Try mate in 8 or mate in 5 problems to stress the program.
Make sure you test out the check-mate, (for and against), stale-mate (for and against), passant and castling (on both sides).
Will
You can't really test a full hash-table implementation on just one position, since problems typically occure one the table starts gettting full. Try mate in 8 or mate in 5 problems to stress the program.
Make sure you test out the check-mate, (for and against), stale-mate (for and against), passant and castling (on both sides).
Will
Author
Quote:Original post by zaidgs
ok, i think i found a bug that might have caused the strange behavior. its that when value returned equals alpha i used to store it as exact value, not an upperbound.
something like:
if ( BestEval < Alpha ) then store(Depth, Node, hfUpperBound);
else store(Depth, Node, hfExactScore);
which should be:
if ( BestEval <= Alpha ) then store(Depth, Node, hfUpperBound);
else store(Depth, Node, hfExactScore);
i am gonna start benchmarking all-over again.
aparently this bug was a false alarm !!! actually code was set up the right way, and i created a bug when i modified it !! it happens ! it took me sometime to track down the bug i created, (well, i corrected it the same day but was late to post this)
so the strange behavior i reported still holds, it performs better in testing epd positions than in actual games ....
so can sm1 tell me the expected boost when using a 2 million entry transposition table ... i think there still must be something wrong because i didnt get a high boost as i thought i should !!!
Author
some engines clear the transposition tables after each move .... is that a good practice ?! what things i should consider to decide on that ?! .....
Quote:Original post by zaidgs
some engines clear the transposition tables after each move .... is that a good practice ?! what things i should consider to decide on that ?! .....
You should be getting major speed boosts. At least 25% faster. I made graphs showing the speed improvements each of these features made to my program. I should really post them.
I don't clear the hash table after every move. I keep track of a move number and a depth-- if move n is a deeper search than the hash, i overwrite the hash. If the move number is at least 6 moves ahead of the hash, I overwrite the hash.
Will
Author
i know that hash tables should give a high boost, but i dunno whats going wrong but its not. according to my benchmarking its the ELO increased by only about 50 points !!! my engine's rating on chessanytime.com was oscilating between 2050 - 2080,
now it is oscilating between 2100 - 2115.
also on a 360 positions test (Chess IQ Test), without TT it solves 106, but with TT it solves 117, by giving it 10 seconds per position. i should dig deeper to see why there is no obvious improovement.
now it is oscilating between 2100 - 2115.
also on a 360 positions test (Chess IQ Test), without TT it solves 106, but with TT it solves 117, by giving it 10 seconds per position. i should dig deeper to see why there is no obvious improovement.
I recall seeing some computer chess tests that involved king-pawn end games. The result was mate in 31.
If you're transposition tables are working you should be able to solve in a few seconds. Even if you can't solve it in 10 seconds, you'll know the hash tables are working if it goes from depth 2 to 25 in about 2 seconds. :)
Sorry, but I no longer have the link..
Will
If you're transposition tables are working you should be able to solve in a few seconds. Even if you can't solve it in 10 seconds, you'll know the hash tables are working if it goes from depth 2 to 25 in about 2 seconds. :)
Sorry, but I no longer have the link..
Will
Author
i think you mean something like this my engine solved it in 3 seconds at depth 25.
to ensure the integrity of my data saving and retrieval i verified data like this:
so i would assume back again that data storage and retrieval is bugless.
i also thought of a different possible reason for the ineffiency of transposition tables in my engine: collision rate higher than normal, but i think its normal according to a test i did.
the test was that i calculated the collision rate when the TT was 30% full. in such a case it is easy to conclude that collision rate should be also 30% and according to the statistics the collision rate was only 23% indicating that my indexing is high randomized.
also around 27% of visited positions had an entry found for them found in the TT.
PS:
true. true. true!
[Edited by - zaidgs on August 27, 2004 1:57:35 PM]
to ensure the integrity of my data saving and retrieval i verified data like this:
if ( CurrentBoardInHash() ){ if ( TTEntry.Type == ExactScore ){ assert( alphabeta(CurrentBoard, TTEntry.Depth, alpha=-infinity, beta=+infinity) == TTEntry.Score ) //hashing disabled } if ( TTEntry.Type == MinScore ){ assert( alphabeta(CurrentBoard, TTEntry.Depth, alpha=-infinity, beta=+infinity) >= TTEntry.Score ) //hashing disabled } if ( TTEntry.Type == MaxScore ){ assert( alphabeta(CurrentBoard, TTEntry.Depth, alpha=-infinity, beta=+infinity) <= TTEntry.Score ) //hashing disabled }}so i would assume back again that data storage and retrieval is bugless.
i also thought of a different possible reason for the ineffiency of transposition tables in my engine: collision rate higher than normal, but i think its normal according to a test i did.
the test was that i calculated the collision rate when the TT was 30% full. in such a case it is easy to conclude that collision rate should be also 30% and according to the statistics the collision rate was only 23% indicating that my indexing is high randomized.
also around 27% of visited positions had an entry found for them found in the TT.
PS:
Quote:Original post by RPGeezus
I made graphs showing the speed improvements each of these features made to my program. I should really post them.
true. true. true!
[Edited by - zaidgs on August 27, 2004 1:57:35 PM]
RE: Lasker Position: That is the exact board setup I was thinking of.
3 seconds is very good. I think it's fair to say that, generally, your code is working properly.
How are you calculating the hash keys for a board? Just a shot in the dark, but maybe you're not being effecient, and the time it takes to generate the keys is robbing you of the speed boost.
Will
3 seconds is very good. I think it's fair to say that, generally, your code is working properly.
How are you calculating the hash keys for a board? Just a shot in the dark, but maybe you're not being effecient, and the time it takes to generate the keys is robbing you of the speed boost.
Will
Author
I just want someone to verify that my enhanced transposition cut off code is actually correct.
for each sucessor node that is found in hash tables{ if ( hash.depth >= depth-1 && -hash.score >= beta && hash.type != hfFailHigh ) return -hash.score;}This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement