[Haskell-cafe] Memoized game-tree evaluation

Matthew adnorm at gmail.com
Sat Jul 25 10:08:20 EDT 2009


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.


More information about the Haskell-Cafe mailing list