c# 2.0 chess project

Talking about chess programming using C#.

Monday, November 29, 2004

Download link available

You can now download the project via the link on the left side of the page. Latest addition to the source code is a working quiescence search which has improved the tactical strength dramatically (although it has slowed things down a little but that's unavoidable). I still have not implemented King safety in the evaluation so the program does silly things like pushing its kingside pawns when castled. Speaking of the evaluation, it's basically an adaptation of Crafty's evaluation logic. It's meant to serve as a placeholder for you dear users, while I work on my own evaluation function. Right now fancy ideas involving static exchange evaluation(SEE) are swimming around in my head. I aim to model Karpovs' playing style of squeezing the opponent until he cries uncle. So stuff like mobility, space control and prophylaxis look good right about now. I estimate it will take me about six months with my schedule and all before I have something usable and better than the evaluation function that's in place right now.

Of course any bug fixes or suggestions are highly welcome. Oh yeah, the next post will be about using bitboards in your chess engine.

NOTE: You need Visual C# express to compile and run the project. Visual Studio.NET 2003 will not work. Download the free beta version of C# express by clicking the link below the project link

Friday, November 12, 2004

Chess Programming is tricky

Really it is. And some aspects are a lot harder than others. When I first started this project, I assumed move generation and book building would be my hardest problems. As it turns out, getting a bug free, fast and reliable search function is costing me more time than I believed possible. There all sorts of factors to consider. To use Negamax or not to use Negamax? MTD(f) or NegaScout/PVS? Verified or Adaptive null move pruning? How the *&**% do you get Lazy Evaluation to work reliably? Futility pruning? Quiescence search? History heuristics and move ordering? These are all the goodies in store for you to beat your brains out on once you get your basic move generation going.
And move generation is what I 'm going to focus on over the next few posts. How do you get your chess engine to reliably churn out moves for you? I will discuss three different approaches. The first obvious attempt would be to represent your chessboard as an 8 x 8 array or a single dimensional array of length 64. Lets assume you adopt the first approach with the form [rank][file]. Then we can say a piece at e1 can be indexed at [0][4]. A piece at d6 can be indexed at [5][3] etc. Using the single dimensional array introduces the difference of having a1 mapping to 0, b1 mapping to 1, c1 mapping to 2 etc. Continuing with the two dimensional example, how would you generate moves for your pieces? Assuming you have a white pawn at e2 , let's see how to generate moves for the piece.
The coordinate e2 maps to [1][4] in our two dimensional array. A pawn can step forward one square or two squares if it's the pawns first move. Pawn captures are done one step forward diagonally. Since our pawn is on e2, it must be in it's initial position. To check if the pawn can move one step forward, we must check that the square e3 ([2][4]) is not occupied. If that is the case we can check about moving two steps forward also. This is only true if the square e4 ([3][4]) is not occupied. For captures we should check that either or both the squares c3 ([2][3]) and f3 ([2][5]) are occupied by an enemy piece.
We can see that our array should at a minimum contain information about the type of piece at an index and the owner of that piece. That bring us to the subject of piece representation. My approach right from the start is to write the program in an object oriented way with pawns represented by a Pawn object, knights by a Knight object and so on. Since it's likely all pieces will have code in common, we can have them inherit from a common abstract class ChessPiece. So our representation could be something like this:

namespace ChessProject{

public enum PieceType { pawn, knight, bishop, rook, queen, king, none}

public enum PieceOwner {white, black, none}


public abstract class ChessPiece{

protected PieceType piecetype;
protected PieceOwner owner;
protected int boardIndex;
protected int pieceIndex;
protected bool isRemoved;

public ChessType(PieceType pieceType, PieceOwner owner, int boardIndex,
int pieceIndex){
this.pieceType = pieceType;
this.owner = owner;
this.boardIndex = boardIndex;
this.pieceIndex = pieceIndex;
isRemoved = false;
}

...................................
....................................

public PieceType Type{ get { return pieceType; } set{ pieceType = value;}}
public PieceOwner Owner{ get { return owner; } set{ owner = value;}}
public int BoardIndex{ get{ return boardIndex;} set{ boardIndex = value;}}
public int PieceIndex{ get{ return pieceIndex;} set{ pieceIndex = value;}}
public bool IsRemoved {get{return isRemoved;} set{isRemoved = value;}}
}
}
}

Using this bare skeleton we can declare our array to be of the type:

public struct BoardCells{
public PieceType type;
public PieceOwner owner;
public int pieceIndex;
}

The variable pieceIndex specifies where we can find our chess piece in an array for either player holding all his chess pieces. These indexes do not change during the game and neither does the array except for a promotion where the array is expanded to include a new chesspiece. The variable isRemoved indicates if a chess piece has been removed from the game and we skip generating moves for it if that's the case. So while generating moves for our pieces we can iterate through the array holding the current players pieces, find it's index on the board and depending on the kind of piece check for moves. Using the example of the white pawn at e2 and mix of pseudo code with real code (with all apologies):

//normal moves
if (boardCells[2][4].owner == PieceOwner.none){
...... add a move one step forward
if (boardCells[3][4].owner == PieceOwner.none){
......add a move two steps forward
}
}

//capture moves
if (boardCells[2][3].owner == PieceOwner.black){
...add a capture move to c3
}

if (boardCells[2][5].owner == PieceOwner.black){
.....add a capture move to f3
}


Of course care must be taken to update the board cells on each move of piece. If a piece is captured, we must use the pieceIndex variable to index the array of chesspieces holding pieces belonging to the owner and set the isRemoved variable to true. Each board cell when vacated by a piece must be reset.
Note there are a thousand ways we can go about using array representation. This is just part of the scheme I came up with when I tentatively started wading into the waters of chess programming. Another type of array representation 0x88 I did not bother with at all but you can investigate by clicking the link. I fiddled around with array based chessboard representation for a couple of weeks until I was satisfied about the usability of the scheme. Move generation is quite fast but for stuff like detecting checks, the performance does not inspire confidence. Still it's a good place to start for the novice chess programmer.
My next post will focus on the scheme I am using in my chess engine. Say hello to bitboards.

More stuff on chessboard representation.