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

Evaluating evaluation functions

A
  • It is a good idea to try different function and compare their performance and against certain special cases
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Minimax?

A
  • It is a depth first search
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

What is expectimax?

A
  • It is a variant from minimax but for games with randomness
How well did you know this?
1
Not at all
2
3
4
5
Perfectly