Previous theoretical work has proposed the use of Markov chain Monte Carlo as a model of exploratory search in memory. In the current study we introduce such a model and evaluate it on a semantic network against human performance on the Remote Associates Test (RAT), a commonly used creativity metric. We find that a family of search models closely resembling the Metropolis-Hastings algorithm is capable of re- producing many of the response patterns evident when human participants are asked to report their intermediate guesses on a RAT problem. In particular we find that when run our model produces the same response clustering patterns, local dependencies, undirected search trajectories, and low associative hierarchies witnessed in human responses.