I am currently trying to use probability theory to help solve a programming problem involving Monte Carlo Tree Search with Information Sets and have hit a roadblock. The problem can be described as follows:
There are N piles, or groups, of cards in which the probability that each card exists in the pile is known in advance. The different piles can be of varying counts, but at all times the count of cards in each pile is known. How should the known probability adjustments be calculated when one particular card is shown to exist with 100% certainty in a particular pile? Conversely, how should the probability adjustments be calculated when a particular card is shown to NOT exist in a particular pile?
An Example for case 1:
In some card games, there exists the possibility to swap your hand with a hidden dummy hand. When such a situation occurs, the player not only knows what cards he/she has, but also what cards were traded away(which are still hidden to other players). Thus the player should be able to more precisely predict what the opponent's cards are than any other player. By ruling out more of the opponent's possible cards, the probability distribution should narrow, and each specific card's probability that still remains uncertain should be more probable than was previously believed.
An Example for case 2:
In most trick taking card games, when a player fails to follow the suit led... that player is effectively revealing that he/she does not have any cards of that suit (Hearts, Clubs, Diamonds, or Spades). The other players are, in turn, more likely to have cards of that particular suit in their hand than previously believed and a little less likely to have cards of the other three suits. Conversely, the probabilities for cards of each of the other three suits in the player's hand that didn't follow suit would go up.
Additional Info:
- There are no duplicate cards.
- The number of cards in each pile is known at all times.
- The problem space does not explicitly revolve around playing cards, but they make for a good representation of the problem.
- A given card can have been passed in a hidden manner from one pile to another, but knowledge of each such pass is guaranteed to have been given (this is not part of the problem, but added to avoid possible oversimplifications) edited: ( these passes should be assumed to be randomly generated )
I have been stumbling around with this particular problem for a while now for a programming project and do not know how best to proceed. I should mention that probability theory is not my greatest strength.
edit:
After going over this post a few times, I think a numerical sample would be appropriate.
There are 3 piles of hidden cards marked A, B, and C. A contains 2 cards, B contains 4 cards and C contains 2 cards. Together within each of these piles are cards labeled 1, 2, 3... up to 8 with no duplicates. The probability that a card Exists in each pile is as follows:
card\pile. A ---- B ---- C
card 1 ... 50% .. 25% .. 25%
card 2 ... 50% .. 25% .. 25%
card 3 ... 10% .. 65% .. 25%
card 4 ... 10% .. 65% .. 25%
card 5 ... 10% .. 65% .. 25%
card 6 ... 10% .. 65% .. 25%
card 7 ... 10% .. 65% .. 25%
card 8 ... 50% .. 25% .. 25%
count ..... 2 ....... 4 ....... 2
Then... card 5 is revealed to exist in pile A. Horizontally, the deduction 'for card 5' is easy to process, but vertically, the necessary adjustment eludes me.