— CPSC 312 – 2019 – Games in Haskell
— Minimax with Memory
module Minimax_mem_hash where
— To run it, try:
— ghci
— :load Minimax_mem_hash
— Uncomment one of the following
import MagicSum_hash
— import MagicSum_ord_hash
— import MagicSum_ord_hash
— Uncomment one of the following
–import TreeDict
import HashTreeDict
–import FunDict
type Mem = Dict State (Action, Double)
—- Determining the best move —
minimax:: Game -> State -> Mem -> ((Action, Double), Mem)
— minimax game state memory => ((move,value_to_player),new_memory)
minimax game st mem =
case getval st mem of
Just act_val -> (act_val,mem)
Nothing ->
let (act_val,mem1) =
argmax_mem (valueact game st) avail mem
in (act_val, (insertval st act_val mem1))
where State _ avail = st
— valueact game st action is the value of doing action act in state st for game
valueact :: Game -> State -> Action -> Mem -> (Double,Mem)
valueact game st act = value game (game act st)
— value game move result = value for current player of the state after move given result
value:: Game -> Result -> Mem -> (Double,Mem)
value _ (EndOfGame val _) mem = (val, mem)
value game (ContinueGame st) mem =
let ((_,val), mem2) = minimax game st mem
in (-val,mem2)
— argmax_mem f lst mem = ((e, f e),mem1)
— updates the memory to mem1. Each call to f can uodate memory
argmax_mem :: Ord v => (e -> m -> (v,m)) -> [e] -> m -> ((e,v),m)
argmax_mem f [e] mem = ((e, v),mem1)
where (v,mem1) = f e mem
argmax_mem f (h:t) mem
| fh > ft = ((h,fh),mem2)
| otherwise = ((bt, ft),mem2)
where
((bt,ft),mem1) = argmax_mem f t mem
(fh,mem2) = f h mem1
— to find the best opening move
— minimax magicsum magicsum_start emptyDict
— stats (snd it) — gets the size and depth of the memory
— fst (minimax magicsum (magicsum Start) emptyDict) —– gets answer without the memory
–Try
as lst = [Action i | i <- lst] -- make it easier to type
-- minimax magicsum (State (as [8,5,4], as [1,2,6,9]) (as [3,7])) emptyDict
-- stats (snd it) -- gets the size and depth of the memory
-- minimax magicsum (State (as [8,5,4], as [1,2,6,9]) (as [3,7])) emptyDict
-- minimax magicsum (State (as [8,5], as [1,2]) (as [3,4,6,7,9])) (snd it)
-- minimax magicsum (State (as [1,2], as [4,5,8]) (as [3,4,6,7,9])) (snd it)
-- minimax magicsum (State (as [1,2,4,5], as [3,7,8,9]) (as [6])) (snd it)
-- minimax magicsum (State (as [1,2,4,5], as [3,6,8,9]) (as [7])) (snd it)
-- minimax magicsum (State (as [1,2,5], as [3,6,8,9]) (as [4,7])) (snd it)
-- minimax magicsum (State (as [1,5], as [3,8]) (as [2,4,6,7,9])) (snd it)
-- minimax magicsum (State (as [1], as [8,5]) (as [2,3,4,6,7,9]))) (snd it)
-- minimax magicsum (State (as [8,5], as [1,2]) (as [3,4,6,7,9])) (snd it)
-- minimax magicsum (State (as [5], as [3,8]) (as [1,2,4,6,7,9])) (snd it)
-- minimax magicsum (State ([], []) (as [1..9])) (snd it)
mm_player:: Game -> Player
mm_player game state = fst (fst ( minimax game state emptyDict))
{-
–with import MagicSum and TreeDict (at the top of this file):
:set +s
mm = minimax magicsum magicsum_start emptyDict
mema = (snd mm)
stats mema — returns
-}