Author |
Topic: moves generation (Read 1420 times) |
|
chessandgo
Forum Guru
Arimaa player #1889
Gender: 
Posts: 1244
|
 |
moves generation
« on: Apr 15th, 2006, 9:24pm » |
 Quote  Modify
|
Hello,
I'm trying to program a bot these days, and it seems to me that the crucial point is move generation. If we manage to create them in a nice order (so that the first ones are among the most relevant, if this has sense), we should be able to get good bots.
Does anyone have an idea ? How do the real programmers do ? That's unfortunately the thing for which I have no idea at all ...
Thanks a lot, I hope you won't mind when Melissa will beat you all 
Jean
|
|
 IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: moves generation
« Reply #1 on: Apr 16th, 2006, 8:21am » |
Quote Modify
|
I won't be happy when Melissa can beat all of us humans  , but I will be happy when it can beat all the current bots, since that will mean new challenges for us. 
Did you see BlackKnight's post about how bot_V generates moves? (8th post in this thread: http://arimaa.com/arimaa/forum/cgi/YaBB.cgi?board=devTalk;action=display ;num=1144302191 ) He is using this move generation for forward pruning, but it seems to me you could just as well use it for move-ordering in a brute-force search. After you generate the useful moves, you would then have to generate all the other moves, including duplicates, but duplicates can quickly be discarded, right?
|
|
IP Logged |
|
|
|
chessandgo
Forum Guru
Arimaa player #1889
Gender:
Posts: 1244
|
|
Re: moves generation
« Reply #2 on: Apr 16th, 2006, 12:00pm » |
Quote Modify
|
Yes I saw Blacknight's post ; it's indeed that kind of thing I'm looking for, but maybe I should have written a more precise question ... Anyway, thanks for your answer, I'll be back when i'll be able to tell it better
c u
Jean
|
|
IP Logged |
|
|
|
chessandgo
Forum Guru
Arimaa player #1889
Gender:
Posts: 1244
|
|
Re: moves generation
« Reply #3 on: Apr 16th, 2006, 6:08pm » |
Quote Modify
|
ok, maybe here is a more precise question : generating steps looks easy, but I'd like to generate full plys ... It looks somewhat hard, even having defined what is a potentially interesting move. I found nothing more clever than combining the "interesting" k-steps moves with each piece to sum up to 4, but I feel like going like a wrong way ...
Does almost anyone look for steps ?
Jean
|
|
IP Logged |
|
|
|
Janzert
Forum Guru
Arimaa player #247
Gender:
Posts: 1016
|
|
Re: moves generation
« Reply #4 on: Apr 16th, 2006, 7:24pm » |
Quote Modify
|
Although probably not exactly what you're looking for, you might want to take a read through Haizhi's thesis from last year. http://www.cs.ualberta.ca/~haizhi/zzz.doc
It had some interesting ideas in move generation.
Janzert
|
|
IP Logged |
|
|
|
chessandgo
Forum Guru
Arimaa player #1889
Gender:
Posts: 1244
|
|
Re: moves generation
« Reply #5 on: Apr 17th, 2006, 2:38pm » |
Quote Modify
|
hehe yes indeed, thx for the link looks like he doesn't believe in ply-search .... I already see the picture : Melissa will play really bad, and when I'll ask why, everyone will answer : do step-search ... 
Nice to read stronger guys thoughts anyway.
c u
Jean
|
|
IP Logged |
|
|
|
jdb
Forum Guru
Arimaa player #214
Gender:
Posts: 682
|
|
Re: moves generation
« Reply #6 on: Apr 17th, 2006, 3:28pm » |
Quote Modify
|
Clueless starts by generating all capture moves then switches to the normal push/pull/slide moves. It would be worth a try to generate other types of interesting moves early on. Maybe moves that protect a trap or threaten a piece.
|
|
IP Logged |
|
|
|
chessandgo
Forum Guru
Arimaa player #1889
Gender:
Posts: 1244
|
|
Re: moves generation
« Reply #7 on: Apr 17th, 2006, 6:34pm » |
Quote Modify
|
on Apr 17th, 2006, 3:28pm, jdb wrote:| Clueless starts by generating all capture moves then switches to the normal push/pull/slide moves. It would be worth a try to generate other types of interesting moves early on. Maybe moves that protect a trap or threaten a piece. |
|
Sure ! The way I see it, one could only generate a tiny fraction of "interesting" moves, then have a quick look at others, and even skipping them with high probability ... the 'interesting moves" being those wich puch or pulls an enemy piece, enforce control of a trap, unweaken a weak piece, unfreezes a forzne piece ... etc. These moves should anly represent a little fraction of the total, is that right 
|
|
IP Logged |
|
|
|
|
Home
Help
Search
Members
Login
Register
Reply
Notify of replies
Send Topic
Print