Strange—ingenious. Hill climbing is bad for these sorts of problems since it gets stuck in local maxima—an as the charts in the evaluation show, there are often multiple maxima in the floating point precision of a program. So instead you need any of a variety of methods that guarantee finding a global maximum eventually. Luckily, MCMC gives you such a guarantee, with better asymptotic probabilistic bounds than simulated annealing. In the evaluation, they have a comparison of MCMC to annealing and hill climbing.