Game Playing

Question 1

Definition of games

Answer 1

zero-sum, discrete, finit, determinist, perfect information

Question 2

zero-sum

Answer 2

one player’s gain is the other player’s loss; does not mean fair

Question 3

perfect information

Answer 3

each player can see the complete game state; no simultaneous decisons

Question 4

game playing as search

Answer 4

states - board configuration
actions - legal moves
initial state - starting board configuration
goal state - game over/terminal board configuration

Question 5

Utility function

Answer 5

used to map each terminal state of the board to a score indicating the value of that outcome to the computer

Question 6

Greedy Search Using an evaluation function

Answer 6

expand the search tree to the terminal states on each branch; evaluate the utility of each terminal board configuration; make the initial move that results in the board configurations with the maximum value

Question 7

problem with greedy search using eval function

Answer 7

ignores what the opponent might do

Question 8

Minimax principle

Answer 8

Assume both players play optimally; computer should choose maximizing moves (high utility), opponent = minimizing moves (low utility)

Question 9

Minimax principle

Answer 9

computer chooses the best move considering both its move and the opponent’s optimal move

Question 10

Minimax Propagation Up Tree

Answer 10

Start at leaves; assign value to parent - min if opponent’s move; max if computer’s move

Question 11

General Minimax Algorithm

Answer 11

For each move done by computer:
perform DFS, stop at terminal states, evaluate each terminal state, propagate upwards the minimax values; choose the move at root with the maximum of the minimax values of its children

Question 12

Time/space complexity of minimax algorithm

Answer 12

space O(bd) (DFS); time: O(b^d)

Question 13

Static Evaluation function

Answer 13

impractical to search game space to all terminal states and apply utility function; SEF - use heuristics to estimate the value of non-terminal state

Question 14

SBE used for

Answer 14

estimating how good the current board configuration is for the computer; reflects chances of winning from that node; must be easy to calculate

Question 15

how is SBE calculated

Answer 15

one subtracts how good it is for the opponent from how good it is for the computer; SBE should agree with the Utility function when calculated at terminal nodes

Question 16

Minimax Algorithm

Answer 16

MaxValues
if (terminal state or depth limit); return SBE value of s
else v = -infinity
   for each s in successors(s)
   v = max (v, Min-Values)

Question 17

Alpha Beta Idea

Answer 17

At maximizing levels; keep track of highest SBE value seen so far in each none
At minimizing levels, lowest SBE value seen so far in tree below

Question 18

Alpha Cutoff

Answer 18

At each min node, keep track of the minimum value return so far from its visited children, store in v; each time v is updated, check its value against the alpha value of all its Max node ancesters; if alpha >= v don’t visit any more of MIN node’s children

Question 19

Beta Cutoff

Answer 19

at each max node, keep track of the maximum value returned so far from its visited children, store in v; each time v is updated at a max node, check its value against the beta value of all its MIN node ancestors; if v >= beta don’t vist any more of the current Max node’s children

Question 20

cutoff pruning occurs when

Answer 20

at max node if alpha >= beta for some Min ancessor

at min node; if for some max node ancestor alpha >= beta

Question 21

alpha

Answer 21

largest value from its MAX node ancestors in search tree

Question 22

beta

Answer 22

smallest (best value) from its min node ancestors in search tree

Question 23

v at max

Answer 23

largest value from its children so far

Question 24

beta at max

Answer 24

comes from min node ancestors

Question 25

alpha at min

Answer 25

comes from max node ancestors

Question 26

prune at max value function

Answer 26

when v >= beta

Question 27

prune at min value function

Answer 27

when alpha is greater than v

Question 28

Time complexity of alpha-beta

Answer 28

In practice O(b^(d/2)) instead of O(b^d); same as having a branching factor of sqroot(b)

Question 29

How to deal with limited time in game

Answer 29

use iterative deepening search - run alpha-beta search with DFS and increasing depth limit

Question 30

How to avoid horizon effect

Answer 30

quiescence search

secondary search

Question 31

quiescence search

Answer 31

when SBE value is frequently changing, look deeper than limit; look for point game “quiets down”

Question 32

secondary search

Answer 32

find best move looking to depth d
look k steps beyond to verify that it still looks good
if it doesn’t, repeat step 2 for the next best move

Question 33

book moves

Answer 33

build a database of opening moves, end games, studied configurations; if current state is in database, use it to determine next move/board evaluation

Question 34

linear evaluation function

Answer 34

a weighted sum of features * weights, more important features get more weight

Question 35

How to learn weights in linear evaluation function

Answer 35

play games; for every move or game, look at the error = true outcome - evaluation function

Question 36

Non-deterministic game representation

Answer 36

game tree representation is extended to include “chance nodes”: computer moves -> chance nodes -> opponent moves

Question 37

How to score in non-deterministic games

Answer 37

weight score by the probability that move occurs
use expected value for move, instead of using max or min, compute the average weighted by the probabilities of each child

Question 38

expected value for move

Answer 38

compute average, weighted by the probabilities of each child; choose move with the highest expected value

Question 39

non-deterministic games do what to branching factor

Answer 39

increase

Question 40

lookahead in non-deterministic games

Answer 40

value diminishes - as depth increases, probability of reaching a given node decreases; alpha-beta pruning less effective

Question 41

How to improve performance in games

Answer 41

reduce depth/breadth of search - use better SBEs (deep learning); sample possible moves instead of exploring all (use randomized exploration of search space)

Question 42

Monte Carlo Tree Search

Answer 42

rely on repeated random sampling to obtain numerical results, stochasic simulation of game, game must be finite

Question 43

Pure Monte Carlo Tree Search

Answer 43

for each possible legal move of current player, simulate k random games with playouts, count how many were wins, move with most wins is selected

Question 44

playouts

Answer 44

select moves at random for both players until game over

Question 45

exploitation

Answer 45

keep track of average wine rate for each child from previous searches; prefer child that has previously lead to more wins

Question 46

exploration

Answer 46

allow for exploration of relatively univisited children (moves)

Question 47

exploitation and exploration

Answer 47

combined to computer a score for each child, pick child with highest score at each successive node in search

Question 48

Monte Carlo Tree Search Algorithm

Answer 48

Start at root, successively select best child nodes using scoring method until leaf node L reached, create and add best new child C of L; perform random playout from C, update score at C and all of c’s ancestors in search tree