c# 2.0 chess project

Talking about chess programming using C#.

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.


0 Comments:

Post a Comment

<< Home