<This might be of interest to some of you. In generating a database, you have to map out all of the positions, and determine if they are wins, losses, or draws for each side to move.

Since there are 80 squares and 4 pieces, most people think you just create an array with four placeholders, one for each piece. Such an array would contain 80 x 80 x 80 x 80 entries, which is 40,960,000 positions per side to move.

This might not seem bad, but such a primitive scheme contains wasted entries. By making 80 slots available for each piece, basically you are allowing two or more pieces to be placed on the same square! For example, element 3,6,23,23 is a valid array index, but not a vaild over-the-board arrangement. Likewise element 12,4,4,31 is invalid, as well as 59,59,1,2....59,59,1,3....59,59,1,4 so you see there is a great deal of waste!

There is a technique to reduce this to setups where pieces are never on top of each other. This is called a sparsely-populated matrix. In this case, there are 80 x 79 x 78 x 77 entries per side to move = 37,957,920. It is smaller, but it makes the "lookup" procedure to locate your position a little more difficult.

In my case, the order I placed pieces on the board were black king (bk), white knight (wn), white bishop (wb), then white king (wk). So there were 80 slots for the bk, 79 remaining for the wn, etc.

So, my "indexing function" is now a formula. The result for any given position on the board is :

i = [(bk - 1) * 79 * 78 * 77] + [(wni - 1) * 78 * 77] + [(wbi - 1) * 77] + wki.

Notice we have an "i" on the end of all terms except the black king. These are "index" terms, not the actual square numbers. More on that later...

Each element, bk, wn, wb, and wk is a number in the range from 1 to 80. There is still one other thing to do before applying the formula. Since not all 80 square are available for the pieces based on the order the board is occupied, you need to "collapse" the indices associated with every piece other than the first one on the board.

That is, start out by letting every index element equal the corresponding square of the piece on the board.

wni = wn
wbi = wb
wki = wk

Then, if:

wn > bk, wni = wni - 1
wb > bk, wbi = wbi - 1
wk > bk, wki = wki - 1

wb > wn, wbi = wbi - 1
wk > wn, wki = wki - 1

wk > wb, wki = wki - 1

The logic is that if a piece is placed on the board AFTER some other piece, if the new piece is on a square which is greater than the square of a previous piece, the previous piece is "taking away one slot" from the new piece. There is 1 less square available for the new piece since the previous piece has already been put on the board, but this slot is only "robbed" when the new piece is greater than the old piece. If it is on a square less than the old piece, there is really no interference.

That being said, there are still ways to reduce the size of the database. In reality, the first king need only be placed on 20 squares for pawnless databases. Any position on the board with one king constrained to the rectangle a1,e1,e4,a4 can be rotated and flipped to produce ANY position on the board with the king unconstrained.

Place a king on a8. place the other pieces anywhere you want. If you flip the board vertically, setting the rank of each piece to 9 - current rank, you will have the king on a1 and all other relative relationships the same.

King on j8? Flip the board horizontally, the king is on a8. Flip it vertically, it is on a1. This can be done for any square outside of the rectangle.

You gain a 400% reduction in the database with the offset of a more difficult lookup scheme, but in this case, the gain is worth it.

There are two other types of reduction that can be performed.

One is to constrain the king pair to eliminate adjacent king positions. These are still elements in the database, although illegal over the board.

I can generate an array of 20 x 80 elements that enumerate the legal king arrangements, 1,2,3,4...etc. I can then use this as the precursor to the indexing function formula, which would be modified slightly.

The next, and final compression that can be done is called RUN LENGTH ENCODING. This technique requires creating another database listing just the wins, losses, and draws with no move to win information. This database will compress very well in this case, where it is mostly wins and losses. This technique will allow me to throw away the drawn positions from the move to win database, which are one byte per entry. It will also allow me to throw away the adjacent kings, and every position where it is white to move and black is already in check!

This should give excellent compression results in the end. I will only have distance to win data for legal chess positions, and distance to win takes up the most disk space.

So, I will work on this during the week, and maybe the resulting databases will be small enough to be placed online here for everyone to play against.