Mirrored Search

In the picture below, think of the centre of the left circles as your goal position. Think of the centre of the right circles as your starting position.

The circles around these centres show the number of nodes searched for each depth of search. You note that in the mirrored scenario, there is an overlap at depth 9. The large black circle drawn around the right circle shows the depth it would have taken if we didn't use mirrored search - depth 18.

For nearly any scenario it's a very simple calculation to prove that 2*depth9 is far more efficient than 1*depth18.

For example; if I expand 5 nodes at every iteration:

2*depth9 = 3,906,250. Quite an improvement on 3,814,697,265,625 I'm sure you'll agree.

Ian MacGillivray, 2008. For Jagex.