• Create Account

# Data Structures & Algorithms for Blackjack Simulator

9 replies to this topic

### #1sooner123  Members   -  Reputation: 229

Like
1Likes
Like

Posted 10 October 2013 - 01:57 AM

I'm trying to create a Blackjack simulator so I can test out (and maybe genetically evolve) some various play-charts, betting-strategies, and card-counting-charts.

Before I dive into it, I wanted to outline the structure in detail, since the game has these caveats that make it less trivial to code than a game like poker. (like splitting)

My basic design so far is this:

Data Structures:

-deck: composed of a vector or list of cards

-card: composed of a value (like 10 for 10's, Jacks, Queens, etc.), a name and a suit

-hand: composed of a bet, a list of cards, and two hands (potential left split and right split)

-player: composed of a balance and a hand

Algorithms:

-shuffling: i'm going to shuffle by sucking cards, randomly, out of the deck and creating a new deck, in order

Questions:

1. Should I use a vector or a list for the cards? I'm thinking:

vector: O(1) for lookup, O(n/4) for removal (average cases)

list: O(n/4) for lookup, O(1) for removal (average cases)

2. How do I deal with Aces? Is the best way to just have some conditional code whenever dealing with cards to see if a card is an Ace to check for soft 17's and the like?

### #2PeterStock  Members   -  Reputation: 337

Like
1Likes
Like

Posted 10 October 2013 - 02:29 AM

You know that the number of items (cards) is going to be very small (52), so I'd think that the O() order of performance doesn't matter so much.

I noticed one thing though - you mentioned extracting statistics for betting strategies. I think real-world shuffling is actually very un-random, if you do your shuffling as described it might not be such a good model. Maybe make N splits in the deck and re-arrange those stack of cards, repeated multiple times? I don't know how casinos do this though, maybe they have a machine or something?

### #3Segmented  GDNet+   -  Reputation: 296

Like
1Likes
Like

Posted 10 October 2013 - 05:42 AM

1/ I think I would prefer to use a std::deque in this case, because it allows fast removal and insertion. However perhaps you should rethink your shuffle model altogether. It sounds like first answer preposed here might be a better fit, in which case I would go with a std::vector.

2/ Aces kind of mess things up because they can have two values. Resorting to a conditional check as you mention may be the best option for that, I can't really think of anything more elegant.

### #4Paradigm Shifter  Crossbones+   -  Reputation: 3993

Like
1Likes
Like

Posted 10 October 2013 - 06:47 AM

Assuming C++, use a vector for the shuffled deck (you will want multiple decks as well, usually 6 or 8. EDIT: They also reshuffle after about half the cards have been dealt). Maintain an iterator (or index) to the next card to be dealt (i.e. don't remove cards from the deck once you have shuffled, just advance the iterator to the next card after dealing one).

Just use std::random_shuffle from <algorithm>

Can't you split multiple times? (i.e. if you split once and you get a pair again can you split again?). I'm not sure ;)

Have an is_soft boolean if you have an ace, and the total is either the total with aces counting as 11 or 10 less than that. I think that works for more than one ace. EDIT: Only the first ace can count as 11 or 1, any others must count as 1, since 11+11 = bust. So count aces as 1 and if you have an ace, you can add 10 on to the total if you wish.

Remember the dealer doesn't get a choice although the rules can be different for different casinos (i.e. what they stand on, sometimes they have to hit soft 17 sometimes they don't, IIRC).

There is a table of best plays, it depends on what the dealer is showing, see the wikipedia page under "basic strategy" http://en.wikipedia.org/wiki/Blackjack

