Ab initio structure determination using directspace methods, although relying on an essentially bruteforce approach, can be greatly improved through smarter algorithms. The most basic improvement involves the use of prior information to reduce the number of configurations evaluated to find the structure solution. It is however vitally important that the parametrization used to incorporate this prior information does not reduce the efficiency with which the configuration space is explored. We will show that this can be achieved by defining molecules and polyhedra through a set of restraints associated to dedicated random changes, allowing to solve structures up to three times as fast as with the ‘standard' approach where atomic positions are parametrized directly from bond lengths, bond angles and dihedral angles. To further enhance the efficiency of the algorithm, it is also possible to ‘tune' the convergence criterion used to compare the structural model to the observed diffraction data (usually X2 or Rwp). By using Maximum Likelihood principles, it is shown that incorporating the fact that the model is approximate in the X2 evaluation can improve the algorithm convergence towards the structure solution.