Magics

As mentioned earlier, I wanted to try Magic bitboards for the sliding pieces (rooks, bishop and queens). Magic bitboards are actually pretty easy once you get the gist of it. There are websites that explain the concept quite nicely (such as www.rivalchess.com).  Basically you take the attack board of your sliding piece, minus the edges.  For example, a rook on a1:

(bitboard 1)
0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0
0 1 1 1 1 1 1 0

This board represents all the squares that the piece can go to, if the board was completely empty.  These can easily be calculated before-hand and stored in an array (long[64]).  I call these the attack bitboard.

(I did not quite understand why the edge squares should be left out.  It's actually pretty easy... Less bits equal less complexity and the piece will always stop on an edge, so we can simplify the board by leaving them out from the start)

...this values gets bitwise "and"-ed with the board containing all the pieces, or the occupancy board.  The result is a board, which indicate all the piece blockers for a rook stationed at a1 (i.e. blocker bitboards).  The big problem and the reason for the various techniques (rotated bitboards, magics, etc.) is that we only really want the first blocker in a direction.  For example, the following blocker bitboards:

(bitboard 2,3 and 4)
0 0 0 0 0 0 0 0    1 0 0 0 0 0 0 0    1 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0    0 0 0 0 0 0 0 0    1 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0    1 0 0 0 0 0 0 0    1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0    0 0 0 0 0 0 0 0    0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0    0 0 0 0 0 0 0 0    0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0    0 0 0 0 0 0 0 0    0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0    0 0 0 0 0 0 0 0    0 0 0 0 0 0 0 0
0 0 0 1 1 1 1 0    0 0 0 1 0 0 0 1    0 0 0 1 0 0 0 0

could all reduce to:

(bitboard 5)

0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0

...and in turn, this board should be used to provide us with:

(bitboard 6)

0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0
0 1 1 1 0 0 0 0

Bitboard 5 (reduced bitboard) indicates a blocker on a6 and d1.  Bitboard 6 represents a rook on a1 that can move to b1,c1 and potentially capture on d1, as well as move to a2, a3, a4, a5, (result bitboard) with a potential capture on a6.  (To determine if we can capture/move on d1 and a6 is trivial as we only need to "and" the result bitboard with the inverse on the friendly pieces.  If d1 or a6 is still set, it means that there the square is either empty or contains an enemy piece that can be captured).

Anyway, back to the problem.  If we had infinite memory, we could create a table long[9,223,372,036,854,775,808] and store the result bitboard for each blocker board (i.e. bitboard 6 for bitboards 2,3 and 4).  However... we don't have that amount of memory, and even if we had, it will be a terrible waste.  This is where Magic bitboards comes in very handy.  Simply take your blocker board, multiply it with some magic number and then simply mod it with a power of 2 (which is essentially a shift).  You end up with some index number which is then used for a lookup in a much smaller database, i.e.:

((attack-bitboards-for-rooks[a1] AND occupancy) * magic-number[a1]) >> (64 - bits-required[a1])

It turns out, that it is easy to find unique locations for a database the size 2 to the power of the number of bits in the original attack board (and thanks to the missing edge-bits, it is 2 bits smaller).  For example, a rook on a1 requires a 12-bit database and we therefore have to shift right with 52 bits, leaving an index in the range 0...4095.

A chess program will typically have a magic number for each piece for each square (i.e. 128 in total), as well as different space requirements for each square, ranging from 5 to 12 bits (and possibly less...).

Finding the magics can be done brute force, using random numbers.  To find a magic number for a specific square, for a specific piece, it boils down to the following:

1. Pick some random 64-bit number, call it magic.
2. Get all the variations for the piece on the square (i.e. for example bb 2,3 and 4).
3. Create a database of size 2^bits (starting of with the number of bits in the original attack-board, i.e. bb 1).
4. For each attack variation
1. Calculate the result bitboard for the variation, i.e. bb 6 for bb 2,3 and 4. 
2. Create an index by multiplying variation with magic and shift it right with 64 - bits.
3. If database[index] is not 0 and the result board stored there is not compatible with variation, then we have a clash and we have to try a new magic number.
4. Otherwise, we store the result bitboard for variation at database[index].
5. If the loop ends with no clashes, then magic is a valid magic number for the piece on a1.

It takes a few seconds to find all 128 magics, if the bits is equal to the number of bits in the original attack bitboard.  However, for a rook on a1, we actually only need a database of size 49. There are only 49 unique configurations with a blocker on the a-rank and first-file.  To find a magic number that magically hashes all 4096 variations to a database of 49 result bitboards is a monumental task and turns out to be ridiculously difficult. In fact, no one really knows whether it is possible or not.

Fortunately, we don't have to go the absolute minimum.  Shaving off a single bit, will half the space requirements for that square already.  So instead of searching for a magic for a 12-bit database, we could try and search for a magic for an 11-bit database for the rook on a1.  This is still difficult, but doable...

I have written a program that searches for magics for all pieces, all squares for all database sizes.  So far, all my efforts have produced, the following:

Piece	Square	Bits in attack board	Bits required for database	Magic! (base-16)
Bishop	a1	6	5	90a207c5e7ae23ff
Bishop	b1	5	4	caad949dbf3ffed4
Bishop	g1	5	4	2a0f37664bfef560
Bishop	h1	6	5	f174631c5963ffd7
Bishop	a2	5	4	b2d764c66b3617f5
Bishop	b2	5	4	f97758b06ebb3f25
Bishop	g2	5	4	2ba278d2d3287f3f
Bishop	h2	5	4	0ca85d99b283fe74
Bishop	a3	5	4	8440f94bf539afdb
Bishop	b3	5	4	c6e0343a763ab7f6
Bishop	g3	5	4	78b4002cccfabedf
Bishop	h3	5	4	cd4a03745eacbfd0
Bishop	a6	5	4	24ffd9f54b3ec007
Bishop	b6	5	4	6ccffd59e5fae014
Bishop	g6	5	4	2eff79dda4a23407
Bishop	a7	5	4	e3dff263999c90f5
Bishop	b7	5	4	f06bfd8ab019c8bd
Bishop	g7	5	4	3fffa27235d24ee9
Bishop	h7	5	4	cf3fa4b1f1bdb60c
Bishop	a8	6	5	83c3fd4a7d787936
Bishop	b8	5	4	f317ee03f569a587
Bishop	g8	5	4	9ad97f53b94894e3
Bishop	h8	6	5	91fff9fd4502052f

If you are interested in the code for the above, drop me a mail.  I will send it to you and put it on here if enough people bug me.  I will continue the search and keep this table updated.

FEN Strings

I've made some progress yesterday.  I have an elementary bitboard representation working and I can set and get the chess board using a FEN string.  A FEN String essentially represents the current board setup in a convenient notation.  Here is an example after white's initial e4:

rnbqkbnr/pppppppp/8/8/4P3/8/PPPP1PPP/RNBQKBNR b KQkq e3 0 1

Each string in between the slashes represents a rank in the chessboard, starting from the 8th rank. Lower case is black, upper case is white. Numbers represents empty squares between pieces.  For example '4P3' represents four empty squares, followed by a pawn, followed by three more empty squares, totaling eight.  The '/8/' therefore means (you've guessed it!) a complete empty rank.

The remaining string 'b KQkq e3 0 1' represents the side to move, the castling rights (e.g. 'K' means white can caste king-side, 'q' that black can caste queen-side, etc.), en-passant square and the move counters.  The en-passant square is the square directly behind the pawn that made the two-square move.  In this case, white move e4, which means that e3 is the en-passant square.  Black can capture the pawn if he had a pawn on either d4 or f4.  Regardless, the en-passant square is always indicated, whether it can be taken or not.  The move counts are the half-moves since a last capture or pawn move (for the 50-move draw rule), followed by the number of full moves.

I found myself constantly checking the validity of the FEN string during the parsing stage, which started to look really ugly.  So I turned to one of my best friends... regular expressions!

Regular expressions can get tricky...quickly, but is incredibly powerful to recognise patterns in strings.  Here is a short extract from Vicki that shows how a FEN string can be checked:

 
The 'verifyRank()' method simply verifies that the a rank adds up to eight. Doing that in a regular expression may get very hairy (actually I don't think it can be done). The code also verifies that there are 2 kings at least.  Of course, that can easily be done by the regular expression, but the string will get rather long. 

Move generation

The first step is move generation.  I have committed myself to Java and bitboards for Vicki 2.0.  The advantage of Java is that it is much more platform independent than C... well, mostly.  Bitboards is also a good move, given that it is theoretically faster than the postbox method and besides, it is something interesting to learn.

So the list of tasks for the next few days is as follows:

1.	Set up data structures	Done
2.	Set and get board (FEN-based)	Done
3.	Simple textual display	Done
4.	Move generation for non-sliders (pawns, knights and kings)	In progress...
5.	Move generation for sliders (bishops, rooks and queens)	Pending
6.	Make move	Pending
7.	Unmake move	Pending
8.	Perft testing	Pending

For now, the representation simply contains positions for each of the pieces.  The derived pieces will be added later.

Something stirring in the shadows...

I have only fond memories of Vicki...  The website is still up, but Vicki has not used a clock cycle in years.  The current release is several years old... written in C.

I am currently (as in already busy) rewriting Vicki.  Vicki 2.0 is a complete rewrite of the engine, reusing nothing but the name.

I am not looking at any existing computer chess code and I am avoiding any heavy bias to single papers and single units of theory - trying my own. The research in computer chess is all but exhausted.  So all that is left is to redesign the wheel for the fun of it and looking at existing code will spoil it for me... Vicki is not meant to "extend" the envelope of computer chess.  It's my Everest and South Pole.  

Vicki 2.0 is being written in Java.  Java's speed is comparable to C and C++ (in some people's opinions!) Also, I want something which is easily transferable between Linux and Windows platforms.  C does not really cut it for me any more.

Board representation will the elusive bitboard (or bitmap) technique.  It cannot be that hard... (famous last words!) and I cannot ignore it's advantages any longer.

I hope to post regularly and have something on the main website up and running soon.