Adversarial Search
adversarial_search | topic
Coverage Score
1
Mentioned Chunks
90
Mentioned Docs
8
Required Dimensions
definitionpros_cons
Covered Dimensions
definitionpros_cons
Keywords
two-playerzero-sum gamegame tree
Relations
| Source | Type | Target | W |
|---|---|---|---|
| Adversarial Search | CO_OCCURS | Alpha-Beta Pruning | 30 |
| Adversarial Search | CO_OCCURS | Minimax | 29 |
| Adversarial Search | CO_OCCURS | Utility Theory | 28 |
| Adversarial Search | CO_OCCURS | State-Space Search | 25 |
| Adversarial Search | CO_OCCURS | Problem Formulation | 22 |
| Adversarial Search | CO_OCCURS | Informed Search | 19 |
| Adversarial Search | CO_OCCURS | Uninformed Search | 14 |
| Adversarial Search | CO_OCCURS | Expectimax | 12 |
| Adversarial Search | CO_OCCURS | Heuristic Function | 10 |
| Adversarial Search | CO_OCCURS | Propositional Logic | 9 |
| Adversarial Search | CO_OCCURS | Inference | 5 |
| Adversarial Search | CO_OCCURS | Algorithm Evaluation Criteria | 5 |
| Adversarial Search | CO_OCCURS | Expected Utility | 5 |
| Adversarial Search | CO_OCCURS | Logical Agents | 4 |
| Adversarial Search | CO_OCCURS | Task Environment | 4 |
| Adversarial Search | CO_OCCURS | Making Simple Decisions | 4 |
| Adversarial Search | CO_OCCURS | Auto Topic: self | 4 |
| Adversarial Search | CO_OCCURS | Constraint Satisfaction Problem | 3 |
| Adversarial Search | CO_OCCURS | Auto Topic: row | 3 |
| Adversarial Search | CO_OCCURS | Depth-Limited Search | 3 |
| Adversarial Search | INCLUDES | Expectimax | 1 |
| Adversarial Search | INCLUDES | Minimax | 1 |
Evidence Chunks
| Source | Confidence | Mentions | Snippet |
|---|---|---|---|
textbook Artificial-Intelligence-A-Modern-Approach-4th-Edition.pdf | 0.69 | 2 | ... a more accurate term, but zero-sum is traditional and makes sense if you imagine each player is charged an entry fee of 1/2. 194 Chapter 6 Adversarial Search and Games XX XX X X X XX X X O OX O O X OX O X . . . . . . . . . . . . . . . . . . . . . XX –1 0 +1 XX X X O X X OX X O O ... |
textbook Artificial-Intelligence-A-Modern-Approach-4th-Edition.pdf | 0.69 | 2 | ... n percentage more and more as the number of playouts goes up. The time to compute a playout is linear, not exponential, in the depth of the game tree, because only one move is taken at each choice point. That gives us plenty of time for multiple 210 Chapter 6 Adversarial Search a ... |
textbook Artificial-Intelligence-A-Modern-Approach-4th-Edition.pdf | 0.69 | 2 | ... he legal moves for MAX and MIN will depend on the outcome of the dice roll in the previous chance node). For chance nodes we 212 Chapter 6 Adversarial Search and Games CHANCE MIN MAX CHANCE MAX . . . . . . B 1 . . . 1-1 1/36 1-2 1/18 TERMINAL 1-2 1/18 ...... ......... ...... 1-1 ... |
textbook Artificial-Intelligence-A-Modern-Approach-4th-Edition.pdf | 0.69 | 2 | ... ter decisions, all have costs, and all have some likelihood of resulting in a certain improvement in decision quality. Monte 220 Chapter 6 Adversarial Search and Games Carlo search does attempt to do metareasoning to allocate resources to the most important parts of the tree, but ... |
module_resources Module Resources/Module-4---Resources_unzipped/Module 5 - Resources/05-Adversarial-Search.pptx.pdf | 0.69 | 2 | ... Game Trees CIS 550 | Property of Penn Engineering | 16 CIS 421/521 | 16 Hexapawn: Simplified Game Tree for 2 Moves White to move Black to move White to move ⬤ ⬤ ⬤ ⬤ ⬤ ⬤ ⬤ ⬤ ⬤ ⬤ ⬤ ⬤ ⬤ ⬤ ⬤ ⬤ ⬤ ⬤ ⬤ ⬤ ⬤ ⬤ ⬤ ⬤ ⬤ ⬤ ⬤ ⬤ ⬤ ⬤ ⬤ ⬤ ⬤ ⬤ ⬤ ⬤ ⬤ ⬤ ⬤ ⬤ ⬤ ⬤ ⬤ ⬤ ⬤ ⬤ ⬤ ⬤ ⬤ ⬤ ⬤ ⬤ ⬤ ⬤ ⬤ ... |
textbook Artificial-Intelligence-A-Modern-Approach-4th-Edition.pdf | 0.68 | 4 | ... aft II games running on a commodity desktop with a single GPU, and ALPHA ZERO could have been run in that mode. Section 6.7 Limitations of Game Search Algorithms 219 MAX 99 100 99 1000 1000 1000 100 101 102 100 MIN Figure 6.16 A two-ply game tree for which heuristic minimax may m ... |
textbook Artificial-Intelligence-A-Modern-Approach-4th-Edition.pdf | 0.66 | 3 | d of this section. In 1928, von Neumann developed a method for finding the optimal mixed strategy for two-player, zero-sum games—games in which the payoffs always add up to zero (or a con-Zero-sum game Section 17.2 Non-Cooperative Game Theory 601 stant, as explained on page 193). ... |
textbook Artificial-Intelligence-A-Modern-Approach-4th-Edition.pdf | 0.66 | 3 | ... cted utility,−1/12, as the mixed strategy itself. Our result for two-finger Morra is an example of the general result by von Neumann: every two-player zero-sum game has a maximin equilibrium when you allow mixed strategies.◀ Furthermore, every Nash equilibrium in a zero-sum game i ... |
textbook Artificial-Intelligence-A-Modern-Approach-4th-Edition.pdf | 0.64 | 2 | ... 2) (0, 5, 2) (5, 4, 5) (1, 2, 6) (4, 2, 3) (6, 1, 2) (7, 4, 1) (5, 1, 1) (0, 5, 2) (7, 7, 1) (5, 4, 5) Figure 6.4 The first three ply of a game tree with three players ( A, B, C). Each node is labeled with values from the viewpoint of each player. The best move is marked at the r ... |
textbook Artificial-Intelligence-A-Modern-Approach-4th-Edition.pdf | 0.64 | 2 | ... (which says when the game is over), and a utility function that applies to terminal states to say who won and what the final score is. • In two-player, discrete, deterministic, turn-taking zero-sum games with perfect infor- mation, the minimax algorithm can select optimal moves b ... |
textbook Artificial-Intelligence-A-Modern-Approach-4th-Edition.pdf | 0.64 | 2 | ... heir extension to other games at the end of this section. In 1928, von Neumann developed a method for finding the optimal mixed strategy for two-player, zero-sum games—games in which the payoffs always add up to zero (or a con-Zero-sum game |
textbook Artificial-Intelligence-A-Modern-Approach-4th-Edition.pdf | 0.64 | 2 | ... 25,000 states in a minute or two. This is an exponential speedup over the normal-form approach, but still falls far short of handling, say, two-player Texas hold ’em, with 1018 states. 612 Chapter 17 Multiagent Decision Making If we can’t handle 10 18 states, perhaps we can simpl ... |
textbook Artificial-Intelligence-A-Modern-Approach-4th-Edition.pdf | 0.62 | 2 | ... primary conference venue is the International Conference on Principles and Practice of Constraint Programming, often called CP. CHAPTER 6 ADVERSARIAL SEARCH AND GAMES In which we explore environments where other agents are plotting against us. In this chapter we cover competitiv ... |
textbook Artificial-Intelligence-A-Modern-Approach-4th-Edition.pdf | 0.61 | 4 | ... As in Chapter 3, we can superimpose a search tree over Search tree part of that graph to determine what move to make. We define the complete game tree as a Game tree search tree that follows every sequence of moves all the way to a terminal state. The game tree may be infinite if t ... |
textbook Artificial-Intelligence-A-Modern-Approach-4th-Edition.pdf | 0.6 | 1 | ... . . . . . . . . . . . . . . . . . . . . . . 187 Bibliographical and Historical Notes . . . . . . . . . . . . . . . . . . . . . . . . 188 6 Adversarial Search and Games 192 6.1 Game Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192 6.2 Optimal Decisions in ... |
textbook Artificial-Intelligence-A-Modern-Approach-4th-Edition.pdf | 0.6 | 1 | ... ee and then backs up the minimax values through the tree as the recursion unwinds. For example, in Figure 6.2, the algorithm 196 Chapter 6 Adversarial Search and Games function MINIMAX -SEARCH (game, state) returns an action player ←game.TO-MOVE(state) value, move ← MAX-VALUE (ga ... |
textbook Artificial-Intelligence-A-Modern-Approach-4th-Edition.pdf | 0.6 | 1 | ... what would have happened any- way. In other cases, a social stigma attaches to breaking an alliance, so players must balance 198 Chapter 6 Adversarial Search and Games the immediate advantage of breaking an alliance against the long-term disadvantage of being perceived as untrust ... |
textbook Artificial-Intelligence-A-Modern-Approach-4th-Edition.pdf | 0.6 | 1 | ... not prune any successors of D at all because the worst successors (from the point of view ofMIN) were generated first. If the 200 Chapter 6 Adversarial Search and Games Player Opponent Player Opponent m n • • • m′ Figure 6.6 The general case for alpha–beta pruning. If m or m′ is b ... |