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.

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.

**: 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 ;-) !

## No comments:

Post a Comment