G: A No-Win Situation

November 25th, 2009 | Categories: 2008 Regionals

This was a simple simulation. No fancy algorithms, just do what you’re told. Unfortunately, that turned out to be harder than we thought. It seems that a lot of our competitors didn’t know how to play Blackjack. That’s probably a good thing. We tried to explain it thoroughly in the problem statement, but we still got a lot of questions, like:

When is an Ace 11, and when is it one? Who chooses, and when?

Do we have to decide when we get the Ace whether it’s going to be 11 or 1?

What happens when we have, say an A=11 and a 5 for 16, but then we get a 9?

How does the dealer choose whether to take a card or not?

If the player has 14 and the dealer has 16, why wouldn’t the dealer stand?

OK, no more Blackjack problems in the SER.

For the Ace = 1 or 11 questions, an Ace counts for 11 unless that would cause a bust, in which case it counts as 1. There is no decision to be made. It’s automatic – in the rules. When does it change value? As soon as a new card is dealt. If you have A5, your hand is worth 16. If you are then dealt  a 9, your A59 hand is worth 15. If your hand has more than one A, then your hand will have the max value possible without busting. Since 11+11=22=bust, that means that at most one of your Aces can count as 11, all the rest are 1.  Which one? It simply doesn’t matter. Pick one.

Here’s another way to look at it: Since Aces can be worth 1 OR 11, if you have an Ace in your hand, then your hand could have different scores. the House will always use the best possible score for any hand – that is, the closest to 21 without going over.

The Dealer’s behavior is completely deterministic. The Dealer has no choice. S/he MUST take a card if his/her score is less than 17. S/he MUST stand if his/her score is greater than or equal to 17. That’s also in the rules. The Dealer is not allowed to think about it, or react to the players’ hands.  <17, Hit. >=17, Stand. That’s it.

The most frequent logic problems we saw had to do with saving and restoring the state of the system each time you try a new possibility. Most often, it was the Dealer’s hand that didn’t get saved and restored correctly.

Here’s the Judge Input, the Judge Output, the main solving program, another Java program, and a C++ program.

It’s not much of an algorithm, but if you need more, there’s some pseudocode in the spoiler.

Spoiler »

Deal first card to Player
Deal second card to Dealer
Deal third card to Player
Deal fourth card to Dealer
Save the Dealer's hand!
While player hasn't won and hasn't busted
    Save the state of the deck
    Restore Dealer's hand
    While Dealer's hand value < 17
        Deal next card to Dealer
    End While
    If Player score >= Dealer score OR Dealer score > 21
        Player wins!
        Restore the Deck
        Deal next card to Player
    End if
End While

It’s probably smart to use the same logic for dealing a card to the Player and to the Dealer. The score of the hand is computed the same way for both of them. Here’s some pseudocode for that:

If the Card is an Ace
    Add 11 to the Score
    Add 1 to the Number of Aces counting as Eleven
    Add the Value of the Card to the Score
End If

While the Score > 21 AND the Number of Aces counting as Eleven > 0
    Subtract 10 from the Score
    Subtract 1 from the Number of Aces counting as Eleven
No comments yet.
You must be logged in to post a comment.