Tic-Tac-Toe Algorithm & HP-41c Implementation
          (published in PPC Technical Notes #13, late 1982)
                     Written by: Christopher Rath

    Note, this is a text copy of a scanned article that is posted
    at http://rath.ca/Misc/HP-41c/PPC_TN_13.pdf (the PDF copy is
    considered canonical).


Tic Tac Toe seems to be one of those games that PPC owners like to
programme into their machines; if they have the memory.  So, let's
talk about some of the major points one encounters during the writing
of such a programme.

One of the first points that appears is, "How to store the board?"
Remember, that it, your method, must be memory efficient in two ways:
1) Data storage space; 2) Programme memory used to access a board
location.

There are three methods that quickly spring to mind: 1) Devoting a
register to each square; 2) Using flags; 3) Or using a single register
for an entire board, and nine digits right of the decimal.

Devoting a register/square violates our memory efficiency decision, and is
not really a consideration at all.  The other two are fine to use; and
also, they do not require synthetics, a big plus (not implying the
first uses them).  Number 3) is the better of the two though.  It
allows distinction between 'Unoccupied', 'X-occupied', and
'O-occupied'; whereas the flags do not.  This may or may not be worth
considering, depending upon your 'system to win'.

Let us consider the board for a moment.  If we number the squares as
shown in fig. 1, then they correspond to the keyboard; making things
easy for the user.

Fig. 1:
        7:8:9
        4:5:6
        1:2:3

Also, about the board; as well as nine squares, there are nine ways to
win.  Let us call these 'win lines'.  Obviously, each time the 41c is
required to make a move, it must look at all nine win lines (in the
worst case).  A question thus arises: Do we keep track of the win
lines in memory, or do we recalculate each time?  Execution time, and
available memory are the consideration here.  If you can spare the
memory then it speeds execution time greatly if a running status of
the win lines is kept.

The next decision is a fairly major one; how to represent the win
lines in storage, or in the programme after calculation?  This will
determine whether to assign a single reg. to each line, or to use the
flag or single ref. for all options.

We can immediately cross the flag option off our list.  It only
allows a there/no there, representation; which is insufficient.  The
difference between individual or single register usage is also great
(from a programme execution point of view).  The key point being that
while a single register for all allows sufficient differentiation, it does
not allow negative number representation.

This may seem trivial, but, what kind of change are you going to
effect to the win line when a piece is played?  There are 8
combinations of men, but only six win line states.  Because it is the
win line state that ultimately matters, it is probably best if we
store that, as opposed to the actual man combinations.

Fig. 2:
-------------------+---------------------+----
  Win Line States  :   Man Combinations  : #3
-------------------+---------------------+----
 1 Null Status     : No men in line      :  0
 2 Possible threat : 1 opponent in line  : -1
 3 Possible win    : 1 of own in line    :  1
 4 Must block      : 2 of opponent       : -2
 5 Will win        : 2 of own in line    :  2
 6 No threat       : 2 and 1 combination :  1
                   : One of each         :  0
-------------------+---------------------+----

There are, without a doubt, many ways to store this status.  But let
us look at one that is very simple to visualize and use.  Using the
single register win line; begin with all the registers at zero.  Now, what
happens if we add 1 to the appropriate registers when the 41c moves,
and subtract 1 when its opponent moves.  As you can see, by column #3
in fig. 2, the states are very well defined, and look simple to test.
Remember that there is always more than one register to add to or
subtract from; with square 5, as an example, there are four registers to
effect changes to.  This method of representation is simple enough
that it is probably worth translation to and from this notation if
you are using the single register for all method.

The only remaining question concerns strategy.  It is important to
note here that square 5 is used in the most win lines, and that the next
most used square is any one of the corners.  Since it is possible to tie,
or win, starting from any square, we can conclude that the first move
made in a game is of no concern.  The second move made does, however,
have an optimum: If the centre was not taken by the first move then it
should be the second move; if the centre is already occupied then any
one of the corners is the best move.  There are other subtleties, but
the interested reader can play out several games and determine them
his-her-self.

                 * * * * * * * * * * * * * * * * * *

The Tic Tac Toe programme shown here uses a register/win line, and a
single register for all squares, for board storage.  Because win lines are
kept current, the board storage only needs to indicate (un)occupied.
I didn't use flags because I have too many other routines that use
them.

To play ^TTT, just XEQ^TTT.  When you are prompted for a "SEED?",
enter a number between 0 and 1.  The 41c will then respond with either
its first move, or the message, "YOU GO FIRST", depending upon the
first Random Number chosen.  The PPC ROM is required, or check back issues
of the Journal for a listing of ^RN.  To enter your move, or interpret
the 41c's, use the digits one to nine of the keyboard, as I suggested
in the discussion.