OK we don't love trees yet ...
           ... BUT we can see they MIGHT be useful!!

----------------------------------------------------------------
           
Please note that I have flipped to using "literate Haskell" this
because I am writing more comments than program!! 

OK so we need to start thinking about game playing!!!!

The ideas behind game playing games like checkers where pioneered by
Arthur Samuel.  His work actually focused particularly on evaluating
game states (often called the "heuristic").  The basic idea is that one
chooses the move that maximizes the heuristic value of the game state
reached by each possible move.

Now to increase the efficacy of these heuristics one combines them with
looking ahead at all the possible plays in the game upto some depth. A single
move (of the opponent or player) in the game is called a "ply": thus one looks 
ahead say 8 ply  (this is quite a lot!!).

When one looks ahead in this manner one sweeps out a "MinMax" tree.  The tree
branches first correspond to the players possible moves, then correspond to
the opponents moves etc. It is called a minmax tree because the opponent
tries to minimize the (backed up) heuristic while the player tries to maximize
the (backed up) heuristic.

Here is the datatype of a minmax tree in Haskell:

> data MinMax a = TipMin Int a
>               | BranchMin [MaxMin a]
>      deriving (Show ,Eq)

> data MaxMin a = TipMax Int a
>               | BranchMax [MinMax a]
>       deriving (Show,Eq)

These MinMax trees are mutually recursive datatypes: "MinMax a" calls "MaxMin a" and
"Maxmin a" calls "MinMax a".

When searching a real game tree a tree such as the above is never built.  Instead the tree is 
implicit in the calculation. However, the datatype above is useful in developing the idea of how 
one eveluates a game tree.  The heuristic is evaluated at the tips of the tree (usually at some 
fixed ply).  The player wants to maximize the reward/heuristic at their turn while the opponent,
at their turn, tries to minimize the reward/heuristic that the player can achieve.

Thus fundamental to game playing is the evaluation of these MinMax trees:

> maxeval:: MaxMin Integer -> Integer
> maxeval (TipMax _ n) = n
> maxeval (BranchMax ms) = foldl max bot (map mineval ms)

> mineval:: MinMax Integer -> Integer
> mineval (TipMin _ n) = n
> mineval (BranchMin ms) = foldl min top (map maxeval ms)

Here is a test MinMax tree to try out the algorithm:

> test = BranchMax
>           [ BranchMin [TipMax 1 7,BranchMax [TipMin 2 9,TipMin 3 2]]
>           , BranchMin [BranchMax [TipMin 4 18,TipMin 5 9], TipMax 6 31]
>           , BranchMin [TipMax 7 17,
>                        BranchMax [BranchMin [TipMax 8 12,TipMax 9 17],
>                                   TipMin 10 45],
>                        TipMax 11 72]
>            ]

Very early in the development in game playing it was realized that the
evaluation of MinMax trees could be optimized.  The optimization ensures
that one does not evaluate parts of the tree which will make no difference
to the result.

The idea is to bound the answer a < ans < b and adjust these bounds as
one does the evaluation.  One starts the process with some "global"
bounds bot < ans < top.

When one is maximizing one can increase the lower bound, while one
is minimizing one can decrease the upper bound.  This gives the
following basic \alpha-\beta pruning algorithm:


> top = 30000
> bot = -30000

> abmaxprune:: (MaxMin Integer) -> Integer -> Integer -> Integer
> abmaxprune t a b| a==b = a -- cutoff
>                 | otherwise = case t of
>                       (TipMax i v) -> min (max v a) b
>                       (BranchMax ts) -> abmaxprunes ts a b
> abmaxprunes [] a b = a
> abmaxprunes (t:ts) a b = abmaxprunes ts newa b
>     where
>         newa = abminprune t a b

> abminprune::(MinMax Integer) -> Integer -> Integer -> Integer
> abminprune t a b| a==b = b --cutoff
>                  | otherwise = case t of
>                       (TipMin i v) -> max (min v b) a
>                       (BranchMin ts) -> abminprunes ts a b

> abminprunes [] a b = b
> abminprunes (t:ts) a b = abminprunes ts a newb
>     where
>         newb = abmaxprune t a b

In order to see the effect of \alpha-\beta pruning we shall "instrument"
the above code to show which "tips" have been evaluated.  This was why
we numbered the nodes of the tree.  In the above example note that
there are 11 "tips" but with pruning only 6 tips are visited.

> abmaxprune':: (MaxMin Integer) -> Integer -> Integer -> (Integer,[Int])
> abmaxprune' t a b| a==b = (a,[]) -- cutoff
>                 | otherwise = case t of
>                       (TipMax i v) -> (min (max v a) b,[i])
>                       (BranchMax ts) -> abmaxprunes' ts a b

> abmaxprunes' [] a b = (a,[])
> abmaxprunes' (t:ts) a b = case abmaxprunes' ts newa b of
>                             (v,indexes') -> (v,indexes++indexes')
>     where
>         (newa,indexes) = abminprune' t a b

> abminprune'::(MinMax Integer) -> Integer -> Integer -> (Integer,[Int])
> abminprune' t a b| a==b = (b,[]) --cutoff
>                  | otherwise = case t of
>                       (TipMin i v) -> (max (min v b) a,[i])
>                       (BranchMin ts) -> abminprunes' ts a b

> abminprunes' [] a b = (b,[])
> abminprunes' (t:ts) a b = case abminprunes' ts a newb of
>                              (v,indexes') -> (v,indexes++indexes')
>     where
>         (newb,indexes) = abmaxprune' t a b

The reason that \alpha-\beta pruning is VERY important in game playing
is that it allows one to search to almost double the ply that one could
with a basic min-max evaluation.  This leads to a MUCH better game
playing performance!!!