Zobrist keys

I am having trouble with Vicki and three-fold repetitions. So before anything else, I need to implement Zobrist keys. I might as well, since this would also need to be used with the transposition tables later on. I've heard that C's rand() function is not always random enough, so maybe in Vicki version 29.3 I'll get some random numbers here. :-)

So what do I need?

• A 64-bit random number generator which will populate 12 145-element arrays (for each piece of each colour).
• A total of 16 Zobrist keys for castling and turn combinations (I really only need 5, but using an array lookup like this will be cheap. All I need to do is to do a lookup, based on the board's status flag, which is a 4-bit value).
• A total of 16 Zobrist keys for e.p. squares.
  

I still need to think how this will impact on draw detection, where e.p. squares and castling rights are ignored. Maybe using two keys, where the one is derived from the other? But now I have to get to work - long gone are the student days of programming for fun all day... :'(

Vicki's first game

To my utter disbelief Vicki played its first game a few moments ago. Its a great feeling. All I used was a the basic alpha-beta search (with no move ordering) with crude mate detection. The evaluation function considers only material and gives a small bonus for controlling central squares (which makes for interesting games as well.) Vicki plays like a complete beginner - but it plays!

Next, I'll probably need to add some Winboard support.

It works!

I finally gave in and decided to write a divide() function to count the number of positions per move and comparing it with the results of Sharper. My other lazy attempts were fruitless. So after writing the divide method, downloading Sharper and seeing how simple it is to use I started debugging...

It seemed castling was the culprit yet again. Let's start with the basic rules of castling: A side may castle if the king has not moved; the rook has not moved; there are no blocking pieces and the king does not move through check or is not in check. Do you spot the bug? Aren't I missing something... Yes, you actually need to HAVE a rook in the first place!! I never canceled the castling bit if the opponents captured a player's rook. The result was a weird castling move without the rook. Funny right? I don't think so! :-)

Well, the move generation, making and taking back of moves now works beautifully. It is not a pure pseudo-legal move generator as it will not generate castling moves if the king moves through check or is in check currently. This does cause a slight drop in speed - but I hope that it will pay off later.

At last, I can start with the alpha-beta search.

Solved in part

I finally found a part of the bug. In turns out that the "bishop" on c8 was actually a phantom king, caused by a faulty take-back of long castling. Running perft() again for the FEN string, "r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq - 0 1", shows correct values up to perft(3). The values obtained were:

perft(1) 48 (correct)
perft(2) 2039 (correct)
perft(3) 97862 (correct)
perft(4) 4085659 (should be 4085603)
perft(5) 193696117 (should be 193690690)

Well at least the program is not hanging anymore. I don't know whether I should ignore this error for now or try and resolve it first. This little project turned out to be much harder than I thought!

Frustrantion, anger and despression!

Vicki kept on getting beaten over the knuckles by Windows (invalid operation) and after hours of debugging, I've detected a nasty error occurring with the piece lists. For some unknown reason, black pieces landed in the white lists and white pieces landed in the black lists. This caused a problem when the makeMove() method tried to remove a white piece from the white list and the white piece happened to be in the black list (something like a naughty boy being caught in the girl's dormitory!).

The can only happen is if a piece captures another piece of the same colour, but surely, that cannot happen. The move generation carefully checks such scenarios. Yet, after generating over 600,000 random games of 10 moves each from the following starting position,
"r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq - 0 1", the following happened:

  +---+---+---+---+---+---+---+---+
8 |   | r | B |   | k | . |   |   |
  +---+---+---+---+---+---+---+---+
7 | . | . | p | N | q | p | b |   |
  +---+---+---+---+---+---+---+---+
6 | . | . | . | . | p | n | p | . |
  +---+---+---+---+---+---+---+---+
5 | p | N | . | P | . | . | . | . |
  +---+---+---+---+---+---+---+---+
4 |   | p | n | . | P | . | P | r |
  +---+---+---+---+---+---+---+---+
3 | . | . | . | . | . | Q | . | p |
  +---+---+---+---+---+---+---+---+
2 | P | P | P | B | . | P | . | P |
  +---+---+---+---+---+---+---+---+
1 | R | . | . | . | K | . | . | R |
  +---+---+---+---+---+---+---+---+
    a   b   c   d   e   f   g   h  

