Arimaa Forum - Print Page


    
      
        Arimaa Forum
        (http://arimaa.com/arimaa/forum/cgi/YaBB.cgi)
      

        Arimaa >> Bot Development >> Transition Tables
        
(Message started by: Swynndla on Jul 16^th, 2011, 5:52am)

Title: Transition Tables
Post by Swynndla on Jul 16^th, 2011, 5:52am

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?

Title: Re: Transition Tables
Post by lightvector on Jul 16^th, 2011, 9:14am

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).

Title: Re: Transition Tables
Post by Swynndla on Jul 16^th, 2011, 5:27pm

Thank you lightvector, you've been most helpful once again! :D 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).

Title: Re: Transition Tables
Post by lightvector on Jul 16^th, 2011, 6:51pm

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! :)