The Main Principles of a Chess Engine

The main ideas behind a chess engine can be easily understood. The Maple worksheet in Every Chess Configuration produces a unique encoding for each board configuration BC, which will be a number in {0,...,t-1}. This number is then passed to the Move Generator, which generates all legal configurations that result from BC. Each such configuration is then passed to the Evaluation Function, which generates a real positional value PV, based on a specific list of criteria. The next best move will be the configuration which maximizes PV. Using explicit steps:

  1. Construct a list of criteria, giving points for each positional or tactical advantage on a specific configuration.
  2. Start with any legal configuration: BCÎ{0,1,2,...,t-1}
  3. Let K be the set {1,2,3,...,k}, with k being the cardinality of all legal configurations which result from BC in one move
  4. Pass configuration BC to Move Generator, to generate all legal configurations one move forward: {BC(i): iÎK}
  5. Pass generated configurations to Evaluation Function recursively (steps 4/5), to generate positional values based on 1: {PV(BC(i)): iÎK}
  6. Next "best" move will be BC(m): PV(BC(m))=maxiÎK{PV(BC(i)): iÎK}

The above list is fairly easy to understand, but quite hard to implement. There are several reasons:

First, it is obvious that the list of criteria should be as long and as detailed as possible, to avoid missing good moves.

Second, it's also fairly obvious that the recursion for steps 4/5 will be extremely time consuming, because the program has to generate all legal configurations n moves forward. Obviously, n has to be a function of some time constraint, otherwise the size of the table of generated moves will eventually grow beyond any reasonable memory bound in a few moves. The variation in quality between chess programs occurs because of differences in steps 1/4/5.

Back to Mathematics

Web Analytics

Valid HTML 4.01 Transitional