Re: Generating all 5-card hands
by merlyn (Sage) on May 18, 2005 at 14:57 UTC
|
You might look at Games::Cards for reusable code regarding scoring and representing hands.
For generating all combinations of 52 cards taken 5 at a time, search here for combinations. I'm sure we've covered this quite a bit. {grin}
But are you really ready to process all 2598960 iterations? At 100 per second,
that's still about a third of a day. Maybe you should use some rules instead.
| [reply] [Watch: Dir/Any] |
|
But are you really ready to process all 2598960 iterations?
Nope. The number that you mention is 52-choose-5: the number of 5-card hands possible sans restrictions. I consider only those hands that have at least one 5 in them to be interesting. This takes out a significant portion (by my math, it leaves only 886656). I will further reduce the set by using the fact that a cribbage hand is inherently non-ordered and, for my purposes, suit doesn't matter. So, I'll not bother scoring a hand if I've already seen a hand with the same cards in it. I just did it in 30 seconds, generating 1820 distinct hands. :)
thor
Feel the white light, the light within
Be your own disciple, fan the sparks of will
For all of us waiting, your kingdom will come
| [reply] [Watch: Dir/Any] |
|
a cribbage hand is inherently non-ordered
But 52-choose-5 is non-ordered.
| [reply] [Watch: Dir/Any] |
|
|
|
|
merlyn,
For generating all combinations of 52 cards taken 5 at a time....But are you really ready to process all 2598960 iterations? At 100 per second, that's still about a third of a day.
In cribbage, order is important contrary to what thor said earlier. The position of 1 card determines its eligibility for "right-jack" so there really are 12,994,800 hands that need to be considered. Even still, it is possible to both generate and score all those hands in under 15 minutes using pure perl. This would encompass everything thor wanted to do and a lot more.
| [reply] [Watch: Dir/Any] |
|
In cribbage, order is important contrary to what thor said earlier.
While you're correct in that order matters, you and I are not disagreeing. My original problem was to prove that all hands that contained a 5 had at least two points. If knobs is obtained, then a jack was cut. With at least one 5 in the hand, this will yield 2 points for the fifteen, thus satisfying the original problem.
thor
The only easy day was yesterday
| [reply] [Watch: Dir/Any] |
Re: Generating all 5-card hands
by 5mi11er (Deacon) on May 18, 2005 at 20:48 UTC
|
Forget brute force, using logic to try to create a hand that has no points:
- All 10, J, Q, K's are eliminated
- Because 6+9=15 and 7+8=15, we may only take one from each group above 5
ie. 6 & 8, 7 & 9 or 8 & 9. 6 & 7 gives a three card run.
- This means we MUST use at least 2 cards less than 5.
- A, 2, no 3, that would be a 3 card run, 4, 5
can't have a 6, 6+4=10, or 7, 7+2+A=10, or 8, or 9 for same reasons. Dead end.
- 2, 3, no 4, 5, 6 ok, no 8 allowed, nor 7. Dead end.
- A, 3, 5, 8, --> Dead end.
- A, 4, 5, 7, --> Dead end.
- 2, 4, 5, 7, no 9, 9+2+4=15. Dead end.
this elminates all possible hands.-Scott Update: L~R beat me to what this essentially boils down to up in this node posted just before I'd managed to finish mine. | [reply] [Watch: Dir/Any] |
Re: Generating all 5-card hands
by Roy Johnson (Monsignor) on May 18, 2005 at 14:54 UTC
|
The set of all five-card hands with a 5 is the set of all four-card hands in a deck missing a 5, plus a 5-card. The easy way would be to use glob:
print "$_\n" while $_=glob '5,{A,2,3,4,6,7,8,9,10,J,Q,K}'
.',{A,2,3,4,5,6,7,8,9,10,J,Q,K}'x3;
but it's not a truly iterative solution (it generates the whole set before beginning iteration). Consider Algorithm::Loops, or Iterating over combinations (found by Super Searching on combinations and iterator).
Caution: Contents may have been coded under pressure.
| [reply] [Watch: Dir/Any] [d/l] |
Re: Generating all 5-card hands
by hv (Prior) on May 19, 2005 at 12:12 UTC
|
For a hand with a 5 to avoid scoring 2 points, it must have no pair, and no subset that sums to 15. Since that means we can only have one of each of the pairs (1, 9), (2, 8), (3, 7), (4, 6) that sum to 10, the hands to consider consist of the 16 ways we can choose one from each of those pairs.
If we have 9 we cannot have 6, so we must have 4, so we cannot have 2, so we must have 8, so we cannot have 7, so we must have 3. But 3+4+8 = 15, so we cannot have 9.
So we must have 1; if we have 8 we cannot have 7, or 6, so we must have 3 and 4. So we have 3+4+8 = 15 again, which means we cannot have 8.
So we must have 1 and 2, which means we cannot have 7, so we must have 3. But 1+2+3+5+4 = 15, and 1+3+5+6 = 15. So there is no hand including a five which doesn't include at least 2 points.
Hugo
| [reply] [Watch: Dir/Any] |
|
I thought you would be interested to know that I added a link to this discussion at Cribbage Corner, in the section on hand distribution and probabilities. Thank you for taking the trouble to work this out!
| [reply] [Watch: Dir/Any] |
Re: Generating all 5-card hands
by TedPride (Priest) on May 18, 2005 at 18:37 UTC
|
use strict;
use warnings;
@_ = (2..10,'J','Q','K','A');
comb('', 4, 2..4,6..10,'J','Q','K','A',@_,@_,@_);
sub comb {
my ($str, $depth, @items) = @_;
if (!$depth--) { interpret($str); return; }
comb("$str $items[$_]", $depth, @items[($_+1)..$#items]) for (0..$
+#items)
}
sub interpret {
my @cards = split / /, "5$_[0]";
# Do whatever with @cards;
}
Actually though, the possible set can't contain any 5's except the original 5, nor can it contain any 10, J, Q, K - since all hands involving those will have at least 2 points. This cuts the number of combinations significantly.
@_ = (2..4,6..9,'A');
comb('', 4, @_,@_,@_,@_);
Nor can you have more than one of any card.
comb('', 4, 2..4,6..9,'A');
It should be fairly easy to figure out whether there are straights or 15's in the permutations? of this set. Code to follow...
use strict;
use warnings;
comb('', 4, 1..4,6..9);
sub comb {
my ($str, $depth, @items) = @_;
if (!$depth--) { interpret($str); return; }
comb("$str $items[$_]", $depth, @items[($_+1)..$#items]) for (0..$
+#items)
}
sub interpret {
my @cards = split / /, "5$_[0]";
@cards = sort {$b <=> $a} @cards;
my $flag = 1;
for (0..3) { $flag = 0 if $cards[$_+1] != ($cards[$_]-1); }
return if $flag;
for (perm(@cards)) {
return if sum(split //) == 15;
}
print join " ", @cards;
}
BEGIN {
my @c_out;
sub perm {
@c_out = ();
permute('', $_, @_) for (0..$#_);
return @c_out;
}
sub permute {
my ($str, $depth, @chars) = @_;
if (!$depth--) {
push @c_out, $str.$_ for @chars;
}
else {
permute($str.$chars[$_], $depth, @chars[($_+1)..($#chars)]
+)
for (0..$#chars);
}
}
}
sub sum { my $n; $n += $_ for @_; return $n; }
Very rough code, but upshot is that there are no hands with a 5 that don't have at least 2 points. I could actually have done this whole thing on paper, since there's very few sets of cards that have to be tested for 15's and straights. | [reply] [Watch: Dir/Any] [d/l] [select] |
Re: Generating all 5-card hands
by zentara (Archbishop) on May 18, 2005 at 18:17 UTC
|
I don't know if it can be adapted to cribbage, but check out poker-evalIt has python bindings, but no Perl yet.
You can do millions of hands in just a few seconds.
I'm not really a human, but I play one on earth.
flash japh
| [reply] [Watch: Dir/Any] |
Re: Generating all 5-card hands
by DrHyde (Prior) on May 19, 2005 at 09:55 UTC
|
Hah! Just last night I was thinking about writing a module for scoring cribbage hands, with the intention of analysing the values of various cards. Yes, this would pay no attention to actually *playing* the hand or to pegging tactics. | [reply] [Watch: Dir/Any] |