how does one climb a hill with no gradient? [serious question]
This sounds like what the experimenters are doing. Perhaps the GP was alluding to "first order hill climbing" as evaluating the gradient in every direction and climbing the steepest one, but the "0th order" version is also usually considered hill climbing and is better for some classes of problem.
Some manifold has a goodness function defined on it, described by a (totally ordered?) relation provided by the observing scientist.
The goodness function is assumed to be (continuous/differentiable/continuously differentiable?) with respect to some metric, and the computer picks a random coordinate within some small distance of the last coordinate in the metric, and then asks the human to order them?
I don't think this is hill climbing, and my simple reasoning for that is that I don't believe the first assertion. The expert is almost certainly behaving non-deterministically. In fact, I believe that each time the expert is presented with the "same" pair of coordinates, he is more likely to yield a different ordering.
That said, I could be reading this wrong.