Announcements
Midterm #2 next Monday ¡ª watch the course web site for more details
One must learn by doing the thing; for though you think you know it, you have no certainty until you try.
Sophocles (¡Ö 497- 406 BCE)
CPSC 312 ¡ª Lecture 16 1 / 15
ýD. Poole 2021
Review: Haskell since midterm
type defines a type name as an abbreviation for other types data defines new data structures (and a type) and
constructors / deconstuctors
IO t is the input/output monad
do can be used to sequence input/output operations
newtype is like data but with more restrictions (and no runtime overhead)
Type constructors and type variables
CPSC 312 ¡ª Lecture 16 2 / 15
ýD. Poole 2021
Overview
Last classes:
Abstraction for games, so we can write interfaces and solvers for any games that fit the abstraction
Representation of magic-sum game and count game A simple human interface for the abstraction
mm_player: a player that searches through all possible games and returns a best move. (Using minimax).
Make minimax more efficient (Caching / Memoization) Abstract data types
Threading state
Today:
More on games and abstract data types
CPSC 312 ¡ª Lecture 16 3 / 15
ýD. Poole 2021
Games
Players observe state and make actions
Games take actions and give a result: updated state of game,
perhaps finishing.
type Game = Action -> State -> Result
type Player = State -> Action
data State = State InternalState [Action]
deriving (Ord, Eq, Show)
data Result = EndOfGame Double State
| ContinueGame State
deriving (Eq, Show)
See MagicSum.hs Play.hs CountGame.hs
CPSC 312 ¡ª Lecture 16
4 / 15
ýD. Poole 2021
Improving Minimax by Caching Results (using a memory)
Minimax without memory:
minimax:: Game -> State -> (Action, Double)
valueact :: Game -> State -> Action -> Double
value:: Game -> Result -> Double
What type should memory be?
type Mem = Dict State (Action, Double)
Memory can be threaded through the program:
minimax:: Game -> State ->
Mem -> ((Action, Double), Mem)
valueact :: Game -> State -> Action ->
Mem -> (Double,Mem)
value:: Game -> Result ->
Mem -> (Double,Mem)
The can all use, pass the memory to functions they call, and update memory.
CPSC 312 ¡ª Lecture 16 5 / 15
ýD. Poole 2021
Threading state through value function
value function:
value:: Game -> Result -> Double
value _ (EndOfGame val _) = val
value game (ContinueGame st) = – snd (minimax game st)
value function with memory
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)
ýD. Poole 2021
CPSC 312 ¡ª Lecture 16 6 / 15
Threading state through minimax function
minimax:: Game -> State -> (Action, Double)
minimax game st =
argmax (valueact game st) avail
where State _ avail = st
With memory:
type Mem = Dict State (Action, Double)
minimax:: Game -> State -> Mem -> ((Action, Double), Mem)
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
ýD. Poole 2021
CPSC 312 ¡ª Lecture 16 7 / 15
Argmax with memory
argmax :: Ord v => (e -> v) -> [e] -> (e,v)
argmax f [e] = (e, f e)
argmax f (h:t)
| fh > ft = (h,fh)
| otherwise = (bt, ft)
where (bt,ft) = argmax f t
fh = f h
argmax with 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
ýD. Poole 2021
CPSC 312 ¡ª Lecture 16 8 / 15
Making Caching Useful
Caching doesn¡¯t prune any nodes in magic-sum game! Why? Represent each state in canonical form:
unique representation for each state. (sorted lists)
with import MagicSum and TreeDict (top of Minimax mem): *Minimax_mem> minimax magicsum magicsum_start emptyDict ((9,0.0),dict)
*Minimax_mem> mema = (snd it)
*Minimax_mem> stats mema
“Number of elements=294778, Depth=103”
with import MagicSum ord and TreeDict (at the top of
Minimax mem):
*Minimax_mem> minimax magicsum magicsum_start emptyDict ((9,0.0),dict)
*Minimax_mem> mema = (snd it)
*Minimax_mem> stats mema
“Number of elements=4520, Depth=52”
ýD. Poole 2021
CPSC 312 ¡ª Lecture 16 9 / 15
Balancing Trees
“Number of elements=294778, Depth=103”
“Number of elements=4520, Depth=52”
What is suspicious about this?
The trees are are very unbalanced. The first dictionary should be able to be represented with a tree of depth 19, and the second one with a tree of depth 13.
Is there a simple way to keep the tree approximately balanced?
use (hash k,k) as the key in the tree, as long as hask k randomizes the ordering.
CPSC 312 ¡ª Lecture 16 10 / 15
ýD. Poole 2021
Clicker Question
Using (hash k,k) as the key in the tree
A has to be done as a special case each time because hash needs to be defined for each type, and Haskell needs a type for the hash function
B could be done in DictTree just by calling hash
C could be done if we define a class for types that include a
hash function, and only use hash for types in the class
D requires support in a low level language like C++, because hash functions could only improve performance if defined efficiently in C++.
ýD. Poole 2021
CPSC 312 ¡ª Lecture 16 11 / 15
Building a hashing dictionary
Define a class for types that implement hash Make the type State be in that class
Define a hashing tree dictionary that uses hash, but does not change the definition of TreeDict
CPSC 312 ¡ª Lecture 16 12 / 15
ýD. Poole 2021
Defining classes (Hash.hs, )
Define a class for types that implement hash class Hash t where
hash :: t -> Int
A type in the Hash class implements hash.
Define hash functions for Ints
instance Hash Int where
hash n = floor(numHashVals *
fractionalPart(arbMun *fromIntegral n))
Define a hash function for lists (as long as the base type is hashable):
instance Hash t => Hash [t] where
hash [] = 1741
hash (h:t) = hash ( hash h + hash t)
CPSC 312 ¡ª Lecture 16 13 / 15
ýD. Poole 2021
Clicker Questions
For the two definitions of Hash for lists:
i) instance Hash t => Hash [t] where hash [] = 1741
hash (h:t) = hash ( hash h + hash t)
ii) instance Hash t => Hash [t] where
hash lst = hash (sum [hash e | e <- lst])
Which one always maps permutations to the same value? A Both (i) and (ii)
B (i) but not (ii)
C (ii) but not (i)
D neither
ýD. Poole 2021
CPSC 312 ¡ª Lecture 16 14 / 15
Defining a tree dictionary with hashing
How can we build a hashing tree dictionary, without changing TreeDict?
See HashTreeDict.hs
Note that Haskell has a standard class Hashable that act like our Hash.
CPSC 312 ¡ª Lecture 16 15 / 15
ýD. Poole 2021