Announcements
“Everything should be made as simple as possible, but not simpler.”
— attributed to Albert Einstein
©D. Poole 2021
CPSC 312 — Lecture 14 1 / 13
Haskell covered 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
CPSC 312 — Lecture 14 2 / 13
©D. Poole 2021
Overview
Last class:
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
A generic solver for the abstraction
Today:
Make it more efficient Abstract data types Threading state
CPSC 312 — Lecture 14
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 14
4 / 13
©D. Poole 2021
Magic Sum Game
players take turns choosing different numbers in range [0..9] first player to have 3 numbers that sum to 15 wins
tie if they run out of numbers to play
To use Play.hs we need to define: Action
Internal State
The Game Function
CPSC 312 — Lecture 14
5 / 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 14 6 / 13
©D. Poole 2021
Minimax
type Game = Action -> State -> Result
type Player = State -> Action
mm_player:: Game -> Player
Minimax takes a game and a state and returns (action,value) for the best move (assuming there are moves available)
minimax:: Game -> State -> (Action, Double) valueact :: Game -> State -> Action -> Double value:: Game -> Result -> Double
The value is either:
the value for the end of the game, or
the negation of the value for the opponent (who now plays)
mm_player game state = fst ( minimax game state) See Minimax.hs (run the test cases)
CPSC 312 — Lecture 14 7 / 13
©D. Poole 2021
Clicker Question
argmax2 :: Ord v => (e -> v) -> [e] -> (e,v)
argmax2 f (h:t) =
foldr (\ e (et,vt) -> let fe = f e in
if (fe > vt) then (e,fe)
else (et,vt))
(h, f h) t
What is not true about this:
A argmax2 f lst returns a pair
B It computes f of each element exactly once
C It works for every list that type checks
D It takes the first element from the list to start the foldr
©D. Poole 2021
CPSC 312 — Lecture 14 8 / 13
Clicker Question
argmax2 :: Ord v => (e -> v) -> [e] -> (e,v)
argmax2 f (h:t) =
foldr (\ e (et,vt) -> let fe = f e in
if (fe > vt) then (e,fe)
else (et,vt))
(h, f h) t
If there are multiple elements with the same maximal value for the function, what is returned?
A The first (e,v) pair that is maximal
B The last (e,v) pair that is maximal
C The second (e,v) pair that is maximal D All of the (e,v) paris that are maximal E It gives a run-time error.
©D. Poole 2021
CPSC 312 — Lecture 14 9 / 13
Improving Minimax
(a) Limit the depth of the tree, and have an evaluation function estimate value of a node when search stops.
(b) Learn value function from data (including self-play).
(c) Run it in parallel.
(d) Cache node values rather than recomputing.
(e) Exploit symmetry.
(f) Limit the width of the tree:
i) Prune dominated nodes (alpha-beta pruning)
ii) Sample random forward passes (Monte-Carlo tree search) iii) Learn plausible moves
Deep Blue (beat world chess champion 1997): a, c, d, f i AlphaGo (beat world Go champion 2016): b, c, f ii, f iii
CPSC 312 — Lecture 14 10 / 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
Minimax can use a state -> (action,value) dictionary. Define getval k dict = value of key k in dictionary dict What happens if k is not in dict?
In Prelude:
data Maybe a = Nothing | Just a
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”
CPSC 312 — Lecture 14 11 / 13
©D. Poole 2021
Binary Search Tree 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
See TreeDict.hs
CPSC 312 — Lecture 14 12 / 13
©D. Poole 2021
Dictionaries without data structures
A dictionary is a function from keys into values. Functions can be used to implement dictionaries
newtype Dict k v = FunDict (k -> Maybe v)
newtype is like data, but implemented like type no runtime overhead of constructor
We could have
type Dict k v = k -> Maybe v
except then we can’t implement show for dictionaries
instance Show (Dict k t) where
show d = “Function_dictionary”
See FunDict.hs
CPSC 312 — Lecture 14
13 / 13
©D. Poole 2021