Finding all addition combinations between 1 and 20

Greets all,

I'm trying to design a card counting system for my MUD's blackjack game. The game uses an 8 deck shoe (so 8 decks are shuffled together).

To begin calculating the odds, I need to know all possible combinations of cards to get any sum from 1 to 20. These combinations allow for repetitions and must account for all possible orderings of the cards. Further, the highest number that can be used is 11 (an ace),

So for 4 we have:

4, 3 + 1, 2 + 2, 1 + 3, 2 + 1 + 1, 1 + 2 + 1, 1 + 1 + 2, 1 + 1 + 1 + 1

I've been trying to write a subroutine that outputs all these combinations, but the one I've written isn't parsimonious enough. When you get into higher numbers (around 15) it takes forever (like hours). I'm wondering if anyone has any ideas on a subroutine that would be able to do this without overwhelming the processor. If anyone wishes, I could post my subroutine which kind of works like an odometer. But as I said, it doesn't work well.

The next problem I'm having is that I'd like to store the combinations in a MUSHclient variable (that way MUSHclient doesn't have to figure out all the cominations over and over again). I've been storing them in the form:

4|3 + 1|2 + 2|1 + 3|2 + 1 + 1|1 + 2 + 1|1 + 1 + 2|1 + 1 + 1 + 1|

But when I get into higher numbers (like 14), the amount of text is too large and it gets cut off. To get an idea of how much text is needed, the formula for calculating the combinations for any particular number is 2^(n-1). So for 20 there are close to 524288 combinations (since we can't have any card greater than 11, there's actually a few less than that). Is there a way to store this large amount information in MUSHclient in a manner that will let it be split into an array later on?

I've been working on this one for a couple weeks and am starting to get frustrated. I think if I was a bit more adept at math, I'd be able to figure out some shortcuts to make this less demanding on the processor. But so far no luck.

Any help is GREATLY appreciated.

Why do you need to store all the combinations for each of the numbers? All you want to do is know the probability of getting certain cards, right? Or...
Just explain what youre specifically trying to accomplish. I can tell already this is going to be enjoyable.

Why not just declare a variable for each card and have the counts maintained for each card? Do you have a way for sure to know when a new set of decks is being used? Are you absolutely certain used cards arent simply recycled after each game? Either of these factors can wreck even the best designed card counters due to the fact that counting systems work on the presumption that cards are never reused until the deck has grown too small to ensure a full hand can be played. The freshness of the deck when you sit at the table will make your counter of limited use until you know for certain a new one is in use and your counts are accurate if the cards aren't being recycled but I've already covered the issue with recycled cards so you face something of a catch 22 here.

Looking at what you do know about the system so far - nomore than 32 of a given card can exist so Id set the intial value for each card to either 0 or 32 and count up/down accordingly as each card is played. Have your display routine show how many of each card have been played(remain to be played?) of the original 32 and you can roughly calculate from there your odds of drawing a given card ie (32 - # played)/(416 - total # played). One way or another, your odds will never be better than 1/13 of drawing a given card and odds will only be that good on a fresh shoe.

Hey Flannel,

I'm glad I've piqued your interest. This problem's been eating my brain for a while now. I dream about this problem (GAH!)

When the original hand is dealt, I get two cards faceup and the dealer gets two. 1 facedown, the other visible.

I need to know whether to hit or not. To decide this, I need to know whether the odds of me hitting and busting are greater than the odds of the dealer getting a better hand than me. The dealer hits until she gets 17 or above.

So if I've got a 16 and the dealer's showing 2, I need to know the odds of the dealer getting a 17, 18, 19, 20 or 21 (and also the odds of her busting).

To get 17, she needs any combination of cards to get 15. So, she can get 15 straight aces (remember, there's 8 decks, which means 32 aces), 13 aces and a two, 11 aces and two 2s, etc. I need to know the odds of all those combinations (there's a lot). Of course, the first step is knowing all those combinations, which is what I'm trying to achieve here.

Does that make sense?

Hey Meerclar,

I gotta run, so this'll be brief. There is a visible message that informs you when the dealer shuffles the decks. There are all sorts of questions, like whether the game is fair, whether the shuffling is simply window dressing, etc. But lets assume it's fair for now.

Remember, I need to calculate the odds of the dealer getting a 17, 18, 19, 20, or 21 before I decide to hit (the dealer goes after you). Because of this, I need to know the combinations possible to get from what she's showing to a 17, 18, 19, 20 or 21.

You've already given a scanario thats almost impossible to calculate accurate odds on unless you have some way of knowing what the dealers face down card is because your counts will always be wrong for that card otherwise. Even if you do know, knowing the odds the dealer can beat your hand doesn't really help very much I'm afraid because you can only calculate the % chance of the dealer drawing a better hand based on the cards they currently have - once you're done hitting you can't update the odds again until the dealer is played out and by then it's too late.

From my understanding it seems that he wants to calculate the cards played so far to see the odds of a card being in a players corner.

For example, say 3 jacks kings queens aces and 10's were played (so far in many previous games), If the dealer has a jack and a face down card, the odd's of the dealer having another queen king or ace is very minimal since theres only 1 of each and like 4 of the rest of the lower value cards.

What i'd probably do which isn't a great way of doing it, is make a 2d array.

The first part of the array would be the 4 suits (spades hearts clubs diamonds). The second part of the array would be how many of each card a suit has, which is possibly 13 (not 100% sure).

Whenever a card is played, go to the index of that card and suit and mark it down as used, then keep generating random selections, if the selection has already occurred, then keep generating random selections until you find one which hasn't been played.

This was just an on the fly guess on the topic, it could be completely off and this thinking could be wrong. Either way i'm never sure, so if this makes sense, great.

Making an AI will be a challenge, good luck

You missed a piece of the puzzle there Trom - there are 8 decks being shuffled together for use at the blackjack table. He's also trying to make a card counter for the blackjack table rather than create the blackjack game from scratch.

As for your array, you wouldnt even need to track which suits of each card have been played, just track how many of each card and keep it simple. As for calculating odds, I actually gave the basis for the formula in my first post without actually intending to, though it does need a bit of tweaking from the example I gave.

That is half a megabyte of combinations, and if each combination took 4 bytes you are looking at 2 megabytes.

I wouldn't save each combination. The most you really need to save is the known cards (the played ones) which sounds like a maximum of 8 X 52 = 416 cards.

From what I know of blackjack it can be defeated by card counters, however card counters can be defeated by having lots of decks (thus reducing the usefulness of counting in the first place). I guess that is why they are using 8 decks.

For instance, if you needed to get a 4 to win, and in a single deck you had already seen 3 4s then your chances of seeing the 4th 4 is much lower (there are less of them left), than if you had not seen any.

However if there are 8 decks then there are 4 X 8 = 32 of each card number, and even if a couple have appeared the odds are only slightly in your favour if you remember that.

Another issue is how often the deck is shuffled. Is is shuffled when all 8 decks are used, or half-way through? If half-way through I think your chances of beating the system are slight.

Greets all,

Thanks to everyone for their input so far. :) I'd really like to avoid getting too bogged down in discussing whether I can calculate these odds or not (I've provided brief responses to Meerclar and Nick below, however, if you'd like to discuss probability matters related to this further, perhaps we can start another thread or do it via private message). What I think is truly interesting here is the challenge of programming something to calculate these addition combinations (I can't solve it in a parsimonious matter). So, for now, I'm hoping we can put aside a discussion whether our grasps of odds calculations are correct and discuss how this particular problem of getting the combinations can be solved. That's what I'm truly interested in.

