[Haskell-cafe] Translating an imperative algorithm - negascout

Thu Feb 26 23:19:01 EST 2009

Colin Paul Adams wrote:
> 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.

Variable names like alpha'' can be seen as an indication that a function 
is too big and/or monolithic.  It's worth keeping in mind the lesson of 
the lambda calculus: that a local variable is just a function in disguise.

To exploit that, you can replace definitions and uses of variables like 
alpha' and alpha'' with calls to functions.  Wherever you have something 
like:

   let alpha' = <new value for alpha>
   in <body>

...try changing it to something like:

   foo <new value for alpha>
   ...
   where foo alpha = <body>

Instead of a monolithic deeply-nested conditional expression, this will 
naturally lead to a set of small functions which call other small 
functions.  As Toby Hutton said, you should also factor out any 
repetition into functions.

One advantage of defining small functions like this is that you can also 
take advantage of guard syntax, which used appropriately in Haskell can 
be cleaner and more readable than either 'case' or 'if'.

For example, to deal with the following pseudocode:

   a := -negascout (child, depth-1, -b, -alpha)
   if a > alpha
      alpha := a

You could write a function such as:

   newAlpha a | a > alpha = a
	     | otherwise = alpha

Note this function depends on 'alpha'.  To avoid having to pass extra 
parameters around all over the place, simply define this function using 
a 'where' clause, at the appropriate scope level so that the 'alpha' it 
needs is in scope.  In your example, it would probably be defined in 
your negascout' function, something like this:

   negascout' node depth beta' alpha beta rest =
     ...
     where
       newAlpha a | a > alpha = a
	         | otherwise = alpha

Note that newAlpha needs to be called with the result of a call to 
negascout.  While we're about it, notice that both of the recursive 
calls to negascout use the same first two arguments, so just for 
readability, we can define this:

   search a b = -negascout child (depth-1) (-b) (-a)

The pseudocode above can now be (mostly) replaced with a call 
'newAlpha', as follows:

   newAlpha (search alpha b)

However, this doesn't deal with what happens to the result of the call 
to newAlpha.  In the imperative pseudocode, alpha is mutated.  For a 
functional version, you can just repeat the above strategy: define a 
function which takes an argument alpha, and call that function with the 
new value for alpha, i.e. the result of the call to newAlpha, so 
something like:

   foo (newAlpha $ search alpha b)

The foo function will implement the remainder of the body of the foreach 
loop from the pseudocode.  (Coming up with a better name than 'foo' is 
left as an exercise...)

I tried this and the result was 13-16 lines, depending how you count, of 
code that is of similarly high level to the original pseudocode.

Anton