Zach's Projects - Thinking About Chess Again

RSS Bot · March 1, 2009

It has been over a year since I've posted anything to my blog. Unfortunately I do not have much time for homebrewing these days, but I still hope someday to get back to some of my unfinished projects.

A while ago, I took on the challenge of making a chess kernel without flickering or Venetian blinds. After many aggravating attempts, I finally got it with some convoluted code. I know a chess homebrew is low priority compared to the other projects I've started, but I've been thinking about how better chess AI could work on the 2600.

There was a brief discussion in this thread about making a better chess game by allowing more RAM and ROM. However, by employing more effficient data stroage, it should be possible to work with the standard 128 bytes of RAM.

The idea is to encode a chess ply (a move by a single player) in one byte. You need a way to encode a chess move in such a way that can be undone. The most obvious way to encode a ply is to save the chessman's starting square, ending square, and the identity of a captured piece, if any. Normally that would take three bytes, and this encoding would fill up RAM quickly as the computer looks ahead.

For a long time, I didn't think it would be possible to reduce a ply to one byte, but I recently figured out how, in conjunction with a 64 byte array to store the board. The idea takes advantage of the fact that pieces don't move to just any square on the board. Each piece is limited to a few squares where it can move at any time. The piece that can move to the most squares is the queen, and the maximum number of places where she can go is 27.

-- -- -- 04 -- -- -- 18
24 -- -- 03 -- -- 17 --
-- 23 -- 02 -- 16 -- --
-- -- 22 01 15 -- -- --
12 13 14 -Q 08 09 10 11
-- -- 21 05 25 -- -- --
-- 20 -- 06 -- 26 -- --
19 -- -- 07 -- -- 27 --

So, the queen's move can be limited to 5 bits. The queen's starting point does not really need to be saved because she can be found on the board. I do not need to be concerned with the whether the black or white queen is moving, because her color is implied by the position in the search tree. Thanks to pawn promotions, there can be more than one queen, so I need 2 bits to keep track of which queen is moving. (That leads to a maximum of four queens. Even though more queens are legally possible, it is not likely to happen in a practical game. A reasonable compromise, I think.) Finally I need one bit to indicate that the piece moving is a queen rather than some other piece.

And so the coding for a queen move would look like this:

1|XX|XXXXX

1 bit: Indicates queen move

2 bits: One of up to four queens

5 bits: One of 28 possible moves. Each of 1-7 squares to the right, up, up-right, and up-left (with wrapping).

Similarly, rooks and bishops can move to 14 places, so a rook/bishop move would look like:

0|1|XX|XXXX

1 bit: Not a queen move

1 bit: A rook or bishop move

2 bits: One of two rooks or two bishops (Unfortunately, this scheme does not allow for three or more rooks/bishops, which is legally possible with pawn promotions.)

4 bits: One of 15 possible moves. Whether the moves are read as rook or bishop depends on the value of the previous two bits. There are actually 14 standard moves, and 1 special move, castling. Whether the castling is king's side or queen's side can be ascertained from the rook's position.

Next are king/knight moves

0|0|1|XX|XXX

1 bit: Not a queen move

1 bit: Not a rook/bishop move

1 bit: A king/knight move

2 bits: Which king/knight. Up to three knights are possible.

3 bits: The move. Both kings and knights can go to up to eight squares.

Finally: Pawn moves:

0|0|0|XXX|XX

1 bit: Not a queen move

1 bit: Not a rook/bishop move

1 bit: Not a king/knight move

3 bits: Which pawn

2 bits: The move. Either 2 steps forward, 1 step forward, or a leftward/rightward capture.

The question is now how to store captures. At first I thought I'd need an addition byte to record them, until I realized that there are plenty of empty squares in the board array. Whenever a piece captures, it swaps positions with its captive, and a flag it set to indicate the captured piece is not longer in play. Of course another piece may need to move to that square, so pieces will have to swap with every move, whether a capture or not. Some mechanism will be needed to indicate when an undo returns a captured piece to the board. What I'm thinking now is that three bits can indicate the current depth of the search, and during an undo when it reaches 0 it comes back into play. That allows for a 14-ply tree, which is probably deeper than the Atari can handle in a reasonable amount of time.

Undoing en-passant captures is a little tricky, and I haven't ironed out all the details yet, but I'm sure it can be done. Again, this whole article is just a description of what is possible, not a plan to get back to work on chess. If I do find time for homebrewing again, Chetiry will be my first priority.

http://www.atariage.com/forums/index.php?a...;showentry=5848