[devit]

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 somewhat good, and also perhaps using 1979 tech for programming.

[raldi]

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.

[ddingus]

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