tags:

views:

241

answers:

2

So I'm working on a minimax implementation for a checkers-like game to help myself learn Haskell better. The function I'm having trouble with takes a list for game states, and generates the list of immediate successor game states. Like checkers, if a jump is available, the player must take it. If there's more than one, the player can choose.

For the most part, this works nicely with the list monad: loop over all the input game states, loop over all marbles that could be jumped, loop over all jumps of that marble. This list monad nicely flattens all the lists out into a simple list of states at the end.

The trick is that, if no jumps are found for a given game state, I need to return the current game state, rather than the empty list. The code below is the best way I've come up with of doing that, but it seems really ugly to me. Any suggestions on how to clean it up?

eHex :: Coord -> Coord -- Returns the coordinates immediately to the east on the board
nwHex :: Coord -> Coord -- Returns the coordinates immediately to the northwest on the board

generateJumpsIter :: [ZertzState] -> [ZertzState]
generateJumpsIter states = do
    ws <- states
    case children ws of
      [] -> return ws
      n@_ -> n
  where 
    children ws@(ZertzState s1 s2 b p) = do
      (c, color)  <- occupiedCoords ws
      (start, end) <- [(eHex, wHex), (wHex, eHex), (swHex, neHex),
                       (neHex, swHex), (nwHex, seHex), (seHex, nwHex)]
      if (hexOccupied b $ start c) && (hexOpen b $ end c)
        then case p of
          1 -> return $ ZertzState (scoreMarble s1 color) s2
                                   (jumpMarble (start c) c (end c) b) p
          (-1) -> return $ ZertzState s1 (scoreMarble s2 color)
                                      (jumpMarble (start c) c (end c) b) p
        else []

EDIT: Provide example type signatures for the *Hex functions.

+1  A: 

Don't abuse monads notation for list, it's so heavy for nothing. Moreover you can use list comprehension in the same fashion :

do x <- [1..3]
   y <- [2..5]      <=>  [ x + y | x <- [1..3], y <- [2..5] ]
   return x + y

now for the 'simplification'

listOfHex :: [(Coord -> Coord,Coord -> Coord)]
listOfHex = [ (eHex, wHex), (wHex, eHex), (swHex, neHex)
            , (neHex, swHex), (nwHex, seHex), (seHex, nwHex)]

generateJumpsIter :: [ZertzState] -> [ZertzState]
generateJumpsIter states =
    [if null ws then ws else children ws | ws <- states]
  where -- I named it foo because I don t know what it do....
    foo True   1  = ZertzState (scoreMarble s1 color) s2
                               (jumpMarble (start c) c (end c) b) p
    foo True (-1) = ZertzState s1 (scoreMarble s2 color)
                               (jumpMarble (start c) c (end c) b) p
    foo False  _  = []
    foo _ _ = error "Bleh"

    children ws@(ZertzState s1 s2 b p) =
      [ foo (valid c hex) p | (c, _)  <- occupiedCoords ws, hex <- listOfHex ]
        where valid c (start, end) =
                 (hexOccupied b $ start c) && (hexOpen b $ end c)

The let in the let in list commprehension at the top bother me a little, but as I don't have all the code, I don't really know how to do it in an other way. If you can modify more in depth, I suggest you to use more combinators (map, foldr, foldl' etc) as they really reduce code size in my experience.

Note, the code is not tested, and may not compile.

Raoul Supercopter
Can't the first list comprehension just be [if null (children ws) then ws else children ws | ws <- states] ? I would expect that repetition of the function call would be eliminated by the compiler.
Nathan Sanders
yep, edited code to follow your comment
Raoul Supercopter
listOfHex would have type listOfHex :: [Coord -> Coord]Every hex on the board is identified by a Coord (which is just a synonym for a pair of Int's). The function nwHex, for example, returns the coordinates the hex to the northwest of the input hex.listOfHex then contains pairs of these functions, which are used to identify if a jump is possible.
Resistor
listOfHex :: [(Coord -> Coord,Coord -> Coord)], it's a list of pair, and each is a function
Raoul Supercopter
You're right. Sorry, my bad.
Resistor
+3  A: 

The trick is that, if no jumps are found for a given game state, I need to return the current game state, rather than the empty list.

Why? I've written minimax several times, and I can't imagine a use for such a function. Wouldn't you be better off with a function of type

nextStates :: [ZertzState] -> [Maybe [ZertzState]]

or

nextStates :: [ZertzState] -> [[ZertzState]]

However if you really want to return "either the list of next states, or if that list is empty, the original state", then the type you want is

nextStates :: [ZertzState] -> [Either ZertzState [ZertzState]]

which you can then flatten easily enough.

As to how to implement, I recommend defining a helper function of type

[ZertzState] -> [(ZertzState, [ZertzState])]

and than you can map

(\(start, succs) -> if null succs then Left start else Right succs)

over the result, plus various other things.

As Fred Brooks said (paraphrasing), once you get the types right, the code practically writes itself.

Norman Ramsey
This is just _part_ of the code for generating the set of possible moves, which is part of the input to minimax. In particular, it is the part concerned with generating the available jumps.
Resistor
The rules are checkers-like: if there are jumps available, they must be taken. If there is more than one available, the player can choose which to take. Chained jumps (i.e. double jumping in checkers) is allowed, and the same required-if-available rule applies.
Resistor
I've been thinking of this as a recursively generated tree of states. I start with the list containing the initial state. From that, I generate the list of reachable states that are at most one jump away. From those I generate the list of states that are at most two jumps away, etc. I repeat this process until the list stops changing.This only works if "dead-end" states stay in the list, rather going to the empty list.
Resistor
@Resistor: It's Haskell! Why aren't you just lazily generating the infinite move tree. All the info you need is in John Hughes's paper [Why Functional Programming Matters](http://www.cs.chalmers.se/~rjmh/Papers/whyfp.html)
Norman Ramsey