Arimaa Forum - Print Page


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

        Arimaa >> Bot Development >> How to find all the "best" moves
        
(Message started by: Swynndla on Jul 7^th, 2011, 10:50pm)

Title: How to find all the "best" moves
Post by Swynndla on Jul 7^th, 2011, 10:50pm

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. :)

Title: Re: How to find all the "best" moves
Post by Swynndla on Jul 8^th, 2011, 12:29am

on 07/07/11 at 22:50:17, 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?

Title: Re: How to find all the "best" moves
Post by Swynndla on Jul 8^th, 2011, 3:48am

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. :-/

Title: Re: How to find all the "best" moves
Post by rbarreira on Jul 8^th, 2011, 4:11am

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/programming/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.

Title: Re: How to find all the "best" moves
Post by Swynndla on Jul 8^th, 2011, 4:46am

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?

Title: Re: How to find all the "best" moves
Post by rbarreira on Jul 8^th, 2011, 4:56am

on 07/08/11 at 04:46:19, 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...

Title: Re: How to find all the "best" moves
Post by Swynndla on Jul 8^th, 2011, 5:19am

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?

Title: Re: How to find all the "best" moves
Post by rbarreira on Jul 8^th, 2011, 6:00am

on 07/08/11 at 05:19:35, Swynndla wrote:

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.

Title: Re: How to find all the "best" moves
Post by Swynndla on Jul 8^th, 2011, 7:37pm

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?

Title: Re: How to find all the "best" moves
Post by Hippo on Jul 9^th, 2011, 1:35am

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.

Title: Re: How to find all the "best" moves
Post by lightvector on Jul 9^th, 2011, 4:45pm

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.

Title: Re: How to find all the "best" moves
Post by Swynndla on Jul 9^th, 2011, 7:12pm

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.

Title: Re: How to find all the "best" moves
Post by Swynndla on Jul 9^th, 2011, 8:19pm

lightvector - your clever method seems to work - thanks! :D

Title: Re: How to find all the "best" moves
Post by Hippo on Jul 10^th, 2011, 2:53am

on 07/09/11 at 19:12:13, Swynndla wrote:

The instability of search due to policy in transposition tables makes narrow window in final search risky.

Title: Re: How to find all the "best" moves
Post by clauchau on Jul 16^th, 2011, 5:23am

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.

Title: Re: How to find all the "best" moves
Post by Swynndla on Jul 16^th, 2011, 5:38am

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?

Title: Re: How to find all the "best" moves
Post by lightvector on Jul 16^th, 2011, 9:56am

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.

Title: Re: How to find all the "best" moves
Post by Swynndla on Jul 16^th, 2011, 6:02pm

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?

Title: Re: How to find all the "best" moves
Post by lightvector on Jul 16^th, 2011, 6:34pm

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.

Title: Re: How to find all the "best" moves
Post by TheVinenator on Oct 20^th, 2011, 10:45am

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.

Title: Re: How to find all the "best" moves
Post by rbarreira on Oct 20^th, 2011, 10:51am

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.