Author |
Topic: lightvector's Thesis (Read 5108 times) |
|
Fritzlein
Forum Guru
Arimaa player #706
Gender: 
Posts: 5928
|
 |
Re: lightvector's Thesis
« Reply #30 on: May 19th, 2011, 6:02pm » |
 Quote  Modify
|
on May 18th, 2011, 9:12pm, 99of9 wrote:| Gnobot, and I'm sure many of the other bots have a "hand written" move-ordering function. |
|
True, but it is interesting that lightvector's move-ranking function, which gave significant strength boost when used to prune, gave no measurable boost when used for move ordering. Since the move-ordering is redone at each ply of iterated alpha-beta searching, and the re-ordering is done on the basis of search+eval, presumably any non eval-based ordering will be quickly "overwitten" by the next iteration, unlike forward pruning which is permanent.
In other words, mere move-ordering not only isn't used to prune, it shouldn't be used to prune, whereas the pruning-order probably shouldn't be used to permanently order moves, since it would be fighting with eval and slowing down search. So in this respect the existence of hand-coded move-ordering isn't very close to what lightvector is doing, and lightvector's innovation is truly sui generis.
Quote:| Although in Gnobot it does not actually do any pruning beyond Haizhi-pruning |
|
Good point. I shouldn't have short-changed Haizhi-pruning, which is indeed a form of hand-coded pruning that is completely independent from evaluation. Indeed, now that I recollect, didn't that inspire a discussion of more general non-evaluation-based pruning? And that no developer was interested in trying it because it wasn't clear on what principle to do such pruning? I forget so quickly...
|
| « Last Edit: May 19th, 2011, 6:10pm by Fritzlein » |
 IP Logged |
