Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Video Chess disassembled and commented

nanochess.org

Post reply on HN
Print view View original

61–70 of 72 posts

Re: Video Chess disassembled and commented

#61

Post by tenebrisalietum »

toast0 wrote: post #53
vikingerik wrote: post #34

Earlier quoted context omitted.

Each square of the board doesn't even need a byte, only a nibble. There are 6 piece types so that fits in 3 bits, plus one for color. If you pack two of those nibbles per byte then you can do it in 32 bytes plus the castling and en passant bits. Video Chess uses the lower nibble of 64 bytes for the board, and the upper bits of those for various other purposes. You actually could condense further than that. Build the…

> writing an engine for that data structure is much more cumbersome, since it can't look at a square to find what piece is on it, instead it has to iterate over all the pieces to find out what's on a square. Ignoring the move generation, this is also way harder to render the output with. The Atari 2600 has very few cpu cyles per line, and I don't know if you'd have enough time to iterate through all the pieces to see…

You won't. You have 76 CPU cycles per line. Searching through a 32 byte array for a match - 4-5 cycles just to load the byte from the array if you use zero page indirect addressing.

Re: Video Chess disassembled and commented

#63

Post by ddingus »

raldi wrote: post #60
devit wrote: post #42

Earlier quoted context omitted.

The 128 bytes of RAM seems quite easy (game state is 32 bytes for chessboard + 1 byte for side-to-move+castling+en-passant plus 2/3 bytes per move in the search stack + 1 byte to record the depth at which castling was disrupted = 54/64 bytes with depth 10, leaving a luxurious 64/74 bytes for call stack and local variables). The problem seems to be more the 4KB of ROM, but only if one is trying to make it actually som…

But the computer also needs to keep a scratch space to consider potential moves it could make, which if done in a straightforward manner would exhaust the other 64 bytes of memory.

It could just mark branches at the cost of recomputing moves repeatedly to evaluate scores.

Re: Video Chess disassembled and commented

#64

Post by bradknowles »

sitkack wrote: post #48
dws wrote: post #29

Many years back (so details are fuzzy), a friend who worked at Atari in the early 80's told that the programmer who did the game part of the work had the basic chess algorithm working in a few months, spent the next year getting it to run in less than 128 bytes of RAM, and was then burnt out and left tech. IIRC, the game devs used a PDP-11 for much of their work, so that had a bit more RAM to work with to get started…

I'd love to see a dev setup for using the PDP-11 and the Atari 2600 for doing gamedev. I did a quick search on youtube and the search engines and couldn't find anything.

We had a PDP 11/70 for undergraduate work when I started studying for my BSCS in 1984. Nothing pretty, just glass vt52 and vt100 type terminals. Oh, and a 110 baud line printer that could also be used as a terminal. That line printer was not fun, but I had to use it on occasion when all the good terminals were taken.

IIRC, ours had 64KB of RAM in two banks.

Re: Video Chess disassembled and commented

#65

Post by ddingus »

toast0 wrote: post #56
kstrauser wrote: post #51

Earlier quoted context omitted.

Wait, the Genesis, which came out in '88, had to race the beam like an old Atari?

The races are quite a bit different. On an Atari, pretty much all games spend the screen on time feeding the TIA chip; with most or all of the game logic happening during vblank. On a Genesis, games spend most of vblank feeding the VDP chip with sprite and other graphics data, and then can run their game logic during the screen on time. With some effects requiring frobbing the VDP chip during the drawing phase. Howev…

"Frobbing" -- added to my goofy nerd lexicon

Re: Video Chess disassembled and commented

#66

Post by vikingerik »

toast0 wrote: post #53
vikingerik wrote: post #34

Earlier quoted context omitted.

Each square of the board doesn't even need a byte, only a nibble. There are 6 piece types so that fits in 3 bits, plus one for color. If you pack two of those nibbles per byte then you can do it in 32 bytes plus the castling and en passant bits. Video Chess uses the lower nibble of 64 bytes for the board, and the upper bits of those for various other purposes. You actually could condense further than that. Build the…

> writing an engine for that data structure is much more cumbersome, since it can't look at a square to find what piece is on it, instead it has to iterate over all the pieces to find out what's on a square. Ignoring the move generation, this is also way harder to render the output with. The Atari 2600 has very few cpu cyles per line, and I don't know if you'd have enough time to iterate through all the pieces to see…

Yeah, of course. I wasn't speaking of the Atari or any computer in any practical sense, just hypothetically about the minimum storage.

Of course it's possible to go even more than that - enumerate every reachable position (so remove situations like a pawn on the first or eighth rank, kings adjacent or in some check situation that couldn't have happened, pawns in positions that would require more captures than there are enemy pieces missing from the board, etc) and assign them all an index number, which requires log N storage size. And of course it would be practically impossible to do anything computationally with positions stored like that.

This link estimates an upper bound of around 10^46 reachable positions, so log2 of that would be only about 150 bits to enumerate them all.

