Chess on the Pico Edition XGamestation

[nczempin]

I've mentioned in another thread that I'm planning to write a chess game for the Pico Edition XGamestation.

Given that it only has 136 bytes of data RAM, this may sound impossible. However, it has been done before:
The Atari 2600 has similar specs (except that the pico is clocked far higher), and they managed to produce a chess game for it, Video Chess.

I'll download a 2600 emulator and the rom, and see how well it plays, so I have a sort of a benchmark.

[hgm]

Says that they had to expand the ROM from 2K to 4K, though.

I guess a lot depends on how much of that ROM you need for generating the video image of the board display.

As for the 136 bytes of RAM: due to size restrictions you will probably be forced to represent the board as a packed array of nybbles, that would take 32 bytes. I did give some thought to the minimal RAM requirement for an alpha-beta search routine a la micro-Max. The minimum you have to store for each ply seems to be

1) FromSquare
2) ToSquare
3) a state variable to remember in which direction you are currently generating moves
4) the Victim
5) a SkipSquare to indicate where e.p. capture is possible, and which you could also use to indicate that the move is a castling and have make/unmake deduce from it how the Rook moves in that case.
6) Alpha
7) BestFrom (to remember the best move)
8) BestTo
9) IterDepth (internal depth counter for IID)
10) Eval (to restore it after differential update)
11) some bitflags to save the 'virgin state' of the moved piece (so UnMake can restore it), and if you are searching the best move of the previous iteration


There is no need to store Beta if you can access the variables in the stack frame of the previous ply, as it is simply minus the Alpha there. The SideToMove and DepthLeft can be kept as global variables. You might be able to pack the flags in unused bits in From and ToSquare.

Even if Alpha and Eval would have to be 2-byte quantities, it seems you can limit the size of the stack frame to below 16 byte. That means that this machine should in principle be able to handle it, and that you could store 6 ply worth of data next to the board in these 136 bytes. That should be enough to play Chess that beats most non-club players.

[nczempin]

Wow, thanks, I'll surely use some of that analysis when the time comes.

In the meantime, I played a game against VideoChess on the Stella Atari 2600 Emulator.

It seems to have a minimum opening book (played c5 to my e4 twice) and doesn't play all that badly.

However, in this position:
[D]2r3k1/1p1q2pp/3Pp3/4P3/p2nQ3/2N5/PPP3PP/2K2R2 w - - 0 1
it seemed to run into some kind of horizon effect, and played
... Rf8??

Final position:
[D]4kQ2/2K5/4N1p1/4P3/p7/6Pp/PPP4P/8 w - - 0 1

So you're probably correct that it would beat most non-club players. Eden would surely trounce it, and that's a very weak engine.


It's satisfying to finally understand why that game does those crazy screen fireworks, (it can't spare the cycles it needs for "thinking" to generate the display). As I said, I hope I can save a bit of program memory by not showing the board, but only the last move (although I still have to think about a way to let the user enter his move, perhaps an empty board will do).

