Computer Chess Club Archives


Search

Terms

Messages

Subject: Help, please: best description of a modern chess program

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.