Author |
Topic: Quiescence Search (Read 1728 times) |
|
haizhi
Forum Senior Member
Arimaa player #350
Gender: 
Posts: 45
|
 |
Quiescence Search
« on: Jul 26th, 2005, 5:55pm » |
 Quote  Modify
|
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?
|
|
 IP Logged |
|
|
|
jdb
Forum Guru
Arimaa player #214
Gender:
Posts: 682
|
|
Re: Quiescence Search
« Reply #1 on: Jul 26th, 2005, 10:36pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
haizhi
Forum Senior Member
Arimaa player #350
Gender:
Posts: 45
|
|
Re: Quiescence Search
« Reply #2 on: Jul 27th, 2005, 1:48am » |
Quote Modify
|
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?
|
|
IP Logged |
|
|
|
jdb
Forum Guru
Arimaa player #214
Gender:
Posts: 682
|
|
Re: Quiescence Search
« Reply #3 on: Jul 27th, 2005, 5:23am » |
Quote Modify
|
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:
I just do this as a hobby in my spare time. I find it interesting.
|
|
IP Logged |
|
|
|
clauchau
Forum Guru
bot Quantum Leapfrog's father
Gender:
Posts: 145
|
|
Re: Quiescence Search
« Reply #4 on: Jul 27th, 2005, 7:44am » |
Quote Modify
|
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...
|
|
IP Logged |
|
|
|
RonWeasley
Forum Guru
Harry's friend (Arimaa player #441)
Gender:
Posts: 882
|
|
Re: Quiescence Search
« Reply #5 on: Jul 27th, 2005, 11:20am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: Quiescence Search
« Reply #6 on: Jul 27th, 2005, 8:08pm » |
Quote Modify
|
on Jul 27th, 2005, 5:23am, 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!
|
|
IP Logged |
|
|
|
|
Home
Help
Search
Members
Login
Register
Reply
Notify of replies
Send Topic
Print