Arimaa Forum - Print Page


    
      
        Arimaa Forum
        (http://arimaa.com/arimaa/forum/cgi/YaBB.cgi)
      

        Arimaa >> Bot Development >> moves generation
        
(Message started by: chessandgo on Apr 15^th, 2006, 9:24pm)

Title: moves generation
Post by chessandgo on Apr 15^th, 2006, 9:24pm

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

Title: Re: moves generation
Post by Fritzlein on Apr 16^th, 2006, 8:21am

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?

Title: Re: moves generation
Post by chessandgo on Apr 16^th, 2006, 12:00pm

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

Title: Re: moves generation
Post by chessandgo on Apr 16^th, 2006, 6:08pm

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

Title: Re: moves generation
Post by Janzert on Apr 16^th, 2006, 7:24pm

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

Title: Re: moves generation
Post by chessandgo on Apr 17^th, 2006, 2:38pm

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 ... ;D
Nice to read stronger guys thoughts anyway.

c u

Jean

Title: Re: moves generation
Post by jdb on Apr 17^th, 2006, 3:28pm

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.

Title: Re: moves generation
Post by chessandgo on Apr 17^th, 2006, 6:34pm

on 04/17/06 at 15:28:41, jdb wrote:

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 ??????