  Motivated by the search for a counterexample to the Poincar\'e conjecture in
three and four dimensions, the Andrews-Curtis conjecture was proposed in 1965.
It is now generally suspected that the Andrews-Curtis conjecture is false, but
small potential counterexamples are not so numerous, and previous work has
attempted to eliminate some via combinatorial search. Progress has however been
limited, with the most successful approach (breadth-first-search using
secondary storage) being neither scalable nor heuristically-informed. A
previous empirical analysis of problem structure examined several heuristic
measures of search progress and determined that none of them provided any
useful guidance for search. In this article, we induce new quality measures
directly from the problem structure and combine them to produce a more
effective search driver via ensemble machine learning. By this means, we
eliminate 19 potential counterexamples, the status of which had been unknown
for some years.