In the above position, Vicki generated the move c8xd7 (capturing it's own knight) ??? I took the FEN-string from the above position and passed it through the move generator by itself. It did not generate the self-capture move, which means somewhere something is messing up the board.

What I really don't understand is that perft(7) gave a valid move count, without any crashes (from the standard opening position), which make me think that promotion may have something to do with it - yet, I did ran a test for promotions and it worked fine! What is going on?

Searching...

The search function (apart from the move generation) is perhaps the most critical piece of code in the entire engine. If the search function is solid, the rest is mere detail (I think I may regret that). OK, so here's the plan:

1. First I need some sort of interface! I've got a nice ASCII board already - but I still need some way to talk to my engine! I'll do WinBoard later.
   
2. A very basic alpha-beta pruning algorithm (once sorting is done, I'll give negascout a try - see point 5!).
3. Simple sorting together with iterative deepening.
   
4. Separating the move generator to generate captures, checks (not sure about this yet) and normal moves separately.
5. Some cleverer and more informed sorting functions.
6. All the other tricks, tips and tweaks.
   
7. International award winning and world-famous chess program.
   

For the rest of this week, I'll focus on 1 and 2. Points 3 is for the weekend, while points 4 and 5 are a for March-April. Point 6 will follow once everything else is done. I don't know how point 7 got there... someone else must have written it! ;)

Move generation fixed!

The move generation seems to be fine now. I discovered more bugs than I thought I would. These included en-passant (ep) status flags that were not set correctly (allowing any piece to capture ep, which is very humorous!), castling which never updated the piece positions (in the lists), creating invisible phantom rooks and kings and numerous other weird and bugs.

I've run two perft tests for now. In both instances the correct move counts were obtained. I guess I need to do a few more, but I am both reluctant, scared and lazy. :-) I want Vicki to start playing chess! Here is the benchmarks so far (which still includes all the asserts). I am happy with the results - although, I don't have any idea if this is slow or fast. It's probably just okay.

For FEN-string:
"rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1"

Up to perft(3), I got 0ms.
perft(4) 0.078s
perft(5) 1.687s
perft(6) 39.985s
perft(7) 17m 53.812s
perft(8) still running :-)

I also checked against the FEN-string
"n1n5/PPPk4/8/8/8/8/4Kppp/5N1N b - 0 1" to catch any promotion bugs. Fortunately, it checked out.

This should cover most move generation, make move and take back move scenarios. Next is a basic search function, to get Vicki to play its first valid chess game. I am still not sure what to actually release. The engine itself should be freeware and available to all, but I am not sure whether I want to release the source code - or is that sore code? ;-) I am open for suggestions, of course.

Uphill battle

I've just discovered another (much older & complete) blog that is doing exactly the same as I'm doing! Jonatan Pettersson's blog is worth a visit. Well done to him!

I have decided to implement Perft calculation to verify my move generator is correct before moving on. The technique simply counts the nodes of valid moves (that is, you have to avoid check, etc.) all the way down the tree. I found this link quite helpful.

My results are the same up to depth 4 (197281 positions), but then miserably falls apart. Not only are the numbers wrong, but the engine occasionally gets slapped over the knuckles by Windows (this is C after all). The moves that cannot occur prior to depth 5 are promotions, castling and en-passant. Logically, it must be one of these moves that is messing things up!

Well, at least the speed that I'm getting from the genMoves(), makeMove() and takeBack() functions are decent (more on that later). I hope I'm not going to spend the next few days trying to get rid of this pesky bug(s).

In the process I've also moved away from passing individual pointers and variables around and settled on a structure that defines the state of the game. The nice thing about a structure like this is that I can dump as much stuff in there without making the functions bloated in any way. Here it is:

typedef struct tag_CHESSENGINE
{
 CHESSPIECE* chessboard[144];
  int status;
 CHESSPIECE* whites;  
 CHESSPIECE* blacks;  
 CHESSPIECE* recycle; 
 CHESSPIECE* whiteking;
 CHESSPIECE* blackking;
} CHESSENGINE;

The pointers, whites, blacks and recycle are lists to ALL the pieces, while whiteking and blackking are pointers to the kings for quickly verifying illegal moves that leaves the king in check. The recycle list is useful to avoid any malloc() calls when taking back moves that resulted in captures. As the engine will only take back moves in a stack-like fashion, it is not even necessary to set the values of the piece structures as they are removed from the recycle list.

Well, back to coding.

What Makes A Good Chess Engine?

While writing the isUnderAttack() function I was wondering about what makes a good chess engine? I realised that it is not only by using the best algorithms and well-informed heuristic functions, but that all the small optimisations also adds up! For example, the method that I just mentioned checks to see if a particular square is under attack. As this function gets called during move generation (for castling) it needs to be pretty fast!

