Minimax and Alpha-beta pruning

Question 1

What is a Game tree?

Answer 1

Directed graph that represents every possible outcome

Question 2

What happens if the entire game tree cannot be generated?

Answer 2

Generate a partial tree

Question 3

What type of search algorithm is the minimax algorithm?

Answer 3

DFS

Question 4

How does the minmax Alg work?

Answer 4

alternate turns, 1st move/layer = max, next layer = min until leaf node is reached

Question 5

What does the Max player try to do in minimax algorithm?

Answer 5

Maximize the minimum values at a position

Question 6

What does the Min player try to do in minimax algorithm?

Answer 6

Minimize max values at position

Question 7

Explanation of Minimax Alg

Answer 7

Repeat until entire tree is traversed{
if (limit is reached){ compute static value of current position relative to the appropriate player and report result }
else if (level is a minimising level){ use the minimax on the children of the current position. return min value of the results}
else{ if level is max level, use minimax on the children of the current position. return max of the results}

Question 8

What is the advantages of Minimax?

Answer 8

Considers all possible moves = most optimal moves to be made = very accurate

Question 9

What are the dis advantages of Minimax?

Answer 9

large branching factor for complex games = slow

Question 10

What is the goal for Alpha Beta Pruning?

Answer 10

Remove branches that have no effect.

Question 11

What does the alpha value store of AB Algorithm

Answer 11

best already explored option along a path to the root for the max layer.
Max score the Maximizer can receive (only maximizer can change this value)

Question 12

What does beta store of AB Algorithm?

Answer 12

Best already explored option along the path to the root for minimizing layer
Min score the minimizer can receive (only minimizer can change this value)

Question 13

When can we prune branches?

Answer 13

if A>=B (the min score is bigger or the same than the current max score)

Question 14

Code for AB pruning + minimax

Answer 14

A = inf, B = -inf
if( node = leaf){ return value}
if(node = min node){
For( each of the children){ apply Minimax + ABP;
if (value returned < B) { B = value}
if(B <= A){ return B}
}
if(node = max node){
For( each of the children){ apply Minimax + ABP;
if(returned value > A){ A = value}
if(A >= B){return A}
}
return A;