Example: Blackjack

Finding a Blackjack Strategy Using Evolutionary.Net

Problem Conditions

Please see the Wikipedia Blackjack article for details about the game itself.

For this solution there is no splitting, no surrender, and the dealer stands on soft 17.

How it Works

The dealer has 10 possible upcards: 2, 3, 4, 5, 6, 7, 8, 9, 10, and Ace. Notice that Jack, Queen or King are not listed here, since they all count as 10. For each upcard, a genetic program is generated to determine a strategy for that upcard. The problem state data holds information about the player's hand, and various terminal functions look at this data and return a boolean value.

Due to the principle of closure, all nodes must be the same type, which in this case is bool. Since the result of such an expression tree is too limited to help us determine a Blackjack strategy, in this case stateful functions increment a vote element in the problem state data if the parameter passed to that function is true. This allows combinations of boolean conditions, with the final solution being the one that got the most votes - stand, hit, or double down.

Problem State Data

The problem state data will hold information about which cards the player holds, and contains counters for the possible votes for a decision:

class ProblemState
{
  // Before evaluating a candidate, we load the state data with the current hand
  public Hand PlayerHand{ get; set; }

  // Each candidate expression tree will have stateful functions that indicate a strategy (stand, hit, etc.)  
  // Since a given candidate could potentially have several of these in the tree, each time such a function 
  // is executed, it's considered a vote for a strategy.  When the tree is completely evaluated, we examine the votes
  // to determine the final strategy to use
  public int VotesForHit { get; set; }
  public int VotesForStand { get; set; }
  public int VotesForDoubleDown { get; set; }
}

Primitive Set

The primitive set doesn't include any constants or variables. Instead, terminal functions are used to examine the players cards:

  // terminal functions to look at game state
  // first, player holding ace?
  engine.AddTerminalFunction(HasAce, "HasAce");
  
  // player hand totals
  engine.AddTerminalFunction(HandVal4, "Has4");
  engine.AddTerminalFunction(HandVal5, "Has5");
  engine.AddTerminalFunction(HandVal6, "Has6");
  engine.AddTerminalFunction(HandVal7, "Has7");
  engine.AddTerminalFunction(HandVal8, "Has8");
  engine.AddTerminalFunction(HandVal9, "Has9");
  engine.AddTerminalFunction(HandVal10, "Has10");
  engine.AddTerminalFunction(HandVal11, "Has11");
  engine.AddTerminalFunction(HandVal12, "Has12");
  engine.AddTerminalFunction(HandVal13, "Has13");
  engine.AddTerminalFunction(HandVal14, "Has14");
  engine.AddTerminalFunction(HandVal15, "Has15");
  engine.AddTerminalFunction(HandVal16, "Has16");
  engine.AddTerminalFunction(HandVal17, "Has17");
  engine.AddTerminalFunction(HandVal18, "Has18");
  engine.AddTerminalFunction(HandVal19, "Has19");
  engine.AddTerminalFunction(HandVal20, "Has20");
  
  // num cards held
  engine.AddTerminalFunction(Holding2Cards, "Hold2");
  engine.AddTerminalFunction(Holding3Cards, "Hold3");

Here's an example what one of those terminal functions looks like:

  private  bool HandVal11(ProblemState stateData)
  {
    return stateData.PlayerHand.HandValue() == 11;
  }

Since our expression tree is of type bool, all terminal functions return a bool.

Next, since we have a bool expression tree, let's provide some standard boolean operators:

  // for a boolean tree, we use the standard operators, and then some
  engine.AddFunction((a, b) => a || b, "Or");
  engine.AddFunction((a, b, c) => a || b || c, "Or3");
  engine.AddFunction((a, b) => a && b, "And");
  engine.AddFunction((a, b, c) => a && b && c, "And3");
  engine.AddFunction((a) => !a, "Not");

Finally, we need some stateful functions to record votes for various strategies:

  engine.AddStatefulFunction(HitIf, "HitIf");
  engine.AddStatefulFunction(StandIf, "StandIf");
  engine.AddStatefulFunction(DoubleIf, "DoubleIf");

Here's how those stateful functions are implemented:

private  bool HitIf(bool value, ProblemState state)
{
  // pass through the value, but register the vote
  if (value) state.VotesForHit++;
  return value;
}

private  bool StandIf(bool value, ProblemState state)
{
  // pass through the value, but register the vote
  if (value) state.VotesForStand++;
  return value;
}

private  bool DoubleIf(bool value, ProblemState state)
{
  // pass through the value, but register the vote
  if (value) state.VotesForDoubleDown++;
  return value;
}

These stateful functions take a single parameter, and if it's value is true, then a vote is logged. After processing via a call to .FindBestSolution(), the final result is used to populate the result grid shown in the screenshot at the bottom of this webpage.

Fitness Evaluation

Our fitness function plays 1000 random hands of Blackjack, following the strategy specified by the candidate. It's quite lengthy, so here's a snippet of it:

private float EvaluateCandidate(CandidateSolution<bool, ProblemState> candidate)
{
  int playerChips = 0;

  for (int handNum = 0; handNum < TestConditions.NumHandsToPlay; handNum++)
  {
    // for each hand, we generate a random deck.  Blackjack is often played with multiple decks to improve the house edge
    MultiDeck deck = new MultiDeck(TestConditions.NumDecks);
    Hand dealerHand = new Hand();
    Hand playerHand = new Hand();
    playerHand.AddCard(deck.DealCard());
    playerHand.AddCard(deck.DealCard());

    // always use the designated dealer upcard (of hearts)
    dealerHand.AddCard(new Card(dealerUpcardRank, "H"));    
    dealerHand.AddCard(deck.DealCard());

    // not all code for this function is shown here, but this is how we have the candidate solution
    // decide what to do:
    candidate.StateData.VotesForDoubleDown = 0;
    candidate.StateData.VotesForHit = 0;
    candidate.StateData.VotesForStand = 0;
    candidate.Evaluate();   // throw away the result, because it's meaningless

    // look at the votes to see what to do
    string action = GetAction(candidate.StateData);

    // at this point there is more simulation of the hand, including having the dealer draw
    // this is not shown here for purposes of space - please see the actual example code for all details
    // and then return the final number of chips - obviously the bigger the better
    return playerChips;
}

You may have noticed the function GetAction. It's a utility function that looks at the votes and decides on an action:

public static string GetAction(ProblemState stateData)
{
  int votesForStand = stateData.VotesForStand;
  int votesForHit = stateData.VotesForHit;
  int votesForDouble = stateData.VotesForDoubleDown;

  if ((votesForHit > votesForStand) && (votesForHit > votesForDouble)) return "H";
  if ((votesForDouble > votesForHit) && (votesForDouble > votesForStand)) return "D";
  return "S";
}

Resulting Strategy

In this screenshot, you see the resulting strategy for hard hands (those without an Ace) on the left. Each column of the table indicates a dealer upcard, and the numbers along the left edge show the player's hand total. The colored cells indicate whether the player should stand, hit or double-down.

On the right side, you see the resulting strategy for soft hands (those with an Ace). A-10 is not listed because that would be a Blackjack (the player automatically wins), so no strategy is required. Like the table on the left, the columns indicate the dealer upcards.