Game Playing Flashcards

1
Q

Definition of games

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

zero-sum

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

perfect information

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

game playing as search

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Utility function

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Greedy Search Using an evaluation function

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

problem with greedy search using eval function

A

ignores what the opponent might do

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Minimax principle

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Minimax principle

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Minimax Propagation Up Tree

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

General Minimax Algorithm

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Time/space complexity of minimax algorithm

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Static Evaluation function

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

SBE used for

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

how is SBE calculated

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Minimax Algorithm

A
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)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

Alpha Beta Idea

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

Alpha Cutoff

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

Beta Cutoff

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

cutoff pruning occurs when

A

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

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

21
Q

alpha

A

largest value from its MAX node ancestors in search tree

22
Q

beta

A

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

23
Q

v at max

A

largest value from its children so far

24
Q

beta at max

A

comes from min node ancestors

25
alpha at min
comes from max node ancestors
26
prune at max value function
when v >= beta
27
prune at min value function
when alpha is greater than v
28
Time complexity of alpha-beta
In practice O(b^(d/2)) instead of O(b^d); same as having a branching factor of sqroot(b)
29
How to deal with limited time in game
use iterative deepening search - run alpha-beta search with DFS and increasing depth limit
30
How to avoid horizon effect
quiescence search | secondary search
31
quiescence search
when SBE value is frequently changing, look deeper than limit; look for point game "quiets down"
32
secondary search
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
33
book moves
build a database of opening moves, end games, studied configurations; if current state is in database, use it to determine next move/board evaluation
34
linear evaluation function
a weighted sum of features * weights, more important features get more weight
35
How to learn weights in linear evaluation function
play games; for every move or game, look at the error = true outcome - evaluation function
36
Non-deterministic game representation
game tree representation is extended to include "chance nodes": computer moves -> chance nodes -> opponent moves
37
How to score in non-deterministic games
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
38
expected value for move
compute average, weighted by the probabilities of each child; choose move with the highest expected value
39
non-deterministic games do what to branching factor
increase
40
lookahead in non-deterministic games
value diminishes - as depth increases, probability of reaching a given node decreases; alpha-beta pruning less effective
41
How to improve performance in games
reduce depth/breadth of search - use better SBEs (deep learning); sample possible moves instead of exploring all (use randomized exploration of search space)
42
Monte Carlo Tree Search
rely on repeated random sampling to obtain numerical results, stochasic simulation of game, game must be finite
43
Pure Monte Carlo Tree Search
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
44
playouts
select moves at random for both players until game over
45
exploitation
keep track of average wine rate for each child from previous searches; prefer child that has previously lead to more wins
46
exploration
allow for exploration of relatively univisited children (moves)
47
exploitation and exploration
combined to computer a score for each child, pick child with highest score at each successive node in search
48
Monte Carlo Tree Search Algorithm
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