I suspect that by simply changing the order in which pieces are checked as potential attackers for the square can make a difference. My current order is bishops/queens, rooks/queens, knights, pawns, king. The ordering is derived from the fact that the pieces that hinder castling is usually bishops, followed by rooks (I get queens for free!) . If a valid attacker is found, the function returns straight away, skipping all the others.

Once I get Vicki to play valid chess, I can start experimenting with these to determine the actual difference that such a seemingly insignificant change could bring.

Generating Moves & Playing Them

The move generator was relatively painless. I decided to represent a move as a 32-bit integer (the most logical choice) and use a structure to represent the pieces. The piece structure looks as follows:

typedef struct tag_CHESSPIECE {
 char type;
 int position;
 struct tag_CHESSPIECE* next;
 struct tag_CHESSPIECE* prev;
} CHESSPIECE;

The two pointers is used in a linked list to avoid iterating through the entire board array. It also saves me from recreating pieces when they are captured, since I simply push the captured piece onto a stack and pop it off with takeBack(). I designed both makeMove() and takeBack() to be tightly coupled, which is a great improvement on my previous attempt. Assumptions often causes problems, but it can sure boost the engine speed! There is simply no room for defensive programming in a chess engine.

The moves are represented by a 32-bit integer, specifically:
bits 00-07 stores the source square.
bits 08-15 stores the destination square.
bits 16-21 stores the captured piece, if any (0 if none is captured)
bits 22-27 stores the promoted to piece, if any (0 if none)
bit 28 is used to indicate whether the move models castling - this allows quick checking in the makeMove() and takeBack() methods.

After some tinkering, Vicki made the first valid chess move. I had some issues with pointer arithmetic, but is seems to be resolved. I cannot wait to get Vicki to play its first valid chess game!

Board Representation

The past two weeks (even before the start of this blog) I have been trying to decide which representation scheme to use. From a bit of research on the net, I found the following techniques:

8x8-element array (or 64-element array)
Straight forward and very intuitive. The main problem with this approach is legality checking. Every time a sliding piece (queen, bishop or rook) moves the program needs to check if a boundary has been crossed. That will be slow. I also had some experience with this in my very first chess engine.

12x12-element array (or 144-element array)
At first glance I wanted to throw out this idea, but after looking at it, I decided that after bit-boards (see below) this can be pretty quick. All I do is to surround the board with a constant INVALID pointer, which makes checking for legality quick and painless. This is the approach that I am going to use in Vicki.

0x88 approach
In this approach the first 4 bits stores the row, and the last 4 the column. Since the rows and columns ranges from 0-7, the 3rd and 7th (counting from 0) are not used. By using this technique it is relatively cheap to determine an invalid board position. Merely and with 0x88 (10001000 in binary) and if the value is non-zero, the position is invalid.

Bit-boards
This is a technique used by most high-end chess engines. It can be very fast, but is rather tricky to implement, especially the rotated bit-board variety. It is based on the idea of soring information in 64-bit integers. By applying various bitwise operations the boards are manipulated all at once. I am still not sure how to effectively retrieve the list of moves from the bit-board set and have decided to leave this for later.

Baby Steps

I have decided to develop a chess engine and keep a diary of the process from the very start and what better way than using a blog! I have written a chess engine before, but it is very weak and nothing to be proud of. It does beat me, but not consistently.

Every chess engine needs to have a name. I am going to call my engine Vicki. Why Vicki? Apart from being a girl's name and containing the letters 'c' and 'i', which could stand for the words 'chess' and 'intelligence' in an acronym, I have no particular reason. But, I do like it.

My expectations of Vicki in the following year are as follows:

• a strong chess engine that consistently beats me and most other human players.
  
• participating in computer chess tournaments and not finishing last.
• playing beautiful chess by preferring position over material and explicitly endeavoring to create pins, skewers, double/discovered attacks, etc.

I have decided to use C as the programming language. Few languages can keep up with C's speed as it is very close to the hardware (I do not buy the Java is faster than C arguments).

I am famous for always starting projects from the wrong ends. So here's the logo for a chess engine that's only consists of ideas at the moment!















The photo was taken by my talented wife who is a professional photographer. Please visit her website.

The text is my own creation. I like the simplicity of the logo. Rather silly to have a logo without a chess engine - so let me start coding!

[Edit: Removed the version information from the logo.]