Author: Artem Pyatakov
Date: 14:33:13 04/01/04
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 1.2 MTD 1.3 IDA 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. Side question: has anyone seriously considered abandoning qsearch in favor of an evaluation that can take non-quiesced positions into account? 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? 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.