Author |
Topic: Transition Tables (Read 1346 times) |
|
Swynndla
Forum Guru
Arimaa player #1821
Posts: 235
|
 |
Transition Tables
« on: Jul 16th, 2011, 5:52am » |
 Quote  Modify
|
I'm wading neck-deep though learning about Transition Tables, and I'd describe them as "cruel". I have my fair share of silly bugs in my programming history, but with TT's, TT's will still give fairly decent results even with bugs. That means they wont be working efficiently, but also that it's difficult to notice there exists a subtle bug (and even more difficult to find it). I'm make progress though!
One thing about TT's that made me LOL is that sometimes instead of doing a move that will win in one move, another move is played instead (still leaving the forced win in one). This is because the TT will report that both moves are of the same winning value. Usually iterative deepening can sort out the quickest win (ie search of depth 1 will find the win in 1 move) but with TT's that changes. Has anyone got suggestions to work around that?
|
|
 IP Logged |
|
|
|
lightvector
Forum Guru
Arimaa player #2543
Gender: 
Posts: 197
|
|
Re: Transition Tables
« Reply #1 on: Jul 16th, 2011, 9:14am » |
Quote Modify
|
For sharp, whenever I encounter a win or loss in the search, I return WIN_SCORE - X or LOSE_SCORE + X, where X is the depth in steps relative to the root. So for instance goal in 3, with the goaling move taking 3 steps would be WIN_SCORE - 19. (4 + 4 + 4 + 4 + 3).
In the transposition table, because entries can be reused at different depths, I check if the score is a win/loss score, and then convert it to be relative to the entry's board position, rather than relative to the root. So for instance, if storing an entry for a position that was 8 steps deep in the tree, I would take the WIN_SCORE - 19 and convert it to WIN_SCORE - 11. When I read an entry back, if it's a win/loss score, I convert it again to be relative to the current depth This could be different than the depth at which the entry was initially stored, so this makes it important that the table contains scores that indicate "win in X steps from this position" rather than "win in X steps from the root position".
For detecting certain transposition table bugs like this, I find that jdb's endgame puzzles are pretty nice. There's even one that has a winning line that uses 3-fold repetition (although it's not the only way to win).
|
| « Last Edit: Jul 16th, 2011, 9:17am by lightvector » |
IP Logged |
|
|
|
Swynndla
Forum Guru
Arimaa player #1821
Posts: 235
|
|
Re: Transition Tables
« Reply #2 on: Jul 16th, 2011, 5:27pm » |
Quote Modify
|
Thank you lightvector, you've been most helpful once again!  That method of yours is a nice one. I'm also glad that the problem I described seems to be normal with TT's (and not yet another bug of mine).
|
|
IP Logged |
|
|
|
lightvector
Forum Guru
Arimaa player #2543
Gender:
Posts: 197
|
|
Re: Transition Tables
« Reply #3 on: Jul 16th, 2011, 6:51pm » |
Quote Modify
|
Hehe, I agree, transposition tables are a mess. I've had all sorts of weird bugs with them. Most of them probably could have been prevented with better foresight (ex: quiescence search is allowed to make special moves like "pass" and multi-step combos, and stores these as the bestmove in the tt, then later the main search encounters these positions again...). But I have found at least once case where I got an anomalous search result due to graph-history-interaction, and I don't remember finding any nice way to fix it.
Good luck on your bot! 
|
|
IP Logged |
|
|
|
|
Home
Help
Search
Members
Login
Register
Reply
Notify of replies
Send Topic
Print