Announcements
I have made this longer than usual because I have not had time to make it shorter.
Blaise Pascal, 1657
I have already made this paper too long, for which I must crave pardon, not having now time to make it shorter.
Benjamin Franklin, 1750
From https: //quoteinvestigator.com/2012/04/28/shorter-letter/
©D. Poole 2021
CPSC 312 — Lecture 15 1 / 13
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)
CPSC 312 — Lecture 15 2 / 13
©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).
Abstract data types (two dictionary implementations). Today:
Make minimax more efficient Threading state Meomization
CPSC 312 — Lecture 15
3 / 13
©D. Poole 2021
Games
Players observe state and make actions
Games take actions and update 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 15
4 / 13
©D. Poole 2021
Counting Game
Players can choose number in a fixed set, e.g., {1, 2, 3, 5, 7} Internal state is a number
When a player plays an action i the state is incremented by i.
Player loses if the internal state is greater than or equal to a break value (e.g., 20 or 21).
CPSC 312 — Lecture 15 5 / 13
©D. Poole 2021
Minimax
type Game = Action -> State -> Result
type Player = State -> Action
mm_player:: Game -> Player
The game can be asked hypothetical questions about the result of a move. (Because it is functional.)
In any state (if there is a move available), the agent chooses the action with the highest value after playing the action. The value is either:
the value for the end of the game, or
the negation of the value for the opponent (who now plays)
minimax:: Game -> State -> (Action, Double)
Minimax takes a game and a state and returns (action,value) for the best move (assuming there are moves available) value:: Game -> Result -> Double
mm_player game state = fst ( minimax game state) See Minimax.hs (run the test cases)
CPSC 312 — Lecture 15 6 / 13
©D. Poole 2021
Improving Minimax by caching results
Minimax could cache the values of states it has evaluated A dictionary can be used to remember values
A dictionary maps a key to a value
Dict k v
is a dictionary with key type k and value type v
Dict Interface:
emptyDict :: Dict k v
getval :: (Ord k) => k -> Dict k v -> Maybe v
insertval :: (Ord k) => k -> v -> Dict k v
-> Dict k v
stats :: Dict t1 t2 -> [Char]
“abstract data type” Minimax can use
Dict state (action,value)
CPSC 312 — Lecture 15
7 / 13
©D. Poole 2021
Binary Search Tree as Implementation of Dictionary
A binary search tree can be used to implement a dictionary
data BSTree k v
= BSEmpty
| BSNode k v (BSTree k v) (BSTree k v)
deriving (Show)
– a binary search tree where k is the type of key, and v is type of value
It can be made to follow the Dict API. See TreeDict.hs
CPSC 312 — Lecture 15 8 / 13
©D. Poole 2021
Clicker Question
data BSTree k v
= BSEmpty
| BSNode k v (BSTree k v) (BSTree k v)
What is not true:
A k is a type variable
B BSNode “Fun” 7 BSEmpty BSEmpty
is of type Num v => BSTree [Char] v
C BSTree is a function that takes 2 arguments
D When using the data structure, k needs to be resolved into an
actual type
E BSNode is a function that takes 4 arguments
©D. Poole 2021
CPSC 312 — Lecture 15 9 / 13
Minimax with memory (Minimax mem.hs)
Minimax without memory:
minimax:: Game -> State -> (Action, Double) valueact :: Game -> State -> Action -> Double value:: Game -> Result -> Double
What type should memory be? Either:
type Mem = Dict State (Action, Double) 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 as appropriate.
CPSC 312 — Lecture 15 10 / 13
©D. Poole 2021
Threading state through value function
With
type Mem = Dict State (Action, Double)
value function:
value:: Game -> Result -> Double
value _ (EndOfGame val _) = val
value game (ContinueGame st) = – snd (minimax game st)
value function with memory (does not update dictionary)
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 15 11 / 13
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 15 12 / 13
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 15 13 / 13