Author |
Topic: bot sharp's AI (Read 4001 times) |
|
Fritzlein
Forum Guru
Arimaa player #706
Gender: 
Posts: 5928
|
 |
bot sharp's AI
« on: Mar 11th, 2011, 8:51am » |
 Quote  Modify
|
Lightvector, if I understand what you said in chat, sharp trained to try to predict expert moves, and eventually got so good that its top 10% of predictions contained the actual move 93% of the time. And then limiting sharp to playing one of these top 10% moves dramatically improved its strength. Will you be posting your senior thesis on line? And if not, will you be answering questions here? 
For starters I'm curious what experts you used for training. If you limited yourself to high-rated human games in the database, your training sample couldn't have been very large, could it?
|
| « Last Edit: Mar 11th, 2011, 8:51am by Fritzlein » |
 IP Logged |
|
|
|
rbarreira
Forum Guru
Arimaa player #1621
Gender:
Posts: 605
|
|
Re: bot sharp's AI
« Reply #1 on: Mar 11th, 2011, 9:05am » |
Quote Modify
|
on Mar 11th, 2011, 8:51am, Fritzlein wrote:| And then limiting sharp to playing one of these top 10% moves dramatically improved its strength. |
|
The first time lightvector talked about it I got the same impression as you, but then later I saw him saying this in the chat:
Quote:2011-03-10 18:27:44 lightvector but for sharp, the root pruning is something like all but 30-40% are pruned by reducing depth by 2
2011-03-10 18:28:00 lightvector and then all but 10% or so are soft pruned by reducing depth by 1 |
|
|
|
IP Logged |
|
|
|
chessandgo
Forum Guru
Arimaa player #1889
Gender:
Posts: 1244
|
|
Re: bot sharp's AI
« Reply #2 on: Mar 11th, 2011, 9:27am » |
Quote Modify
|
dam.n, I was waiting for my turn to speak to relay that learning thing about pruning, asking you guys (and lightvector in the chat) more about it, and I just forgot I suppose 
|
| « Last Edit: Mar 11th, 2011, 9:27am by chessandgo » |
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: bot sharp's AI
« Reply #3 on: Mar 11th, 2011, 9:41am » |
Quote Modify
|
Hmm, and is that depth reduction by one and two steps respectively, or one and two ply?
|
|
IP Logged |
|
|
|
lightvector
Forum Guru
Arimaa player #2543
Gender:
Posts: 197
|
|
Re: bot sharp's AI
« Reply #4 on: Mar 11th, 2011, 5:44pm » |
Quote Modify
|
So, the basic observation I had was this:
Look at typical Arimaa position, and generate a few random legal moves. Most will likely be completely meaningless and accomplish nothing. They also have a decent chance of doing things like leaving pieces hanging on traps, or giving up important squares, or releasing phalanxes in frames and blockades, etc.
Now consider the moves played by strong human players. By contrast with the random moves, nearly every move will do something identifiably good, like add defenders to traps, or push away opponent defenders, or flip opposing pieces, or advance or retreat pieces in a coordinated fashion, possibly by unfreezing them. In fact, if you look at a typical complicated midgame with multiple trap fights, and count the proportion of moves that involve one of: (a) Adding defenders to an underdefended trap, (b) pushpulling opposing defenders away from traps, (c) making or defending capture threats, (d) moving the elephant, camel, or horses between important positions. It's really quite remarkable how many of the moves do one of these things, and quite often several of them at once.
So if you look at enough of these features together, there's clearly a tremendous amount of predictive power to be exploited. And you don't even have to be that good at it. It's already very useful if you can just distinguish the difference between the junk that comprises random moves, and the tiny subset of moves that occur in good games, because so many thousands of moves really are utter garbage. But coding by hand how to combine and weight such a variety of things by hand is really hard, especially when each one has its own exceptions. That's where the machine learning comes in.
So what I'm doing is taking Arimaa moves and computing feature vectors from them, where each entry in the vector indicates something like "adds defender to trap x" or "moves elephant to square x", or "captures horse", or "suicides own horse". From there, you can apply standard supervised-learning algorithms for classification and ranking (such as bayesian methods, support vector machines, neural nets, etc) to try to learn an appropriate ranking function. I've been experimenting with some algorithms, and have gotten some great results for Arimaa.
For training data, I used games played on this site by human players with ratings 1800 or greater over a span of several years, as well as some bots.
1800 is a little bit low of a cutoff, and I might consider re-running some more tests with a higher cutoff. But I think it's okay. In the case of players on the weaker end of things, the moves might sometimes be massive strategic blunders, but that's okay. Nearly all the strategic blunders will still be moves from this small subset of "moves that do good things", despite being wrong for the global position. My feeling is that 1800 is around the rank when people begin really to be able very consistently fight for squares around traps and make/defend threats, even if the execution isn't perfect.
And of course there's a lot of noise in the data. People make tactical blunders, people sacrifice pieces in response to the opponent's forced goal, gameroom ratings can be misleading, etc. But the majority of it is good, good enough for a robust learning algorithm to readily pick out the correct, strong signal.
|
|
IP Logged |
|
|
|
lightvector
Forum Guru
Arimaa player #2543
Gender:
Posts: 197
|
|
Re: bot sharp's AI
« Reply #5 on: Mar 11th, 2011, 5:58pm » |
Quote Modify
|
As for how I'm using it in bot_sharp. I'm just using the expert move predictor to order the moves at the root of the search, and then pruning based on that.
I ran tests, and apparently I gain something like 100-200 elo from pruning 95% of the moves outright, not even searching them. Granted, this is in self play, and only at 5s/move. But at the very least, seeing that even this extreme pruning doesn't greatly harm the bot in comparison to the gains, we can conclude that the ordering is quite good, and doesn't lose too many good moves.
I would not actually use such a pruning scheme in bot_sharp for real. The current 2011CC bot_sharp does the more conservative pruning, with the depth reductions (in steps), as I mentioned. This is because I didn't have time before having to submit bot_sharp to test it more in detail. With no time to test it, I decided not to go with risky hard-pruning or with any extreme 95% pruning, because if it turns out to cause bot_sharp to miss some easy tactics, that's really bad. Reducing depth by 1-2 steps already produces a fair amount of speedup, because the cost of a search is exponential in the depth.
But I'm pretty sure I could gain some strength by being a little more aggressive, given how high-quality the learned ordering is turning out to be, I just need to do testing, preferably some in games with longer time controls than 5s. It's definitely low-hanging fruit, and I'll be doing it this summer, after I stop being buried under my coursework.
I will be submitting my thesis on April 1, still working on writing it. I will see about posting it up when done.
|
| « Last Edit: Mar 11th, 2011, 6:00pm by lightvector » |
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: bot sharp's AI
« Reply #6 on: Mar 11th, 2011, 6:02pm » |
Quote Modify
|
on Mar 11th, 2011, 5:58pm, lightvector wrote:| I will be submitting my thesis on April 1, still working on writing it. I will see about posting it up when done. |
|
Thanks for considering posting your thesis, and thanks for the excellent explanation in the mean time.
|
|
IP Logged |
|
|
|
Hippo
Forum Guru
Arimaa player #4450
Gender:
Posts: 883
|
|
Re: bot sharp's AI
« Reply #7 on: Mar 11th, 2011, 6:33pm » |
Quote Modify
|
Wow, nice I was thinking about somethink like that, but never started codding. So it is basically alpha beta with iterative deepening but with "reason" ordering and huge prunnig (branch shortening).
So you generate and order all moves and after that you start prunnig. I was thinking about generate moves by trying to find "answers". The idea to try all moves and evaluate what answers it found does not look much slower and seems much easier to define.
The problems with alpha-beta unfinished search of given depth at given time and comparing static evaluation of positions in different depth remain.
The same problem with time management would be easier with MCTS like scheme (with moves chosen with probability according to the move "reason" ordering).
That would be very simillar to the method human players are playing, but them limited to around 4 moves (in depth as well as breadth).
I would be scared to play such a bot. I am already scared to play sharp2011 .
I was sceptical by bot's improvement during 2010, but the "reason" ordering was very big step forward.
|
| « Last Edit: Mar 11th, 2011, 6:35pm by Hippo » |
IP Logged |
|
|
|
chessandgo
Forum Guru
Arimaa player #1889
Gender:
Posts: 1244
|
|
Re: bot sharp's AI
« Reply #8 on: Mar 12th, 2011, 5:59am » |
Quote Modify
|
Thanks for the interesting insight.
|
|
IP Logged |
|
|
|
omar
Forum Guru
Arimaa player #2
Gender:
Posts: 1003
|
|
Re: bot sharp's AI
« Reply #9 on: Apr 1st, 2011, 4:03pm » |
Quote Modify
|
on Mar 11th, 2011, 5:44pm, lightvector wrote:
But coding by hand how to combine and weight such a variety of things by hand is really hard, especially when each one has its own exceptions. That's where the machine learning comes in.
So what I'm doing is taking Arimaa moves and computing feature vectors from them, where each entry in the vector indicates something like "adds defender to trap x" or "moves elephant to square x", or "captures horse", or "suicides own horse". From there, you can apply standard supervised-learning algorithms for classification and ranking (such as bayesian methods, support vector machines, neural nets, etc) to try to learn an appropriate ranking function. I've been experimenting with some algorithms, and have gotten some great results for Arimaa.
|
|
Wow, essentially you are classifying the moves. That's quite an interesting approach. It certainly sounds closer to how humans play. Good luck with the Thesis. I would suggest also submitting a brief paper about this approach to the ICGA journal as well.
|
|
IP Logged |
|
|
|
|
Home
Help
Search
Members
Login
Register
Reply
Notify of replies
Send Topic
Print