Jump to content
Have You Played Atari Today?
2600|5200|7800|Lynx|Jaguar|Forums|Store
  • entries
    53
  • comments
    536
  • views
    68,395

Thinking About Chess Again

Zach

Entry posted by Zach

961 views

 Share

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 efficient data storage, 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 additional 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 is set to indicate the captured piece is no 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.

 Share

5 Comments

Recommended Comments

Thomas Jentzsch

If you want to go for even more complexity, you could only code the possible moves. Encode all numbers (moves, objects etc.). By using Huffman encoding, you could also code numbers not dividable by 2 more effectively. I did this for the Jammed puzzles and got 600 puzzles compressed into ~2.5k.

 

Though in your case you have to encode dynamically and enocding/decoding is increasing calculation time. So finding the best compromise between CPU time and space usage is a difficult task.

Link to comment
batari

Huffman coding is efficient only when a priori frequencies of each possible number is known, and the frequencies are substantially different. The frequencies for fixed data can easily be predetermined, but for dynamically generated data on a system with no RAM to spare, it might not be so easy.

Link to comment
Zach

Thanks, Thomas. The only compression algorithm I've studied is LZW. What do you like about Huffman encoding?

Link to comment
Thomas Jentzsch
Huffman coding is efficient only when a priori frequencies of each possible number is known, and the frequencies are substantially different. The frequencies for fixed data can easily be predetermined, but for dynamically generated data on a system with no RAM to spare, it might not be so easy.

Correct. But Hufamann encoding optimizes the bit usage quite good, even without any compression.

 

Depending on the frequency of possible numbers, in chess I would expect that the closer a field is, the more likely it becomes.

Link to comment
Thomas Jentzsch
Thanks, Thomas. The only compression algorithm I've studied is LZW. What do you like about Huffman encoding?

Actually Hufmann is optimizing on bit level, while LZW is compression on byte level. Hufmann compresses based on frequency. Both can be combined, bit level after byte level compression.

 

If you e.g have 3 possible values, you take the most frequent one and encode it in one bit (A=0) and the other two ones in two bits (B=10, C=11). If you encode multiple values, you get a bit stream (e.g. 010011=ABAC).

 

In the case you describe, you probably won't get very far with LZW, but Huffman encoding can help.

Link to comment
Guest
Add a comment...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Loading...
×

  • Recently Browsing   0 members

    • No registered users viewing this page.
AtariAge
Forums
Store
General
Follow AtariAge

Copyright ©1998-2023 AtariAge

×
×
  • Create New...