Simplification of information - how to do it efficiently?

Hello sci.math!

I've been struggling with a programming problem for quite some time
(July last year?), but a friend has suggested I'd try a math newsgroup
to see if it is actually solvable, and for hints for an as efficient
implementation as possible. My own math isn't that awesome (basic
calculus and such), so I hope that while giving you people a nice
problem to think over, I'll be able to follow a bit of the discussion.
In advance, thanks for reading and thinking along.

Before I can get to the problem, first I need to explain a bit of
notation. Suppose I have a hand of cards, some cards of which are
known to me and some of which I only have a bit of information. Take
the following notation:

< (a, b, c), d, e >

This means I have three cards: two cards which I know with certainty -
d and e - and one card of which the exact nature is uncertain to me,
but I am certain that it is either an a, b or c. So far, so simple.
Now imagine the cards increasing, and the possibilities per card
increasing. Examples like

< (a, b, c), (c, d), (e, f, g, h, i, j, k, l), (c, f, g, h, l), (a, b,
f, g, k, l) >

might show up. My particular situation has to be able to handle 10
cards, each having upto 20 choices, but more about that after I
explain the problem. Also, there is no order to these cards. So < (a,
b), (c, d) > would be the same as for example < (c, d), (b, a) >.

A basic rule of data is that it is not useful unless you can
understand it. Let's take a more practical example using real life
cards:

< (Ace of Hearts, Ace of Diamonds, Ace of Clubs, Ace of Spaces),
(Ace of Hearts, Ace of Diamonds, Ace of Clubs, Ace of Spaces),
(Ace of Hearts, Ace of Diamonds, Ace of Clubs, Ace of Spaces) >

Simple logic can tell us there is atleast one black and one red card
in there. More elaborate computerlogic might evaluate all possible
choices (or a variation thereof) to arrive at the following
simplification:

< (Ace of Hearts, Ace of Diamonds),
(Ace of Clubs, Ace of Spaces),
(Ace of Diamonds, Ace of Clubs) >

This information can still represent the exact same possible hands of
cards as the one above. It is less redundant and better queryable than
the former representation. "Do I have a black card?" is a question
that is far easier answered with the second set. Although, to be fair,
depending on how you end up simplifying it the question might not be
answered as easily. Take for example:

< (Ace of Diamonds, Ace of Clubs),
(Ace of Hearts, Ace of Spaces),
(Ace of Hearts, Ace of Diamonds) >

So while the simplification method isn't sure to provide answers such
as these, it certainly increases the chances... which is what I am
after. I personally have only one 'real' goal: reduce the amount of
choices as much as possible while doing it in such a fast manner as
time (not take much more than say, 1s). With the relatively huge data
sets I may be running into, the only method I have been able to
calculate these simplified representations has been rather exponential
in processing time.

Other information that may be useful but are more about the domain the
problem is situating in than the actual problem I am looking for:

- There are no 'double' cards - e.g. all cards are unique. One deck so
to say, if I were to continue with the cards comparison.
- The cards are obtained one after another, at which point I am
immediately aware of the possible cards (I called them choices above)
it can represent.
- Over time, I may be able to say: 'I do not have a 3 of Hearts' or 'I
have no cards that are Spades'

My question to you, sci.math: what is an efficient method to calculate
such a simplified situation?

Thanks for taking a look at this problem, and I look forward to any
pointers the upcoming discussion may give. If anything isn't clear,
let me know and I'll try to answer them to the best of my abilities.
.

Relevant Pages

  • Re: mea culpa, mea maxima culpa
    ... Eric> so far - one heart and two diamonds. ... Eric> you will eventually have to lead a spade in which case RHO will ... RF> But why can't RHO have both the Ace of spades and the Q of clubs? ...
    (rec.games.bridge)
  • Re: Defensive problem -- different problem, different answer
    ... guaranteed a first round control by agreement, I would lead a spade. ... rid or 7 clubs in dummy if he has a club loser. ... Your hand is without an ace. ... Declarer did have 3 diamonds, ...
    (rec.games.bridge)
  • Re: Single dummy which game?
    ... On a single dummy basis, which game would you want to play in: ... when E holds DA and W holds HA, or when E has 5 diamonds and any ace. ... E has the D ace is 50%. ... Sure, if clubs are 4-1, they could score a ruff. ...
    (rec.games.bridge)
  • Re: Easy probability question (Bayes theorem)
    ... an ace of diamonds out of a deck of cards ... Assuming you are choosing two cards at random ... is it asking for the aces of spades and diamonds to be ... the ace of spades is 2/52, and the conditional probability, given that the ...
    (sci.math)
  • Re: Play this Hand
    ... North East South West ... and East plays the 9 of clubs, Now West switches to the Jack ... I win the Ace and play a club. ... E after 2 rounds of diamonds. ...
    (rec.games.bridge)