Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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?

like image 710
embee.games Avatar asked Jun 14 '12 11:06

embee.games


People also ask

What is the Monte Carlo tree search algorithm?

Monte Carlo Tree Search (MCTS) is a search technique in the field of Artificial Intelligence (AI). It is a probabilistic and heuristic driven search algorithm that combines the classic tree search implementations alongside machine learning principles of reinforcement learning.

What is the difference between MCTS and Monte Carlo tree search?

MCTS is a simple algorithm to implement. Monte Carlo Tree Search is a heuristic algorithm. MCTS can operate effectively without any knowledge in the particular domain, apart from the rules and end conditions, and can find its own moves and learn from them by playing random playouts.

What are the disadvantages of Monte Carlo tree search?

As the tree growth becomes rapid after a few iterations, it requires a huge amount of memory. There is a bit of a reliability issue with Monte Carlo Tree Search. In certain scenarios, there might be a single branch or path, that might lead to loss against the opposition when implemented for those turn-based games.

What is the Monte Carlo method of randomization in Linux?

There is also a more optimized version which is applicable on linux due to utilizing cython and you can find it in here. Monte Carlo method was coined by Stanislaw Ulam for the first time after applying statistical approach “The Monte Carlo method”. The concept is simple. Using randomness to solve problems that might be deterministic in principle.


1 Answers

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.

like image 156
ziggystar Avatar answered Oct 02 '22 07:10

ziggystar