Author |
Topic: Haizhi's Arimaa Project (Read 5348 times) |
|
haizhi
Forum Senior Member
Arimaa player #350
Gender: 
Posts: 45
|
 |
Re: Haizhi's Arimaa Project
« Reply #30 on: Jun 28th, 2005, 3:43am » |
 Quote  Modify
|
After I carefuly read what you wrote again, I will say, since you described it that way, then in my understanding TD() is a linear system, non-linear is not supported here.
Sorry for reply too fast.
There is a big name in our department knows those stuff very well, Machael Buro, his world champion program has over 1 million weights that auto tuned.
I don't like these "run a month to get a result" methods.
|
|
 IP Logged |
|
|
|
jdb
Forum Guru
Arimaa player #214
Gender:
Posts: 682
|
|
Re: Haizhi's Arimaa Project
« Reply #31 on: Jun 28th, 2005, 6:12am » |
Quote Modify
|
Quote:| I understand that you could turn it into a linear model by making 16*16 features. |
|
Its interesting the difference in approaches.
My initial thought was to make a 16*16 lookup table, as you suggest, and fill in the values by hand. This way it is easy to see what each parameter is. If the bot overvalues 12 pieces vs 10, one can just change that parameter. Tweaking an equation, for me, would be much harder on my brain.
|
|
IP Logged |
|
|
|
99of9
Forum Guru
Gnobby's creator (player #314)
 
Gender:
Posts: 1413
|
|
Re: Haizhi's Arimaa Project
« Reply #32 on: Oct 10th, 2005, 7:59pm » |
Quote Modify
|
I just finished reading Haizhi's thesis. I think one of his most important contributions is this:
He noticed that very rarely is a move played (in a human game) where all 4 steps are unconnected. Usually there is a push, a pull, a double, triple or quadruple single-piece move, or an unfreeze-then-move combination. However, his computer calculates that a large proportion of the possible moves actually do have all 4 steps unconnected.
He believes that humans are objectively correct to basically ignore these possibilities. The rationale he gives is that it's rare for single steps (often in unconnected regions of the board) to all be vital all at once.
Because of the vast potential savings in the number of moves he must consider, he totally cuts such moves out of his move generator.
I hope that summary does justice to his important contribution. Now, here are my questions to you all:
1) Do humans ignore these possibilities because they are nearly always objectively worse than moves including a "step-combo"? Or do they just ignore them because they're focussed on acheiving a particular goal at a particular time, and cannot keep 4 different plans in their mind at once?
2) Do you think bomb plays 4-unconnected's with the same frequency that an 1800 rated human does?
3) Can you think of some simple examples where a 4-unconnected is undoubtedly the best move?
4) Can you find some "normal" game positions where a 4-unconnected is undoubtedly the best move?
I must say, that although I had a previous hazy understanding of this phenomenon, I had never even considered making use of it within a bot. Even if Haizhi is a bit optimistic to completely cut these moves out, he's definitely onto something, and at the very least, they should be demoted in search importance.
|
|
IP Logged |
|
|
|
nbarriga
Forum Guru
Almost retired Bot Developer
Gender:
Posts: 119
|
|
Re: Haizhi's Arimaa Project
« Reply #33 on: Oct 10th, 2005, 9:38pm » |
Quote Modify
|
on Oct 10th, 2005, 7:59pm, 99of9 wrote:| I just finished reading Haizhi's thesis. . |
|
Is it available online somewhere?
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: Haizhi's Arimaa Project
« Reply #35 on: Oct 11th, 2005, 12:58am » |
Quote Modify
|
on Oct 10th, 2005, 7:59pm, 99of9 wrote:3) Can you think of some simple examples where a 4-unconnected is undoubtedly the best move?
|
|
How about this one?
Gold (to move) Rc1 Rf1 Hc4 Mf4 Ec8 Cf8
Silver mb4 eg4 rb7 re7
With four single steps Gold can guard all four traps and freeze both of Silver's rabbits. But this position is very contrived. I think it quite likely that the search speedup is worth completely ignoring the four-independent-step moves in practice. I concur that it's a very original and important idea.
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: Haizhi's Arimaa Project
« Reply #36 on: Oct 11th, 2005, 1:04am » |
Quote Modify
|
Oh, that reminds me of a potentially important improvement to bot_haizhi that is potentially easy to implement. He gives a horse hostage a value of zero, which is roughly correct when the horse is held hostage by an elephant, but when a camel holds a horse hostage it is a significant positive. Not all horse hostages are created equal.
I'd even consider noting that a camel holding a dog hostage isn't as good as a horse holding a dog hostage, but that doesn't have nearly the same significance in an age of frequent elephant/horse attacks.
|
|
IP Logged |
|
|
|
99of9
Forum Guru
Gnobby's creator (player #314)
Gender:
Posts: 1413
|
|
Re: Haizhi's Arimaa Project
« Reply #37 on: Oct 11th, 2005, 3:04am » |
Quote Modify
|
Yes, I am also interested in whether Haizhi plans to continue developing his bot now that he's got his degree.
|
|
IP Logged |
|
|
|
99of9
Forum Guru
Gnobby's creator (player #314)
Gender:
Posts: 1413
|
|
Re: Haizhi's Arimaa Project
« Reply #38 on: Oct 13th, 2005, 12:12am » |
Quote Modify
|
on Oct 11th, 2005, 12:58am, Fritzlein wrote:How about this one?
Gold (to move) Rc1 Rf1 Hc4 Mf4 Ec8 Cf8
Silver mb4 eg4 rb7 re7 |
|
Yep, that seems pretty clear  . I suppose if you scatter a few extra pieces around the board, a position like that even looks vaguely normal.
|
|
IP Logged |
|
|
|
omar
Forum Guru
Arimaa player #2
Gender:
Posts: 1003
|
|
Re: Haizhi's Arimaa Project
« Reply #39 on: Oct 14th, 2005, 5:48pm » |
Quote Modify
|
I don't think humans discount unconnected moves. If the situation requires it, they will consider them. I think such moves become critical in situations where both players have advanced rabbits and there are goal threats. You use some steps for defense and some for offense. The offensive steps are typically unconnected from the defensive steps. However, I think Haizhi is correct in that most of the time the moves are connected. This is a great contribution and should make the bots stronger. It will be interesting to see how bot_Haizhi will do in this years computer tournament.
|
| « Last Edit: Oct 14th, 2005, 5:48pm by omar » |
IP Logged |
|
|
|
|
Home
Help
Search
Members
Login
Register
Reply
Notify of replies
Send Topic
Print