# [Haskell-cafe] Translating an imperative algorithm - negascout

Anton van Straaten anton at appsolutions.com
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
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

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

```