1

I'm developing a card game AI.

A player only knows it's cards and needs to randomly distribute the unseen cards to its opponents.

Some opponents will have 0% chance of having some cards (this is a must).

The opponents will be more likely to have some cards than others (this would be good but my main question is to solve the situation presented before).

Now the problem is that this card distribution must happen lots of times in a very short period of time, so randomly distributing it until the 0% chance cards are not in the hand of the opponents that have 0% chance of having them is not feasible.

What approach would you suggest if I want to solve this problems:

  1. Make sure no opponent has a card that he has 0% chance of having while ensuring the other cards are evenly distributed (and one other opponent will have this card)

  2. (In a situation where some players have 10%, 40%, etc.. chance of having a card)

    Make sure the cards are distrubuted acording to their weights. Eg: A player has to choose 3 cards, he has 2% chance of having A, K or Q so he cannot only have thoose 3 cards to choose from (he may end up with n different highcards from different suits)

If you could help me to solve situation number 1 (in any language, or pointing me to an algorithm), I would realy apreciate it.

Thanks!

EDIT: I should clarify that while some opponents may have 0% chance of having one card other opponents may have a normal chance of having them (and someone definily will have to have it).

EDIT2: This means that if we keep distributing cards at will we may end up with only forbidden cards for the last player to take (which can't happen).

Community
  • 1
  • 1
joaoroque
  • 179
  • 10
  • If there's a 0% chance of having a particular card, remove that card from the distribution. You can still *claim* in the user interface that there are 52 cards in the deck. But if, say, 5 of those cards can never be used then you really only have 47 cards in the deck. At the very least, when you distribute you select from the deck of 52 only the cards to be distributed. (Something like `cards.Where(c => c.Probability > 0)`) – David Mar 03 '14 at 20:05
  • @David: I edited to clarify. This situation is to distribute the cards when we know one opponent doesn't have a given suit while others will 100% sure have it. – joaoroque Mar 03 '14 at 20:10
  • As an aside, Are you using an existing hand evaluator or did you write yoour own? – AShelly Mar 03 '14 at 20:20
  • @AShelly: I'm not using a hand evaluator, I'm using ISMCTS to simulate games and see the final score when endgame is reached. – joaoroque Mar 03 '14 at 20:29
  • You still an evaluator to take the hands and figure out who won, don't you? – AShelly Mar 03 '14 at 21:32
  • Kind of. Everytime a trick has ended the scores are updated. When there are no more trick left to play i check who has the highest score. – joaoroque Mar 03 '14 at 21:33
  • Oh, I was assuming Poker. You're doing Bridge or Hearts or some such. – AShelly Mar 03 '14 at 21:46
  • Yes. Actually is a bit of a mixture of the two. Your commment of going in order of most to least restrictive helped a bit! Thanks. – joaoroque Mar 03 '14 at 21:52

3 Answers3

1

For #1, if you deal a 'forbidden' card into a hand, just shuffle it back into the deck.
For #2 you might be able to use something like a "Cumulative Distribution Function"

I think this question might be relevant.

Community
  • 1
  • 1
AShelly
  • 34,686
  • 15
  • 91
  • 152
  • The problem is that we may end up only with forbden cards in the deck for the last player to choose from. – joaoroque Mar 03 '14 at 20:26
  • 1
    deal in order of most- to least-restrictive hands. If the deck is truly shuffled randomly, there's no statistical difference between giving 5 cards to player A, followed by 5 to B, etc. versus a round-robin deal. – AShelly Mar 03 '14 at 21:25
  • That may be a step in the right direction, but there are still edge cases where you are left with no cards to deal. This is a bit of an hard problem! (two guys can take 2 suits, they take all the cards that the guy that can take 3 suits needs, because they took too much of one suit or the other) – joaoroque Mar 03 '14 at 21:41
0
  1. Make sure no one has a card that he has 0% chance of having while ensuring the others are evenly distributes

To make a 0% chance for some cards to be dealt, simply remove those cards as options. E.g.

IList<int> cardOptions = Enumerable.Range(1, 52).ToList();
// all 52 cards in this deck represented as integers
// remove some:
cardOptions.Remove(5);
cardOptions.Remove(42);
// when you randomly select from cardOptions,
// each remaining card has a 1/50 probability of being chosen

2. (In a situation where some players have 10%, 40%, etc.. chance of having a card)

Make sure the cards are distrubuted acording to their weights. Eg: A player has to choose 3 cards, he has 2% chance of having A, K or Q and that's the only cards he has left to choose from (from 2 different suits)

This sounds different from a typical weighted random distribution. You could do the following (pseudocode):

double probabilityOfHavingCertainCard = 0.4;
int thatCard = 52;
if (randomDoubleBetween0and1 < probabilityOfHavingCertainCard)
    cardResults.Add(thatCard);

cardOptions.Remove(thatCard);
while (cardResults.Count < 5)
    cardResults.Add(random from cardOptions, not previously chosen);

That is, it treats the weighted card as a special case, not as part of the ordinary shuffle of the hand.

Community
  • 1
  • 1
Tim S.
  • 55,448
  • 7
  • 96
  • 122
  • I changed the text in your first quote to make it more explicit. The second one wont work that easly because we may end up with only cards that the last player has 0% chance of having so he can't have them. – joaoroque Mar 03 '14 at 20:25
0

I found a similar question on another site altought it doesn't actually get an answer on how to solve the simple part of my question.

If anyone else is interested the link is:

https://math.stackexchange.com/questions/220606/n-piles-of-hidden-cards-of-known-marginal-probability-distribution-then-a-card

Edit: I ended up distributing all the cards using the constraints of some opponents not having some suits. When one opponent had no cards he could choose from he tries to swap a card from the pile he has no use for with another opponent than can take this card. That opponent in exchange gives him a card he can take. It is not the best solution, but works 99.9% of the times.

Community
  • 1
  • 1
joaoroque
  • 179
  • 10