MicroChess in C++

This directory contains a C++ port of MicroChess, a simple chess-playing program by Peter Jennings, originally written for the KIM-1, the first computer developed by Commodore. The program is therefore in 6502 assembler.

Not exactly a functional programming language! But I’ll make up for that later. In any case, all our chess-playing programs need something to play against. So consider this a benchmark.

“As can be seen, MICROCHESS is only the beginning”
—Peter Jennings, the MicroChess Manual

How to play

If you have XBoard installed, this is super easy:

make playx

This will compile MicroChess and run XBoard with MicroChess playing white against you.

Playing in text mode

make play

There's also a text-only user interface.

If you think that’s primitive, consider that MicroChess in its original form communicated through seven-segment displays.

• Type Q and hit Enter to quit.

• Enter P to tell the computer to take a turn. MicroChess always plays white.

• To take your turn, enter the coordinates of the piece you want to move, then the square you want to move it to, then Enter. For example:

  R N B K Q B N R   1
  P P P . P P P P   2
  . . . . . . . .   3
  . . . P . . . .   4
  . . . . . . . .   5
  . . . . . . . .   6
  p p p p p p p p   7
  r n b k q b n r   8
  
  h g f e d c b a        0F 13 33
  

  To counter with e5, you’d type e7e5 Enter.

  Then type P and MicroChess will respond (with Nf3). And so on.

• There’s one more command, R, which reverses the board. Bizarrely, the letters and numbers around the edges stay where they are — the way this is implemented is a little weird. It actually reverses the positions of all the pieces in memory. (The UI maybe ought to compensate, but it doesn’t.)

MicroChess peculiarities:

• MicroChess doesn’t enforce any rules whatsoever. You can move your pieces in illegal ways. You can take six turns in a row. You can move the computer’s pieces.

• MicroChess does not support castling, en passant, or promotion.

  You can castle anyway, simply by moving your king and rook to the appropriate squares, and capture en passant by moving your pawn first on top of the opposing pawn and then to the square where it should go. There is no way to promote, though.

How MicroChess works

MicroChess originally sold on cassette tape for $5, and for that price you got not only the software but a 37-page manual containing not only instructions on how to play but a fairly technical explanation of the algorithm.

I didn’t read it all, so what I know is mainly from looking at the code. Here are the basics.

The board is represented by a 32-byte array called BOARD. Each byte is location of one of the pieces or pawns in the game, or $CC if the piece has been captured.

For example, if the byte at address $50 is $12, that means the white king is at row 1, column 2. MicroChess numbers the rows and columns differently from standard chess notation—they’re zero-indexed and the columns are numbered in the opposite direction—so this corresponds to square c2.

The main AI starts at NOOPEN. It’s rather bewildering; here are the parts that make sense to me:

• There is a routine, GNM, that simply finds every possible move, and calls another routine JANUS, for each one.

  In other words, it’s map JANUS availableMoves.

  JANUS can do several different things; its behavior is determined by the variable STATE. GNM is thus a utility that the AI uses in several different ways. The poor man’s higher-order function.

• The AI has the ability to look ahead at capture exchanges, examining that part of the game tree depth-first. (This looking-ahead is what JANUS does when STATE is between -5 and 0.) From the manual:

  Exchange counts are used to analyse the effect of the potential exchange combinations. Each count reflects the maximum number of points capturable at each level of an exchange combination. Capture chains are halted by pawn captures, king captures, or by reaching a limit of three captures per side.

• Every chess AI needs a scoring algorithm, to compare the possible moves and decide which is best. MicroChess has a fancy one. It likes for its pieces to have lots of available moves, and particularly for the queen to be mobile. It values attacking its opponent’s high-value pieces. And it values attacking a large total value of material (it will totally fork your pieces with a knight given the chance).

MicroChess does not contain a general minimax algorithm. From the manual:

With the exception of the capture tree, the MICROCHESS program analyses in full only one move for each side beyond the move it will make. It is possible to use the same recursive technique used by TREE to carry out a full analysis to a further depth. To do this would require a routine to analyse and evaluate each intermediate position arrived at. Sequences of possible positions with positive values for computer moves and negative values for opponent's moves can be summed to give the total long term value of each currently available move.

Even this is not a description of minimax, as it contemplates move values being "summed" rather than the one best move being selected.

In order to be time efficient, this analysis can be performed on a subset of the available continuations selected by a quick static analysis. In addition, a system of 'tree pruning' should be implemented to prevent long excursions down low valued branches. Programmers embarking on this type of program should bear in mind that from an average position with 50 available moves per side, a total of 15.625 billion sequences are generated in three moves per side.

(It’s true: 50⁶ is 15.625 billion; but the average number of moves available to the player in any given position is more like 35, and 35⁶ isn’t even 2 billion! So you see.)

Opening. One more cool thing. MicroChess also conatins a script for one standard opening. If you let MicroChess play white, it’ll open with e4, and if you play the black moves listed below, MicroChess plays the white moves.

1. e4 e5 (e7e5)
2. Nf3 Nc6 (b8c6)
3. Bc4 Bc5 (f8c5)
4. c3 Nf6 (g8f6)
5. d4 exd4 (e5d4)
6. cxd4 Bb4+ (c5b4)
7. Nc3 Nxe4 (f6e4)
8. o-o Bxc3 (b4c3)
9. bxc3

This is the only way MicroChess can castle. In fact, because MicroChess doesn’t really support castling, after 8. o-o the user has to move white’s rook manually by typing h1f1 Enter!

The whole opening is encoded in 28 bytes, and the manual explains how to replace this opening with four others.

Source

The source I started with came from http://benlo.com/files/Microchess6502.txt and Microchess6502.txt is a copy of that file.

The MicroChess manual contains an earlier listing.