2
$\begingroup$

I would like to know how to find the average branching factor for 8 puzzle.While referring Artificial Intelligence by George F Luger it says that:

Suppose,for example we wish to establish the branching factor of the 8-puzzle.We calculate the total number of possible moves: 2 from each corner for a total of 8 corner moves,3 from center of each side for a total of 12, and 4 from the center of the grid for a grand total of 24.This divided by 9,the different possible locations of the blank, gives an average branching factor of 2.67.

Why do we have to divide by 9(possible locations of the blank space) to get the average branching factor.I'm confused with how the blank space affects the branching factor?

$\endgroup$
  • $\begingroup$ By "8 puzzle", you mean the sliding blocks puzzle with 8 tiles in a 3-by-3 grid? $\endgroup$ – David Richerby Feb 18 '15 at 17:11
  • $\begingroup$ "4 from the corner of the grid for a grand total of 24" should be "center" instead. $\endgroup$ – Daniil Agashiyev Feb 19 '15 at 3:41
  • $\begingroup$ @DavidRicherby:Yes of course. $\endgroup$ – justin Feb 20 '15 at 11:04
4
$\begingroup$

The average branching factor is defined as :

On average, how many moves can you do, from a given position.

For some positions (corners 4x), you have 2 moves. For other positions (sides 4x), you have 3 moves. Lastly, for some position (centers 1x), you have 4 moves.

So, a weighted average gives you $$4 \cdot 2 + 4 \cdot 3 + 1 \cdot 4 \over 4 + 4 + 1$$

The blank space affects the branching factor of a given position by limiting the number of moves you can make.

$\endgroup$
5
$\begingroup$

The relevance of the blank space is that a move is encoded by the transition of the blank space. So for example, if the blank space is in the center we have 4 possible moves:

enter image description here


This is what the author is talking about when he says

"2 from each corner for a total of 8 corner moves."

The blank space is what's in the corner. Here's one of the 4 possible corner positions:

enter image description here

As you can see, when the blank space is in the corner there are two possible transitions.

Continuing,

"3 from center of each side for a total of 12"

There are 4 centers of a side and each has 3 possible transitions.

enter image description here

I hope this combined with Jeffrey's weighted average explanation answers the question.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.