Author |
Topic: How to find all the "best" moves (Read 3981 times) |
|
Swynndla
Forum Guru
Arimaa player #1821
Posts: 235
|
 |
How to find all the "best" moves
« on: Jul 7th, 2011, 10:50pm » |
 Quote  Modify
|
Let me talk about moves instead of steps, just so I can explain it easier...
If a position is given to the alpha-beta search function, then it will return the best evaluation it can find, but it will not tell you which move gave this best eval. Furthermore, alpha-beta seems to be designed to search for the first best move it can find, so even if you modify the function to track the move that had the best eval, you'd only end up with one move. If you want all the moves (if there happens to be more than one) that have that best eval, so you can then randomly choose which move to do, then the above wouldn't work.
One way to do it is to feed each of the primary moves from the root position into the alpha-beta search function and track the scores returned for each one, then if there are are more than one best move, it'd be easy to collect them. The disadvantage of this is that alpha wont be shared across the primary moves, and so the alpha-beta search will have less cut-offs and so will be slower (or wont be able to search as deep).
I thought that I might be able to read off all the moves with the best eval from the transposition table, but from playing around with it, it doesn't seem to get all of the best moves (and this may be because of cut off's not searching the line fully and not returning the correct score as that is how alpha-beta is designed to work ... or it may because of a bug, but as I say, I think it's how alpha-beta is designed to work?).
So how should I collect all the best moves, or should I not bother trying to?? Any tips/advice for someone new to all this would be welcome. 
|
|
 IP Logged |
