Chess is said to be a game of perfect information, meaning that all the information is visible to both sides at all times. This allows a computer to play chess by searching the game tree for the best possible move. Thus a simple chess engine is composed of three major parts that define how it plays:

1. A move generator
2. An evaluation function
3. A search function

The same basic components are present in any game of perfect information, such as checkers, connect 4, tic tac toe.

Move Generator

A move generator is capable of producing all legal chess moves given a particular board representation. This function is needed by the search to produce moves in order to traverse the game tree (more on this later). It's critical that this part of the chess engine be very fast as it's going to be called perhaps millions of times for a single move.

There's a lot of information to take into account in this part as well, such as castling information, captures, en passant, 50 move rule, double jumps and promotions. In TSCP, Tom uses a 'bits' component in his move structure to store such information, as follows (from defs.h):

/* This is the basic description of a move. promote is what
 piece to promote the pawn to, if the move is a pawn
 promotion. bits is a bitfield that describes the move,
 with the following bits:

 1    capture
 2    castle
 4    en passant capture
 8    pushing a pawn 2 squares
 16    pawn move
 32    promote

 It's union'ed with an integer so two moves can easily
 be compared with each other. */

typedef struct {
    char from;
    char to;
    char promote;
    char bits;
} move_bytes;

Bitwise operations such as the union are fast and compact, making for a good storage medium. It can also be expanded on really easily -- if we wanted to add a boolean field for something else, we could just union 64 with the bits character without affecting 1 - 32. Neat eh?

Usually chess engines contain a 'pseudolegal' move generator which builds a list of moves based on basic piece movements. From there the moves are then pruned based on their legality, i.e., can't move somewhere if your king is in check, castling through check, etc.. More on this in another post.

The Evaluation Function

The evaluation function is exactly what it sounds like. It looks at a board state and gives it a score -- typically positive if the board favours white and negative for black. It's essentially the source of chess knowledge for your engine. Simple evaluation functions can be constructed by tallying the pieces values for each side, i.e. 9 for the queen, 5 for the rook, 3 for the bishop and knight and1 for the pawn. More complex evaluation functions contain positional information such as the number of attacked squares per side, control of the center, doubled up pawns. It's also imperative that you make the evaluation function as fast as possible, for the same reasons as the move generator.

The Search Function

As I've said before, the search function searches the game tree and returns the best possible move. How does it do this? It employs the move generator to generate all possible moves from a position, then recursively calls the search function again on each of the newly created positions, decreasing the depth each time until it reaches a node where the depth is zero; from there it returns the evaluated board (depth is defined as the number of total turns the game tree searches, so 6 would be three moves by white and three moves by black below the current board position). That's probably really hard to understand right now (it was hard to write), so it might be a little easier with some pseudocode:

function minimax(node, depth)
    if node is a terminal node or depth = 0
        return the heuristic value of node
    else
        let α := -∞
        foreach child of node      { evaluation is identical for both players }
            let α := max(α, -minimax(child, depth-1))
        return α

(taken from http://en.wikipedia.org/wiki/Minimax) This algorithm is called minimax. The reason it's called minimax is that it tries to maximize the possible score for white at one search depth, and minimizing the score for white at the next. This allows us to grab move which leads to the best possible score for white (or black) at the end. It's basically a bruteforce to search all possible positions for the best one. Now this isn't very efficient is it? There are a lot of faster search algorithms out there, I'll just name a few for reference:

• Alpha beta pruning, which allow us to grab the same principle variation as with the minimax search algorithm. It does so in a much quicker manner by introducing the concept of "pruning" in that if a certain score is absolutely terrible after a search, it causes a cutoff where it stops search that branch of the tree. This is heavily dependent on move ordering. In this best case scenario, it allows for a sqrt() speedup compared to minimax, and in the worst case scenario, it's just as good as the minimax.
• Negascout, which has been shown to speed up chess searches by ~10%. It's essentially the same as the principal variation search for all practical purposes.
• MDT(f) -- which is proven to be very fast, but is heavily dependent on transposition tables (more on this later too)
• SSS* -- also dependent on transposition tables I believe.
• Aspiration Windows, which allow for a more selective pruning of the search tree.

There's a whole lot more I want to add here: Quiescence Search, Transposition tables, etc, but that should be fine for now. I highly suggest you check out my links page for sites that can provide a better explaination that my own.

Happy Chessing.