The search engine included in ChessApp is basically that of tscp with a few modifications.
The backbone of practically all chess-playing programs is some form of minimax algorithm. This is a way of looking ahead to find the best move. It assumes that the opponent is intelligent and that I have some way of scoring positions. It works like this: On my move, choose the move which maximizes my score. On my opponent's move, assume he will choose the move which minimizes my score. To see this, let's look at an example. Let us say that the position is:
It's white to move. The computer works out which moves it can play. Amongst these are Kxd7 and f7. Let us suppose that the computer looks forward a maximum of 2 half-moves. So part of its thinking will go like this: if I play Kxd7, he can play lots of moves which don't involve taking the pawn. That would leave me better off. But he could play Kxf6 which would leave us even. So his best move is that one, and the overall score for Kxd7 is that I will be even with him. If I play f7, I have a pawn on the seventh rank, which is good for me, and none of his moves reduce my score. So the overall score for f7 is better than even, so I'll play that move.
At the heart of ChessApp is just such an algorithm, though it has many refinements. The first is an obvious one - rather than maximizing the score on my moves and minimizing it on my opponent's move, I can regard my opponent's score as the negation of mine (opponentScore = -myScore) and maximize score for whoever is moving. This is the so-called negamax algorithm. This gives the following, neatly-defined recursive algorithm:
search(board, depth)
if depth is zero, return a score for the board calculated by an
evaluation function
Calculate all the possible moves for this board
for each move
make the move on the board
score = -search(board, depth - 1)
if score is the best so far
remember it and the move that led to it
take back the move
end for each
return the best score (and the best move)
The success of this algorithm relies heavily on how good an estimate of the worth of the position the function which calculates scores for boards is. Obviously, if a perfect function existed, we wouldn't have to look ahead at all: we'd just score the possible positions arising from the current one and make the move which led to the best one. Unfortunately (or fortunately, if you happen to love chess) this doesn't seem to be possible.
Obviously we also want all the components (the move generator, the board evaluator and the search algorithm itself) to operate at the fastest speed possible, so that we can search as many boards as possible in the time available.
A major refinement of negamax is so-called alpha-beta cutoff. Suppose I search the first possible move and I score 0 - i.e. the position arising from the first move is even. Suppose now that I take a look at the second move on my list, but when I look at my opponent's first possible reply, it turns out to score -10 (better for him than even). Well now it doesn't matter what his other possible moves score since the best I can possibly expect from my second move is -10 and I already have 0 from my first. So I can skip searching his other possible replies to my second move - they aren't going to change anything. We say that his reply refutes my second move. I have an upper bound of -10 on how well I will do playing that second move and since my first move scores 0, we know the actual score from the second move is going to be worse than that, and we don't need to calculate what it scores exactly. This is a win because I can search fewer, sometimes considerably fewer, boards. ChessApp v0.2.2 uses negamax with alpha-beta cutoffs. [Recent versions of ChessApp use negascout, a variant of negamax.]
Some further refinements: searching to a fixed depth is generally OK, but if there is a long series of captures in the play ahead, I might end up stopping searching in the middle of the series and get a completely wrong idea of how good the position is for me. Consequently, it is better to search to a fixed depth, and then look ahead until play "quietens down". This is called waiting for quiescence.