Advanced game playing Flashcards
1
Q
What is iterative deepening?
A
- 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
2
Q
What is breadth first search?
A
- You must finish evaluating all the nodes in a certain level of the tree to be able to go to the next level
3
Q
Varying branching factor
A
- 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
4
Q
What is the horizon effect?
A
- 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
5
Q
Evaluating evaluation functions
A
- It is a good idea to try different function and compare their performance and against certain special cases
6
Q
What is alpha beta pruning?
A
- 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
7
Q
Minimax?
A
- It is a depth first search
8
Q
Which are good evaluation functions?
A
- 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.
9
Q
Multiplayer games
A
- 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
10
Q
What is multiplayer alpha beta pruning?
A
- 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
11
Q
What is expectimax?
A
- It is a variant from minimax but for games with randomness