CODEWITHSUNDEEP
algorithmartificial-intelligence
embee.games
embee.games

Reputation: 71

Monte Carlo Tree Search or other algorithms for a stochastic card game?

I am currently working on an implementation of a 2 player trick-and-draw card game, similar to 66 or Schnapsen. Basically you need to gather points by winning tricks and while there are cards in the pack, both players draw a card after each round.

I am at the point of programming a good AI for the game that does not cheat, but really calculates the best moves by using only the information it has at the given game state. I am stuck deciding which algorithm or logic would be the best to use. I decided against algorithms like Alpha-Beta pruning because there are too much hidden information especially at the beginning of the game. I read many interesting things about the Monte Carlo Tree Search and the related UCT search, but because the game has stochastic elements, the tree needed to be searched would grow huge in a short time.

Which algorithm or approach would be the best to use?

Upvotes: 7

Views: 2610

Answers (2)

ziggystar
ziggystar

Reputation: 28680

Here's a link to an application of UCT to Klondike Solitaire. MCTS is a perfect fit for the problem since it can deal well with the stochasticity.

You can look at the sparse method described inside the paper for a way to limit the width of the tree.

Upvotes: 2

Łukasz Lew
Łukasz Lew

Reputation: 50238

MCTS will be definitely better. Regardless of which one do you choose you will have to deal with incomplete information which is the central problem here.

Upvotes: 1

Related Questions