[r-t] Bobs only Erin Triples (was: Composition search)
alan.burlison at gmail.com
Wed Nov 25 13:55:57 UTC 2015
On 25/11/2015 12:12, Ian Broster wrote:
> You can remove rotations of the same touch from the search space by
> using the path from the root to the current node as your starting point
> for the next recursion.
> For example, if your path from root to node is ppppppb (because you have
> already found that ppppppp is false (or actually, comes round and makes
> any longer touch containing it false - awkward corner case!) then you do
> not need to try (ever) the sequence ppppppp in your search space. You do
> this by using the path ppppppb to prune direct the next recursive call.
> Sorry that's not explained very well! It was years ago I last coded
> something like that.
Actually, that's perfectly clear. The rotations point is interesting as
well, although checking if one path is a rotation of another might be
fairly expensive, especially as the paths get longer.
> As you get further through the search space, the gains from this get
> much greater. i.e. if your path starts pbbb... then you never need to
> look at anything with more than one consecutive p.
> Obviously, an easy optimization is to do this in a loop rather than a
> recursive call. That more than doubles the speed, but that optimization
> is clearly secondary to reducing the search space!
Thanks for the insights!
More information about the ringing-theory