Announcements
“…there are two ways of constructing a software design: One way is to make it so simple that there are obviously no deficiencies and the other way is to make it so complicated there are no obvious deficiencies. The first method is far more difficult.”
— Tony Hoare, 1980 ACM Turing Award Lecture
©D. Poole 2021
CPSC 312 — Lecture 13 1 / 8
Review
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 13 2 / 8
©D. Poole 2021
Game Abstraction
type Player = State -> Action
A player is given a state of the game and selects a move.
type Game = Action -> State -> Result
A game takes an action and the state and returns a result Result is either
the end of the game with a reward and starting state or a continue with a new state
data Result = EndOfGame Double State
| ContinueGame State
As part of the state is internal state and the available moves:
data State = State InternalState [Action]
State is threaded through the code (a state is input and a state is output).
Generic players should not make any assumptions about the form of the internal state or the actions.
CPSC 312 — Lecture 13 3 / 8
©D. Poole 2021
Clicker Question
type Action = Int
data State = State ([Action],[Action]) [Action]
deriving (Eq, Show)
data Result = EndOfGame Double State
| ContinueGame State
deriving (Eq, Show)
What is not true:
A State is both a type and a constructor
B We can compare States with ==
C EndOfGame is a function of type Double -> State -> Result
D State([1],[])[4] == ContinueGame(State([1],[])[4]) returns False
E ContinueGame (State a b) can be used on the left side of an equality
©D. Poole 2021
CPSC 312 — Lecture 13 4 / 8
Clicker Question
type Action = Int
data State = State ([Action],[Action]) [Action]
deriving (Eq, Show)
data Result = EndOfGame Double State
| ContinueGame State
deriving (Eq, Show)
What happens if the third line is removed?
A Nothing as long as we don’t compare or show states
B It gives a compile-time error as Result then cannot be in Eq or Show
C It gives a run-time error if a state is compared or shown
D The proof of Show and Eq will loop forever
©D. Poole 2021
CPSC 312 — Lecture 13 5 / 8
Interacting with user (Play.hs)
Two mutually recursive functions:
person_play :: Game -> Result -> Player ->
TournammentState -> IO TournammentState
The person’s play: takes Game, the Result of the previous play (the computer’s move, except initially), the computer Player, and updates the tournament state
If the result (of previous move) is to continue, asks the person for an action, computes result, then it’s the computer’s turn
If the result (of previous move) is the end of the game, the value of the result is the value for the computer, and so needs to be negated for the person. Start again.
computer_play :: Game -> Result -> Player ->
TournammentState -> IO TournammentState
Similar except, it calls the Player to get the next action. No negation needed.
CPSC 312 — Lecture 13 6 / 8
©D. Poole 2021
Minimax
For two-player zero-sum games – the value for one player is the negation of the value of the other player – the optimal strategy can be computed using:
At the end of the game, the result provides the value for the player that ended the game.
When an action is chosen, the value for that player is the negation of value for the opposing player of the resulting state.
An agent gets to choose the action with the maximum value for them.
Use functional definition of a game to simulate game
Select move with best evaluation function
….. then it’s the opponents turn to select their best move ….. until end of game
CPSC 312 — Lecture 13 7 / 8
©D. Poole 2021
Minimax
type Game = Action -> State -> Result
The game can be asked hypothetical questions about the result of a move. (Because it is functional.)
A game has a value for each player at the end of the game. Assumes a two-player zero-sum game:
The value for a player is the negative of the value of the opponent.
minimax:: Game -> State -> (Action, Double) valueact :: Game -> State -> Action -> Double value:: Game -> Result -> Double
Minimax takes game and a state and returns (action,value) for the best move for agent playing,
assuming a move is available
type Player = State -> Action
mm_player:: Game -> Player
mm_player game state = fst ( minimax game state)
See Minimax.hs (run the test cases at bottom)
CPSC 312 — Lecture 13 8 / 8
©D. Poole 2021