BYTE.com > Features > 2003
How to Write a Chess-Playing Program, Part 2
By Ihor Bobak
September 1, 2003
(How to Write a Chess-Playing Program, Part 2
: Page 1 of 1 )
In last week's article we considered theoretical issues influencing the "brain" of
a chess program. Now we will consider a practical implementation. Questions like "How do I program the transposition table?" "How do I choose the estimation function?" and "What data structures are best suited for chess?" are answered in this article.
To write a chess playing program we need to do a few things:
- Study the rules of chess
- Define the data structures and classes for handling things like the notions state,
the game tree, moves, etc.
- Develop a mechanism for move generation
- Invent the estimation function
- Implement the search algorithm
- Invent a user interface
This article will cover all these tasks except the last one: 2D graphics issues are not covered here. I'll use Delphi as the development tool.
Game Rules
Most people think they know all the rules of chess, but those feeling self-confident should look at this page in order to review them again. Believe me, you will find there something new unless you're a professional chess player.
Data Representation
The Board
Most chess playing programs (including ours) use the following board
representation. The board is represented as a set of 64-bit numbers called
bitboards. Each bitboard keeps some board characteristic. For example,
bitboard can keep the position of white pawns:
|
| Figure 1: Game position (to the left) and the corresponding bitboard |
The board is implemented in the following class:
TBoard = class
private
FCurrentPlayer: integer;
FBitBoards: array[0..ALL_BITBOARDS-1] of TBitBoard;
FHasCastled: array[0..
Page 1 of 1
BYTE.com > Features > 2003
|
