Arimaa Forum - Print Page


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

        Arimaa >> Bot Development >> Breaking minimax determinism
        
(Message started by: Marty on May 19^th, 2014, 5:27am)

Title: Breaking minimax determinism
Post by Marty on May 19^th, 2014, 5:27am

i am building a simple bot (not Arimaa). i've got minimax + alpha-beta, i am working on transposition tables etc., but there is one issue i have - a minimax based bot is inherently deterministic and it will move always the same given the game state. this is bad both for playing with humans and for a possible training by self-playing.

how is this commonly solved?

i can imagine using an opening database to choose a random move from, but i don't have one. i could use an entirely random move from time to time, but that would be likely a blunder. i could add some random noise to the evaluation function. i can't very well look for two best moves and choose between them, because alpha-beta cuts off everything suboptimal. i thought of using alpha-beta with two alphas and two betas and cut off only with the worse values to get me two good moves, but i don't know if it is a good idea.

Title: Re: Breaking minimax determinism
Post by n00bftw on May 20^th, 2014, 12:48pm

I believe it is done a couple different ways, but the essential part is to add randomness in somewhere -- either in the evaluation function or in the search function. The evaluation function is (relatively) easy to randomize; I don't recall off the top of my head how search is randomized, but multi-threading adds some inherent randomness to the search. If you look around the forum some more (including in general Arimaa discussion) I think you'll find a couple of threads that mention it.

Title: Re: Breaking minimax determinism
Post by rbarreira on May 21^st, 2014, 2:16pm

One of the easiest (and least intrusive) things you can do is to randomly shuffle the list of root moves before starting each search. If you don't have a root search function you can have a flag passed as a parameter of your search function to tell whether you're on the root node, and shuffle the list of steps when the flag is set to true. Of course you only want to do this once, not in each iteration of the iterative deepening (you should have a good heuristic for move ordering instead).

As soon as you add multi-threading that will also make your bot less deterministic.

Slight variations in timing / CPU speed will also provide a little bit of non-determinism.

For my bot, these three things together are enough to make it non-deterministic to a satisfactory degree.

Title: Re: Breaking minimax determinism
Post by petermck on May 22^nd, 2014, 11:56pm

One approach I've used in the past is to add a small random value to thinking time.

Another one I've heard of is adding some random noise to the piece-square tables (or any eval term for that matter) when initializing the program before a game.