Arimaa Forum - Print Page


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

        Arimaa >> Bot Development >> Step-based search vs. move-based search
        
(Message started by: n00bftw on Oct 6^th, 2014, 5:04pm)

Title: Step-based search vs. move-based search
Post by n00bftw on Oct 6^th, 2014, 5:04pm

It's my impression based on various Arimaa papers (e.g. those of Haizhi, Kozelek, and Wu) that step-based search is preferred by all of the advanced bots. However, I asked a related question about this in the chat on Aug. 29, and clyring said that ziltoid doesn't do step-based searches at all. Is that true?

My question was whether most bots generate all root moves and then search (perhaps after some pruning), or do equally as many search the steps from the initial position? Clueless does the first method, and so (I think) does sharp. Occam does the second. I'm wondering what advantages there are to the first method, other than pruning, which is an obvious time-saver.

Title: Re: Step-based search vs. move-based search
Post by lightvector on Oct 8^th, 2014, 7:07am

Yes, I think that's true of ziltoid, but I don't know the details of what it does. I think either design for the search is okay as long as you take care to make it efficient and sensible (ex: with move-based-search, naively generating and sorting all 10000+ legal moves at a node where you're going to fail high with a beta cutoff on the very first move tried is not ideal). If you're step-based, then of course you should make sure to keep the number of steps remaining as an intrinsic part of the game state, where if the search ends in the middle of a turn, the evaluation (and/or quiescence search) should fully "understand" that that player still has a partial turn remaining.

Yes, sharp generates all moves at the root. At the root, you actually can do the dumb thing of generating all 10000+ legal moves first, and you get a slight advantage if you have good ordering heuristics, because, for example, you are easily able to search move X first without also mandating that you must search every move that begins with the same step as X immediately next.

Whether it's an advantage for pruning or not depends on things like whether your pruning is forward-looking ("from this position, I can tell a move I would not want to play is X") or backward-looking ("from this position that I reached after playing X, I can now tell that I shouldn't have done so"). In the former case, it helps, in the latter case, it doesn't.

Title: Re: Step-based search vs. move-based search
Post by n00bftw on Oct 9^th, 2014, 1:38pm

Thanks for the response; that's very interesting. I would tend to think that given what seem to me to be two very different choices of how to search, one would be demonstrably superior, but it doesn't look that way.

Perhaps the reason most developers have preferred step-based search is that it's easier to not be woefully inefficient, whereas with move-based search, as you said, you have to be more careful in how you generate and search through all the possible moves.

Title: Re: Step-based search vs. move-based search
Post by elescondite on Oct 12^th, 2014, 8:32pm

Just my two cents for what it's worth… My bot uses a move-based search, and from playing some of the other bots, I don't think I'm the only one. Having said that, it is actually a little more complicated. My bot is multithreaded, and jobs are created for each top level child in the tree. In addition, as my bot iteratively deepens the search, it creates child nodes for the best evaluated child one level down, so that it will always evaluate the best move first each time it deepens the search. Pruning works much better when the best move, or nearly the best move, is evaluated early in the search. This is one of the most important things about optimizing a negamax search: try to evaluate the best moves as soon as possible. So when I am creating the jobs to be handled by the worker threads, I sort them starting with 4 steps first, then 3 and etc. The logic behind this is that generally most of the best moves use all 4 steps, and if not all 4, then 3 and etc. Once the search is below the top level, jobs are not created. Each thread works its way down the tree until it completes that branch. For each node, my search will try the first 1 step move it can find, in the hopes that I will get an early cutoff and not have to search any further. If I don't get a cutoff, I then generate all of the 1-3 step moves. I do this so I can generate the 4 step moves, which I evaluate first. I did this because I felt like it was important to try to sort the moves such that the best ones would be tried first, and these are generally the 4 step moves. All moves are generated one at a time, so if a 4 step move causes a cutoff, no further time is wasted generating any of the other 4 step moves. After the 4 step moves have been tried, the 3 step moves are tried, and etc. Note that I have considered using this same process, but starting with the 3 step moves first, thus doing 3, 4, 2, 1. The logic behind this is that a great many 4 step moves really contain 3 important steps and one step that is less important. If I could evaluate the 3 step move that contained the important steps, I suspect that I could start pruning moves more effectively quicker. At some point I may change my evaluation sequence this way.

I think there is much that could be said to support either step based or move based searching. Ultimately, one of the real goals of mine is to figure out a good way to "guess" at the probable effectiveness of certain moves, and evaluate them first. This would definitely emphasize a move-based search. I already attempt to do this by keeping track of the results of my evaluation function. So for my level 1 search, I store all of the moves that I generate, along with the results from the evaluation function. For subsequent levels, I no longer have to regenerate those moves. Instead, I sort them from best to worst and evaluate them in that order. For the higher level searches, I currently do a delayed cutoff, keeping track of the top 20 (at the moment) moves. These moves get put on the front of the list for subsequent iterations. The nice side effect of this is that I am always evaluating the list of moves from best to worst order (as determined by my evaluation function), so whenever I get a timeout in the middle of evaluating the next ply, I have already been searching the moves in the best order as determined from the previous ply (at least the top 20 best anyway), so I can use whatever results I have found up to that point. In other words, I can get benefit from a partial ply search.

Anyway, that's what I do, for better or worse. Note that when a bot evaluates 4 step moves first and it detects a win, it will immediately play it, even if the win could be achieved with less steps. A developer could go to the trouble of having the bot check to see if the win was possible with fewer steps, but what's the point? This is generally the telltale sign of a bot evaluating 4 step moves first: you will see unnecessary steps for some wins. My bot will do this, and I've seen others do it too. This is obviously a very nonhuman thing to do, and ultimately it points to the huge limitation presently with AI. Human beings very instinctively identify important pieces, and from that important move sequences, while computers so far are not as good at this. When computers can perform move generation based on the significance of pieces/moves, they will begin to be able to compete with humans.

Title: Re: Step-based search vs. move-based search
Post by n00bftw on Oct 12^th, 2014, 10:16pm

After reading this thread (http://arimaa.com/arimaa/forum/cgi/YaBB.cgi?board=devTalk;action=display;num=1385006477) and rbarreira's description of his bot (which I am pretty sure is currently known as ziltoid), I would say that ziltoid does in fact use step-based searches. It does iteratively deepen 4 steps at a time, but of course that's not the same thing as solely move-based searches. Before, I thought it was generating moves as necessary to expand a node (or "generating moves in batches") as rbarriera called it in his post. But I now understand that that is what elescondite is doing with his bot, and I think his will be the first to use that method. It's easier to describe with pseudocode. I think there are essentially three options for doing alpha-beta searches from a high-level view. I think I got these descriptions of the bots right, but please correct me if I'm wrong:

Option 1 -- Clueless, sharp, and ziltoid do this

Code:

search(position)
moves = generate all unique moves for position, perhaps pruning some
depth = 1
while time remaining
for each move
new_position = play move on new_position
move.score = stepwise_search(new_position, depth)
depth += depth_increment// 1 or 2 for sharp, 4 for ziltoid
return move with best score

Option 2 -- bot_Occam and bot_Fairy do this, but honestly it's hard to tell at a glance with bot_Fairy

Code:

search(position)
result = stepwise_search(position)
from result, return a move consisting of the root step plus the remaining 0-3 steps

Option 3 -- elescondite's bot does this, but no one else's

Code:

search(position)
return move with highest minimax value from movewise_search(new_position, depth)

stepwise_search returns the minimax value (plus additional info if necessary), generating child nodes by generating each possible step for that position (including 2-step pulls and pushes)

movewise_search returns the minimax value, generating child nodes by generating a legal move but only when necessary

Title: Re: Step-based search vs. move-based search
Post by n00bftw on Nov 2^nd, 2014, 3:34pm

After modifying bot_opfor to do movewise searches, I am starting to reach the conclusion that they are indeed inferior. The best movewise search times for the same position are > 10 times as long as the stepwise searches. I believe this is because they generate fewer cutoffs and therefore reach many, many more leaf nodes. Of course, it's difficult to sort the moves (other than the root moves) in order to get more cutoffs because of the way you have to generate moves one batch a time, so as to not waste time producing unused moves. bot_opfor uses a very interesting step sorter. I'm not sure how much of a performance gain that gives to its searches; I could try incorporating the step sorter into the batch move generator.

There are also other optimizations that bot_opfor does that I didn't put into my movewise search, though I'm currently searching at such a basic depth of 2 moves that I doubt that any of those would affect it too much. (By contrast, a depth of 8 steps gives "room" for more optimizations.)