I'm interested in building an AI algorithm to play a board game. This is a sequential two-player game, where they alternate taking turns, so minimax or alpha-beta algorithms sound natural.

However, the twist here is that the game is randomized. There is a deck of cards that is shuffled randomly; each turn involves drawing the next card from the deck, then making a move.

What algorithms are appropriate for selecting a move, in a game with randomness?

I understand that one approach is to think of this as a three-player game: in addition to the two players, there is a third player (the dealer) who makes a random move. For instance, if the two players are Minnie and Maxwell, we might alternate moves in the following order: Dealer (chooses a random card for Minnie), Minnie (selects a move), Dealer (chooses a random card for Maxwell), Maxwell (selects a move), and so on. I think I've read that alpha-beta search can be adapted to this setting. However, this doesn't sound too promising to me. There are perhaps 52 possible outcomes of the moves by Dealer, so the tree will be very bushy (with a large branching factor), causing exponential blowup. Also, this sort of modified alpha-beta search feels a bit inefficient to me. Each move likely affects a player's score by only a little bit at a time, so we'd expect that the effects of the randomness to average out over many moves, and there is no need to explore all combinations of possible random outcomes. To put it another way: the game is more about positional elements and random luck than about tactical/combinatorial elements.

Is there a better algorithm framework for randomized games, that takes into account the stochastic element? (Bonus points if you can suggest something that takes advantage of the fact the strength of a position changes only slowly over many moves.)

  • Isn't the wikipedia page Stochastic_game relevant to your question? – J.-E. Pin Oct 1 '13 at 8:01
  • @J.-E.Pin, thanks for the reference - I hadn't seen that before. It looks a bit different: in a stochastic game, players move simultaneously, whereas in mine, players alternate (sequentially). I expect this to make a big difference; e.g., the difference between chess and the prisoner's dilemna. My game is more like chess than like the prisoner's dilemna. (Also in my game there is no payoff at each stage, only at the end.) But please do correct me if it's more relevant than I realize! – D.W. Oct 1 '13 at 17:48

From your explanation I assume that the game is not episodic, but sequential: each move outcome is dependent on the previous moves.

The Minimax algorithm modification you explained is called Expectimax and is generally a standard approach for such problems as far as I know. In order to avoid the big branching factor you can try some variation of the Monte Carlo algorithm. This way you will be able to explore deeper the game tree and still take into consideration the randomness.

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.