I am trying to solve a code challenge. It is about the game blackjack. 2 cards are given to me, 1 to the dealer. I know every card including the deck. I need to calculate the probability to win, to tie, and to lose. As the sum of these must be 1, it suffices to calculate two of them.
I provide here the translation of original code challenge:
Blackjack is a card-based game of chance. It is played using a poker deck, each card counting its value, except face cards which all count as 10, and the Ace which counts as 1 or 11 depending on what benefits the card holder the most. The player's objective is to reach 21 without exceeding it. At the start of the game, the player is dealt 2 cards, and the dealer (represented by a croupier) is dealt 1 card. From this point on, the player can request another card as many times as they want (until reaching 21 or exceeding it), or stand with what they have. If the player stands with 21 or less, then the dealer starts dealing cards to himself until he reaches 17 (the dealer is obliged to request another card if his sum is less than 17 and stand if his sum is 17 or greater). Once both have stood or exceeded 21, the winner of the hand is decided. If the player exceeds 21, they lose regardless of what the dealer has. If the dealer exceeds 21 and the player does not, the player wins. Finally, if both have 21 or less, the one with the higher sum wins. If both have the same sum, the hand ends in a tie. Lastly, it remains to explain what it means to have blackjack. Having blackjack means having a hand that sums to 21 with only two cards. The advantage of having blackjack is that it beats a hand that has 21 with more than two cards, that is, 21 without blackjack.
Having explained the rules of blackjack, the objective of this problem is to calculate the probabilities of winning, tying, and losing if I stand with a certain sum, knowing what the dealer's initial card is and how many cards of each type are still to come (this is because the cards that have already come out cannot come out again, so when drawing a card from the deck not all cards are equally probable).
A very simple case would be, for example, if the player stands with 17, the dealer's card is a 10, and there are 1 seven, 2 nines, and 1 five left in the deck. In this case, the player's probability of > losing would be 50%, tying would be 25%, and winning would be 25%.
Input Format
For each test, the first line will be 𝑆, the sum with which the player has stood. If instead of a number, "B" is given, it means 21 in two cards (blackjack).
The second line will be 𝐶, the dealer's initial card (both face cards and tens are considered the same card, since they all count as 10, and they will all be represented as 10).
The next 10 lines will be 𝐷𝑛, the number of cards of each type (Ace, two, three, ...., nine, ten) that are left in the deck (both face cards and tens are considered the same card, since they all count as 10, and they will all be represented as 10).
Constraints
- 3 < 𝑆 < 22
- 0 < 𝐶 < 11
- 0 < 𝐷𝑛 < 128
Output Format
The output should be three lines. The first will contain the probability that the player has of winning, the second the probability of tying, and the third the probability of losing. All probabilities should be expressed with one decimal place, truncating the remaining decimal figures (not rounding).
Example 1
Input:
17 10 0 0 0 0 1 0 1 0 2 0Output:
25.0 25.0 50.0Example 2
Input:
13 2 24 24 24 24 24 24 24 24 24 128Output:
39.9 0.0 60.0
For the first example, my code provides the correct answer. But for the second input it returns:
41.8
0.0
58.1
...which differs slightly from the expected output. My code also fails other (hidden) test cases.
My Java code:
import java.util.*;
public class Main {
private static final Map<String, double[]> memo = new HashMap<>();
public static void main(String[] args) {
List<Integer> deck = new ArrayList<>();
Scanner scanner = new Scanner(System.in);
String playerTotalString = scanner.next();
int playerTotal;
if (playerTotalString.equals("B")){
playerTotal = 21;
} else {
playerTotal = Integer.valueOf(playerTotalString);
}
int dealerTotal = scanner.nextInt();
for (int i = 1; i <= 10; i++) {
int n = scanner.nextInt();
for (int k = 0; k < n; k++) {
deck.add(i);
}
}
scanner.close();
if (dealerTotal == 1){
dealerTotal = 11;
}
double[] result = getWinOrTieProbability(deck, playerTotal, dealerTotal, 1);
System.out.println((float)Math.floor(result[0] * 1000)/10);
System.out.println((float)Math.floor((1 - result[1] - result[0]) * 1000)/10);
System.out.println((float)Math.floor(result[1] * 1000)/10);
}
public static double[] getWinOrTieProbability(
List<Integer> deck, int player, int dealer, int numDealerCards) {
if (dealer > 21) {
return new double[]{1, 0};
}
if (dealer >= 17) {
if (player > dealer) {
return new double[]{1, 0};
} else if (player == dealer) {
if (player == 21 && numDealerCards > 2) {
return new double[]{1, 0};
}
return new double[]{0, 0};
} else {
return new double[]{0, 1};
}
}
String memoKey = deck.toString() + player + dealer + numDealerCards;
if (memo.containsKey(memoKey)) {
return memo.get(memoKey);
}
double sumWin = 0, sumLose = 0;
int deckSize = deck.size();
int count = 0;
for (int i = 0; i < deckSize; i++) {
int card = deck.get(i);
List<Integer> deckCopy = new ArrayList<>(deck);
deckCopy.remove(i);
double[] results;
results = getWinOrTieProbability(deckCopy, player, dealer + card, numDealerCards + 1);
sumWin += results[0];
sumLose += results[1];
count++;
if (card == 1 && dealer + 11 <= 21) {
results = getWinOrTieProbability(deckCopy, player, dealer + 11, numDealerCards);
sumWin += results[0];
sumLose += results[1];
count++;
}
}
double[] result = new double[]{sumWin / count, sumLose / count};
memo.put(memoKey, result);
return result;
}
}
Where is my mistake that explains the wrong output?
There is a problem when the dealer hits an ace: in that case you allow two scenarios to play out, but that is not how it works in reality: the dealer will only count it as a 1 when they would bust otherwise. There is no choice. Yet your code will consider what happens if they do count it as a 1 even when they don't bust with counting 11. This will infect your statistics.
Furthermore, if they use an ace as 11, and then bust with a later card, they should replace that earlier ace with a 1, but your code does not perform that reduction. You need to keep track of the fact whether the dealer still has an ace in their hand that counts as 11.
After your edit one more issue surfaced:
You write at the top that the player has been dealt 2 cards, but the description of the challenge indicates that the player might have received more cards before they stand. It also explains that there is a difference between blackjack and "just" 21. The first is indicated with a "B" and a normal 21 implies that the player had actually received more than 2 card. In your logic you did not retain the distinction between blackjack and just 21 for what concerns the player's hand. Moreover, when both have 21, you have not foreseen a case where the dealer can still win, yet that is possible: when the player does not have blackjack, and the dealer has blackjack. Also, when both have 21 which are not blackjacks, then it should be a draw. To make this possible, I suggest you also provide a parameter called player_has_blackjack
Here is a correction:
import java.util.*;
public class Main {
private static final Map<String, double[]> memo = new HashMap<>();
public static void main(String[] args) {
List<Integer> deck = new ArrayList<>();
Scanner scanner = new Scanner(System.in);
String playerTotalString = scanner.next();
int playerTotal;
// Part of the state to retain is whether player has blackjack
boolean playerHasBlackjack = playerTotalString.equals("B");
if (playerHasBlackjack) {
playerTotal = 21;
} else {
playerTotal = Integer.valueOf(playerTotalString);
}
int dealerTotal = scanner.nextInt();
for (int i = 1; i <= 10; i++) {
int n = scanner.nextInt();
for (int k = 0; k < n; k++) {
deck.add(i);
}
}
// Keep tack of whether dealer has used an ace as 11
boolean dealerHasAce = dealerTotal == 1;
if (dealerHasAce){
dealerTotal = 11;
}
// Pass extra arguments
double[] result = getWinOrTieProbability(deck, playerTotal, playerHasBlackjack, dealerTotal, 1, dealerHasAce);
System.out.println((float)Math.floor(result[0] * 1000)/10);
System.out.println((float)Math.floor((1 - result[1] - result[0]) * 1000)/10); // Ties
System.out.println((float)Math.floor(result[1] * 1000)/10);
}
/*
* Provide extra parameter to know whether dealer has an 11 in their hand
* Provide extra parameter to know whether player has blackjack
*/
public static double[] getWinOrTieProbability(
List<Integer> deck, int player, boolean playerHasBlackjack,
int dealer, int numDealerCards, boolean dealerHasAce) {
if (dealer > 21 && dealerHasAce) {
// Don't bust! Continue with 1...
dealer -= 10;
dealerHasAce = false;
}
if (dealer > 21) {
return new double[]{1, 0};
}
if (dealer >= 17) {
if (player > dealer) {
return new double[]{1, 0};
} else if (player == dealer) {
// If exactly one has blackjack, they win
if (player == 21 && playerHasBlackjack != (numDealerCards == 2)) {
return playerHasBlackjack ? new double[]{1, 0}
: new double[]{0, 1};
}
return new double[]{0, 0};
} else {
return new double[]{0, 1};
}
}
String memoKey = deck.toString() + player + playerHasBlackjack + dealer + dealerHasAce + numDealerCards;
if (memo.containsKey(memoKey)) {
return memo.get(memoKey);
}
double sumWin = 0, sumLose = 0;
int deckSize = deck.size();
for (int i = 0; i < deckSize; i++) {
int card = deck.get(i);
List<Integer> deckCopy = new ArrayList<>(deck);
deckCopy.remove(i);
double[] results;
// There is always only one scenario, never a choice of two:
if (card == 1 && !dealerHasAce) {
results = getWinOrTieProbability(deckCopy, player, playerHasBlackjack, dealer + 11, numDealerCards + 1, true);
} else {
results = getWinOrTieProbability(deckCopy, player, playerHasBlackjack, dealer + card, numDealerCards + 1, dealerHasAce);
}
sumWin += results[0];
sumLose += results[1];
}
double[] result = new double[]{sumWin / deckSize, sumLose / deckSize};
memo.put(memoKey, result);
return result;
}
}