FIGnition oxo game! (noughts and crosses/ tic-tac-toe)

After my doom and gloom blog about the arctic, I thought I'd write a bit of a journal on how to write a simple noughts and crosses game. So, this'll be technical, and fairly involved as it'll include code, but at the same time will give a bit of insight into FIGnition, Forth and simple strategy games.

FIGnition is a real 80s-style computer. It's got enough memory (8Kb) to write simple programs and enough built-in storage to develop them in. The keyboard's somewhat awkward, but I'm getting used to it (I designed it).

The Computer History Museum is running an event called Hacker's delight, and as I'm exhibiting, they've asked me to produce a version of noughts and crosses to be demoed there. Demoing the development is as important as playing the game.

I started by looking at a few versions of tic-tac-toe. It's possible to write a recursive min-max algorithm, but I took my original cue from an online version of Not Only 30 Programs for the Sinclair ZX81. There are some insights into playing the game here.

Firstly, how to number the board. The board is numbered not in the order:

1|2|3
-+-+-
4|5|6
-+-+-
7|8|9

But

1|2|3
-+-+-
8|0|4
-+-+-
7|6|5

And it's done this way to make it easier to analyse the board. Opposite corners have a difference of 4 and subsequent diagonals have a difference of 2. In fact it's best to represent the board like this, because it reflects the real structure of a oxo board: if you rotate it by 90º it's still the same.

So let's first convert the ZX81 game. The ZX81 version simplifies the game by making the computer go first, by placing an 'X' in the centre. It then follows the following strategy:

• In the first move (A=1), the computer plays the opponents move+1 (so, if the user played to middle, the computer plays to the next corner and if the user plays to the corner, the computer plays to the next middle).
• In all other moves, if the user fails to block, then the computer plays opposite of the previous move and wins (i.e. because the user failed to block).
  
• Otherwise, for the computer's third move if the user had played to the middle of a row in its first move then we step 1 back from our previous move and win. (That's our other winning case). That's because the computer's second move always creates a dual two-in-a-row where the previous location is its other winning choice.
  
• Otherwise for the fourth move then we backwards by 2 and it's a draw.

It's a really simple strategy, which if you note, doesn't involve responding directly to the user's moves, except to record whether they first played on an odd or even square or whether they last blocked the computer's move.

In Forth we can simplify it by representing the moves as a table, one set for when the person played to an even-numbered square and the other set for when the person played to an odd-numbered square:


cdata compMoves 1 c, 2 c, 7 c, 0 c, 1 c, 2 c, 3 c, 6 c,

And then the algorithm simplifies to:

• If the user didn't block or we haven't played yet, then pick the next move from the table adding it to our current position and if the move was '7' we win, else if it was a '6' we draw.
  
• Otherwise we move to the opposite side of the board to our last move and win.

In Forth this is:


: compPlay ( movnum comp h -- m c f )
dup opp + brdRange = ( m c h h+4=c )
>r over = r> or if
over compMoves + c@ dup >r + r>;
7 =
else
opp + 1
then
;

An entire oxo game in approximately 9 lines of code! The entire game is listed on the FIGnition website and also here. It takes up approximately 5 screens and 554 bytes.

( Simple oxo )
: 2drop drop drop ;

: .brdLine
cr ." -+-+-" cr ;

: . Board
." 1|2|3" .brdLine
." 8|X|4" .brdLine
." 7|6|5" ;

4 const opp
64 15 + const (o)
64 24 + const (x)

: cdata <build does> ;

0 var board

cdata posConv
0 c, 0 c, 1 c, 2 c,
5 c, 8 c, 7 c, 6 c,
3 c,

: pos2xy posConv + c@
3 /mod 1 << swap 1 << swap ;

: place ( pos ch -- f )
over 1 swap << board @ swap over or 2dup =
if ( pc old nu )
2drop 2drop 0
else
swap drop board !
swap pos2xy at emit 1
then ;

: range? (val lo hi -- val | 0 )
rot swap over <
>r swap over > r>
or if drop 0 then ;

: humPlay
0 begin drop
begin
key 49 57 range?
dup until
48 - dup (o) place
until
;

: brdRange 1 - 7 and 1+ ;

cdata compMoves
1 c, 2 c, 7 c, 0 c,
1 c, 2 c, 3 c, 6 c,

: compPlay ( mv c h ..)
2dup opp + brdRange =
>r over = r> or if
over compMoves +
c@ dup >r + brdRange
r> 7 =
else
opp + 1
then
over (x) place drop
; ( .. -- mv c f )

: init 0 board ! cls .brd
;

: win? 5 0 at
?dup if
." I WIN!" key drop 1
else
over compMoves + c@ 6 =
?dup if
." DRAW!" key drop 1
else 0 then then ;

: oxo
init humPlay dup 1 and
4 * swap dup
begin
compPlay win?
0= while
swap 1+ swap humPlay
repeat
2drop ;

In a future post I'll look into a more sophisticated (2Kb!) version of noughts and crosses: where the person can start first, where I use real UDGs for a full-screen display and where the computer can LOSE ;-) !