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

Arctic Smashed

I've been doing some simple analysis of the arctic sea ice extent data in order to generate my own prediction of the summer low. I'm now almost entirely convinced that the 2011 record will be smashed in 2011.

I've based it on the Jaxa arctic data from 2002 to 2011, which I imported into a gnumeric spreadsheet. You can see from the initial image that the SIE for 2011 is below the record-breaking year 2007 and has been every day since mid-May. In itself, this should be cause for alarm, but let's go back to 2007 to see why it's even worse than you might think.

2007 was a record-breaking year, but it didn't look that way until it lurched into free-fall in the last 10 days of June, due to a 'perfect-storm' of (AGW-induced) weather conditions, which set the scene for a record loss in late September. So the fact that 2011 has been lower since May isn't conclusive.

So, what I did was take the Jaxa data an import it into a spreadsheet. My first estimates were based simply on the ice loss from previous years after July 16 bolted on to July 16, 2011. There I discovered that the SIE minimum for this year would be about 4.16million KM2 - a new record, but not by much, a mere 80,000Km2. What's scary though is that simply bolting on the curves means that we'd get a record for 7/9 of the previous 9 years.

July 16: 2011	7347656
Year:	2010	2009	2008	2007	2006	2005	2004	2003	2002
Minimum:	4813594	5249844	4707813	4254531	5781719	5315156	5784688	6032031	5646875
July 16	8025000	8342969	8423438	7592500	8079844	8401094	9029375	8858281	8832969
Simple Prediction:	4093125	4199219	3549219	3911874	5024844	4174218	4058906	4426406	4077187
Average:	4168333

But it's not a realistic estimate - it's likely to be an underestimation. That's because SIE curves tend to have some continuity between the current state (and conditions) and the future state. So I constructed a slightly better estimation. In this one, I calculated the slope of the ice loss from July 1 to July 16 and compared the ratio with the eventual ice-loss at the minimum SIE for every year.

July 1 to July 16:	1715157
Year:	2010	2009	2008	2007	2006	2005	2004	2003	2002
July 1-July 16:	781563	1379844	1221562	1696406	1158750	1214375	1031250	1108750	1210937
Ratio to min SIE	5.11	3.24	4.04	2.97	2.98	3.54	4.15	3.55	3.63
July 1-16 Extrapolated:	3.002E+05	3.503E+06	2.131E+06	3.973E+06	3.946E+06	2.989E+06	1.951E+06	2.976E+06	2.835E+06
Average:	2.734E+06

With this, the best-case projection (i.e. maximum minimum SIE) will be 3.95million Km2 and the worst case will be 300,000Km2 (average 2.7million Km2). That's - stunning, and stunning doesn't even cover it: a 50% ice loss from 2007 in the best case, a 93% ice loss in the worst case, 33% ice loss in the average case.

The question is then how reliable these estimates are. Well, I'd be the first to say, "not very". My projections can be skewed easily by a steep anomaly in early July 2011 which would project a much lower summer minimum than would be likely.

The irony is that 2011 has had a smoothly falling curve between May and mid-July and it was 2007 which had the sudden acceleration over July. So 2007 makes my 2011 estimate look higher than it's likely to be. So, I'll stick my neck out at this point and say I figure the arctic record will be smashed this year, it's likely to be around 20% lower than 2007, probably in the range of 3.5million Km2, almost certainly lower than 4.0million Km2 and perhaps even as low as 3.0million Km2.