|
|
|
Swynndla
Forum Guru
Arimaa player #1821
Posts: 235
|
|
Re: How to find all the "best" moves
« Reply #1 on: Jul 8th, 2011, 12:29am » |
Quote Modify
|
on Jul 7th, 2011, 10:50pm, Swynndla wrote:| One way to do it is to feed each of the primary moves from the root position into the alpha-beta search function and track the scores returned for each one, then if there are are more than one best move, it'd be easy to collect them. The disadvantage of this is that alpha wont be shared across the primary moves, and so the alpha-beta search will have less cut-offs and so will be slower (or wont be able to search as deep). |
|
Oh ... typing this out helped to clarify things in my head, and I now realize all I have to do is share alpha across the primary moves! Seems obvious now, but then again I am pretty dumb. 
I'd still be interested to know if others collect all the "best" moves and chose one at random. I think lightvector said he put a slight randomness into his eval function, so I'm guessing he'd only collect the first best move he finds?
|
|
IP Logged |
|
|
|
Swynndla
Forum Guru
Arimaa player #1821
Posts: 235
|
|
Re: How to find all the "best" moves
« Reply #2 on: Jul 8th, 2011, 3:48am » |
Quote Modify
|
Nope, that didn't work either ... it finds the best eval and the move associated with it is correct, but it also finds other moves that are incorrect, and this would be because (I think) alpha-beta is designed to find the best eval of the first best move it finds.
So I'm back to being stuck again. 
|
|
IP Logged |
|
|
|
rbarreira
Forum Guru
Arimaa player #1621
Gender: 
Posts: 605
|
|
Re: How to find all the "best" moves
« Reply #3 on: Jul 8th, 2011, 4:11am » |
Quote Modify
|
You are correct that alpha-beta only promises to find the "best move", not the 2nd best move, 3rd best etc. To find those you would have to either use pure minimax, or do several successive alpha-beta searches (in each one pretending the better moves don't exist).
Quote:| If a position is given to the alpha-beta search function, then it will return the best evaluation it can find, but it will not tell you which move gave this best eval. |
|
It is not hard to upgrade alpha-beta search to return the variation corresponding to the returned score. See for example:
http://web.archive.org/web/20040427013839/brucemo.com/compchess/programm ing/pv.htm
As the page says, this doesn't have any noticeable impact on performance since it's quite rare for any sub-search to change its best move. That's how I do it in my bot and it has worked well.
It may happen not to get a full variation though, for example with transposition table hits which don't return a variation.
|
|
IP Logged |
|
|
|
Swynndla
Forum Guru
Arimaa player #1821
Posts: 235
|
|
Re: How to find all the "best" moves
« Reply #4 on: Jul 8th, 2011, 4:46am » |
Quote Modify
|
Thanks for your help again rbarreira - I appreciated it!
So how do you make your bot non-deterministic? - ie, from the same position, it wont always do the same move, right?
|
|
IP Logged |
|
|
|
rbarreira
Forum Guru
Arimaa player #1621
Gender:
Posts: 605
|
|
Re: How to find all the "best" moves
« Reply #5 on: Jul 8th, 2011, 4:56am » |
Quote Modify
|
on Jul 8th, 2011, 4:46am, Swynndla wrote:Thanks for your help again rbarreira - I appreciated it!
So how do you make your bot non-deterministic? - ie, from the same position, it wont always do the same move, right? |
|
Non-determinism from multithreading alone already makes the bot choose different moves in many positions. But I also shuffle the root moves list before starting each search (i.e. once per move after generating the list of root moves). This means it will choose different moves having the same score in the first iteration (depth 1), and chaos will ensue afterwards...
|
|
IP Logged |
|
|
|
Swynndla
Forum Guru
Arimaa player #1821
Posts: 235
|
|
Re: How to find all the "best" moves
« Reply #6 on: Jul 8th, 2011, 5:19am » |
Quote Modify
|
Shuffling the root moves I understand, and it's a good idea!
As for non-determinism from multi-threading, well I thought that on the same hardware, it would be deterministic ... are you saying that there is randomness in how multi-threading works?
|
|
IP Logged |
|
|
|
rbarreira
Forum Guru
Arimaa player #1621
Gender:
Posts: 605
|
|
Re: How to find all the "best" moves
« Reply #7 on: Jul 8th, 2011, 6:00am » |
Quote Modify
|
on Jul 8th, 2011, 5:19am, Swynndla wrote:Shuffling the root moves I understand, and it's a good idea!
As for non-determinism from multi-threading, well I thought that on the same hardware, it would be deterministic ... are you saying that there is randomness in how multi-threading works? |
|
The OS has to schedule threads to CPUs, halt them from time to time (for example when other threads request CPU time or a thread has to wait for another to release a mutex). All of this is timing-sensitive, and since threads are communicating and working together (also by using the same global transposition table), it's definitely non-deterministic.
|
|
IP Logged |
|
|
|
Swynndla
Forum Guru
Arimaa player #1821
Posts: 235
|
|
Re: How to find all the "best" moves
« Reply #8 on: Jul 8th, 2011, 7:37pm » |
Quote Modify
|
Is that because different processes are running at different times (and even the same processes are at different stages at different times)? ... and so one thread may produce a cut-off slightly before another one, but next time around the other cut-off may be ahead?
I guess if the server was somehow rewound back so it was at exactly the same state as previously (including the clock etc) then the bot would do exactly the same moves? (ie the same way as if a random seed was reset then the pseudo-random generator would produce exactly the same numbers.) Or are you saying that some sort of entropy will still make some differences? It wouldn't be based on electrical differences due to quantum effects right? (as they would be too small to make a difference). If the server was a virtual server and the multi-processing was virualized then perhaps it would be easy to rewind the server to a previous state and then the bot would do the same moves (although I'm guessing the virtual multi-processing would be slow).
Sorry that this is off topic - it's just interesting that's all.
Back to on topic - do any arimaa bots use a search method that isn't alpha-beta?
|
|
IP Logged |
|
|
|
Hippo
Forum Guru
Arimaa player #4450
Gender:
Posts: 883
|
|
Re: How to find all the "best" moves
« Reply #9 on: Jul 9th, 2011, 1:35am » |
Quote Modify
|
The nondeterminism is not the same as in NP class (the existence quantifier), but meaning rather unpredictability.
Multithread search with shared transposition tables involves unpredictability in principle. If two threats worked with the same address in "the same time" the order of access highly changes the execution. So small change of timing in one threat makes big differences later.
This "randomness" will be visible especially in situations where several moves appear to be almost equally good.
One can "replay" a game to check for different proposals.
|
|
IP Logged |
|
|
|
lightvector
Forum Guru
Arimaa player #2543
Gender:
Posts: 197
|
|
Re: How to find all the "best" moves
« Reply #10 on: Jul 9th, 2011, 4:45pm » |
Quote Modify
|
One easy way you can find all the best moves is if you pass in (alpha-1, beta) as the window to the next recursion, rather than (alpha,beta). Of course, flipping and negating it if the side to move changes (negamax).
Passing in a window of (x,y) to an alpha beta search basically means "I'm interested in exact evaluations between x and y, and otherwise, tell me only "<= x" or ">=y". So if you actually want a full list of the moves that return the best score, that means you are interested in knowing when the search will return exactly alpha (the current best score), so you must shift the lower bound to alpha-1. If you do this everywhere, and back it up with an appropriate data structure to store and propagate the pvs (like the one in rbarreira's post except adapted to hold multiple pvs at once), then you will get all the best moves, and for each of those, all the best responses by the opponent, then all your best responses to any of the opponent's best responses, etc.
If you only want the list of best moves at the root, and don't care about knowing all the opponent's best responses to each of them, you can do the (alpha-1,beta) only during the first move.
Beware that loosening the alpha bound like this may slow down your search. Because of course, you are making the program do extra work to find the additional info.
|
| « Last Edit: Jul 9th, 2011, 4:48pm by lightvector » |
IP Logged |
|
|
|
Swynndla
Forum Guru
Arimaa player #1821
Posts: 235
|
|
Re: How to find all the "best" moves
« Reply #11 on: Jul 9th, 2011, 7:12pm » |
Quote Modify
|
Hippo - ahh yes I see your point, it's not really non-determinism (more like chaos).
lightvector - wow this is exactly what I was after! I'll have to have a play as I don't know that the extra time it will take will be worth it (as you said). I was originally thinking of doing something like finding "a" best move with a complete alpha-beta search, and then re-searching with (alpha, alpha) where alpha is the eval of the best move found, but it didn't seem to work and it may need (alpha-1, alpha+1) or something like that.
|
|
IP Logged |
|
|
|
Swynndla
Forum Guru
Arimaa player #1821
Posts: 235
|
|
Re: How to find all the "best" moves
« Reply #12 on: Jul 9th, 2011, 8:19pm » |
Quote Modify
|
lightvector - your clever method seems to work - thanks! 
|
|
IP Logged |
|
|
|
Hippo
Forum Guru
Arimaa player #4450
Gender:
Posts: 883
|
|
Re: How to find all the "best" moves
« Reply #13 on: Jul 10th, 2011, 2:53am » |
Quote Modify
|
on Jul 9th, 2011, 7:12pm, Swynndla wrote:Hippo - ahh yes I see your point, it's not really non-determinism (more like chaos).
lightvector - wow this is exactly what I was after! I'll have to have a play as I don't know that the extra time it will take will be worth it (as you said). I was originally thinking of doing something like finding "a" best move with a complete alpha-beta search, and then re-searching with (alpha, alpha) where alpha is the eval of the best move found, but it didn't seem to work and it may need (alpha-1, alpha+1) or something like that. |
|
The instability of search due to policy in transposition tables makes narrow window in final search risky.
|
|
IP Logged |
|
|
|
clauchau
Forum Guru
bot Quantum Leapfrog's father
Gender:
Posts: 145
|
|
Re: How to find all the "best" moves
« Reply #14 on: Jul 16th, 2011, 5:23am » |
Quote Modify
|
And once you are sure your search does see all the best moves, you don't really need to gather them all and choose one in random at the end.
You only need to count them, increasing the counter n every time a new move is found with the same evaluation score as the best move, and randomly choose to keep the previous selected one with (n-1)/n probability or the new one with 1/n probability. In the end, this is tantamount to uniform selection among the n equivalent moves.
|
|
IP Logged |
|
|
|
|
Home
Help
Search
Members
Login
Register
Reply
Notify of replies
Send Topic
Print