Table of Contents

## What is Expecti Max Search explain with algorithm?

The Expectimax search algorithm is a game theory algorithm used to maximize the expected utility. It is a variation of the Minimax algorithm. While Minimax assumes that the adversary(the minimizer) plays optimally, the Expectimax doesn’t.

## What is adversarial search?

Adversarial search is search when there is an “enemy” or “opponent” changing the state of the problem every step in a direction you do not want. Examples: Chess, business, trading, war.

**Which of the following is a variation of MIN MAX algorithm?**

The expectiminimax algorithm is a variation of the minimax algorithm, for use in artificial intelligence systems that play two-player zero-sum games, such as backgammon, in which the outcome depends on a combination of the player’s skill and chance elements such as dice rolls.

### What are the characteristics of adversarial search?

Adversarial Search

- Two player.
- Turn taking.
- Zero-sum.
- Perfect information — deterministic, fully observable.
- Have small number of possible actions.
- Precise, formal rules.

### When should one use adversarial search?

Each agent needs to consider the action of other agent and effect of that action on their performance. So, Searches in which two or more players with conflicting goals are trying to explore the same search space for the solution, are called adversarial searches, often known as Games.

**How is the expectimax algorithm used in game theory?**

The Chance nodes take the average of all available utilities giving us the ‘expected utility’. Thus the expected utilities for left and right sub-trees are (10+10)/2=10 and (100+9)/2=54.5. The maximizer node chooses the right sub-tree to maximize the expected utilities. Expectimax algorithm helps take advantage of non-optimal opponents.

#### How is the expectimax algorithm used in Pacman?

In Pacman, if we have random ghosts, we can model Pacman as the maximizer and ghosts as chance nodes. The utility values will be the values of the terminal states (win, lose or draw) or the evaluation function value for the set of possible states at a given depth.

#### Which is better minimax or expectimax for minimax?

For minimax, if we have two states S1 and S2, if S1 is better than S2, the magnitudes of the evalaution function values f (S1) and f (S2) don’t matter as along as f (S1) > f (S2) . For expectimax, magnitudes of the evaluation function values matter. Algorithm: Expectimax can be implemented using recursive algorithm as follows,

**When to use expectimax as a heuristic value?**

// taken as heuristic value. Space complexity: O (b*m), where b is branching factor and m is the maximum depth of the tree. Applications: Expectimax can be used in environments where the actions of one of the agents are random. Following are a few examples,