https://math.stackexchange.com/questions/1406919/how-many-le...

Re: Video Chess disassembled and commented

#67

Post by flohofwoe »

danmaz74 wrote: post #5

I started developing software as a kid on a Commodore 64, and I thought we were pretty clever if we were able to accomplish interesting things using only 32KB of RAM. But the idea that somebody was able to develop a full chess engine using only 128 Bytes of RAM boggles my mind.

Think of the 128 bytes RAM to be only used for your dynamic gameplay state variables.

C64 (and other home computer) games had to load all code and data into RAM, which usually accounts for most RAM usage. Game consoles like the Atari 2600 stored the code and static data in a ROM cartridge.

For simple arcade-style games (like Pacman), 128 bytes of RAM is more then enough to manage the gameplay state.

(still of course: a chess engine in 4 KByte ROM and 128 bytes RAM is pretty damn impressive)

Re: Video Chess disassembled and commented

#68

Post by danmaz74 »

flohofwoe wrote: post #67
danmaz74 wrote: post #5

I started developing software as a kid on a Commodore 64, and I thought we were pretty clever if we were able to accomplish interesting things using only 32KB of RAM. But the idea that somebody was able to develop a full chess engine using only 128 Bytes of RAM boggles my mind.

Think of the 128 bytes RAM to be only used for your dynamic gameplay state variables. C64 (and other home computer) games had to load all code and data into RAM, which usually accounts for most RAM usage. Game consoles like the Atari 2600 stored the code and static data in a ROM cartridge. For simple arcade-style games (like Pacman), 128 bytes of RAM is more then enough to manage the gameplay state. (still of course:…

Fitting a chess game state in 128 bytes is for sure doable; what is really impressive is being able to use the same memory not just for the current position, but also to compute the next moves in a decent way.

Re: Video Chess disassembled and commented

#69

Post by zikduruqe »

danmaz74 wrote: post #45
croshan wrote: post #40

Earlier quoted context omitted.

I tried it out, was enjoyable to play a few puzzles. My feedback is a) that the ring sound (when you win a puzzle) was too loud, so I ended up muting the tab, and b) that the logo looks like "BraiMax", and doesn't stylistically fit with the rest of the site theme.

Thank you for your feedback! By the way, you can disable sound from the little cog icon just above the chessboard.

I'd recommend changing the sounds up a bit. The piece moves sound more like doors locking or unlocking from FPS games in the 90's. And the bell... just doesn't sound "successful chess puzzle" to me.

I'm no UX engineer at all, but the sounds just do not sound chess-y. Just a thought.

Re: Video Chess disassembled and commented

#70

Post by ttonkytonk »

This is off topic (I owned an Atari 2600, and loved Atari, but never owned Video Chess), but I've come up with a chess variant I call "Transposition Chess" (not to be confused with Transcendental Chess).

The rules are the same with three major differences.

I) Black has the option of transposing any two pieces on their back rank before play begins. If they do they must transpose the parallel pieces on their other side to make their setup symmetrical (unless they transpose the king and queen). White must adjust their setup to mirror Black's, and then play can commence.

This creates 11 possible setups:

1)b>RNBQKBNR w>RNBQKBNR

2)b>RNBKQBNR w>RNBKQBNR

3)b>RBNQKNBR w>RBNQKNBR

4)b>BNRQKRNB w>BNRQKRNB

5)b>NRBQKBRN w>NRBQKBRN

6)b>RNQBBKNR w>RNQBBKNR

7)b>RNKBBQNR w>RNKBBQNR

8)b>RQBNNBKR w>RQBNNBKR

9)b>RKBNNBQR w>RKBNNBQR

10)b>QNBRRBNK w>QNBRRBNK

11)b>KNBRRBNQ w>KNBRRBNQ

Castleling is only possible in the first five set-ups, and will always be with the piece that occupies the Rook's original square.

II) Pieces can be demoted by moving them to an original pawn square (on one's own side of the board) and declaring a demotion. However, there must be at least one of their pawns captured that they can "exchange" it for. Note that the new pawn could deliver checkmate/stalemate.

III) Pawns can only be promoted to pieces currently captured. If no pieces are currently captured, the pawn may not move to the promotion rank (as if a piece was blocking it). Note that it may still deliver checkmate/stalemate in this position, as normal.

The thinking behind the first rule is to make book opening memorization less of an issue (without making things too complicated or unusual) as well as giving Black compensation for moving second. The thinking behind demotions is to make games that would normally be draws due to lack of material (or skill) winning. The thinking behind the last rule is to make over-the-board play easier (e.g. no confusion about whether a piece is a pawn or queen), though it also potentially makes "two for one" exchanges more attractive for the person capturing two pieces (I recently saw somewhere that there's some evidence that when the queen is exchanged for two rooks or the rook for two minor pieces, the person losing two pieces typically does better, though nominally they have less in material value).

Post reply on HN