🎉 Celebrating 25 Years of GameDev.net! 🎉

Not many can claim 25 years on the Internet! Join us in celebrating this milestone. Learn more about our history, and thank you for being a part of our community!

Back to Artificial Intelligence

Transposition table

cryo75 · 2013-03-19T16:25:10

I'm adding TT to my negascout function and I'm using zobrist keys. I have a question with regard to storing the score in the table. When storing the best move as well, is this always the best move that is updated in the root function?

Artificial Intelligence Programming

Started by cryo75 March 17, 2013 01:32 PM

14 comments, last by cryo75 11 years, 3 months ago

alvaro

21,604

March 18, 2013 10:24 PM

Also, how can I test transposition tables to check that the code I added with regards to TT works fine?

One thing I've done is to perform each search with TT on and TT off and then check that the same result is being returned. The TT shouldn't affect the result (only in extremely rare instances) compared to a normal search - it should only affect the speed.

Unfortunately the result is affected much more often than "in extremely rare instances". Search instability is a well-known phenomenon in alpha-beta search, and transposition tables are responsible for quite a bit of it. In chess this is particularly easy to trigger in situations where draw by repetition or the 50-move rule are involved.

http://chessprogramming.wikispaces.com/Search+Instability

DarrylStein

653

March 19, 2013 02:04 AM

It appears that most of these are caused by interactions with other search enhancements. Surely for the purpose of proving that an implementation is correct, you would disable these enhancements initially?

alvaro

21,604

March 19, 2013 02:10 AM

A lot of it also has to do with graph-history interaction. It is possible that nine men morris doesn't have any such issues, and perhaps then this isn't much of an issue.

What happens when a position is repeated in nine men morris? Is the game a draw? If that's the case, there is the potential for trouble already.

cryo75

143

Author

March 19, 2013 05:52 AM

When adding quiescence search with TT, should the code be similar to this when depth == maxdepth??


        if (depth == maxDepth)
        {
        	val = quiesce(board, alpha, beta);
        	setTT(key, depth, val, TTEntry.BOUND_EXACT, null);
        	
        	return val;
        }

Is it also necessary to save the move struct in the TT? Can it be used for something??

alvaro

21,604

March 19, 2013 04:11 PM

I would store the position in the transposition table inside `quiesce'. Storing the move can be useful, because later on you are likely to visit this position again at a higher depth, and the move that turned out to be best in quiescence search is a reasonable candidate to try first.

Disclaimer: I have never obtained an improvement in my programs by using transposition tables in the quiescence search, so I don't use it.