Author |
Topic: Psuedo-random sparse search (Read 1302 times) |
|
Rednaxela
Forum Senior Member
Arimaa player #4674
Gender: 
Posts: 34
|
 |
Psuedo-random sparse search
« on: Aug 23rd, 2010, 8:58pm » |
 Quote  Modify
|
Well, while working on a new bot, I started wondering that if one wanted to try forward pruning, what would be best to prune. I'm wondering if anyone has any comments on the following strategy for such:
- First, evaluate 'obvious' and 'interesting' moves of course. Use techniques such as a capture decision tree I've seen mentioned in order to do so. Be careful with this as to avoid pitfalls.
- Then, start evaluating remaining moves in a pseudo-random manner, with bias towards evaluating moves that are similar to moves already evaluated to be strong. (A simple way of choosing 'similar' is with proximity in the step tree)
- Repeat until all moves evaluated or there is a time crunch.
Maybe I'm wrong, but I'm thinking this approach could be a good way of to search deeper by evaluating fewer moves and branching less. The idea is that the weighted-but-random search priority would also mean it would 1) tend to do more useful searches first, 2) still explore the search space a reasonable amount, and 3) mitigate disadvantages of a less complete search by not predictably ignoring the same things.
Any thoughts?
(Also, all that said, I'm probably not trying this approach in my current bot-in-progress (at least for now). After all, my current planned approach is more about making the most of low depth. Just wondering if anyone has thoughts on this idea.)
|
| « Last Edit: Aug 23rd, 2010, 9:06pm by Rednaxela » |
 IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: Psuedo-random sparse search
« Reply #1 on: Aug 24th, 2010, 1:21am » |
Quote Modify
|
My intuition is that the Arimaa Challenge is less likely to fall to improving the evaluation of full-width alpha-beta searchers, and more likely to fall to some aggressive pruning scheme we haven't thought of yet. However, I have no idea what such pruning would look like, and everything that has been tried so far has worked poorly. So maybe evaluation and not search is the key after all.
|
| « Last Edit: Aug 24th, 2010, 1:22am by Fritzlein » |
IP Logged |
|
|
|
Hippo
Forum Guru
Arimaa player #4450
Gender:
Posts: 883
|
|
Re: Psuedo-random sparse search
« Reply #2 on: Aug 24th, 2010, 5:32am » |
Quote Modify
|
I would still consider MCTS like methods but with modified exploration ... I would like a heuristic able to generate move candidates in as good order as possible and explore just limited number of them at a time. After the branch becomes visited treshold number of times another portion of moves would be added. This would limit width of MCTS tree in less perspective branches and I hope speeded the perspective branches.
Of course bad candidate order heuristic would made the method poor. And especially goaling, goal preventing, capturing, capture preventing moves should be included in the explored part as fast as possible. But as there is (in Kozelek's work) shellow alpha-beta evaluator, at least best looking candidate moves could be find quickly in transposition tables.
|
|
IP Logged |
|
|
|
Rednaxela
Forum Senior Member
Arimaa player #4674
Gender:
Posts: 34
|
|
Re: Psuedo-random sparse search
« Reply #3 on: Aug 24th, 2010, 6:40am » |
Quote Modify
|
Yeah, issues with bad heuristics for candidate order would be problematic... which is part of why I was thinking "the result of evaluation of similar moves" would perhaps be a powerful heuristic to involve, as far as impact per amount of cpu use. Of course that would certainly be a lower priority heuristic than goaling/goal-prevention/capture related ones yeah.
|
| « Last Edit: Aug 24th, 2010, 6:43am by Rednaxela » |
IP Logged |
|
|
|
speek
Forum Guru
Arimaa player #5441
Gender:
Posts: 75
|
|
Re: Psuedo-random sparse search
« Reply #4 on: Aug 24th, 2010, 1:20pm » |
Quote Modify
|
I currently just use my evaluation function to determine good search candidates. It does not work all that well, though it's a very simple eval function - a better one might work better.
But, it does seem like candidate recognition has to be different from position evaluation.
I am trying to visualize my bot as a bunch of spiders that roam the search tree independently looking for good things and avoiding bad things. Some sort of randomization in their roaming is probably good. I'm also thinking that multiple different candidate recognizers might also be helpful.
The similar move thing sounds interesting, but also sounds difficult to really make it work well. A lot of moves that will look similar will often prove to have very different effects on the game.
|
|
IP Logged |
|
|
|
rbarreira
Forum Guru
Arimaa player #1621
Gender:
Posts: 605
|
|
Re: Psuedo-random sparse search
« Reply #5 on: Aug 25th, 2010, 5:37am » |
Quote Modify
|
on Aug 24th, 2010, 1:21am, Fritzlein wrote:| However, I have no idea what such pruning would look like, and everything that has been tried so far has worked poorly. |
|
I thought Haizhi's pruning scheme had been adopted by a few bots. How much it helps I'm not sure.
|
|
IP Logged |
|
|
|
|
Home
Help
Search
Members
Login
Register
Reply
Notify of replies
Send Topic
Print