Flashcards
Artificial intelligence - Adversial Search
Cards in this deck (12)
- 1Adversial Search Algorithm
- 2MinMaxGenerate game tree to the terminal states and apply the utiliy function on these state. After apply minmax to go on the top and value determine move.
Minmax is complete if tree is finite. - 3MinMax Algos
- 4Alpha-Beta Pruning• Discards parts of the search tree
○ guaranteed not to contain good moves
○ Similar idea than in search
• Same best result than MiniMax
• Substantial time and space savings
○ Cut the exponent in half
○ Still exponential, however - 5Alpha-Beta Algo
- 6Game Tree versus Graph• Possible to memorize visited states
• Store the evaluation of these states
• Called transposition tables (closed list)
• Impractical to store all the states ! - 7Imperfect real-time decisionsIn practice, make complete game tree is usually not pratical. So, program should cut off the search
earlier and apply a heuristic evaluation function on states in search to estimate the expected utility.
Change minmax :
1. Utility function by heuristic evaluation function (eval)
2. Replace terminal set by a cuttoff test that decide when apply eval - 8Minmax evaluation function• Must be consistent with the utility function.
• Tradeoff between accuracy and time cost.
• Reflect the actual chances of winning.
• Weighted linear function are frequently used with a combination of features.
We used weighted linear function only if the feature are independent (For exemple some piece in the
chess are more powerful at the end of the game because there is more space). So some program use non
linear combinations of feature. - 9Cutting off searchThe most straightforward approach ti to set a fixed depth limit. But there is a issue if the state is
favorable to fast change in the next state. . .
Quiescent To solve this problem, the evaluation function should be applied only to position that are
quiescent, i.e stable state. (unlikely to exhibit wild swings in value in the near futur) - 10Forward pruningSome moves at a given node are pruned immediatly without further consideration. It cutoff moves you
know are bad.
One approach is beam search : considere only at “beam” of the n best moves rather than all possible
moves. - 11Search vs LookupFor many game, table lookup are used for the opening and end of the game. Because at first (at the
end) the situation are very similar. After some moves, the actual search must be done because situation
differs. - 12ExapectminimaxAlgorithm that add chance node in addition to the max/min node.
Information
- Description
- A-Level Artificial intelligence Flashcards on Artificial intelligence - Adversial Search, created by Wojciech Gryncze on 10/01/2016.
- Created by
- Wojciech Gryncze · Jan 2016
- Updated
- Feb 19, 2016
- Views
- 0
- Tags
- Rating