Author |
Topic: How to find all the "best" moves (Read 3864 times) |
|
Swynndla
Forum Guru
Arimaa player #1821
Posts: 235
|
 |
Re: How to find all the "best" moves
« Reply #15 on: Jul 16th, 2011, 5:38am » |
 Quote  Modify
|
Interesting and cunning not having to keep all the moves. I don't understand the mathematics though ... wouldn't that mean the first move would always be selected 50% of the time no matter how many equal moves were found?
|
|
 IP Logged |
|
|
|
lightvector
Forum Guru
Arimaa player #2543
Gender: 
Posts: 197
|
|
Re: How to find all the "best" moves
« Reply #16 on: Jul 16th, 2011, 9:56am » |
Quote Modify
|
Well, you do only have a 1/2 chance on the second equal move to replace the first move, but if you don't, you still have a 1/3 chance on the third equal move to replace it, and if you don't, you still have a 1/4 chance on the fourth equal move, etc.
I used to do like rbarreira did and simply shuffle the move list at the root prior to searching. Then, if you take the first best move, it's equally likely to be any of them, so you don't have to bother with any of this.
But I found that this didn't quite provide enough randomness, and definitely didn't after I added root-level move ordering. So I switched to adding a small random value to the evaluation function. The random values are generated as a function of the zobrist hash of the evaluated board position and a random seed that stays fixed for the duration of each search. This ensures that the evaluation doesn't change within a single search if a position happens to be revisited multiple times.
|
|
IP Logged |
|
|
|
Swynndla
Forum Guru
Arimaa player #1821
Posts: 235
|
|
Re: How to find all the "best" moves
« Reply #17 on: Jul 16th, 2011, 6:02pm » |
Quote Modify
|
Ahh yes I now understand how it works - thanks lightvector!
Wow your randomness in the eval function is a very interesting idea. It means the bot doesn't have to spend lots of time collecting equal moves. Also, in your case I get the impression that your eval function is so granular, and your root primary move ordering is so granular that there would not be any equal moves for Sharp to choose from if you didn't have these random additions.
Would this make the principal variation constantly change with incremental deepening (more than it otherwise would), and therefore make the number of searched positions increase?
|
|
IP Logged |
|
|
|
lightvector
Forum Guru
Arimaa player #2543
Gender:
Posts: 197
|
|
Re: How to find all the "best" moves
« Reply #18 on: Jul 16th, 2011, 6:34pm » |
Quote Modify
|
Ah, sorry if I was unclear. The random seed also stays the same during a series of iterative deepens. It only changes each new move in the actual game.
It would also probably be fine to use the same seed for a whole game and only change between games. I might change it to this if I ever implement pondering and/or transposition table sharing between moves. The idea is to keep the seed fixed so long as you are continuing to propagate evaluation data for that seed (such as returning values up the search tree or in the transposition table), so that the search is as stable as possible.
For eval granularity, sharp puts the value of an opening rabbit capture at 1000 ("millirabbits"). I don't know what frequency of equally-evaluated moves this implies, but my guess is that they would not be too rare, although not overly common either.
|
| « Last Edit: Jul 16th, 2011, 6:36pm by lightvector » |
IP Logged |
|
|
|
TheVinenator
Forum Full Member
Arimaa player #6821
Gender:
Posts: 15
|
|
Re: How to find all the "best" moves
« Reply #19 on: Oct 20th, 2011, 10:45am » |
Quote Modify
|
many moons ago i wrote a program (YINGYANG) to play Othello. it played pretty good considering it was on a DOS platform with no hash memory.
when doing analyst of games for annotation, it was useful to know the scores of the moves at the root. so the program had a setting that prevented cutoffs at the top level of a search. this of course took longer but it returned the score of every possible move till interrupted. this was useful for seeing if the 2nd or 3rd best move was "close" to the first.
the same logic can be applied in the middle of the game tree to introduce randomness. do a search on the first 2 moves and then compare the results. if they are "close" enough in value, randomly select one of them and continue the search. too much of this will greatly slow down the search so you might not want to do it deep in the tree.
getting beat the same way over and over isn't usually an issue with most Othello/Chess programs since after a game the opening book tree is updated and a suitable variation move is somewhere upstream.
opening game history could be used with Arimaa programs precisely for that purpose. if someone finds a way to win, they can set up their pieces exactly the same way the next time and win again easily. Fritz Juhnke gives an example of that in his "Beginning Arimaa" book. keeping track of that history would prevent the situation from being repeated...if for nothing else.
Prior to a tournament I would download all the games from the Othello game server played by the other programs. these were fed into my opening book tree. YINGYANG was able to beat one program by playing every move out of its book because the opponent had not updated their own games they had recently played.
|
|
IP Logged |
|
|
|
rbarreira
Forum Guru
Arimaa player #1621
Gender:
Posts: 605
|
|
Re: How to find all the "best" moves
« Reply #20 on: Oct 20th, 2011, 10:51am » |
Quote Modify
|
Lack of randomness is not much of an issue these days with multi-threaded (and therefore non-deterministic) bots.
Bomb was a single-threaded bot without much explicit randomness, which is why it was possible to get it to repeat games (even then it could deviate due to timing variations).
But even in a single-threaded bot there are ways to introduce randomness without having to search for moves which are nearly the best but not quite the best. Shuffling the list of root moves is what I did to add even more randomness.
|
|
IP Logged |
|
|
|
|
Home
Help
Search
Members
Login
Register
Reply
Notify of replies
Send Topic
Print