Meerclar,

Thanks for the input on calculating odds.


Actually, you can calculate the odds for this using conditional probability. ;) If you're unconvinced, I can provide an example, but that'll take a lot of writing and I'd like to save that time if you're willing to trust me on this.



Again, I very strongly believe that what I need re: calculatin odds can be achieved and I'd be willing to discuss this in another thread or privately).

Nick,

The problem with what you propose is I don't know if I need a 4 to "win." I think what you're getting at is, if I had 17 (thus needing a 4 to get to 21), I could calculating the odds of me getting a 4, 3, 2 or ace v.s. the odds of me getting something bigger than that (and busting).

However, there's more to it than that. Sometimes the odds of me hitting and busting are large, but the odds of the dealer beating my hand (by flipping her hole card and hitting as needed)without busting if I stand is even greater. In a situation such as this, it's a better bet to hit than stand.

However, to calculate those odds, I need to know all the combinations of cards she could attain to beat my hand if I stand.

Ah, you want to know all possible combinations? Like, you would have 52 * 8 (416) cards to start with which are randomly dealt. You can subtract out the ones that you have seen since the last shuffle, if any, and then work out the permutations for the rest. Sounds like a lot of work, and a lot of memory.

Aren't you better off simply working on probabilities? eg, if there are 380 cards left, and you have seen 2 aces then the probability of another ace is around 2 * 6 / 380 or something like that.

Similarly you could work out the possibilities for the card the dealer has face down.

I think what Bobble actually needs is a way to tell how many ways can numbers from 1 to 11 combine in to form a difference between the value of the dealers' upcard and 21. Sounds to me like an "n choose k" problem. Just counting that, I get (correct me if I am wrong) C(19, 11) = 126025 total combinations. That sounds like an awful lot of work and memory indeed.

Why not just go with basic strategy - graphs for that are abundant on the net for absolutely free and it's pretty much the same thing. Those things tell you whether you need to hit, stand, or double, taken into account the value of your 2 cards and the dealers' upcard, in a very nice and visible manner.

But why not post what you've got already, I, at least, would like to take a look at it, if for no other reason than out of curiousity.