Algorithm to generate all possible deals

From: Anonymous (disposable0005_at_yahoo.com)
Date: 01/23/04 

Date: 23 Jan 2004 12:02:31 -0800

I'm a computer science student working on a AI for the game board game
Clue/Cluedo. If you're not familar with it, the game is basically as
follows (simplified just a little):

7 players are each dealt 3 cards from a deck of 21 card. Then
constraints are revealed about various players hands ("Player 1 does
NOT have card B" or "Player 4 has at least one of the following cards:
 A, D, or G"). A player wins when he has determined the correct
location of each card.

In order to do this, I will need to generate all possible sets of
hands (since this is a special case of the infamous satisfyability
problem).

My question is this: What algorithm & data structures should I use
to most-efficiently generate all possible permutations of hands?

The simplest (and worst) would be to go through every possible
"pre-deal" deck (n! decks) and then deal it out to players to create
the set of hands. However this approach has a lot of inefficiency in
it because within a given hand order isn't important (if you get a
King as your first card and a Queen as your second, that is the exact
same hand as if get a Queen first and King second).

Just experimenting, I have improved on this method a lot, but I
suspect my algorithm still is pretty inefficient-- surely somebody
has to have analyzed this problem and come up with the best way to do.
 Any ideas?

Relevant Pages

  • Re: Transfer Rules Proposition
    ... War (the card game with a standard 52-card deck) ... Those games are pure competition: ... A lot of poker players I know *hate* no-limit five card draw. ...
    (rec.games.trading-cards.jyhad)
  • [Review] Cold War: CIA vs. KGB
    ... I've always thought that the Cold War would make an excellent theme ... and I hadn't read much about the game; ... a small card game. ... allows players quite a few options once they realize how the different ...
    (rec.games.board)
  • Re: spin-off topic: Is deal making inherent to mutiplayer games?
    ... Taking 30-45 minutes to deal is Slow Play if and only if 30-45 minutes ... legally played, but it becomes a game which few new players, and some ... portion of existing players, have no interest in participating in. ... I'm still going to bring a good deck, but its likely to be something more ...
    (rec.games.trading-cards.jyhad)
  • Re: Pokerstars Does Cheat -- Heres the Incentive
    ... beats from weaker players pushing crap hands. ... in the game.) ... So...what is the only card that saves this great cardplayer? ... uses on texas hold'em and take peoples real money and fake money i got ...
    (rec.gambling.poker)
  • Re: Engling Fury and rarity
    ... > Power Nine because of their game effect (though, ... > in any card game, has more Big than Black Lotus. ... but how many decks out there want Mariana? ... > make these players non-competitive, ...
    (rec.games.trading-cards.jyhad)