Zarkov, like all computer chess programs has several major sets of routines which allow it to play chess. Here is a very brief description of these routines which may help to give you a bit of insight into how Zarkov chooses its moves.

Zarkov maintains an array of numbers (called board[]) in memory which describes the current board position at any point in the search. Each element of this array corresponds to a particular square on the board with the contents of the array element containing a code denoting what type of piece is on that square. The index into the board array is composed of 4 bits for the rank followed by 4 bits for the file. In the opening position for example, the array element board[0] contains the code for a white rook, while array element board[0x74] contains the code for a black king. For each piece type the program has an array of offsets which are added to an origination square to generate a destination square. A simple test is made to eliminate moves in which the destination square lies off the board. For bishops, rooks, and queens the process is continued until another piece is encountered or the destination square is off the board. As an example, to compute the moves for a knight on square f3 the program would peform the following calculations:

Note that if the destination square falls off the chess board, bit 7 or bit 4 will be set. So, in C, the following code snippet can be used to efficiently generate moves for a knight.

KnightOffsets[9] = {0x0E,0x1F,0x21,0x12,-0x0E,-0x1F,-0x21,-0x12,0};
for (offset = KnightOffsets; *offset != 0; ++offset)
  {
    tsq = fsq + *offset;
    if (!(tsq & 0x88))                // Is the destination square on the board?
      {
        if (!(board[tsq] & friendly)) // And not occupied by a friendly piece?
          {
            AddMove(fsq,tsq);             // Add the tsq to the move list
          }
      }
  }

For generations chess Grandmasters have written books describing various positional elements which are good and those which are deemed poor. Some of these concepts are relatively simple to program, such as computing piece mobility and detecting doubled or isolated pawns. Other concepts such as piece cooperation or king safety are more difficult to define in strict mathematical terms even though they may be intuitively obvious to a human. The major factor contributing to Zarkov's evaluation is the material value for the pieces on each side. The basic piece values are: Pawn=100, Knight=325, Bishop=335, Rook=540, Queen=1050. Since most moves in a chess game do not lead to the win of material, the move choice is usually governed by the positional chess knowledge contained in the program. Zarkov contains about 100 positional 'heuristics' which are oriented toward developing pieces, creating piece mobility, achieving decent pawn structure, attacking the enemy king, promoting pawns etc... The material value of the pieces as well as the value of the positional bonuses varies depending on the total material remaining on the board. There are two main philosophies employed in computer chess programs:

A. Evaluate positional terms only once -- at the beginning of the search -- to generate tables containing the value of each piece on every square. At each position in the tree search the score is computed incrementally using these tables to determine how the previous move affected the positional score. This method is very fast and allows maximum search depth, but as the search gets deeper the piece-value tables become less relevant and the accuracy of the evaluation may suffer.

B. Evaluate positional terms on the fly, at every node visited during the tree search. The evaluation for a given node is computed as the sum of the positional scores for each piece on the board plus any global positional bonuses or penalties which may exist. This method involves much computation which slows the search down, but gives a more accurate evaluation of the position.

Zarkov mosty uses the latter of these two approaches, computing terms such as pawn structure, bishop and rook mobility, and king safety dynamically. This static evaluation of terminal nodes, combined with an effective tactical look-ahead procedure gives Zarkov a relatively "human-like" playing style and results in an increase in positional awareness as thinking time is increased. While an experienced human chessplayer does a very good job of integrating the static positional characteristics of a board position with the dynamic possibilities inherent in the position, the computers 'thought' process is much more rigid and a static evaluation may often prove inaccurate. To compensate for this the computer must 'look ahead' at as many variations as possible to get a more accurate evaluation of a position. This procedure is described in the next paragraph.

From the early 1970's until the early 1990's, most of the top computer chess programs used an exhaustive "full width" search which generates all moves from a given position and searches each of the moves by generating and making all replies to that move, responses to each reply and so on to a fixed depth. At the end of the fixed depth search a "quiescence search" is performed which typically looks at only capturing moves and may go quite deep, until no more captures remain. The score from the terminal nodes is backed up the tree (with the assumption that each side will play the best move) to provide a score for each candidate at the starting position. This search is conducted iteratively -- starting with a one ply (a "ply" is a half-move) fixed depth search, followed by a two ply search and so on until the target time limit is reached. There are two major problems with this search approach.

A. Since the search considers all moves, it spends a considerable amount of time on ridiculous move sequences which would never occur in actual play. In the opening position for example, a full width search would investigate such brilliant possibilites as 1. Nh3 e5 2. Ng1 .... It would appear that if there are 35 move choices at each ply in the search that the full width approach would have to examine 35*35*35 = 42875 positions. This is not the case however, a technique called alpha-beta pruning which is briefly explained here reduces this number quite drastically. In the example above, once the computer has found that the reply 1. ... e5 returns a score for Nh3 which is worse than that for another candidate which has previously been evaluated the program does not need to consider other moves which refute Nh3, it already knows that it is inferior since black had at least one good reply. Still, even with the alpha-beta algorithm, the full-width search wastes a lot of time on unlikely positions.

B. The program can delude itself by playing delaying moves such as checks and captures which postpone unhappy events until they occur beyond the depth of the full-width search. This is called the "horizon effect" and while the it is much less common on today's fast machines than it was 10 years ago, it is still an issue.

Zarkov attempts to improve on the full-width search approach by pruning the search tree resulting from moves which it deems are blunders or are significantly poorer than other candidates. This saves a considerable amount of time which is used to analyze more promising lines of play. To do this, Zarkov employs a combination of "null-move" search, "reduced-depth" search, and threat heuristics to determine when to prune the tree. In addition to pruning, Zarkov extends the nominal depth of search on sequences of forced moves to help overcome the disastrous "horizon effect". These enhancements significantly improve the tactical awareness of the program.

To increase variety and help Zarkov achieve reasonable positions early in the game, Zarkov uses a positional based opening book. This opening book was created by taking many thousands of games played by strong human players and storing the positions arising from the first 40 or so moves played in each game. Positions which do not have at least three wins to their credit are eliminated, leaving only "reasonble" opening positions. When playing a game, before computing it's move Zarkov checks each of the legal moves to see if it reaches a book position. If multiple candidates exist, Zarkov gives priority based on the number of occurances of each position. When Zarkov is "in book" it will respond with it's move immediately and save time on its clock for use later in the game. Zarkov recognizes book transpositions so that book knowledge will not be lost when move order is altered.

Zarkov stores positions in which the score changes significantly between a shallow search (about 2 plies) and a deeper search in a file called a "learn table". These positions are retrieved at the start of each game and allow Zarkov to "remember" things that it previously discovered. This helps it to avoid making the same mistake(s) game after game, although it is not really learning much since it cannot apply this knowledge except when exact position matches occur.