Author |
Topic: Breaking minimax determinism (Read 1939 times) |
|
Marty
Forum Junior Member
Arimaa player #7639
Gender: 
Posts: 10
|
 |
Breaking minimax determinism
« on: May 19th, 2014, 5:27am » |
 Quote  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:
Posts: 15
|
|
Re: Breaking minimax determinism
« Reply #1 on: May 20th, 2014, 12:48pm » |
Quote 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:
Posts: 605
|
|
Re: Breaking minimax determinism
« Reply #2 on: May 21st, 2014, 2:16pm » |
Quote 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
Gender:
Posts: 6
|
|
Re: Breaking minimax determinism
« Reply #3 on: May 22nd, 2014, 11:56pm » |
Quote 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 |
|
|
|
|
Home
Help
Search
Members
Login
Register
Reply
Notify of replies
Send Topic
Print