There's also the (assembly) source code to an early 6502 chess game "Microchess" floating around, which uses considerably less than 4k if I remember correctly. Haven't checked how much actual RAM it uses.
(Hey, there's an idea for a name for the game: Picochess. No, HGM probably uses that already...)

[hgm]

(Hey, there's an idea for a name for the game: Picochess. No, HGM probably uses that already...)

Well, the Polish version of that already exists (PicoSzachy).

MicroChess was indeed running in 1.25KB. But that was all RAM, and I don't know how it was divided between data and code. It didn't have to bother displaying a board, just a 7-segment display, for which it didn't bother to generate letters eaither. It presented its move to the user as square numbers...

For the I/O functions it could use routines present in the system ROM, though.

[nczempin]

(Hey, there's an idea for a name for the game: Picochess. No, HGM probably uses that already...)

Well, the Polish version of that already exists (PicoSzachy).

MicroChess was indeed running in 1.25KB. But that was all RAM, and I don't know how it was divided between data and code. It didn't have to bother displaying a board, just a 7-segment display, for which it didn't bother to generate letters eaither. It presented its move to the user as square numbers...

For the I/O functions it could use routines present in the system ROM, though.

Perhaps using 8x8 LEDs would be sufficient. Perhaps I should get myself one of those old chess computers (boards) and rip out some of the hardware and then interface it to the Pico.

I'm dreaming; all those things I could do with hardware, they'd be really cool.


I could call it XPico Chess, or XG-Pico Chess, or whatever.

[hgm]

Well, this thing as a number of I/O ports, and you could of course connect those to a static RAM chip. It would be a bit cumbersome to access the data there, as you would first have to write the external-memory address into one port, and then transfer the data through another port. But it could be done, and then you could even afford a small hash table or triangular PV array.

[nczempin]

Well, this thing as a number of I/O ports, and you could of course connect those to a static RAM chip. It would be a bit cumbersome to access the data there, as you would first have to write the external-memory address into one port, and then transfer the data through another port. But it could be done, and then you could even afford a small hash table or triangular PV array.

Yes, it could be done, but I don't want to dwell on the Pico Edition too long, just long enough for a Proof of Concept or two, and then I'll "advance" to the Micro Edition.

[nczempin]

I've received my kit, and have started to put it together. I didn't have an RS-232 cable handy, so I had to wait until tonight to start actually doing some stuff with it.
Because I don't have a TV in the hotel room I'm staying in, I can't test the video/audio output until the weekend.
I will play around blinking a few LEDs, and perhaps connect the 7-segment display that comes with the "extended" Pico (2.0).

In the meantime, I thought a bit about techniques to save memory ruthlessly. I don't care much if I lose speed by some of these techniques; I can always get back a bit of speed if it turns out I'm not even using all those 136 bytes of RAM.

So, here are some ideas:

1. If I disallow sub-promotion and only allow a maximum of 5 queens, I can pack a move into 1 byte instead of two:
1 queen, 28 moves max: 28
2 rooks, 14 moves max: 28
2 bishops, 14 moves max: 28
2 knights, 8 moves max: 16
1 king, 10 moves max: 10
8 pawns, 4 moves max: 32

So I have 142 possible codes using just one queen, and 28 more per additional queen, for five queens I'd need 254 states. Just enough for 1 byte.

Sub-promotion would be much costlier, and occurs virtually never in real games. So I figure it's an adequate tradeoff.

2. For the state of the board I need 4 bits per square * 64 squares = 32 bytes. Using an "indexed" scheme similar to the move packing above I could get it down to 28 (although I don't remember how I did this right now). Plus 3 bits for en passant (one of eight) and 4 bits for castling rights, so make it a byte; we'll find a use for that extra bit

If there are any flaws in my calculations, please let me know...

[hgm]

Well, the Queen and Bishops have in fact one move less.

But if you would encode a move that way (for the purpose of being able to unmake it later) is there really a way to decode it easily? RAM is not the only limitation you will be facing. To encode the move as a simple (From,To) pair requires only 12 bits, 4 more than you propose here. That would be for each ply, of course, so perhaps 40 bits = 5 bytes in total. You would have to weigh that against an enormous demand on program memory (and execution time!) for decoding the compact repesentation when you actually need to unmake the move.

The 12 bits for (From,To) would have to be distributed over 2 bytes, so you might as well put 6 bits in each bytes in the natural place (depending on your square numbering scheme, 0x88 or just 0-63), and use the 2 bits that remain in each byte to store other information that needs to be saved and restored on recursion (like 3 bits for the Victim type, and 1 bit to indicate that it is a promotion so that you can convert the Piece back to a Pawn on unmake). In that case it would be reasonably straightforward to recover the information in a usable form, by just two shift and mask instructions.

Even with (From,To) it might be difficult to restart the move generator to figure out after unmake what the next move in the current node should be. So perhaps it would be better to not store From, but in stead a 3-bit number indication the direction (the loop counter that the move generator uses as index in the list of board step vectors for the moving piece) and a 3-bit distance code giving the number of steps already made in that direction. Then it would still be reasonably easy to reconstruct the From square from the stored move information and what is on the board.

(It would be a pain to have to subtract the step vector repeatedly from the To-square for distant slider moves, but if you are really clever you could combine unmake with make of the next move on the ray, and then you would not need to know the From-square at all. Only when reaching the end of the ray (or a beta cutoff) you would need to reconstruct the From square.)

My guess is that you would be better off using the slightly larger, but much simpler encoding.

And I don't think there is a reason to shy away from under-promotions: they do not require extra information for unmaking, as you can see what piece is on the board. You just have to remember that the move was a promotion, which you would have to do anyway even if you promote only to Queen.

[nczempin]

Well, the Queen and Bishops have in fact one move less.

Of course, you're right.

But if you would encode a move that way (for the purpose of being able to unmake it later) is there really a way to decode it easily? RAM is not the only limitation you will be facing. To encode the move as a simple (From,To) pair requires only 12 bits, 4 more than you propose here. That would be for each ply, of course, so perhaps 40 bits = 5 bytes in total. You would have to weigh that against an enormous demand on program memory (and execution time!) for decoding the compact repesentation when you actually need to unmake the move.

Well, it depends what you mean by "easily". Of course it is way more inconvenient to decode my move, but it is possible. At the moment my goal is to squeeze everything into as little RAM as possible, even at the expense of (proportionately much worse) execution speed. After all, the Atari 2600 ran at around MHz, and I have about 80x that. There is also a chess program for the ZX81, in 1k (although AFAIK it uses 2k of RAM). So anything is possible.

And with 8 bits vs. 12 you are of course aware that it's not just the 4 bits, but it's a complete byte (regardless of what else I can put in there), i. e. double the size! It sounds pretty significant to me.

On the other hand you have at least two to three orders of magnitude more experience than me in these low-level matters, and perhaps I should swallow my pride and simply go with your suggestions

The 12 bits for (From,To) would have to be distributed over 2 bytes, so you might as well put 6 bits in each bytes in the natural place (depending on your square numbering scheme, 0x88 or just 0-63), and use the 2 bits that remain in each byte to store other information that needs to be saved and restored on recursion (like 3 bits for the Victim type, and 1 bit to indicate that it is a promotion so that you can convert the Piece back to a Pawn on unmake). In that case it would be reasonably straightforward to recover the information in a usable form, by just two shift and mask instructions.

From what you've seen so far, you won't be surprised that I was planning for 8x8 or 0-63, not even 8x10 (or whatever that scheme is called where you don't have to check the vertical edges), let alone 0x88 (what? a whole board, a bunch of bytes with nothing in them? )

Even with (From,To) it might be difficult to restart the move generator to figure out after unmake what the next move in the current node should be.

My coding scheme would allow for this, because there'd be a fixed order, e. g. "Rook one +1 vertical"; if I take this back, the next moves after Rook one's move would be Rook 2's. They would be uniquely defined simply by defining rook one to be the one closest to a1 (in the one-dimensional array). They could swap positions during the game, of course.

So perhaps it would be better to not store From, but in stead a 3-bit number indication the direction (the loop counter that the move generator uses as index in the list of board step vectors for the moving piece) and a 3-bit distance code giving the number of steps already made in that direction. Then it would still be reasonably easy to reconstruct the From square from the stored move information and what is on the board.

(It would be a pain to have to subtract the step vector repeatedly from the To-square for distant slider moves, but if you are really clever you could combine unmake with make of the next move on the ray, and then you would not need to know the From-square at all. Only when reaching the end of the ray (or a beta cutoff) you would need to reconstruct the From square.)

My guess is that you would be better off using the slightly larger, but much simpler encoding.

As I said, your advice is valid, and I'm thinking about it. I'll probably have enough trouble given my lack of experience in assembly. I just hope I don't run out of bytes at some stage...

And I don't think there is a reason to shy away from under-promotions: they do not require extra information for unmaking, as you can see what piece is on the board. You just have to remember that the move was a promotion, which you would have to do anyway even if you promote only to Queen.

I will consider it in case I really go to two bytes. With one byte there's no point, as I'd have to support three or more rooks etc.
Although previously I had been frowning upon (strong) engines that didn't have underpromotion, in this case I am very sure of my decision (based on a not-yet-final one-byte-per-move decision).


I have another restriction: only eight levels of stack. So unless I'll recode alpha-beta iteratively, that is a hard limit on the number of plies. May be a problem in endgame positions.

But, alas, it's only a proof of concept. I'd much rather play with additional hardware (robot arm, anyone?) than optimize its strength. The source will be open, so those inclined to optimize after I have provided a baseline, are free to do so.

This may not be obvious to you, but yesterday, when I got the blinking LEDs working, and even changed a few things, I felt I was 12 again! It's really about me learning to play around with hardware, something I feel is missing from my youth