c# 2.0 chess project

Talking about chess programming using C#.

Tuesday, June 07, 2005

Onward!!

I hate dead blogs and yet, there I was about to contribute one to cyberspace. It's been six months since I last posted and the reasons have been varied. Basically, I have just been incredibly busy but I have some breathing space now and I plan to continue writing about the minefield that is C# 2.0 chess programming for the benefit of all you out there who are interested (yeah, all three of you).
So I have to cultivate blog discipline and next post, I do promise to talk about those rotated bitboards. I also need to make some time to start working on UCHE version 2 and get the program to work with winboard. In the meantime, click the download link and enjoy.

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.


Friday, October 22, 2004

Step one: - Getting started

It's really incredible the amount of work it takes to write a chess program in ANY language. If you are using a new language (or beta in the case of c# 2.0), you are obviously going to spend a lot of time getting yourself acquainted with the language features. By far though, you will probably spend most of your time researching stuff about computer chess. There is plenty of stuff available on the internet. The trick is to find it. You should start with articles giving a general overview on chess programming. Perhaps the best is the series of articles written by François Dominic Laramée at gamedev.net.

There are some good technical papers available at Professor Bob Hyatt (the creator of Crafty) site. If you are ever going to succeed in implementing rotated bitboards by yourself without checking out any available source code (No need for that really. You can always read the source for my program), then this is the place to start. Be sure to download a copy of Crafty while you are at it and also get a copy of winboard. Details on how to hook it up to Crafty are available here.

The Hyatt papers were all I really needed to get a rotated bitboard implementation working. For another approach to move generation, check out Nagaskaki by Neels Groenewald and the various tips on his page. Once you got move generation working, you will probably spend the rest of the time on game searching algorithms. A good intro is the series of articles by Bruce Moreland. You should also check out a description of Negascout, MTD and verified null move pruning. Once you get deep into getting an efficient algorithm working, you should also take a look at Ed Schroeder's article , "How Rebel Plays Chess".
I just discovered a huge cache of articles on chess programming recently, available at http://digilander.libero.it/gargamellachess/papers.htm . I'm still wading through it all but already some it looks pretty useful.

That's all for now. I promise to have that source code up pretty soon.

Wednesday, October 20, 2004

first post - what this blog is about

Hello. This blog will detail my efforts to write a chess program in C# 2.0 comparable in strength to popular engines like Crafty and Rebel. I will post stuff about move generation using rotated bitboards, move pruning and C# specific issues with performance I encounter while writing this program. My primary motivation? Well, I am something of a chess nut and writing a chess program is something I have always wanted to do. It's not trivial and finding ways to tweak your program to provide great performance can keep you occupied for years. I decided to use C# 2.0 for the following reasons:

a) There are no chess engines coded in C# or any other modern object oriented language that I am aware of (no strong chess engines anyway). All the really strong engines are coded in C.
b) I am curious about finding out if I can tweak a chess engine written in C# to provide the kind of performance you normally get with a similar engine written in C or C++.
c) It's fun!

I started coding up my engine around the start of July 2004. I submitted a half finished entry to Microsoft's summer of express competition. Of course I didn't win (who would with a half finished program?) but if they live up to their promise, they will be posting the submitted code soon. It should provide a stark contrast to the current status of the program (I will post the updated code in a couple of days). I got the move generation and basic book building worked out. Right now, I'm beating my brains out over producing a reasonable search and evaluation function.

Oh, about me. Just graduated from UMASS Boston with a MS in Computer Science this summer. I live in Boston and my day job involves ASP.NET programming.