Arimaa Forum - Print Page


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

        Arimaa >> Bot Development >> Quiescence Search
        
(Message started by: haizhi on Jul 26^th, 2005, 5:55pm)

Title: Quiescence Search
Post by haizhi on Jul 26^th, 2005, 5:55pm

In almost every bot's playing, we can see if a strong piece is at an avoidble lost possition, the bot sacrifices weak pieces just to provide fake protection and push the horizen of "big loss" further.

This problem is called "horizon effect". In other games like chess, normally a "Quiescence Search" can solve this problem, which means the search line will go deeper untill it reachs a stable ( no material loss) state .

But in arimaa, where every move is composed of up to 4 steps, Quiescence Search costs too much. So far I don't have any clue to solve it.

Anybody has somthing to say address this probelm?

Title: Re: Quiescence Search
Post by jdb on Jul 26^th, 2005, 10:36pm

This is how I attempted to handle the problem in clueless. It doesn't work all the time, but it might work ok as a starting point.

// Check for windmill
// 1) White elephant is touching trap
// 2) >=2 white pieces touching trap
// 3) =1 black defender touching trap (not elephant!)
// 4) >=1 black frozen 2 steps from trap

If all these conditions are met black is likely trying to push a catastrophe over the horizon. This setup would give a huge bonus to white.

Title: Re: Quiescence Search
Post by haizhi on Jul 27^th, 2005, 1:48am

Wow, I never thought another local search might solve this problem.

Good thinking! Would you mind if I use that in my bot?

I am working on TD(lamda) now. A 5-ply game takes about 1 minute, so I can run 1000+ games every day, should be enough to get a sound result.

BTW, Jeff, my surpervisor Jonathan Scheffer is curious about who you are, and we spend 10 minute searching on web today. No luck. : ) Hope you don't mind me asking, are you a professional game developer?

Title: Re: Quiescence Search
Post by jdb on Jul 27^th, 2005, 5:23am

Quote:

Would you mind if I use that in my bot?

That's fine with me. As far as I'm concerned, any ideas I mention can be used by anyone else.

Quote:

who you are

I just do this as a hobby in my spare time. I find it interesting.

Title: Re: Quiescence Search
Post by clauchau on Jul 27^th, 2005, 7:44am

I noticed most undisputable fake protections from young bots were like: the move only consisted in moving the sacrificed piece and the opponent could gobble it without altering anything else on the board either. No change on any other piece on both sides. That could be a fast specialized local search.

My next step would then be to allow additional changes on the board by the bot and compare the board evaluation before the change with after the piece is gobbled...

Title: Re: Quiescence Search
Post by RonWeasley on Jul 27^th, 2005, 11:20am

JDB's suggestion is a good example of how a better static evaluation function can overcome the horizon limitation.

Something else to consider in quiescence search is to experiment with the definition of a quiescent position. If I had time, which I haven't had in the recent past, I would like to try expanding the quiescence search to be sensitive to goal threats through sacrifices or majorities, blockade opportunities, and imminent trap attacks. Defining these may be hard and the expansion could make the search too large. The approach would have to be very selective. I think humans do this and the trick is to identify how we do it. I think arimaa is a game ideally suited for making progress in this area.

Title: Re: Quiescence Search
Post by Fritzlein on Jul 27^th, 2005, 8:08pm

on 07/27/05 at 05:23:48, jdb wrote:

I just do this as a hobby in my spare time. I find it interesting.

Most of the botbashing (or praising) attention has focused on Bomb, since Bomb is the champ. Recently, however, I played Clueless a few times and was impressed by its positional feel in some ways. I was reminded that Clueless only lost to Bomb on the tiebreak, and that coming close at all was extremely impressive given that Bomb had such a head start in development from the previous year.

Like Haizhi, I'm interested in who you are, and how you came to write such a great bot just in your spare time. Not that you have to share any personal information, but it's fun to speculate. What of your experiences contribute? Is your success based on technical excellence, or your own feel for the game, or engineering which is clever (as opposed to elegant)?

I guess nobody knew what sort of programming would work for chess until they tried it. Now, similarly, I'll just have to see who wins the Arimaa computer championships and ask them how they did it. Best of luck in the coming contest!