Advanced game playing

Question 1

What is iterative deepening?

Answer 1

• It is a method used in search for being able to obtain a result under the limit time.
• What you do is you start finding a minmax answer for the first level and you store it. Then, you begin again but find the answer for level 2 and store it. You keep looking for the solution for each level until time runs out and you return the answer for the last completed level.
• It is more efficient than DFS is the answer is in one of the top levels
• When the branching factor increases the redundancy of nodes visited by DFSID is less

Question 2

What is breadth first search?

Answer 2

• You must finish evaluating all the nodes in a certain level of the tree to be able to go to the next level

Question 3

Varying branching factor

Answer 3

• When this happens it is a good idea to combine shallow search and then depth search, depending on the branching behavior of the tree at certain levels

Question 4

What is the horizon effect?

Answer 4

• It is that the human player can detect that some move is going to define the result of the game although there are still some moves to finish, but the computer player can’t. So detecting this cases could make the search more efficient

Question 5

Evaluating evaluation functions

Answer 5

• It is a good idea to try different function and compare their performance and against certain special cases

Question 6

What is alpha beta pruning?

Answer 6

• The trick is that it is possible to compute the correct minimax decision without looking at every node in the game tree
• When applied to a standard minimax tree, it returns the same move as minimax would, but prunes away branches that cannot possibly influence the final decision.
• No possible better answer from looking other nodes
• Ordering correctly the game tree can make alpha beta pruning very fast

Question 7

Minimax?

Answer 7

• It is a depth first search

Question 8

Which are good evaluation functions?

Answer 8

• the evaluation function should order the terminal states in the same way as the true utility function: states that are wins better than draws better than losses.
• the computation must be faster than the normal minimax
• for nonterminal states, the evaluation function should be strongly correlated with the actual chances of winning.

Question 9

Multiplayer games

Answer 9

• You have to use a special version of minimax (Maxn). Each level corresponds to each players move. The evaluate value is a (3,3,3)
• Have to use a special Alpha Beta Pruning

Question 10

What is multiplayer alpha beta pruning?

Answer 10

• we assume an upper bound on the sum of the evaluations for each player, and a lower bound on each individual evaluation.
• then shallow alpha-beta pruning possible, not deep pruning.
• In the best case, the asymptotic branching factor is reduced to (1 + 4bv’~b-“s~-3)/2.
• In the average case, however, pruning does not reduce the asymptotic branching factor. alpha-beta pruning
  effective only in the special case of two-player games

Question 11

What is expectimax?

Answer 11

• It is a variant from minimax but for games with randomness