From nobody Sun Aug 12 16:22:53 2001 Path: news.ifm.liu.se!news.lth.se!newsfeed.sunet.se!news01.sunet.se!logbridge.uoregon.edu!dispose.news.demon.net!demon!shale.ftech.net!news.ftech.net!diablo.netcom.net.uk!netcom.net.uk!feed.textport.net!sn-xit-04!sn-post-01!supernews.com!corp.supernews.com!not-for-mail From: "Bruce Moreland" Newsgroups: rec.games.chess.computer Subject: Re: Move Generation And Quiescent Search Date: Sat, 11 Aug 2001 09:51:39 -0700 Organization: Posted via Supernews, http://www.supernews.com Message-ID: References: <9krj3d$2n3$1@oprah.cc.utexas.edu> <9l21ac$oe7$1@slb4.atl.mindspring.net> X-Priority: 3 X-MSMail-Priority: Normal X-Newsreader: Microsoft Outlook Express 5.00.2919.6600 X-MimeOLE: Produced By Microsoft MimeOLE V5.00.2919.6600 X-Complaints-To: newsabuse@supernews.com Lines: 72 Xref: news.ifm.liu.se rec.games.chess.computer:118607 If you search a fixed-depth tree, evaluate at the tops, and min-max it, you could get errors because the last move was QxP, leading to a score of +1, when the next move would be PxQ, which brings us to -8. There are a few ways to handle this. One is quiescent search. When you get to a tip node, rather than returning eval(), you call the quiescent search instead. This search is slightly different from the regular one. The first thing it does is call the eval function, and if the score is >= beta, it returns beta. Meaning, if the side to move is already ahead by a sufficient amount, it doesn't try to do anything. Assuming that the score is not >= beta, there is room for improvement, so it tries available captures. If one of them pushes the score to >= beta, it returns beta. Alpha is adjusted if necessary and it's returned at the end. If you implement the above exactly as described, you will end up searching a huge number of nodes, as you follow out long nonsensical capturing sequences. It's important to find some way to order the captures, at very least. One way is MVV/LVA, which stands for "most valuable victim/least valuable attacker". You order the moves from high to low, based upon a primary key that's the value of the taken piece. If there's a tie, you break it by ordering, low to high, based upon the value of the taking piece. So PxQ comes first, then NxQ, RxQ, QxQ, then PxR and so on. MVV/LVA is fast but it generates a lot of nodes. Another way is to do this via a static exchange evaluator (SEE). This is a function that resolves the captures to a single square and figures out what's the best each side can do. This function is fairly hard to write, and it's expensive to call, but the ordering is better, and you can do some pruning based upon its output. If a capture costs you a rook, why even do it? MVV/LVA won't let you make that determination. You can refine the SEE concept further by refusing to allow even winning captures if you are a long way behind. If you discover that you are 600 centi-pawns below alpha, you aren't going to cut off or get a improved score unless you win a whole queen, so you can reject winning captures that win pawns or knights or rooks. There are flaws with all of the above, but these all work to varying degree in practice. bruce "Robert E Green" wrote in message news:9l21ac$oe7$1@slb4.atl.mindspring.net... > Could you please talk a little bit more about the line "Think about how you are going to limit your quiescent search" > > I'm unclear about quiescent search in general (yep, I've STFI (searched the internet) on this and read all I could find) so > some quiescent-search-for-dummies would be all right as well :) > > Thanks! > > Bob G. > > >Think about how you are going to detect check. Think about how you are > >going to limit your quiescent search. Think about how you are going to > >promote pawns, in relation to the two previous things. Think about how you > >are going to write your evaluation function in relation to all of the above. > > > >bruce > > > > > > > >