May 23, 2018 SRM 734: The Hacking CardCounter Problem

Single Round Marathon (SRM) 734 had a simplified card counting problem, CardCounter. Though solving the problem will not win the programmer Hollywood-level fame and fortune, the solution proves to be a good mental exercise and is a bit difficult to come by.
Blackjack is the daring card game where the winner scores as close to twenty-one points as possible. If a player does not “bust” or have a total higher than twenty-one and has a total higher than the dealer, the player wins. Card counting allows the player to take the element of luck out of the game by figuring out the chances that a particular card is played next in the sequence. For the following problem, two cards are dealt. One of the dealer’s cards will have a known value and the other will have an allocated value that is unknown to the problem solver.
The player can choose to take a “hit” and be dealt another card. He can keep going until he reaches a total number of points greater than or equal to twenty-one or decides to “stand” with the total held. The dealer will then reveal his card and take the hit if his total is below seventeen. Once he reaches, seventeen, he stands. If the player has a total higher than the dealer and has not gone over twenty-one, he wins. If the dealer has a total higher than the player or the player goes bust, he wins.
For this problem, the deck will have 10 elements, and each element will be valued between 0 and 4 inclusive. The deal will have a value between 1 and 10. The player will be an array with two elements where each element will be between 1 and 10 inclusive. The cards that remain in the deck will be no more than sixteen, and the total value of all the cards showing and remaining in the deck is at least fifty-six. The problem statement determines that the deck is passed as an array of integers, the dealer is passed as an integer, and the player’s cards are passed an array of integers. The probability of the player winning the hand is returned. Now that the rules have been stated, let us look at solving the problem.
The first thing to do to solve the problem is determine when the dealer and the player go bust. The dealer will go bust at a lower value than the player, and making sure that this is accounted for in the code is important. The preliminary pseudocode for the problem is as follows:

	deck = argv[0]
  dealer_probability, player_probability
  for card in deck:
    dealer_score = argv[1]
    player_score = sum(argv[2])
              dealer_score += card
              player_score += card
  if dealer_score > 17:
    player_probability += 1
  if player_score > 21:
    dealer_probability += 1
  else:
			continue
	return player_probability/(dealer_probability+player_probability)

This preliminary approach will not pass the test cases. For example, if the player or dealer decides to hold instead of incrementing their score, the program will not take this into account. The algorithm needs to be further fine-tuned. One way to do this is by checking how close the player and dealer are to their ideal score. For example, if the player has a score of twenty and the deck has cards that have a value of two or higher, the player should stand in order to increase the chances of the ]player winning. If the player has a score of nineteen and the deck has a 70% chance of returning a card that is two and a 0% chance that the dealer can advantageously increase the dealer’s point value with a hit, the player should take the hit.
In order to take account of this programmatically, one can add states to take into account how close a person is to winning, multiply it with the dealer’s chance of winning while in that state, and return the overall probability for all the states. The pseudocode that handles these states is written as such:

  for card in deck:
  if dealer_score + card <= 17:
     dealer_score += card
  else:
    continue
  for card in deck:
     if player_score + card <= 21:
     player_score += card
  else:
    continue
      if dealer_score > player_score:
        dealer_probability += 1
      elif player_score > dealer_score:
        player_probability += 1
      else:
        continue
    return player_probability/(dealer_probability+player_probability)

This takes into account whether or not the person playing will stand or will continue to increment their score.  All the possibilities for the cards are considered. Now that the pseudocode has been written, the reader can go ahead and tackle the problem.  The solution will be handled in O(n²) time.