view release on metacpan or  search on metacpan

lib/HTML/Tree/AboutTrees.pod  view on Meta::CPAN

always lose within a few moves anyway.

Consider, then, this rather short game where X starts:

  xxxx___oooo
    ^         Move 1: X moves from 3 (shown with caret) to 5
               (Note that any of X's pieces could move, but
               that the only place they could move to is 5.)
  xx_xx__oooo
          ^   Move 2: O moves from 9 to 7.
  xx_xx_oo_oo
     ^        Move 3: X moves from 4 to 6.
  xx__xxoo_oo
           ^  Move 4: O (stupidly) moves from 10 to 9.
  xx__xxooo_o
      ^       Move 5: X moves from 5 to 10, making the board
              "xx___xoooxo".  The three o's that X just
              surrounded are removed. 
  xx___x___xo
              O has only one piece, so has lost.

Now, move 4 could have gone quite the other way:

  xx__xxoo_oo
              Move 4: O moves from 8 to 4, making the board 
              "xx_oxxo__oo".  The surrounded x's are removed.
  xx_o__o__oo
  ^           Move 5: X moves from 1 to 2.
  _xxo__o__oo
        ^     Move 6: O moves from 7 to 6.
  _xxo_o___oo
   ^          Move 7: X moves from 2 to 5, removing the o at 4.
  __x_xo___oo
              ...and so on.

To teach a computer program to play Alak (as player X, say), it needs to
be able to look at the configuration of the board, figure out what moves
it can make, and weigh the benefit or costs, immediate or eventual, of
those moves.

So consider the board from just before move 3, and figure all the possible
moves X could make.  X has pieces in slots 1, 2, 4, and 5.  The leftmost
two x's (at 1 and 2) are up against the end of the board, so they
can move only right.  The other two x's (at 4 and 5) can move either
right or left:

  Starting board: xx_xx_oo_oo
   moving 1 to 3 gives _xxxx_oo_oo
   moving 2 to 3 gives x_xxx_oo_oo
   moving 4 to 3 gives xxx_x_oo_oo
   moving 5 to 3 gives xxxx__oo_oo
   moving 4 to 6 gives xx__xxoo_oo
   moving 5 to 6 gives xx_x_xoo_oo

For the computer to decide which of these is the best move to make, it
needs to quantify the benefit of these moves as a number -- call that
the "payoff".  The payoff of a move can be figured as just the number
of x pieces removed by the most recent move, minus the number of o
pieces removed by the most recent move.  (It so happens that the rules
of the game mean that no move can delete both o's and x's, but the
formula still applies.)  Since none of these moves removed any pieces,
all these moves have the same immediate payoff: 0.

Now, we could race ahead and write an Alak-playing program that could
use the immediate payoff to decide which is the best move to make.
And when there's more than one best move (as here, where all the moves
are equally good), it could choose randomly between the good
alternatives.  This strategy is simple to implement; but it makes for a
very dumb program.  Consider what O's response to each of the potential
moves (above) could be.  Nothing immediately suggests itself for the
first four possibilities (X having moved something to position 3), but
either of the last two (illustrated below) are pretty perilous,
because in either case O has the obvious option (which he would be
foolish to pass up) of removing x's from the board:

   xx_xx_oo_oo
      ^        X moves 4 to 6.
   xx__xxoo_oo
          ^    O moves 8 to 4, giving "xx_oxxo__oo".  The two
               surrounded x's are removed.
   xx_o__o__oo

or

   xx_xx_oo_oo
       ^       X moves 5 to 6.
   xx_x_xoo_oo
          ^    O moves 8 to 5, giving "xx_xoxo__oo".  The one
               surrounded x is removed.
   xx_xo_o__oo

Both contingencies are quite bad for X -- but this is not captured
by the fact that they start out with X thinking his move will be
harmless, having a payoff of zero.

So what's needed is for X to think I<more> than one step ahead -- to
consider not merely what it can do in this move, and what the payoff
is, but to consider what O might do in response, and the
payoff of those potential moves, and so on with X's possible responses
to those cases could be.  All these possibilities form a game tree -- a
tree where each node is a board, and its children are successors of
that node -- i.e., the boards that could result from every move
possible, given the parent's board.

But how to represent the tree, and how to represent the nodes?

Well, consider that a node holds several pieces of data:

1) the configuration of the board, which, being nice and simple and
one-dimensional, can be stored as just a string, like "xx_xx_oo_oo".

2) whose turn it is, X or O.  (Or: who moved last, from which we can
figure whose turn it is).

3) the successors (child nodes).

4) the immediate payoff of having moved to this board position from its
predecessor (parent node).

5) and what move gets us from our predecessor node to here.  (Granted,
knowing the board configuration before and after the move, it's easy to