This paper considers simulation-based optimization of the performance of a regime-switching stochastic system over a finite set of feasible configurations. Inspired by the stochastic fictitious play learning rules in game theory, we propose an adaptive random search algorithm that uses a smooth best-response sampling strategy and tracks the set of global optima, yet distributes the search so that most of the effort is spent on simulating the system performance at the global optima. The algorithm responds properly to the random unpredictable jumps of the global optimum even when the observations data are temporally correlated as long as a weak law of large numbers holds. Numerical examples show that the proposed scheme yields faster convergence and superior efficiency for finite sample lengths compared with several existing random search and pure exploration methods in the literature.