Author: Pat King
Date: 05:50:32 02/06/04
Go up one level in this thread
An interpretation by a perpetual newbie. First, a quick summary of the thread so far: Chess program is based on search & evaluation. In the simplest view, they can be considered seperately. You search so many moves, you evaluate, you pick the biggest number. The result of the search depends on the nature of the evaluation. Point 1: quiescience - after searching so many moves, its hard to evaluate static positions accurately where theres hanging material, or someone in check. Hence, you search so many moves, call qsearch (which only stops when there are no more useful captures), and then evaluate. The result still depends on the evaluation (which typically assumes a static position), but hopefully will be more accurate. Point 2: search technique - the goal of the search is finding the best move, GIVEN an evaluation function, which summarizes what YOU, the author, thinks important. Any valid search technique should find the same best move leading to the same best position, based on YOUR evaluation function. Point 3: Alpha-beta, and its derivatives, are most efficient when they search the best move first. Since the whole point of the exercise is to FIND the best move, when we do the search, we're obviously GUESSING. The better our guesses (translate, MOVE ORDERING), the faster our search. Our move ordering, to be effective, must therefore be related to our evaluation. Bad move ordering shouldn't affect the answer, only how long it takes to find it. AB's reliance on move order is what couples the search and the evaluation. On with our thread, already in progress. On February 05, 2004 at 20:07:17, Robert Hyatt wrote: >On February 05, 2004 at 15:01:13, Bob Durrett wrote: > >> >>So, in modern engines, what are the determining factors which set the move >>ordering? What does choice of move ordering depend on and what does it not >>depend on? >> >>Bob D. > > >Big question. There are lots of things. The transposition table is critical to >supply best moves from previous iterations, which is why we did them in the >first place. The previous iterations have direct knowledge of what the evaluation function "thinks" of this position, which is why the hash move should be checked first. > Then killer/history heuristic moves, Based on prior search, and therefore again a good reflection of the evaluation function's "opinion". > good/even captures. Some use >their evaluation code to help in sorting the moves... > The first clear break between material and position. If the position terms of your eval are large enough, then it may pay to call your evaluation code in the current position. >The choice has to be based on whatever the goal of the search is. IE if you are >going to play "loser's chess" then you want to look at moves that give up the >most material first, etc... The goal determines the nature of the evaluation. Move ordering, in a sense, seeks to emulate the evaluation (guessing the best move) and so must also be based on the goal. My newbie recommendations to newbies: Have a qsearch from the beginning. Worry about move ordering before hash (transposition) tables. Generate & sort capture moves first (MVV/LVA). Generate & sort quiet moves last (history table). Worry about hash tables before lazy eval. Never take advice from a newbie ;) Pat King
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.