This paper investigates the utility of introducing randomization as a means of boosting the performance of search heuristics. We introduce a particular approach to randomization, called Value-biased stochastic sampling (VBSS), which emphasizes the use of heuristic value in determining stochastic bias. We offer an empirical study of the performance of value-biased and rank-biased approaches to randomizing search heuristics. We also consider the use of these stochastic sampling techniques in conjunction with local hill-climbing. Finally, we contrast the performance of stochastic sampling search with more systematic search procedures as a means of amplifying the performance of search heuristics.