## Blackjack Basic Strategy – Infinite Deck

May 24, 2010 at 06:24 (algorithm, java, math.PR)

I came across a good programming exercise over on this thread at Math Help Forum (I’m “undefined”), and here are the results. This program reproduces the charts and expected value on this page over at The Wizard of Odds for an infinite deck. I realise the code could be cleaner, but I’m pleased with the performance of the underlying algorithms. On my laptop with modest specs, calculation takes about 20 milliseconds.

I see room for some optimisations here and there, mainly involving counting to 10 instead of 13, intermediate variables, redundant rows, and redundancy in the form of f(x,y) = f(y,x), but I don’t intend to update the code anytime soon.

```import java.util.Scanner;

public class BlackjackStrat {
static final int S = 0, H = 1, D = 2, Ds = 3, P = 4, R = 5;

static double[][] expRetStandMemo = new double[6][10];
static double[][] expRetHitHardMemo = new double[18][10];
static double[][] expRetHitSoftMemo = new double[10][10];
static double[][] expRetDoubleHardMemo = new double[18][10];
static double[][] expRetDoubleSoftMemo = new double[10][10];
static double[][][] expRetIfNoSplitMemo = new double[10][10][10];
static int[][][] basicStatIfNoSplitMemo = new int[10][10][10];
static double[][] expRetSplitMemo = new double[10][10];
static double[][][] expRetMemo = new double[10][10][10];
static int[][][] basicStratMemo = new int[10][10][10];
static double expVal = 0, currExpRetGlob = 0, eps = 0.000000001;

public static void init() {
System.out.println("Blackjack basic strategy program for an infinite deck.\n");
long time = System.currentTimeMillis();
System.out.println("Calculating values.");
double dummy = 0;
for (int i = 0; i < 6; i++)
for (int j = 0; j < 10; j++)
expRetStandMemo[i][j] = -50;
for (int i = 0; i < 18; i++)
for (int j = 0; j < 10; j++)
expRetHitHardMemo[i][j] = -50;
for (int i = 0; i < 10; i++)
for (int j = 0; j < 10; j++)
for (int k = 0; k < 10; k++)
expRetIfNoSplitMemo[i][j][k] = -50;
// calculate expected returns by standing
for (int i = 16; i < 22; i++)
for (int j = 1; j < 11; j++)
dummy += expRetStand(i, j);
// calculate other expected returns
calcExpRetHit();
calcExpRetDouble();
calcExpRetSplit();
calcBasicStrat();
System.out.println("\nCalculation took " + (System.currentTimeMillis() - time) / 1000.0 + " seconds.\n");
}

public static void main(String[] args) {
init();
}

Scanner in = new Scanner(System.in);
String option = "";
while (true) {
System.out.println("Options:\n");
System.out.println("0 - Rules");
System.out.println("1 - Player's Expected Return by Standing");
System.out.println("2 - Player's Expected Return by Hitting");
System.out.println("3 - Player's Expected Return by Doubling");
System.out.println("4 - Player's Expected Return by Splitting");
System.out.println("5 - Basic Strategy Table");
System.out.println("6 - Player's Expected Value");
System.out.println("7 - Exit\n");
option = in.nextLine();
if (option.equals("0")) displayRules();
else if (option.equals("1")) displayExpRetStand();
else if (option.equals("2")) displayExpRetHit();
else if (option.equals("3")) displayExpRetDouble();
else if (option.equals("4")) displayExpRetSplit();
else if (option.equals("5")) displayBasicStrat();
else if (option.equals("6")) displayExpVal();
else if (option.equals("7")) break;
else System.out.println("\nInvalid input. Please enter an integer between 0 and 7, inclusive.");
System.out.println();
}
}

public static void displayRules() {
System.out.println("\nRules:\n");
System.out.println("1) Dealer stands on a soft 17");
System.out.println("2) Infinite deck");
System.out.println("3) Player may double after a split");
System.out.println("4) Split up to three times except for aces");
System.out.println("5) Draw only one card to split aces");
System.out.println("6) For calculating expected value, surrender is disallowed");
}

public static void displayExpRetStand() {
System.out.println("\nPlayer's Expected Return by Standing:\n");
System.out.println("(Player's Hand) (Dealer's Up Card) Expected Return\n");
for (int i = 16; i < 22; i++)
for (int j = 2; j < 12; j++) {
String playerTotStr = (i == 16) ? "2-16" : String.valueOf(i);
int dealerShows = (j == 11) ? 1 : j;
String dealerShowsStr = (dealerShows == 1) ? "A" : String.valueOf(dealerShows);
System.out.println("(" + playerTotStr + ") (" + dealerShowsStr + ") " + expRetStand(i, dealerShows));
}
}

public static void displayExpRetHit() {
System.out.println("\nPlayer's Expected Return by Hitting:\n");
System.out.println("(Player's Hand) (Dealer's Up Card) Expected Return\n");
for (int i = 4; i < 22; i++)
for (int j = 2; j < 12; j++) {
int dealerShows = (j == 11) ? 1 : j;
String dealerShowsStr = (dealerShows == 1) ? "A" : String.valueOf(dealerShows);
System.out.println("(" + i + ") (" + dealerShowsStr + ") " + expRetHitHard(i, dealerShows));
}
for (int i = 1; i < 11; i++)
for (int j = 2; j < 12; j++) {
String playerNonAceTotStr = (i == 1) ? "A" : String.valueOf(i);
int dealerShows = (j == 11) ? 1 : j;
String dealerShowsStr = (dealerShows == 1) ? "A" : String.valueOf(dealerShows);
System.out.println("(A, " + playerNonAceTotStr + ") (" + dealerShowsStr + ") " +
expRetHitSoft(i, dealerShows));
}
}

public static void displayExpRetDouble() {
System.out.println("\nPlayer's Expected Return by Doubling:\n");
System.out.println("(Player's Hand) (Dealer's Up Card) Expected Return\n");
for (int i = 4; i < 22; i++)
for (int j = 2; j < 12; j++) {
int dealerShows = (j == 11) ? 1 : j;
String dealerShowsStr = (dealerShows == 1) ? "A" : String.valueOf(dealerShows);
System.out.println("(" + i + ") (" + dealerShowsStr + ") " + expRetDoubleHard(i, dealerShows));
}
for (int i = 1; i < 11; i++)
for (int j = 2; j < 12; j++) {
String playerNonAceTotStr = (i == 1) ? "A" : String.valueOf(i);
int dealerShows = (j == 11) ? 1 : j;
String dealerShowsStr = (dealerShows == 1) ? "A" : String.valueOf(dealerShows);
System.out.println("(A, " + playerNonAceTotStr + ") (" + dealerShowsStr + ") " +
expRetDoubleSoft(i, dealerShows));
}
}

public static void displayExpRetSplit() {
System.out.println("\nPlayer's Expected Return by Splitting:\n");
System.out.println("(Player's Hand) (Dealer's Up Card) Expected Return\n");
for (int i = 2; i < 12; i++)
for (int j = 2; j < 12; j++) {
int playerCard = (i == 11) ? 1 : i;
String playerCardStr = (i == 11) ? "A" : String.valueOf(i);
int dealerCard = (j == 11) ? 1 : j;
String dealerCardStr = (j == 11) ? "A" : String.valueOf(j);
System.out.println("(" + playerCardStr + ", " + playerCardStr + ") (" +
dealerCardStr + ") " + expRetSplit(playerCard, dealerCard));
}
}

public static void displayBasicStrat() {
System.out.println("\nBasic Strategy Table:\n");
System.out.println("Hard       2  3  4  5  6  7  8  9 10  A");
for (int i = 4; i < 22; i++) {
System.out.print(rowNum);
for (int j = 2; j < 12; j++) {
int dealerShows = (j == 11) ? 1 : j;
}
System.out.println();
}
System.out.println();
System.out.println("Soft       2  3  4  5  6  7  8  9 10  A");
for (int i = 13; i < 22; i++) {
System.out.print(rowNum);
for (int j = 2; j < 12; j++) {
int dealerShows = (j == 11) ? 1 : j;
}
System.out.println();
}
System.out.println();
System.out.println("Splits     2  3  4  5  6  7  8  9 10  A");
for (int i = 2; i < 12; i++) {
String rowNum = String.valueOf(i);
if (i == 11) rowNum = "A";
rowNum += "," + rowNum;
System.out.print(rowNum);
int playerCard = (i == 11) ? 1 : i;
for (int j = 2; j < 12; j++) {
int dealerShows = (j == 11) ? 1 : j;
}
System.out.println();
}
System.out.println();
System.out.println("Lengend:\n");
System.out.println("S  Stand");
System.out.println("H  Hit");
System.out.println("D  Double if you can, otherwise hit");
System.out.println("Ds Double if you can, otherwise stand");
System.out.println("P  Split");
System.out.println("R  Surrender if you can, otherwise hit");
}

public static void displayExpVal() {
System.out.println("\nThe player's expected value is " + expVal + ".");
}

//~~~~~~~~~ calculate and retrieve methods follow ~~~~~~~~~

// code written first is towards the bottom. later calculations tend to rely on
// earlier calculations.

public static String getLetter(int n) {
switch (n) {
case S: return "S";
case H: return "H";
case D: return "D";
case Ds: return "Ds";
case P: return "P";
case R: return "R";
default: return "";
}
}

public static int basicStrat(int playerTot, int dealerShows) {
if (playerTot < 5) return H;
if (playerTot < 13) return basicStrat(2, playerTot - 2, dealerShows);
if (playerTot < 20) return basicStrat(10, playerTot - 10, dealerShows);
return S;
}

public static int basicStrat(int playerCard1, int playerCard2, int dealerShows) {
// only call this AFTER running init()!
return basicStratMemo[playerCard1 - 1][playerCard2 - 1][dealerShows - 1];
}

public static void calcBasicStrat() {
// note: this calculates expected values for all possible card combinations, then uses
// this info to determine the best strategy. since surrendering always results in an
// expected return of -0.5, it is the best option if and only if the expected return would
// otherwise be less than -0.5. also, expected value is calculated in the process.
for (int i = 1; i < 11; i++) {
double p1 = (i == 10) ? 4 / 13.0 : 1 / 13.0;
for (int j = 1; j < 11; j++) {
double p2 = (j == 10) ? 4 / 13.0 : 1 / 13.0;
for (int k = 1; k < 11; k++) {
double p3 = (k == 10) ? 4 / 13.0 : 1 / 13.0;
double expRet = expRetIfNoSplit(i, j, k);
int bestStrat = basicStatIfNoSplitMemo[i - 1][j - 1][k - 1];
if (i == j) {
double expRet2 = expRetSplit(i, k);
if (expRet2 > expRet) {
expRet = expRet2;
bestStrat = P;
}
}
if (expRet < -0.5) {
//expRet = -0.5;
bestStrat = R;
}
expRetMemo[i - 1][j - 1][k - 1] = expRet;
basicStratMemo[i - 1][j - 1][k - 1] = bestStrat;

double p = p1 * p2 * p3;
// expected value calculation must take blackjacks into consideration
if (!(i == 1 && j == 10) && !(i == 10 && j == 1)) {
if (k == 1) {
expVal -= p * 4.0 / 13.0;
expVal += p * expRet * 9.0 / 13.0;
}
else if (k == 10) {
expVal -= p / 13.0;
expVal += p * expRet * 12.0 / 13.0;
}
else expVal += p * expRet;
}
else {
if (k == 1) expVal += 1.5 * p * 9.0 / 13.0;
else if (k == 10) expVal += 1.5 * p * 12.0 / 13.0;
else expVal += 1.5 * p;
}
}
}
}
}

public static double expRetSplit(int playerCard, int dealerShows) {
// only call this AFTER running init()!
if (dealerShows > 10 || dealerShows < 1 || playerCard > 10 || playerCard < 1) {
System.out.println("Error: illegal input, id 6.");
System.exit(1);
}
return expRetSplitMemo[playerCard - 1][dealerShows - 1];
}

public static void calcExpRetSplit() {
// note: the logic here is that if you split once, then you might as well split as
// many times as possible. so the expected returns are not necessarily the maximum
// expected returns, which would be obtained by calculating at each step the expected
// return from splitting and from not splitting, and then taking the maximum. but in
// those cases where splitting is ideal, then the expected returns are in fact maximal.
// also, it seems that the chart i was going based off of allows one to split a pair of
// ten-valued cards even if they are not the same (e.g., 10 and Q). i do not know
// whether this is common practice, or perhaps i misinterpreted.

// ace
for (int i = 1; i < 11; i++) {
double currExpRet = 0;
double p = 2 / 13.0;
for (int j = 1; j < 11; j++) {
double p2 = (j == 10) ? 4 * p : p;
currExpRet += p2 * expRetStand(11 + j, i);
}
expRetSplitMemo[0][i - 1] = currExpRet;
}

// non-ace
for (int i = 2; i < 11; i++) {
for (int j = 1; j < 11; j++) {
double expRetNotSplittable = 0;
for (int k = 1; k < 11; k++) {
if (i == k) continue;
double p = (k == 10) ? 4 / 12.0 : 1 / 12.0;
if (i == 10) p = 1 / 9.0;
expRetNotSplittable += p * expRetIfNoSplit(i, k, j);
}
double expRetNoResplit = 0;
for (int k = 1; k < 11; k++) {
double p = (k == 10) ? 4 / 13.0 : 1 / 13.0;
expRetNoResplit += p * expRetIfNoSplit(i, k, j);
}
double rets[] = {expRetNotSplittable, expRetNoResplit};
double expRet = recurse2(i, 1, rets, 2, new int[4], j);
expRetSplitMemo[i - 1][j - 1] = expRet;
}
}
}

public static double recurse2(int initCard, double p, double[] rets, int numHands,
int[] hands, int dealerShows) {
// helper method for calcExpRetSplit()
int ind = 0;
while (ind < numHands && hands[ind] > 0)
ind++;
if (ind == numHands) {
double currExpRet = 0;
for (int i = 0; i < numHands; i++)
currExpRet += rets[hands[i] - 1];
return p * currExpRet;
}
else {
double currExpRet = 0, nextP = 12 * p / 13.0;
double p2 = (initCard != 10) ? p / 13.0 : 4 * p / 13.0;
if (initCard == 10) nextP = 9 * p / 13.0;
// draw same card, therefore split
if (numHands < 4)
currExpRet += recurse2(initCard, p2, rets, numHands + 1, hands.clone(), dealerShows);
else nextP = p;
// draw different card
int[] nextHands = hands.clone();
nextHands[ind] = (numHands == 4) ? 2 : 1;
currExpRet += recurse2(initCard, nextP, rets, numHands, nextHands, dealerShows);
return currExpRet;
}
}

public static double expRetIfNoSplit(int playerCard1, int playerCard2, int dealerShows) {
// assume playerCard1, playerCard2 and dealerShows are between 1 and 10, inclusive
int ind1 = playerCard1 - 1, ind2 = playerCard2 - 1, ind3 = dealerShows - 1;
if (!doubEquals(expRetIfNoSplitMemo[ind1][ind2][ind3], -50))
return expRetIfNoSplitMemo[ind1][ind2][ind3];
if (playerCard1 == 1) {
int temp = playerCard1;
playerCard1 = playerCard2;
playerCard2 = temp;
}
double expRet1 = 0, expRet2 = 0, expRet3 = 0;
int playerTot = playerCard1 + playerCard2;
if (playerCard2 == 1) playerTot += 10;
expRet1 = expRetStand(playerTot, dealerShows);
if (playerCard2 == 1) {
expRet2 = expRetHitSoft(playerCard1, dealerShows);
expRet3 = expRetDoubleSoft(playerCard1, dealerShows);
}
else {
expRet2 = expRetHitHard(playerTot, dealerShows);
expRet3 = expRetDoubleHard(playerTot, dealerShows);
}
double expRet = Math.max(expRet1, Math.max(expRet2, expRet3));
if (doubEquals(expRet, expRet1)) basicStatIfNoSplitMemo[ind1][ind2][ind3] = S;
else if (doubEquals(expRet, expRet2)) basicStatIfNoSplitMemo[ind1][ind2][ind3] = H;
else basicStatIfNoSplitMemo[ind1][ind2][ind3] = (expRet1 > expRet2) ? Ds : D;
return expRetIfNoSplitMemo[ind1][ind2][ind3] = expRet;
}

public static double expRetDoubleSoft(int playerNonAceTot, int dealerShows) {
// only call this AFTER running init()!
// playerNonAceTot is the value other than the ace; for the hand (A, A) this is also
// an ace. so when playerNonAceTot == 4, this means a soft 15.
if (dealerShows > 10 || dealerShows < 1 || playerNonAceTot > 10 || playerNonAceTot < 1) {
System.out.println("Error: illegal input, id 5.");
System.exit(1);
}
return expRetDoubleSoftMemo[playerNonAceTot - 1][dealerShows - 1];
}

public static double expRetDoubleHard(int playerTot, int dealerShows) {
// only call this AFTER running init()!
if (dealerShows > 10 || dealerShows < 1 || playerTot > 31 || playerTot < 4) {
System.out.println("Error: illegal input, id 4.");
System.exit(1);
}
if (playerTot > 21) return -1;
return expRetDoubleHardMemo[playerTot - 4][dealerShows - 1];
}

public static void calcExpRetDouble() {
double p2 = 2 / 13.0;

// hard totals
for (int i = 0; i < 10; i++)
expRetDoubleHardMemo[17][i] = -2;
for (int i = 4; i < 21; i++) {
for (int j = 1; j < 11; j++) {
double currExpRet = 0;
for (int k = 1; k < 14; k++) {
int cardVal = (k > 9) ? 10 : k;
int playerTot = i + cardVal;
if (k == 1 && playerTot + 10 < 22) playerTot += 10;
currExpRet += p2 * expRetStand(playerTot, j);
}
expRetDoubleHardMemo[i - 4][j - 1] = currExpRet;
}
}

// soft totals
for (int i = 1; i < 11; i++) {
for (int j = 1; j < 11; j++) {
double currExpRet = 0;
for (int k = 1; k < 14; k++) {
int numAces = (i == 1) ? 2 : 1;
int cardVal = (k > 9) ? 10 : k;
if (k == 1) {
numAces++;
cardVal = 11;
}
int playerTot = (i == 1) ? 22 + i : 11 + i;
playerTot += cardVal;
while (numAces > 0 && playerTot > 21) {
numAces--;
playerTot -= 10;
}
currExpRet += p2 * expRetStand(playerTot, j);
}
expRetDoubleSoftMemo[i - 1][j - 1] = currExpRet;
}
}
}

public static double expRetHitSoft(int playerNonAceTot, int dealerShows) {
// only call this AFTER running init()!
// playerNonAceTot is the value other than the ace; for the hand (A, A) this is also
// an ace. so when playerNonAceTot == 4, this means a soft 15.
if (dealerShows > 10 || dealerShows < 1 || playerNonAceTot > 10 || playerNonAceTot < 1) {
System.out.println("Error: illegal input, id 3.");
System.exit(1);
}
return expRetHitSoftMemo[playerNonAceTot - 1][dealerShows - 1];
}

public static double expRetHitHard(int playerTot, int dealerShows) {
// only call this AFTER running init()!
if (dealerShows > 10 || dealerShows < 1 || playerTot > 31 || playerTot < 4) {
System.out.println("Error: illegal input, id 2.");
System.exit(1);
}
if (playerTot > 21) return -1;
return expRetHitHardMemo[playerTot - 4][dealerShows - 1];
}

public static void calcExpRetHit() {
// first, get expected returns for hard totals >= 11
for (int i = 0; i < 10; i++)
expRetHitHardMemo[17][i] = -1;
for (int i = 20; i > 10; i--) {
for (int j = 1; j < 11; j++) {
int ind1 = i - 4;
int ind2 = j - 1;
double currExpRet = 0;
for (int k = 1; k < 14; k++) {
int cardVal = (k > 10) ? 10 : k;
int playerTot = i + cardVal;
if (playerTot > 21) currExpRet -= 1 / 13.0;
else {
double bestOption = Math.max(expRetStand(playerTot, j), expRetHitHardMemo[playerTot - 4][ind2]);
currExpRet += bestOption / 13.0;
}
}
expRetHitHardMemo[ind1][ind2] = currExpRet;
}
}

// next, get expected returns for soft totals. this relies on knowing expected
// returns for hitting on hard totals >= 12.
for (int i = 10; i > 0; i--) {
double p = 1 / 13.0;
for (int j = 1; j < 11; j++) {
double expRet1 = expRetHitHard(i + 11, j);
double expRet2 = 0;
for (int k = 1; k < 14; k++) {
int cardVal = (k > 9) ? 10 : k;
if (i + cardVal < 11) expRet2 += p * Math.max(expRetHitSoft(i + cardVal, j),
expRetStand(i + cardVal + 11, j));
else expRet2 += p * Math.max(expRetStand(i + cardVal + 1, j),
expRetHitHard(i + cardVal + 1, j));
}
double currExpRet = Math.max(expRet1, expRet2);
expRetHitSoftMemo[i - 1][j - 1] = currExpRet;
}
}

// finally, get the rest of the expected returns for hard totals.
for (int i = 10; i > 3; i--) {
double p = 1 / 13.0;
for (int j = 1; j < 11; j++) {
int ind1 = i - 4;
int ind2 = j - 1;
double currExpRet = 0;
for (int k = 1; k < 14; k++) {
int cardVal = (k > 9) ? 10 : k;
int cardVal2 = (k == 1) ? cardVal + 10 : cardVal;
double expRet1 = p * expRetStand(i + cardVal2, j);
double expRet2 = 0;
if (k == 1) expRet2 = p * expRetHitSoft(i, j);
else expRet2 = p * expRetHitHard(i + cardVal, j);
currExpRet += Math.max(expRet1, expRet2);
}
expRetHitHardMemo[ind1][ind2] = currExpRet;
}
}
}

public static double expRetStand(int playerTot, int dealerShows) {
// this method uses memoization. so if the value has already been calculated, it is
// quickly returned; else, the value is calculated and then returned.
if (dealerShows > 10 || dealerShows < 1 || playerTot > 31 || playerTot < 2) {
System.out.println("Error: illegal input, id 1.");
System.exit(1);
}
if (playerTot > 21) return -1;
int ind1 = (playerTot < 17) ? 0 : playerTot - 16;
int ind2 = dealerShows - 1;
if (!doubEquals(expRetStandMemo[ind1][ind2], -50)) return expRetStandMemo[ind1][ind2];
currExpRetGlob = 0;
int dealerAces = (dealerShows == 1) ? 1 : 0;
int dealerTot = (dealerShows == 1) ? 11 : dealerShows;
return expRetStandMemo[ind1][ind2] = currExpRetGlob;
}

public static void recurse1(double p, int playerTot, int dealerTot, int dealerAces, boolean first) {
// helper method for expRetStand()
// assume playerTot <= 21
// assume player and dealer do not have blackjack
if (dealerAces == 0) {
// dealer bust
currExpRetGlob += p;
return;
}
dealerAces--;
}

// no need to check dealerAces; stand on soft 17
if (dealerTot > playerTot) currExpRetGlob -= p;
if (dealerTot < playerTot) currExpRetGlob += p;
return;
}

// iterate through all possible cards
double nextP = p / 13.0;
boolean initAce = first && dealerTot == 11;
boolean initTen = first && dealerTot == 10;
if (initAce) nextP = 1 / 9.0;
if (initTen) nextP = 1 / 12.0;
for (int i = 1; i < 14; i++) {
if (!(initAce && i > 9) && !(initTen && i == 1)) {
int nextDealerAces = dealerAces;
if (i == 1) {
nextDealerAces++;
}
else if (i > 9) nextDealerTot += 10;
}
}
}