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.)
