We propose a novel simulation approach for pricing American-style contingent claims. We develop an adaptive policy search algorithm for searching the optimal policy in exercising an American-style option. The option price is obtained by first estimating the optimal option exercising policy and then evaluating the option with the estimated policy through simulation. Both high-biased and low-biased estimators of the option price are obtained. We show that the proposed algorithm leads to the convergence to the true optimal policy with probability one. This policy search algorithm requires little knowledge about the structure of the optimal policy and can be naturally implemented by parallel computing methods. As illustrative examples, computational results on pricing regular American options and American-Asian options are reported and they indicate that our algorithm is faster than certain alternative American-style option pricing algorithms reported in the literature.