MATEY.TXT       29-May-2026

Matey is a relatively simple chess-playing program. It's intended more as
an XPLW programming example than as a strong competitor. (It's more of a
"playmate-y," or "stalemate-y," rather than a "checkmate-y.") However,
despite its limitations, it can still beat most people.

Matey helps teach newcomers about the game by showing legal moves and by
preventing illegal moves.


RUNNING THE PROGRAM

Matey begins by asking who is first. If you would like to go first, press
P followed by the Enter key. If you would like Matey to start the game
then press M. The default is P, so merely pressing the Enter key is the
same as selecting "Person." Matey then asks who goes second.

If P is selected for both first and second then two people can play, and
Matey merely provides the chess set and inforces the rules. If M is
selected for both first and second then you can watch the action as Matey
play against itself.

The third question sets Matey's skill level. It determines how much, and
how long, Matey thinks about its moves. Level 3 is a good place to start.
(Type "3" followed by the Enter key.) Levels 2 through 5 are the
recommended range, but 1 through 7 are accepted. Level 1 is so dumb that
it's only useful for debugging the program, and level 7 is so slow (hours
per move) that it's only useful for something like a correspondence game.

The mouse is used to make moves. Click on the piece you want to move then
click on the square you want to move it to. You can also click and drag a
piece.

Clicking the mouse on the [Exit] button (at the bottom of the screen) ends
the program. The Esc key also ends the program, and it responds even while
Matey is thinking about its move. (If Level is set above 3, it may take
several seconds before the program ends.)

The [Undo] button undoes the last pair of moves (black's and white's).
Pressing [Undo] a second time, undoes the undo. In other words, it
restores the original positions.

The [Info] button is 3-way: It turns off the teaching mode, which shows
which squares a selected piece may be moved to. Pressing the button a
second time shows all the computer's possible moves with their values.
The current value is shown above the best value found so far. Capturing a
pawn is worth 100 points. Striking a key causes the display to pause. A
second keystroke resumes.

The [Sound] button turns the sound effects off and on.

The [Reset] button starts a new game.

To castle, move your king two squares either left or right. The rook will
move automatically.

To capture en passant, move your pawn diagonally, as though the
opponent's pawn only advanced a single square. (En passant is an unusual
move: If an opponent's pawn advances two squares instead of one to avoid
being captured by your pawn then you can, on the next move only, capture
the opponent's pawn as though it moved one square.)

The moves listed in the window at the left of the screen are also
recorded in a file called "mateygame.txt." If you want to save this file,
rename it to something else, otherwise it will be overwritten by the next
game. The numbers in parenthesis in the file are the values of Matey's
moves.


LIMITATIONS

Matey doesn't include castling in its search for a move. A human player
can castle, but Matey can't. (You might feel it's unfair to take
advantage of something that Matey can't do.) Also, Matey doesn't enforce
all the rules on castling. It's illegal to castle if you're in check or
if the intermediate position is in check.

Pawns that reach the 8th rank are always promoted to queens; there is no
option for selecting another piece, such as a knight.

Matey sometimes continues playing even after a king is captured. It does
"Resign" if it detects it's about to be checkmated, but it doesn't always
quit moving its pieces.

Matey doesn't understand all the rules involving stalemates. It does
prevent you from moving into check, and it will declare a stalemate if it
is not in check and its only move is into check. However it's up to you to
declare a draw if a position has been repeated three times or if 50 moves
have gone by without either side capturing a piece or moving a pawn.

When Matey is playing against itself, the mouse is not active, thus the
[Exit] button cannot be clicked - hit Esc instead. This mode is useful
for debugging, or as a demo or teaser.


HOW IT WORKS

Matey uses a recursive routine to search a large tree of possible moves.

In the 1950's it was thought that a computer playing grand-master-level
chess was soon to be made. However it took much longer than expected,
mostly because of the incredibly huge size of the search tree required.
There are about 10^120 moves in an average game. To get an idea of how big
this number is, there are only about 3x10^18 nanoseconds in a century.

Matey limits the size of the search tree by its Level setting. This is
the normal level, or depth, that the tree is generated. For example
setting Level to 4, searches four half moves (equal to two full moves).
Assuming 30 possible moves per turn, this generates a tree with 837,930
nodes (30^4 + 30^3 + 30^2 + 30).

Each node in the tree is assigned a value called its "static value."
These values are determined by captures, advancement across the board,
and the number and location of squares to which pieces can move (their
mobility). A penalty is assessed for moving the queen or king too early
in the game.

A depth-first tree search is used to generate nodes, thus only "Level"
number of nodes are saved in memory at one time. The state of each node
is automatically saved in the local variables of the search routine
(TryMove) as it recurses.

When the search reaches a terminal node, the minimax algorithm is
applied. This algorithm assumes that both the computer and the player
select the best move available. The best move for a terminal node is the
one with the highest static value. Thus this value is returned when the
search routine moves back up a level, and it's called the "BackupValue."

What's best for the player is worst for the computer, and vice versa, so
the signs of the backupValues alternate at each level. These backupValues
are added together, one for each level. The computer makes the move that
corresponds to the branch at level 1 that has the greatest sum.

The easiest way to understand all this is to look at the accompanying
Tic-Tac-Toe program, TTT.XPL. Incidentally, the keypad is used to specify
where to place your X. Make sure Num Lock is turned on.

Matey has a few more complications. If a capture occurs at what would
normally be the terminal node, the search is extended another level. If
there are additional captures (exchanges), the extensions continue to the
maximum depths shown here:

        Level   Max. Extension   Max. Total Depth
          1      +      0       =        1
          2      +      1       =        3
          3      +      1       =        4
          4      +      2       =        6
          5      +      2       =        7
          6      +      3       =        9
          7      +      3       =       10

Another complication is the use of alpha-beta pruning. This dramatically
reduces the number of branches and nodes that must be searched in the
tree. However, it's only partially effective in Matey because the most
promising moves are not searched first. (A shallow search could be done
to determine the most promising moves.)

Matey actually uses a minor variation of minimax called "negamax." The
accompanying files MINIMAX.TXT and NAGAMAX.TXT show the comparison and
provide an example of how alpha-beta pruning works.

It's left to you to determine just how intelligent this tree search makes
the computer. At its level 4 it plays with an Elo rating of about 1100 (as
determined by competing against Chessmaster 9000). In the case of
Tic-Tac-Toe the tree is small enough that it can be completely searched,
and thus the TTT program cannot be beaten (and probably isn't any fun to
play).

-Loren Blaney
