Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

In the game there are 5 players, each with 8 cards in hand. No other card is present.

Using Monte Carlo (MCTS) I run many simulations of the game from the current state to the end of the match. In those simulations adversaries play with very simple dumb rules. When generating a new simulation I assign to them unknown cards with a uniform random distribution. I say a card is unknown if it is not in my hand, it is not on the table and it has not been discarded before, then it must be in someone other's hand.

However, uniform random distribution it's not the best way to distribute cards. In fact, sometimes it's straightforward to a human player a reasoning like this:

If he had 3♥ he probably would have discarded it the previous turn as it was a very good move. Then, it's very unlikely that he'll discard 3♥ in hand hereinafter.

Well, before discarding, before generating the Monte Carlo simulations, I would assign to each adversary the set of unknown cards with their probability distribution:

{ (3♥, 0.20) , (4♥, 0.12) , (5♥, 0.03) ...}.

How can I calculate those probabilities? Is there some paper or some ideas where to start from?

EDIT: An idea: Computationally talking, would it be a good idea to run a simple Monte Carlo simulation when chosing adversaries' strategy? With simple I mean a rough, fast, simulation which ends in a small time like a second. In this way, the next turn I would have a measure of the goodness of adversaries moves and I can start doing inference from there.

share|improve this question
    
Help me understand. You want to be able to start from likely hand configurations from players who play intelligently? Wouldn't it be simpler to simply write an intelligent AI and start from the beginning? –  Neil Jan 9 at 9:42
    
@Neil Do you mean using minimax? I've tried it at it is too much time consuming. –  HAL9000 Jan 9 at 9:46
    
Oh, I think I understand now. You mean to determine the probabilities of cards that a player would have prior to each play of an AI, right? –  Neil Jan 9 at 9:51
    
Answering your EDIT: if you want to develop simple but effective heuristics for playing the game, you can try the genetic approach. Basically let your AIs play against eachother and evolve (by mutating the parameters randomly). An example of Tetris-playing AI: luckytoilet.wordpress.com/2011/05/27/… –  Konrad Morawski Jan 9 at 9:51
    
@Neil exactly, it's a way of improving efficiency of Monte-Carlo. I want to generate simulations which are more likely to be coherent with the current state. –  HAL9000 Jan 9 at 9:54

1 Answer 1

You are talking about attributing states of belief to the other players. This is relatively easy to do if your opponents are computers with simple algorithms; for instance, you can perform normal game-tree analysis for all possible cases and value the actions that the opponents would have made if they played deterministically and optimally according to some fixed metric.

If your opponents are programs with algorithms as sophisticated as yours or more sophisticated, then things get very tough very fast. Whatever decisions you program might be exploited by opponents who know how you're going to react, opening the path to all kinds of bluffs, swindles, automatic learning to exploit your strategy as seen in the past, etc. Human players pose the same problem, except that the best ones are even better at this. In general, even modestly complex hidden-state games against human opponents tend to become as hard as general AI to play well.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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