116
O. Keszocze et al.
Fig. 5.5 Search trees produced by the MCTS-based solver with (left) and without clause learning
on the graph coloring problem sw100-68 with 500 variables and 3100 clauses
Fig. 5.6 Search trees produced by an algorithm with a small (left) and large exploration constant
on the planning problem logistics.a with 828 variables and 6718 clauses
they were ignored due to a low estimated value. In contrast, the right tree is more
equally explored in every direction.
In this example, the variant with the small exploration constant worked better and
was able to find a solution in less time and with a smaller search tree. One clearly
sees that the used heuristics led the search into the correct direction and thus the
exploitation in this direction turned out to be a good choice. In contrast the variant
with a large exploration constant wasted time exploring other branches. While the
usage of a low exploration constant turned out to be successful for this example, it
highly relies on the usage of accurate heuristics and on accurate value estimations
for the tree nodes.
Despite all these advantages, the MCTS-based CDCL solver was still not able
to compete with state-of-the-art solvers and to solve hard instances. Nevertheless,