🚀 go-pugleaf

In <1992Nov12.183048.1308@schunix.uucp> sonix@schunix.uucp (Duane Morin) writes:

>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
>	

I remember from an AI class learning something about alpha-beta testing.
A lot of AI books talk about it.  Using this will give your game the
ability to "think ahead".