On Fri, Feb 27, 2009 at 7:54 AM, Colin Paul Adams wrote:

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.

In my opinion keeping the code looking vaguely like the pseudo-code is a good idea for when you revisit it weeks later and try to remember what the hell you were originally doing. But I don't want to try and refactor the code you've provided without some tests to ensure everything is correct. Rule number one for refactoring. :) But for starters I imagine it's far more readable to covert all the 'case boolExpr of' expressions to 'if then else'. Secondly there's a lot of repeated functionality in there that should be abstracted to smaller functions, which I think could still be done without sacrificing the correlation to the algorithm pseudocode. There's 3 parts which check if alpha is greater than beta which could be abstracted and there's the check if rest is empty else recurse which could be abstracted. negascout' would be far more readable if you did this as long as you gave the helper functions good names. :) Sorry to be so vague though. If you have some data and tests then I can help you out some more if you like.

Any comments on my effort here, are welcome:

module Move (negascout            ) where

{-# contract negascout Ok -> {depth | depth >= 0} ->  Ok -> Ok -> Ok #-} negascout :: Node -> Int -> Int -> Int -> Int negascout node depth alpha beta =    case depth == 0 || is_terminal node of      True -> evaluate node      False -> let child:rest = children node                   b = beta  -- initial window is (-beta, -alpha)               in negascout' child (depth-1) (- b) (- alpha) beta rest

-- Implementation

{-# contract negascout' Ok -> {depth | depth >= 0} ->  Ok -> Ok -> Ok -> Ok -> Ok #-} negascout' :: Node -> Int -> Int -> Int -> Int -> [Node] -> Int negascout' node depth beta' alpha beta rest =    let a = negate $ negascout child depth beta' alpha    in case a > (- alpha) of         True -> let alpha' = a                 in case alpha' >= beta of                      True -> alpha' -- beta cut-off                      False -> case alpha' >= (- beta') of -- null window failed high?                                 True -> let alpha'' = negate $ negascout child depth (- beta) (- alpha') -- full re-search                                         in case alpha'' >= beta of                                                         True -> alpha'' -- beta cut-off                                                         False -> case rest of                                                                    [] -> alpha''                                                                    child':rest' -> let b' = alpha'' + 1                                                                                    in negascout' child' depth (- b') alpha'' beta rest'                                            False -> case rest of                                                       [] -> alpha'                                                             child':rest' ->  let b' = alpha' + 1                                                                              in negascout' child' depth (- b') alpha' beta rest'                    False -> case rest of                               [] -> alpha                                     child':rest' ->  let b' = alpha + 1                                                      in negascout' child' depth (- b') alpha beta rest'

-- Colin Adams Preston Lancashire _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

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