🚀 go-pugleaf

Often at work the senior engineer and myself discuss AI and such topics as
computer game strategy.  He proposed a game that he suggests I attempt to 
code an "optimal" strategy for.  What I'd like to ask the net is some 
suggestions on whether or not I'm taking the right approach, and if so how
to go about getting something concrete written.

The game:  Many people will know this game, usually played on a piece of 
paper with a few pencils.  A grid of 5x5 dots is drawn on the paper.  The 
players (usually 2) take turns connecting lines either horizontally 
or vertically.  If a player succeeds in creating a box (i.e. four connected
lines) he gets to move again.  The player with the most boxes at the end 
of the game wins.  (I've pointed out to him that a 5x5 grid creates 4x4
squares, thus allowing for the possibility of a tie).

Problem:  There are certain layouts that the board can fall into where one 
player, given the chance, can chain together enough moves to cover the 
board (or, at least, get the maximum number of squares).  Thus, a computer
strategy would have to see this possibility and guard against it.

Strategy:  Here's my initial thoughts:  Look at the grid as a 4x4 array
of boxes.  Each box can be described in 4 bits, representing the status
of its 4 walls.  Any line that can be placed on the grid will effect 
either one or two boxes (only one if its on an edge).  A box's value can 
be weighed something like this:  

	See the possibility of making  4, take it.
	Don't make any 3's.  Your opponent can turn them into 4's.
	Conversely, make lot's of 2's.
	Except early on in the game, avoid 1's.

This weighting strategy is simple, and might work.  Unfortunately, it has
no lookahead or any capacity for learning.  What I'd like to try is 
something that learns from it's mistakes...for example, let it play 
against itself again and again and develop it's own strategy.  Anybody
got an idea of how I'd do that?  I really can't see doing anything where
I have to represent all the states of the board (40 lines on the grid, 
on or off, yields 2^40 states, correct?)

Or perhaps, something with lookahead?  At any given time, there are 40 or 
less moves that the computer can make.  Temporarily make each one
(recursing if necessary, if the move yields a 4), and then for each one 
weigh the possible moves that the other player could make.  I don't know
how far down I could do this, though...maybe some sort of minimaxing?

As you can probably tell, I'm somewhat familiar with the theory behind writing
such a game strategy.  However, having never actually coded it, I'm in a 
bit of a bind as to how to approach the problem.  Any help would be 
wonderfully appreciated.

Thank you,
 Duane Morin
 sonix@schunix.uucp