2. An Explanation of the Proposed Heuristic

From Barbarosa by Bevin Alexander,  the purpose of military strategy is to diminish the possibility of resistance. It should be the aim of every leader to discover and exploit the weaknesses of the enemy. This is the ideal strategy for winning battles and wars.

This advice goes back at least to Sun Tzu in the fifth century B.C., but it is easier said than done. We can also apply the principles of Bourcet's 'plan with branches' and Comte de Guibert's ideas to use mobility to concentrate superior strength against a point of enemy weakness. Perhaps Napoleon was right when he declared 'The whole secret of the art of war lies in the ability to become master of the lines of communication.'

In order to more accurately estimate the positional pressure produced by the chess pieces, it is proposed that we calculate and maintain a database of "potential mobility" for each chess piece 3 moves into the future, for each position we evaluate. The concept is similar to the attack "trajectories" proposed by Botvinnik.

We update this piece mobility database dynamically as we evaluate each new chess position.

This database lets us reward chess pieces for specific objectives they can accomplish in the future (such as 2 moves away from defending a piece or 3 moves away from attacking a square next to the enemy king). Note that the piece mobility we calculate is not itself the desired objective - it is the means through which we determine the pressure the piece can exert on a distant objective (such as an enemy piece).

This contrasts with traditional chess programs, which reward pieces for nearness to the center of the board or for having a large number of moves they can make (a simplification).

The traditional evaluation function used by most chess programs rewards pieces for sitting on squares. This concept works because a piece's position on the board "generally" translates into an offensive, defensive, and collaborative ability, and is relatively fast to calculate. Any beginner will tell you that he (or she) would rather have a knight prominently placed in the center of the board rather than on the back rank, unmoved. He or she may not be able to calculate what the piece can do 3 moves into the future, but generally a piece is better in the center than on the edge of the board.

But this type of "evaluation" (a piece value determined by location on the board only) eventually breaks down when we want to build a high performance system. There are many cases where a piece may need to temporarily sit on the edge of the board in order to accomplish an objective. Our search process may miss the opportunity to find this move sequence because our evaluation function penalizes the unfavorable location of the piece on the board and is not aware of (or searching for) any strategic objective in placing the piece there. Additionally, the traditional evaluation function performs well tactically, but not as well positionally. Most moves made at high level tournament games can benefit from a strong positional sense.

The proposed heuristic calculates what are effectively "maps" of what each piece can do 3 moves into the future. We establish "objectives" and reward our pieces for the potential to accomplish these objectives. We reduce our bonus for each move that it takes the piece to accomplish the desired objective. Additionally, we consider realistic restrictions on piece mobility when calculating the pressure each piece and create (see Chapter 3 for a more detailed explanation).

For example, let's consider pieces in the starting position. What does our "unrestricted mobility map" look like for the white knight on the king's side of the board? (The squares on a chessboard are traditionally identified by using "algebraic" notation - we number the rows from bottom to top from 1 to 8 and letter the columns from left to right from a to h. The white knight in question would therefore be on square g1.)

1 move map (black knight represents potential move):

2 move map (moving a piece out of the way or doing nothing takes a move):

3 move map:

Here are some worthwhile objectives: attacking enemy pieces, defending friendly pieces, attacking squares near our opponents king (especially involving collaboration), minimizing our opponents ability to attack squares near our own king, having large amounts of future mobility (as a means to exert pressure, not an end in itself), restricting the mobility of enemy pieces (specifically, their ability to accomplish objectives), etc. In this way, we are "getting real" about what the piece can do. The bonus we give the piece is 1. a more precise estimate of the piece's ability to accomplish objectives that have value and 2. operationally based on "real" things present on the chessboard. Therefore, our evaluation function will be more accurate. It is still an estimate, but it is more accurate than simply giving a piece a bonus for sitting on a square. The goal here is to focus our search efforts on likely moves, and to produce fast cut-offs in our search tree.

The traditional evaluation is not specific - it is only a rough estimate of the piece's offensive, defensive, and collaborative ability, and can cause the machine to waste time searching many positions that don't matter. However, this method offers a focus that is useful because the evaluation can be performed faster. In certain tactical situations, advantageous moves can be discovered simply by trying large number of moves.

Let's look at what Claude Shannon (born 1916, died 2001), the father of information theory (and a pretty smart guy) said about the chess playing computer in 1950 in his groundbreaking paper "Programming a Computer for Playing Chess"

http://www.pi.infn.it/~carosi/chess/shannon.txt

Shannon describes in his paper the basic software "structure" of a modern chess playing computer program. His "evaluation function", described in his Appendix, is a little simplistic.

His last section, number 8 "Another type of Strategy", is of interest.

"The strategies described above [in his paper] do not, of course, exhaust the possibilities, In fact, there are undoubtedly others which are far more efficient in the use of the available computing time on the machine."

"...it [traditional chess engine] plays something like a beginners (sic) at chess who has been told some of the principles and is possessed of tremendous energy and accuracy for calculation but has no experience with the game."

"To program such a strategy [an advanced evaluation function] we might suppose that any position in the machine is accompanied by a rather elaborate analysis of the tactical structure of the position suitably encoded. ...in short, all the facts to which a chess player would ascribe importance in analysing tactical possibilities. These data would be supplied by a program and would be continually changed and kept up-to-date as the game progressed. The analytical data would be used to trigger various other programs depending on the particular nature of the position. A pinned piece should be attacked. ...It is not being suggested that we should design the strategy in our own image. Rather it should be matched to the capacities and weakness of the computer."

Shannon thought that there were other possible ways to build an evaluation function for a computer chess program, but he was not able to make his ideas specific. Shannon's paper is remarkable for its time and for the fact that computers were relatively recent inventions, in addition to being somewhat slow, expensive, unreliable, limited in memory, and difficult to program.

Recently, Gerd Gigerenzer (see chapter 6) has published works on the subject of ecological rationality - the idea that successful heuristics are adapted to the information or cues present in the environment and to the capabilities of the person/ or agent involved.

Let's see if we can take the above ideas and put them in a design specification.

Continue to next section