Author |
Topic: Haizhi's Arimaa Project (Read 5537 times) |
|
99of9
Forum Guru
Gnobby's creator (player #314)
 
Gender: 
Posts: 1413
|
 |
Haizhi's Arimaa Project
« on: May 23rd, 2005, 6:03pm » |
 Quote  Modify
|
Hey Haizhi,
Weren't you at one time working on an Arimaa bot as a project for your university degree? How did that go? Is your thesis available online? I'm sure many of us would be interested to read it.
Thanks
Toby
|
|
 IP Logged |
|
|
|
omar
Forum Guru
Arimaa player #2
Gender:
Posts: 1003
|
|
Re: Haizhi's Arimaa Project
« Reply #1 on: May 30th, 2005, 6:13pm » |
Quote Modify
|
You might want to ask this as a comment to one of his games. He might see it sooner.
|
|
IP Logged |
|
|
|
haizhi
Forum Senior Member
Arimaa player #350
Gender:
Posts: 45
|
|
Re: Haizhi's Arimaa Project
« Reply #2 on: Jun 6th, 2005, 1:39am » |
Quote Modify
|
Thank you for remembering me and my bot, 99 and omar.
I am still working on building the bot ( in fact rebuilding it). A lot of stuff happend, I haven't graduated from UA, not yet, but got a very busy job a year ago, struglling in 2 frontiers ( in fact there were 3, I also got a familly to take care of). I couldn't give up my arimaa project, I selected it as my gruaduate thesis topic. Couldn't make out a showable bot ( and a MSc. thesis) in 3 years, I am the worst student of Jonathan's.
Thanks Fotland, I read his paper, it makes me rebuild my program. I found I made some fatal mistakes at the very biginning, for example, my search was move-based, not step-based! It hundreds times slower.
His evaluation function is really impressive. How can he do a 6-step local trap search, or a 8-step goal search? that is totally unthinkable to me. I spent a month but could not make out a 4-step one.
I spend a lot of time to adjust feature weights as well, didn't work. Jonathan suggest that I should try TD(lamda), let the machine do it for me.
Jonathan said searching deeper would beat a better evaluation function, so that was what I have been trying to do. Unfotunately it is very hard for arimaa, what make it worse is that I do have some ideas, but each one takes a lot of time to test.
Still a lot of stuff to do. But this years tounament I am sure my bot will show up.
|
|
IP Logged |
|
|
|
99of9
Forum Guru
Gnobby's creator (player #314)
Gender:
Posts: 1413
|
|
Re: Haizhi's Arimaa Project
« Reply #3 on: Jun 6th, 2005, 4:42am » |
Quote Modify
|
on Jun 6th, 2005, 1:39am, haizhi wrote:| Thank you for remembering me and my bot, 99 and omar. |
|
How could we forget the 48-hour Arimaa marathon man?
I'll look forward to seeing your bot in action later this year. By the way, I made the same mistake of using move-based search when I first started (that's what Gnobot_2004 was).
Congratulations on your family and your job. Some things are more important than arimaa  .
|
| « Last Edit: Jun 6th, 2005, 4:43am by 99of9 » |
IP Logged |
|
|
|
PMertens
Forum Guru
Arimaa player #692
Gender:
Posts: 437
|
|
Re: Haizhi's Arimaa Project
« Reply #4 on: Jun 6th, 2005, 9:26am » |
Quote Modify
|
Quote:| Jonathan said searching deeper would beat a better evaluation function |
|
I sincerely doubt that
|
|
IP Logged |
|
|
|
jdb
Forum Guru
Arimaa player #214
Gender:
Posts: 682
|
|
Re: Haizhi's Arimaa Project
« Reply #5 on: Jun 6th, 2005, 3:52pm » |
Quote Modify
|
I must agree with PMertens. There are several common features in games that require evaluation. Hostage pieces, elephant blockades and rabbit formation to name a few.
Clueless uses the move based approach in several places. The more I work on clueless, the more move based stuff seems to get added. Whether it will work out in the end is another story.
|
|
IP Logged |
|
|
|
haizhi
Forum Senior Member
Arimaa player #350
Gender:
Posts: 45
|
|
Re: Haizhi's Arimaa Project
« Reply #6 on: Jun 6th, 2005, 11:17pm » |
Quote Modify
|
Well, my english is not good enough, maybe I wasn't make it very clear.
About the "knowledge vs search", Jonathan got that idea in his early years experince in building chess program. Being a strong chess player himself, he once tried putting a lot of knowledge into the program, and found it doesn't work well. Another version that could search a little deeper tend to be much stronger.
He always emphasize the huge difference that search one ply deeper will create, and suggested me not putting a lot into the evaluation. But for Arimaa, searching deep is really difficult, I guess so far 12 step per min is the best we can hope. And we have to put much more stuff into the eva, otherwise the bot won't attack. The situation is like in GO.
I think Jonathan as a AI researcher has a tendency of loving those "brute-force" stuff, like history-heuristic, pattern database...for their high adapabilty. He doesn't show much interest in GO research, the reason I belive is same.
In his book he said he didn't trust marchine feature weight tuning much, I guess he already changed this opinion. He instructed one of his PhD student applied TD(lamda) on his chinook program, the result was very promising, they even published a paper on that.
Jonathan is alway very good to me, so I really want do somthing (academically) to repay him.
|
|
IP Logged |
|
|
|
99of9
Forum Guru
Gnobby's creator (player #314)
Gender:
Posts: 1413
|
|
Re: Haizhi's Arimaa Project
« Reply #7 on: Jun 7th, 2005, 1:48am » |
Quote Modify
|
on Jun 6th, 2005, 1:39am, haizhi wrote:| I am the worst student of Jonathan's. |
|
Even if this is true, there's no shame in being the worst of a fantastic bunch. I've read a number of papers from Jonathan's group, and they were all impressive.
Regarding machine feature-weight tuning. I tried a very primitive version of this, but I found that I got much greater improvements by simply adding more features that I knew about. I agree that it's important to tune your weights, but I found that I could do that quite effectively by hand after watching a few games my bot played.
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: Haizhi's Arimaa Project
« Reply #8 on: Jun 7th, 2005, 6:09pm » |
Quote Modify
|
on Jun 6th, 2005, 3:52pm, jdb wrote:I must agree with PMertens. There are several common features in games that require evaluation. Hostage pieces, elephant blockades and rabbit formation to name a few.
Clueless uses the move based approach in several places. The more I work on clueless, the more move based stuff seems to get added. Whether it will work out in the end is another story.
|
|
My intuition is very strong that move-based approach is better than a step-based approach. But why do I think this? I have neither practical experience nor any convincing theory.
Also I have a similarly strong intuition that bots need to get smarter more desperately than they need to get faster, and in particular that bots are too stupid at present to do much helpful pruning. Again, I have neither practical experience nor any convincing theory to support this position.
Probably both of my biases are based on nothing more than an assumption that computers need to think more like I think in order to play Arimaa better.
|
|
IP Logged |
|
|
|
omar
Forum Guru
Arimaa player #2
Gender:
Posts: 1003
|
|
Re: Haizhi's Arimaa Project
« Reply #9 on: Jun 7th, 2005, 9:55pm » |
Quote Modify
|
on Jun 7th, 2005, 6:09pm, Fritzlein wrote:
Also I have a similarly strong intuition that bots need to get smarter more desperately than they need to get faster, and in particular that bots are too stupid at present to do much helpful pruning. Again, I have neither practical experience nor any convincing theory to support this position.
|
|
I think Bomb's participation in the postal tournament was a good experiment in this regard. Since the humans were thinking for a few minutes about their move and Bomb was thinking for a few hours about it's move, the situation was as if Bomb was running on much faster hardware. I remember seeing a comment that David Fotland made after seeing some of Bombs loses in the postal games that having Bomb run faster to search deeper would not be of much use and that the place to focus for future improvements was in the evaluation.
|
| « Last Edit: Jun 10th, 2005, 8:53am by omar » |
IP Logged |
|
|
|
haizhi
Forum Senior Member
Arimaa player #350
Gender:
Posts: 45
|
|
Re: Haizhi's Arimaa Project
« Reply #10 on: Jun 8th, 2005, 12:27am » |
Quote Modify
|
[I remember seeing a comment that David Fotland made after seeing some of Bombs loses in the postal games that having Bomb run faster to search deeper would not be of much use and that the place to focus for future improvements was in the evaluation]
I don't agree with you guys on that. The problem in Arimaa is that the branching fator is so huge that even give a computer days it still searches very shallow. I guess in a postal game Bomb still cannot search more than 16 steps (4 moves). Deep blue and Chinook can easily search 16-18 moves every minute, that is a huge difference.
I doubt the potential of improvements in the evaluation, you put more stuff in it, the program will become slowerand slower, and there are too many exceptions.
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: Haizhi's Arimaa Project
« Reply #11 on: Jun 8th, 2005, 1:04am » |
Quote Modify
|
on Jun 8th, 2005, 12:27am, haizhi wrote:Deep blue and Chinook can easily search 16-18 moves every minute, that is a huge difference.
|
|
Well, certainly, if you could make a computer that would search 16 moves (eight moves for each side) in Arimaa, it could be a very, very strong opponent even if its evaluation function were very stupid (for example only goal and material, nothing positional). I don't dispute that (16-move search + dumb evaluation) would overwhelm a bot with (4 move search + smart evaluation), as well as overwhelming all human players.
But how can you possibly get a computer to search that deep? No computer on Earth is fast enough to look at that many positions even just for goal. The only way to get deep search is to prune away bad moves, and right now Arimaa bots are too stupid to prune away bad moves.
Since you can't look at all moves deeply, how can you tell an Arimaa bot which moves to look at deeply? For chess it is pretty easy to prune based on material only. Also one can do search extensions based on forcing moves likes captures and checks only. A simple (i.e. stupid) idea can do lots of useful pruning for chess. But in Arimaa there are rarely credible goal threats in the opening, and often no captures for ten or twenty moves. The computer might have a totally losing position before it gets tactical enough to prune away bad moves by any simple idea.
In short, it seems to me that a smarter evaluation is needed, not so much at the end of the search tree as in the middle to tell which moves are worth examining. If you could generate a list of only, say, 100 moves in every position which are worth looking at, that would be a huge accomplishment. But how can one do that by any simple means?
To put my argument another way, the dichotomy of deep search vs. smart evaluation seems false in the case of Arimaa, because it seems to me that you can't even get deep search unless you first have smart evaluation. Please enlighten me if I am missing the point.
|
|
IP Logged |
|
|
|
jdb
Forum Guru
Arimaa player #214
Gender:
Posts: 682
|
|
Re: Haizhi's Arimaa Project
« Reply #12 on: Jun 8th, 2005, 8:32am » |
Quote Modify
|
There are a few other types of moves that can be called second rate, even in the opening. Moves likes captures and freezing an enemy piece are usually worth investigating.
Here is a list of types of moves one could prune/sort moves on: (in no particular order)
a) does it capture a piece?
b) does it suicide a piece?
c) is it a goal threat?
d) does it allow an enemy goal threat?
e) does it advance a rabbit?
f) does it advance an enemy rabbit?
g) how does the move effect elephant mobility?
h) does it place a major piece in a risky location?
i) does it threaten an enemy major piece?
j) does it threaten to capture an enemy piece?
k) does it allow the enemy to threaten an enemy piece?
l) does it send a minor piece off the back three ranks?
m) reversible moves
This list is by no means exhaustive. All of these items can be approximated relatively quickly and would help to focus the search on moves that are more likely to be reasonable.
For example, in the opening sending a piece (other than the elephant) down the board on its own, could be flagged as highly questionable and given only brief consideration.
|
|
IP Logged |
|
|
|
haizhi
Forum Senior Member
Arimaa player #350
Gender:
Posts: 45
|
|
Re: Haizhi's Arimaa Project
« Reply #13 on: Jun 9th, 2005, 1:10pm » |
Quote Modify
|
on Jun 8th, 2005, 1:04am, Fritzlein wrote:
In short, it seems to me that a smarter evaluation is needed, not so much at the end of the search tree as in the middle to tell which moves are worth examining. If you could generate a list of only, say, 100 moves in every position which are worth looking at, that would be a huge accomplishment. But how can one do that by any simple means?
|
|
Fritzlein , the way you descript is so-called "forward pruning", it seems natual as it is the way that human play games, but unfortunately it doesn't work well in game building. The problem is: even you are 95% confidence that the best move is in your 100 selected moves, if the search goes 10 ply deep, the chance that you finally miss that move is about 40%. The normal "after search" evaluation function can be rough, but this "before search" evaluation must be almost 100% accurate to really work, which is impossible, otherwise we don't need any search). That is the reason that usually people don't do it in the game building.
The biggest problem in letting the program have heavy knowledge is that the exceptions. A move that lost your elephant is bad, but in the case of supporting a rabbit to reach the goal it is not. You will end up putting more and more context into the program, that cannot last forever.
My point is, beside improving the evaluation function, I belive we still have a big potential in the search itself. We know that changing the search from move-based to Step-based alone makes it hundreds time faster, Transportation table, null move, move ordering ( iterative deepenning, killer moves, history heuristic)...all these methods enable us to search 12-step, but they are not the end of the story, what we need is to discover more methods to reach deeper.
|
|
IP Logged |
|
|
|
jdb
Forum Guru
Arimaa player #214
Gender:
Posts: 682
|
|
Re: Haizhi's Arimaa Project
« Reply #14 on: Jun 9th, 2005, 3:09pm » |
Quote Modify
|
Haizi, your comments regarding forward pruning are correct, when applied to games such as chess.
However, in arimaa, forward pruning may have a better chance. The search depth is, say, about 4 full moves. There are about 5000 moves in a standard position. (That is 5000 different reachable board positions). That leaves an ~81% chance of the PV having all best possible moves.
I also agree with you, that there are certain situations where search is required.
Time will tell what approach(es) work well. Best of luck with your arimaa program.
|
|
IP Logged |
|
|
|
|
Home
Help
Search
Members
Login
Register
Reply
Notify of replies
Send Topic
Print