[Haskell-cafe] Translating an imperative algorithm - negascout

[Holger Siegel]

Am Donnerstag, den 26.02.2009, 20:54 +0000 schrieb Colin Paul Adams:
> Hello Haskellers,
> 
> I want to implement the negascout algorithm for the game I'm writing.
> 
> Wikipedia gives the algorithm in imperative terms:
> 
> http://en.wikipedia.org/wiki/Negascout
> 
> I've tried to translate this into Haskell. I'm not sure if I'm going
> about it the right way, and if I am, if I've done it correctly.
> 
> 
> Any comments on my effort here, are welcome:

A more systematic transformation may lead to a more efficient
loop:

In the pseudocode, I have replaced the first conditional with the max
function and pulled the calculation of (depth - 1) out of the loop:

function negascout(node, depth, alpha, beta)
    if node is a terminal node or depth = 0
        return the heuristic value of node
    b := beta
    d := depth - 1
    foreach child of node
        alpha := max(alpha, -negascout (child, d, -b, -alpha))
        if alpha >= beta
            return alpha
        if alpha >= b
           alpha := -negascout(child, d, -beta, -alpha)
           if alpha >= beta
               return alpha
        b := alpha+1
    return alpha


In order to make this more Haskell-ish, we assume three self-explaining
functions:

> terminal        :: Node -> Bool
> heuristicValue  :: Node -> Int
> children        :: Node -> [a]

(Idiomatic) Haskell does not use mutable state or conditionals without
else-branch, so we make three modifications:

1) We use pattern matching for the first conditional
 
2) Every other conditional

     if c then a
     rest

   is rewritten as

     if c
     then do a
             rest
     else rest
     
   and

     do return x
        rest

   is abbreviated as

     return x

   (Here, 'return' is the imperative return statement, not the monadic
   unit)

3) We bring the program into single static assignment form. That is, we
   introduce new variables, so that every variable is assigned to only
   once. This is not always possible, because the loop would require
   us to introduce an unknown number of variables. Therefore, we allow
   reassignments at the end of an iteration.

And there it is, written in Haskell-like pseudocode:

> negascout :: Node -> Int -> Int -> Int -> Int
> negascout node depth alpha beta
>     | terminal node || depth == 0
>         = heuristicValue node
>     | otherwise
>         = do b := beta
>              d := depth - 1
>              foreach child of node do
>                  alpha' := max(alpha, - negascout child d (-b)
(-alpha))
>                  if alpha' >= beta
>                  then return alpha'
>                  else if alpha' >= b
>                       then do alpha'' := - negascout child d (-beta)
(-alpha')
>                               if alpha'' >= beta
>                               then return alpha''
>                               else do alpha := alpha''
>                                       b := alpha'' + 1
>                       else do alpha := alpha'
>                               b := alpha' + 1
>              return alpha

Now we see that only alpha and b are modified by the loop. From that it
follows how the loop can be turned into a recursive function: This
function takes alpha, b and the list of remaining children as its
argument:

> negascout node depth alpha beta
>    | terminal node || depth == 0
>        = heuristicValue node
>    | otherwise
>        = loop alpha beta (children node)
>    where
>    d = depth - 1
>    loop alpha b (c:cs) 
>        = let alpha' = max(alpha, - negascout c d (-b) (-alpha))
>          in if alpha' >= beta
>             then alpha'
>             else if alpha' >= b
>                  then let alpha'' = - negascout c d (-beta) (-alpha')
>                       in if alpha'' >= beta
>                          then alpha''
>                          else loop alpha'' (alpha'' + 1) cs 
>                  else loop alpha' (alpha' + 1) cs
>    loop alpha _ [] = alpha

Now you can move around the declarations, introduce some nice guards,
optimize the calls where b==alpha+1 or beta==alpha+1 and hunt for
hidden folds.

(Warning: I didn't test it)