Author: Dann Corbit
Date: 15:22:58 04/01/04
Go up one level in this thread
On April 01, 2004 at 17:33:13, Artem Pyatakov wrote: >Hello CCC, > >I would like to once again ask for your help. I am looking for a good >description of the basic components of a modern, state-of-the-art > >chess program with the emphasis on clarity. Basically something that clearly >documents various part of something like Crafty, or a less > >strong program, with general descriptions of the various heuristics, but with >enough detail for each one. (Perhaps even some source that > >would motivate each heuristic instead of focusing on implementation?) > >I have found a couple of such descriptions in academic papers, but though I >would ask the CCC for some more sources. I am planning to use > >this description a starting point for my discussion of the "modern chess >program" in my thesis. > >I am also considering various ways to structure my discussion of the anatomy of >the chess program (instead of just laundry-listing all > >heuristics), and here is one of the ways I am thinking about doing it (very >priliminary, be gentle). The idea here is to consolidate many > >different components of a chess program into logical areas. Again the focus is >on making it conceptually simple, not to make it an > >implementation manual: > >1. Search algorithms > 1.1 Discussion focused on PVS NegaScout and all the algorithms leading up to >it like MiniMax and AlphaBeta For minimax, be sure to tell prospective programmers not to waste time implementing it. > 1.2 MTD > 1.3 IDA People use iterative deepening two ways, but it is not applied to the A* algorithm in practice, unless you know of someone who is doing it. >2. Evaluation function > 2.0 Discusses important aspects of the eval - material, king safety, etc. > 2.1 includes discussion of qsearch, motivated by the fact that qsearch is only >really necessary to make a correct evaluation. Sounds kind of important. (e.g. "Don't use it unless you want to get a good answer." >Side question: has anyone seriously considered abandoning qsearch in favor of an >evaluation that can take non-quiesced positions into account? If you keep a table of the counts of attack by piece type for each square, you don't have to bother with quiescence. The question in that case is whether it is better to do the work of updating the tables or to do the work of quiescence. > 2.2 Mentions pawn hash tables as useful shortcuts for eval > 2.3 Talks about eval tuning > >3. Algorithms to guide/speed up the search. The key role is to facilitate >transfer of information from one part of the tree to the other, > >and from one search iteration to another (for IDA). > 3.1 Exact Memory > -Transposition table (exact because the position has to match EXACTLY for the >suggested move (or cutoff) to be used) > -EGTBs, Opening book (can be viewed as a form of permanent hash tables, its >somewhat of a stretch, but I view them as presenting > >suggestions to the search as well. Comments?) > 3.2 Fuzzy Memory (position doesn't need to match exactly) > -Killer heuristic > -History heuristic > 3.3 SEE (mention the simple MVV/LVA) > >4. Shaping the search tree (notice the difference from the last section, where >the techniques were all designed to search a given tree > >faster) > -Futility pruning (+extended, +razoring) > -Null move > -The dangers of pruning > -Extensions (check extensions, etc.) > >I know there are probably a lot of areas missing, since this is very, very rough >(and I need to go for now). CCC, do you have suggestions? > >What major things did I miss? 1. EGTB and bitbase perfect knowledge 2. Opening books 3. Board representations 4. Book learning 5. Position learning 6. TD-lambda learning >Thank you very much as always. The replies in the forum (when I do get them :-) >) are very useful. > >Artem
This page took 0.01 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.