Author |
Topic: Arimma search strategies (Read 1876 times) |
|
fotland
Forum Guru
Arimaa player #211
Gender: 
Posts: 216
|
 |
Arimma search strategies
« on: Oct 6th, 2003, 3:06pm » |
 Quote  Modify
|
Is anyone interested in comparing notes on search algorithms for arimaa?
Speedy is pretty conventional. It uses:
PVS alpha-beta search
Iterative deepening with transposition table (4 million positions).
Killer and history heuristics
Null move
Several search extensions
It does not have a quiescence search or static exchange evaluator.
-David
|
|
 IP Logged |
|
|
|
99of9
Forum Guru
Gnobby's creator (player #314)
 
Gender:
Posts: 1413
|
|
Re: Arimma search strategies
« Reply #1 on: Oct 7th, 2003, 7:52am » |
Quote Modify
|
Firsttry currently uses a mixture of conventional and unconventional stuff. Obviously there's more I want to add though, so treat this as a temporary list.
Conventional:
alpha / beta (No principal variation search)
Fixed depth search
Transposition tables to eliminate multiple methods of playing the same move (however these tables only currently make the comparison at the end of the full move, and they only compare across all positions with the same parent ... so I expect massive performance increases when I change this)
Null Move (Don's suggestion) ... (only tested at MAXPLY-1)
No Killer Move, or History.
No Quiescence or other Search Extensions.
Ok, here's the unconventional:
Caveat: Please do not implement/publish this just yet, please give me at least a little chance to use what I think is an innovation... as you can see from the above, I have a long way to go in other areas of my game... this is my only real gem. However I am in favour of dialogue, so if you think this is a good/terrible idea, feel free to let me know.
Heavy selectivity - Only considers N branches from any position. To choose those N branches, it does a complete 1 ply evaluation of all possible moves, using *multiple* (F) evaluation functions. These evaluation functions are *not* just added together with weights to get one big evaluation function. The evaluation functions each measure a different feature of the game position. Now imagine if you had F=2 evaluators: Material and Rabbit Winchance/Losechance. You might want to explore the branch with the best Material first, but second you should explore the branch with the best Rabbit score, even if it's total score looks negative. Seems common sense? Yes, because I believe this is somewhat similar to the way a human selects moves to explore. I think this also counters the problem that bots often have in arimaa where they are deceived by large material sacrifices into letting a rabbit through. Now actually I don't just select the best N/F moves of each Feature, it's more complicated than that because there is a "better way", but I'd rather not discuss the details just yet, because after all, it might not work, and secondly, suspense is a "good thing", and anyway, you've got the idea of how to use multiple evaluation functions already!
We all know that "good" move ordering is important for alpha/beta, but I claim that "diverse" move ordering is almost as important! This method would also work in non-selective alpha/beta, it's fundamentally a move-ordering method.
So after that long diatribe... has anyone ever heard of this approach before? (remember that I have not read much of the literature as I am new to all of this). Have I explained it clearly enough? Does it seem reasonable? Does it look like it might work? Did you cry "Eureka" when you read this post?
|
|
IP Logged |
|
|
|
99of9
Forum Guru
Gnobby's creator (player #314)
Gender:
Posts: 1413
|
|
Re: Arimma search strategies
« Reply #2 on: Oct 7th, 2003, 8:12am » |
Quote Modify
|
PS Just reread David's post:
firsttry does not have "static exchange evaluator" either... in fact I don't even know what one is (but I'm sure Google will help me with this failing  )
|
|
IP Logged |
|
|
|
fotland
Forum Guru
Arimaa player #211
Gender:
Posts: 216
|
|
Re: Arimma search strategies
« Reply #3 on: Oct 7th, 2003, 10:58pm » |
Quote Modify
|
Static exchange evaluator just gives the material result of a set of exchanges. It's used in chess programs to avoid searching all the permutations. There aren't as many exchanges in arimaa, so I left it out.
Selective search is good, as long as it gets you enough extra depth to make up for the missed moves. I prefer null move for selective search, since it uses information from the search itself, and its easy to implement.
Figuring out how much material is worth an advanced rabbit is hard I evaluate certain advanced rabbits as worth more than a camel, but it's not easy to get the balance right.
|
|
IP Logged |
|
|
|
RonWeasley
Forum Guru
Harry's friend (Arimaa player #441)
Gender:
Posts: 882
|
|
Re: Arimma search strategies
« Reply #4 on: Nov 3rd, 2003, 12:38pm » |
Quote Modify
|
I'm new here, but believe 99of9's innovation has merit. If I understood, features of the game may sometimes be expressed as different branches in the search.
I'm now figuring out how to host a bot on antique equipment. I expect to progress very slowly. My plan has some similarity to 99of9's. Coming from a military simulation background, I'm trying to look at the game as a collection of threats to which resources must be distributed. The bot will try to coordinate its resources better than the opponent. The bot will attempt to identify threats, value them, and apply resources. This is the way I see humans discuss chess and warfighters discuss operations. Some searching will be required to perform the evaluation.
So without giving away anymore, I would encourage 99of9 to press on.
-Ned
|
|
IP Logged |
|
|
|
99of9
Forum Guru
Gnobby's creator (player #314)
Gender:
Posts: 1413
|
|
Re: Arimma search strategies
« Reply #5 on: Nov 4th, 2003, 5:41am » |
Quote Modify
|
Thankyou for your encouragement NedRon. I shall indeed press on.
Quote:| If I understood, features of the game may sometimes be expressed as different branches in the search. |
|
Yes I think you've got it, but I wouldn't use quite those words. I'd summarise with:
Deliberately explore branches with very different features than those of branches you've explored before.
For the alpha-beta nuts, when we're thinking move ordering, we want to hit the correct move asap in our exploration. To do this we first try our best guess (the one with the best total "score"), however if that fails, it's less likely that one very like it will pass, it's more likely that a move which favours totally different features could be the winner.
Regarding David's comment:
Quote:| Selective search is good, as long as it gets you enough extra depth to make up for the missed moves. I prefer null move for selective search, since it uses information from the search itself, and its easy to implement. |
|
My issue with null move is it doesn't seem to cut out enough for my liking. From what I understand of Speedy and Occam, they are truly very well optimised, and both use null move, but still only get to a depth of around 3 full moves (of 4 plays each). Now that's not really a criticism, because that's the whole point of arimaa... it's hard to do a deep search when the tree is so wide. But I know that as a human I sometimes think far deeper than 3 moves ahead (that's only "my move, your move, and my next move"), (obviously I'm not thinking full width however). So I'm sure that harsh selectivity can be done well.
The first part of your quote is also valid. At the moment that's the problem with GnoBot ... although it can search 4 full moves ahead or so, it misses some vital move on the 2nd ply, and gets things totally wrong! But then again, that's partly because my evaluation functions for selecting the selectivity are still rudimentary. Just last night I started dumping data that will help me use a genetic algorithm to refine the evaluation function constants. When that is implemented, Gnobby will improve with every game!
99of9
|
| « Last Edit: Nov 4th, 2003, 5:49am by 99of9 » |
IP Logged |
|
|
|
fotland
Forum Guru
Arimaa player #211
Gender:
Posts: 216
|
|
Re: Arimma search strategies
« Reply #6 on: Nov 11th, 2003, 10:37pm » |
Quote Modify
|
Speedy typically searches 10 or 11 steps, and bomb searches 12 or 13 steps. But I have many search extensions, so it is not unusual for some lines to get to 20 steps.
-David
|
|
IP Logged |
|
|
|
|
Home
Help
Search
Members
Login
Register
Reply
Notify of replies
Send Topic
Print