Although counting cards can improve this (but you'll get a "talking to" in the back room if they catch you counting cards in a real casino, and you will be banned and casinos share information with each other about counters). EDIT2: Online casinos probably shuffle after every hand, so counting is useless I expect. Casinos would shuffle after every hand if they had the time.

Edited by Paradigm Shifter, 10 October 2013 - 11:21 AM.

"Most people think, great God will come from the sky, take away everything, and make everybody feel high" - Bob Marley

### #5sooner123  Members   -  Reputation: 229

Like
0Likes
Like

Posted 10 October 2013 - 11:25 AM

PeterStock

I think the performance may matter since I'm intending on running the simulation as a GA that will evolve towards better play. Also, I didn't mention this, but I'll actually be using upwards of 8 decks (4 and 6 most frequently) to better simulate real casino settings.

Segmented

Thanks for the link. That's a nice algorithm. I'm actually leaning towards multiple splits and maybe some splits + messy merges to better simulate real shuffling.

Yeah I am intending on having a variable for depth of penetration. The casino I just visited (for my first casino experience and a $1330 win overall in Blackjack ) Seemed to reshuffle after roughly 75% penetration into four decks. I didn't know what I was doing or have any real system, but I was keeping separate running counts for 5's, 6's, Aces, and Faces, which apparently is more difficult than and less edge-earning than a simple High-Low system. Didn't know about random_shuffle. That's awesome. Thanks. Most casinos don't allow splitting on splits (vast majority if not all) and the opportunity is so rare. However, I feel like I should leave it an option for simulations in which billions of hands may occur. Hopefully my current "hands" design should allow for this. I'll be keeping it in mind. Your is_soft should do the trick. I'll have to pay special attention to that. Dealer rules will be part of the parameters of the sim. (hit/stand on soft 17, double after splits, whether you can surrender, # decks, % depth penetration) The problem with a static table of best plays (which is what I used when I won this weekend in Vegas) is that the best plays do shift somewhat as you reach the end of a deck and counting indicates a heavily loaded or unloaded deck. Not super often, but enough to constitute more advantage from card-counting than is gained from just varying your bets. So I kind of want to give it the "standard table of best plays" and let things "evolve." Counting cards actually isn't illegal. Only if aided by a device. Nowadays, if you are hurting the house's bottom line, they're more likely to just ask you to stop playing that specific game. My hope is to just grind them down rather than try to make some big plays. From my calculations, in fact, my leaving Vegas on my first trip with a 600% return-on-bankroll was a tad less likely than bankruptcy. So I got lucky and I'd like it to be slightly less "luck" next time Edited by sooner123, 10 October 2013 - 11:29 AM. ### #6Paradigm Shifter Crossbones+ - Reputation: 3993 Like 0Likes Like Posted 10 October 2013 - 11:40 AM A good betting system to use is the one where you pick 4 numbers which sum to what you want to win each "round". Say you want to win$10 per round, write down 1,2,3,4. Bet the sum of the first and last numbers in the list (so start with 5). If you win, knock off the first and last item in the list (so list becomes 2,3). If you lose, add the amount you just staked to the end of the list (so list becomes 1,2,3,4,5). Repeat. 1,2,2,3 is another good list to use. Then you only need to win half as often as you lose + 2 extra wins to win a round. Like all betting systems it gets steep quickly if you go on a losing streak, but it's not as bad as doubling up all the time just to win \$1.

If you use a betting system you need to account for house limits on a single bet.

"Most people think, great God will come from the sky, take away everything, and make everybody feel high" - Bob Marley

### #7PeterStock  Members   -  Reputation: 337

Like
0Likes
Like

Posted 10 October 2013 - 11:40 AM

Cool, GAs are great   From my (little) experience with them, I think the encoding can make quite a difference - if you can ensure the offspring is (1) valid and (2) similar to the parents then it's all good, otherwise it's kind of like expensive random search

### #8Paradigm Shifter  Crossbones+   -  Reputation: 3993

Like
0Likes
Like

Posted 10 October 2013 - 11:50 AM

What does "surrender" mean?

Disregard the "insurance" bet, that's not a good deal at 2-1. (EDIT: Actually, if you are counting, the odds might swing in your favour if there are a lot of 10s left in the deck, you'd have to do the maths but I suspect you would need to know exactly how many cards are left in the deck as well to calculate the odds, which is going to tax your brain even more, so I'd probably ignore insurance bets completely).

Do you get your stake back for a tie? You should, but then again in America they have 2 zeroes on a Roulette wheel so I wouldn't put it past them. In the UK they only have one zero (although I have seen a sign outside a casino advertising "American Roulette", LOL, why would you play that if you have a one zero table as well?) In French Roulette you get half your stake back for an evens bet when zero comes up! So the best Roulette to play is Blackjack ;) > French Roulette > British Roulette > American Roulette.

EDIT: And I edited my original post about is_soft in case you were replying when I edited and missed it. Count aces as 1 and if you have an ace add 10 on (and call it soft) if you have a total of 11 or less. Always stand on soft 21 though ;)

EDIT2: @Peter Stock - yes, they use shuffling machines at casinos. They wouldn't want to let a crooked dealer shuffle anyway.

Edited by Paradigm Shifter, 10 October 2013 - 12:30 PM.

"Most people think, great God will come from the sky, take away everything, and make everybody feel high" - Bob Marley

### #9AngleWyrm  Members   -  Reputation: 551

Like
0Likes
Like

Posted 14 October 2013 - 03:43 PM

• For C++, std::random_shuffle ( myvector.begin(), myvector.end() );
• For Java, Collections.shuffle( myArrayList );

Then just take as many as needed from one end.

Edited by AngleWyrm, 14 October 2013 - 03:45 PM.

--"I'm not at home right now, but" = lights on, but no ones home

### #10Paradigm Shifter  Crossbones+   -  Reputation: 3993

Like
0Likes
Like

Posted 14 October 2013 - 04:16 PM

std::shuffle() in C++11 is probably better since it allows unbiased random number generators rather than relying on rand(). I suggested std::random_shuffle() earlier on though too. Both are in <algorithm> and the new random generators are in <random>.

"Most people think, great God will come from the sky, take away everything, and make everybody feel high" - Bob Marley

PARTNERS