I'm working on defining a data type for representing game-trees for chess or other two-person board games. My plan is to memoize the evaluations of a game-state at each depth so that values don't need to be recomputed for future moves.
Here's the definition I'm using so far:

        data GameState = GameState {color :: Color, board :: Board}
data GameTree = GameTree {state :: GameState, values :: [Int], branches :: [GameTree]}

        genGameTree :: GameState -> GameTree
genGameTree st | finalState st = GameTree st (repeat (evalState st)) []
                                        | otherwise     = GameTree st vs bs
         where
                bs = map genGameTree (nextStates st)
vs = (evalState st) : map (\d -> (optimize (color st)) (map ((!!d) . values) bs)) [0..]
                optimize Black = minimum
                optimize White = maximum

I'd like to rewrite the generation of "vs" to evaluate using alpha- beta cutoffs, but I'm having trouble coming up with a way to do so without losing memoization. I don't know if my failures so far are because ab-pruning is necessarily incompatible
with memoization, or if I simply haven't found the right insight yet.

Can anyone suggest a solution, or convince me there isn't one?

Thanks in advance.
_______________________________________________
Haskell-Cafe mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/haskell-cafe

Reply via email to