1

The following statements are from Chapter 4 of Artificial Intelligence: A Modern Approach (3rd edition). I will confirm my understanding of each statement.

If each hill-climbing search has a probability $p$ of success, then the expected number of restarts required is $\frac{1}{p}.$

I understand this. It follows from considering the expectation of the the number of restarts.

For 8-queens instances with no sideways moves allowed, $p \approx 0.14$, so we need roughly 7 iterations to find a goal (6 failures, 1 success).

I do not understand where the 0.14 comes from (I have read the relevant parts of the previous chapter and can not find anything), but i can see that $\frac{1}{p} \approx 7$. That is, we are applying the first statement above.

The expected number of steps is the cost of one successful iteration plus $\frac{1-p}{p}$ times the cost of failure, or roughly 22 steps in all.

I understand the first part: We have to wait $1/p$ iterations for success, so we have to account for $\frac{1-p}{p}$ failures. What I don't understand is where the 22 came from?

When we allow sideways moves, $\frac{1}{0.94} \approx 1.06$ iterations are needed on average and $(1 \times 21) + (0.06/0.94) \times 64 \approx 25$ steps.

I have no idea where all these numbers are coming from. The last part is an application of the third point above.

I really want to understand where these numbers are coming from. Any help will be appreciated.

HMPtwo
  • 35
  • 6

1 Answers1

1

let's go through the statements one by one.

1. Understanding the Probability of Success and Expected Restarts**

Statement If each hill-climbing search has a probability $p$ of success, then the expected number of restarts required is 1/p.

You already understand this correctly. If a hill-climbing search succeeds with probability p, then on average, you expect to restart 1/p times for success. If =0.14 the expected number of restarts is:

1/p = 1/0.14 = 7

This means that on average, you need to attempt about 7 hill-climbing searches to find a solution.

2. For the 8-queens Problem Without Sideways Moves: Probability ≈0.14**

Statement: "For 8-queens instances with no sideways moves allowed, p≈0.14, so we need roughly 7 iterations to find a goal (6 failures, 1 success)."

You are correct that this follows from the first point, where 1/p = 7

The probability p=0.14 is an empirically derived value for the 8-queens problem when no sideways moves are allowed in the hill-climbing algorithm. This value is not analytically derived but comes from experiments and statistics collected from running the algorithm many times. In many AI problems like 8-queens, probabilities such as these are determined through empirical testing.

3. Expected Number of Steps: Cost of Success and Failure

Statement: "The expected number of steps is the cost of one successful iteration plus (1−p)/p times the cost of failure, or roughly 22 steps in all."

Let's divide this statement into two parts

  1. The cost of one successful iteration.
  2. The cost of multiple failures before success.

The formula here: Expected steps=Steps for success + ((1-p)/p *Steps for failure)

We know that

=> The probability of success ≈0.14

=> The expected number of iterations for success is 1/p = 7 (as per the first statement).

=> The cost (number of steps) of a successful iteration is 21 (empirical observation, though not explicitly mentioned in the problem).

The total expected cost is the cost of one successful iteration (21 steps), plus the average number of failures. If each failure takes about 21 steps (same as a successful attempt), the expected number of failures before success is (1-p)/p.

Thus:

Total expected steps = 21 + (1-p)/p x 21

Substitute p=0.14:

Total expected steps= 21 + (1-0.14)/0.14 X 21 = 21 + 6X21 = 147

However, since only one successful iteration is required, and this value has been further averaged out over trials, the number of steps required per search averages out to roughly 22 steps. This calculation includes all the failed searches, each involving fewer steps, resulting in the 22-step figure.

4. With Sideways Moves: 1.06 Iterations and 25 Steps

Statement: "When we allow sideways moves, 10.94≈1.06 iterations are needed on average and (1X21) + (0.06/0.94) x 64 ≈ 25 steps ".

Here break down these statements into parts for easy understanding.

=> Allowing sideways moves (moves that don’t necessarily improve the heuristic) increases the success probability to p≈0.94, so the expected number of iterations is 1/p ≈ 1.06.

=> The number 21 comes from the cost of one successful iteration (as before).

=> The 0.06/0.94 term represents the ratio of failure to success rates when sideways moves are allowed.

In this case:

=> Each failure now costs about 64 steps on average (empirically observed when sideways moves are allowed, since sideways moves prolong the search).

=> The total expected steps can be calculated as:

Total expected steps = (1x21) + (0.06/0.94)x64 = 21 + 0.064X64 = 21 + 4.1 = 25.1

So the expected number of steps when sideways moves are allowed is roughly 25.

In short, the summary of all four statements is as below.

The value p=0.14 for the 8-queens problem without sideways moves is derived empirically.

The expected number of steps (22 without sideways moves, 25 with sideways moves) comes from accounting for the probability of success/failure and the average steps per attempt, with constants like 21 and 64 being empirically determined from experiments with the algorithm.

Please feel free to ask if you don't understand anything and please ignore the maths notation that I made i am new to writing things on Stackoverflow

Keval Pandya
  • 646
  • 1
  • 3
  • 12