|
|
|
jdb
Forum Guru
Arimaa player #214
Gender:
Posts: 682
|
|
Re: lightvector's Thesis
« Reply #31 on: May 20th, 2011, 9:07am » |
Quote Modify
|
Almost any form of pruning, or reductions for that matter, will be an improvement. Increased pruning means greater search depth which means greater playing strength.
Jdb's theorem:
In arimaa, 99% of the available moves are garbage 99% of the time.
Pick a position and print out all of the legal moves. Its amazing how many of them are pointless. As long as the pruning scheme stays away from the 1%, any method will do a decent job. That's why something like haizhi pruning works. It identifies moves that fall into the 99% category.
In order to be safe, some form of verification search is required. For example a test to make sure a goal in 2 or a capture in 2 has not been missed. This can be done with a dedicated function and takes little time.
|
|
IP Logged |
|
|
|
Swynndla
Forum Guru
Arimaa player #1821
Posts: 235
|
|
Re: lightvector's Thesis
« Reply #32 on: May 21st, 2011, 6:45am » |
Quote Modify
|
on May 19th, 2011, 12:46pm, Fritzlein wrote:| Given this explanation, Swynndla, would you suggest a different term than "asymmetric" to refer to what I am trying to get at? |
|
Your explanation was extremely clear and informative. Thank you also for the crafty example. You convinced me that asymmetric is indeed the correct term. All this is very thought provoking, and I haven't been able to think about anything else.
Quote:| The main point is to throw away as many moves as possible while still capturing all moves that might be best. |
|
With all my pondering, I thought I might have it all figured out, but I'm not quite there. I understand what you said just fine, but when I read the rest of what you've written and think about how it works ... are you saying that the pruning function looks at only risky/extreme/speculative moves (and prunes all others)? I can't imagine you are saying that as not many expert moves are like that. You're just saying they shouldn't be excluded, right? - and that that is a clear example of how it differs from the evaluation function.
What you're saying is risky moves should be included along with solid moves (solid moves like threats and trap strengthening, etc) and then the rest can be pruned, right? There are a lot of risky moves. I keep thinking that the Bradley Terry optimization did so well (ie around 90% of expert moves falling within the top 5% of the ordering, and around 94% within 10%), that there isn't a lot of room to fit all the risky moves in. In fact it seems to me the risky moves are so far and few, that to exclude them entirely would give better percentages, because most expert moves would be solid moves (ie not sacrificing the my camel), and so the expert moves would be predicted within a smaller percentage of the move ordering.
If I've explained what I mean properly, then I guess you'll see that I'm a bit confused about it. I have a feeling it's because lightvector's optimization orders moves that are likely to be expert moves not in general, but based on a given position, and that for a given position, it will have only a small number of risky (but likely) moves near the top. Would I be correct? It makes sense to me, although I'm impressed that the optimization function works so well. I suppose it works like this, eg it only looks at sacrificing its camel if there's a potential goal threat (eg advanced rabbit, weakened defense), but at the beginning of the game, a camel sacrifice would be pruned. So an advanced rabbit feature and a weakened defense & supporting friendlies would increase the value given to sacrifices (value to be ordered higher & therefore not as likely to be pruned), and lightvector's optimization would work this out for itself, because strong players will start sacrificing when there are goal threats. These sacrifices by strong player are still fairly rare, so I'm not sure how the optimization is able to kick up the value high enough not to be pruned, as there's more pressure in the data not to sacrifice even in those positions. So nope, it's still not straight in my head (and it's giving me a headache).
on May 18th, 2011, 1:48am, lightvector wrote:| And for moves that aren't so obvious, things like Haizhi's step combo (dependency components) as well as closeness to the previous two moves will help distinguish them from random piece shuffling. |
|
Haizhi's pruning I understand, but closeness to the move before, and the move before that I'm not sure about. It doesn't mean that because I moved my rabbit and horse up on the east, that I should consider moving them further, does it? And if I added a defender to a trap, that I should look at adding another? Or does it really mean those sort of things?
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: lightvector's Thesis
« Reply #33 on: May 21st, 2011, 8:50am » |
Quote Modify
|
on May 21st, 2011, 6:45am, Swynndla wrote:
are you saying that the pruning function looks at only risky/extreme/speculative moves (and prunes all others)? I can't imagine you are saying that as not many expert moves are like that. You're just saying they shouldn't be excluded, right? |
|
Right. The goal here is not to favor playing risky move more often than solid moves. The goal is it play the objectively best move, regardless of its nature. For the purposes of pruning, risky moves should be less likely to be pruned, because they have high variance, and might turn out to be the best move even if static evaluation is unimpressed at first.
Quote:| In fact it seems to me the risky moves are so far and few, that to exclude them entirely would give better percentages, because most expert moves would be solid moves (ie not sacrificing the my camel), and so the expert moves would be predicted within a smaller percentage of the move ordering. |
|
This sounds counter-intuitive, but my hunch is that even if most expert moves are solid moves, the move prediction function is going to fare badly if it biases towards solid moves. The point is that initial impressions of risky moves are most likely to be wrong. If you think a solid move is decent (or weak) without searching it, you are probably right. If you think a risky move is decent (or weak) without searching it, you have a good chance of being wrong. The true value of the risky move could be wildly different than your initial evaluation of it. So you can't prune on that initial evaluation. You have to keep the risky move around and look at it just in case.
Quote:| I have a feeling it's because lightvector's optimization orders moves that are likely to be expert moves not in general, but based on a given position, and that for a given position, it will have only a small number of risky (but likely) moves near the top. Would I be correct? |
|
I think you are correct, but maybe also missing the point. The point isn't that the expert move predictor has some magical way to tell what move is the best move without searching ahead. That would be strong magic indeed, and you would want to use that function for evaluation as well as for pruning.
The point is that the expert move predictor can tell what moves are likely to be the best move. I believe that this means it includes more risky moves in its list than the evaluation function would include in its list of best moves. The evaluation function has to rank from best to worst knowing no more search will happen. This is a harsh constraint not laid on the expert move predictor. The pruning function realizes that more search is yet to come, so it doesn't have to throw away dubious-looking risky moves that might secretly be brilliant. Those can be thrown away later by evaluation if they are still no good when searched.
Perhaps this thought experiment will help clarify: Why not use the expert move predictor for post-search evaluation as well? Lightvector couldn't, of course, because it is too slow to use for evaluation. My hunch is that even if the speed weren't a problem, it would work badly. The expert move predictor would play too unsoundly, because too many of the "it might be best" moves will actually turn out to be sub-optimal when searched.
Lightvector, would you be interested in making this thought experiment a real experiment? You could pit your machine-learned move-predictor versus your hand-tuned evaluation function at one ply. You have two ways to rank the moves: which one plays betters in the absence of search?
Quote:| So an advanced rabbit feature and a weakened defense & supporting friendlies would increase the value given to sacrifices (value to be ordered higher & therefore not as likely to be pruned), and lightvector's optimization would work this out for itself, because strong players will start sacrificing when there are goal threats. |
|
No, you are giving the expert move predictor too much credit. It doesn't have fancy connections like "if you control the c6 trap, then advance rabbits in the west". Advancing rabbits in the west has a weight that is independent of trap control.
|
| « Last Edit: May 21st, 2011, 9:01am by Fritzlein » |
IP Logged |
|
|
|
99of9
Forum Guru
Gnobby's creator (player #314)
 
Gender:
Posts: 1413
|
|
Re: lightvector's Thesis
« Reply #34 on: May 22nd, 2011, 5:07am » |
Quote Modify
|
on May 21st, 2011, 8:50am, Fritzlein wrote:
No, you are giving the expert move predictor too much credit. It doesn't have fancy connections like "if you control the c6 trap, then advance rabbits in the west". Advancing rabbits in the west has a weight that is independent of trap control.
|
|
As far as I recall, density of pieces in the locale is included in the rabbit advancement terms.
|
|
IP Logged |
|
|
|
omar
Forum Guru
Arimaa player #2
Gender:
Posts: 1003
|
|
Re: lightvector's Thesis
« Reply #35 on: May 25th, 2011, 4:50pm » |
Quote Modify
|
Thanks for posting the Thesis David. I've added it to the Arimaa papers page.
I haven't read through it yet, but it looks very interesting. Developing automated techniques for generating the evaluation function is definitely in the spirit of the Arimaa challenge 
|
|
IP Logged |
|
|
|
|
Home
Help
Search
Members
Login
Register
Reply
Notify of replies
Send Topic
Print