Question

Artificial Intelligence Question. This topic is about Heuristic search and stochastic methods. I will like it if this is good explained and answer

Suppose you’re playing a game where you consecutively roll 3 dice. After each roll you may choose to either roll the next dice or sacrifice one die to reroll any number of the previous dice. If you get a number greater than 5 you win, but if you roll doubles or a number less than 6 you lose.

1. Considering each roll a separate state what is the approximate branching factor? Justify.
2. Draw the full state space considering only the number of distinct dice that have been rolled, not what’s on the dice (so if you have rolled one dice and have a 6 that is the same state as if you had rolled a 2). What is the approximate branching factor of this space?
3. Evaluate the probability of winning for each end state only considering the end state, not the path there.
4. Using the probability of winning as a heuristic highlight the path of a best first search.

Answer 1

Ans:

A useful measure of search efficiency is the effective branching factor, B. It describes how sharply a search process is focussed toward the goal. Suppose that search finds a path of length d and generates a total of N nodes. B is then equal to the number of successors of each node in that tree having the following properties:

Each nonleaf node in the tree has the same number (B) of successors.

The leaf nodes in the tree are all of depth d.

The total number of nodes in the tree is N.