Welcome, Guest. Please Login or Register.
Mar 29th, 2024, 9:18am

Home Home Help Help Search Search Members Members Login Login Register Register
Arimaa Forum « Breaking minimax determinism »


   Arimaa Forum
   Arimaa
   Bot Development
(Moderator: supersamu)
   Breaking minimax determinism
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Breaking minimax determinism  (Read 1892 times)
Marty
Forum Junior Member
**



Arimaa player #7639

   


Gender: male
Posts: 10
Breaking minimax determinism
« on: May 19th, 2014, 5:27am »
Quote Quote Modify Modify

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.
IP Logged

(\__/)
( O.o)
(> < )
This is Bunny, The Great Emperor. Copy Bunny into your signature to help him on his way to world domination.
n00bftw
Forum Full Member
***



Arimaa player #9394

   


Gender: male
Posts: 15
Re: Breaking minimax determinism
« Reply #1 on: May 20th, 2014, 12:48pm »
Quote Quote Modify Modify

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.
IP Logged
rbarreira
Forum Guru
*****



Arimaa player #1621

   


Gender: male
Posts: 605
Re: Breaking minimax determinism
« Reply #2 on: May 21st, 2014, 2:16pm »
Quote Quote Modify Modify

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.
« Last Edit: May 24th, 2014, 6:18am by rbarreira » IP Logged
petermck
Forum Junior Member
**



Arimaa player #9440

   
Email

Gender: male
Posts: 6
Re: Breaking minimax determinism
« Reply #3 on: May 22nd, 2014, 11:56pm »
Quote Quote Modify Modify

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.
IP Logged
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Arimaa Forum » Powered by YaBB 1 Gold - SP 1.3.1!
YaBB © 2000-2003. All Rights Reserved.