The new algorithms which are the central focus of this thesis will be validated empirically on a broad range of large-scale search problems. This section briefly describes the major domains. I will also report results on testbed domains such as the the children's game of Pig (see Appendix B.1) and small Traveling Salesperson problems.