hgm wrote: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
