Sunday, April 28, 2019

Code Kata: the card game of war

The card game of war is a very old, but still popular game. I used to play it when I was a child. The game is very suitable for small kids, because it has simple rules and the players don't need to make any decisions - it's enough to follow the rules. In this article, we will try to go through the process of modeling the game of war as a computer program. And as we will see later, the modeling may have some very practical uses. Let's start.

The game is usually played with 24 cards of four colors. The cards are as follows, next to each card there is a single letter that will represent the card for us.
  • Ace - A
  • King - K
  • Queen - Q
  • Jack - J
  • 10 - T
  • 9 - N
The colors do not matter in the basic version of the game. The 24 cards are distributed randomly between two players. Each player starts with 12 cards. The player who loses all the cards loses the game. Main steps of the game will be executed by the function:

nextMove (cardsA, cardsB)

The game then can be started by invoking: nextMove ("AKQJTNAKQJTN", "QQKKTTNNAJAJ")

nextMove needs to recognize when the game ends:

nextMove (cardsA, cardsB):
  if cardsA == null:
    print "Player A won."
    return
  else if cardsB == null:
    print "Player B won."
    return
  else:
    firstA, cardsA = split (cardsA)
    firstB, cardsB = split (cardsB)
    outcome = resolve (firstA, firstB)
    if outcome == "A":
      nextMove (cardsA.append (firtsA).append (firstB), cardsB)
    else:
      nextMove (cardsA, cardsB.append (firtsB).append (firstA))

If the game continues (both players have cards) we are in the else block above. The resolve function takes first cards from both players and determines the outcome. The stronger card wins and the player with the stronger card takes both cards and puts them at the bottom of the deck. The split function is a helper function that simply returns the first card and the rest.

This logic is enough to handle game scenarios where the cards do not repeat. If we distribute 6 cards of the same color between the two players, there will always be a winning card. When we allow the possibility of repeated cards with different colors, we need to introduce the war function.

...
    if outcome == "A":
      nextMove (cardsA.append (firtsA).append (firstB), cardsB)
    else if outcome == "B":
      nextMove (cardsA, cardsB.append (firtsB).append (firstA))
    else:
      war (cardsA, cardsB, firstA + firstB)

The war function will be a bit complicated, because it needs to take a few scenarios into account, such as:
  • either of the players having not enough cards to continue the game
  • a tie - nobody wins
  • the war ends with the same cards and this triggers next war
The complete set of functions is provided below. OK, so the computer can play play the game of war instead of two real players, great. Does it have any practical use? There are actually some practical uses of this kind of game modeling:
  • by executing the game many times with random card distribution, we can determine the average and median number of moves needed to complete the game.
  • from the number of moves, we can derive the expected time length of the game.
  • for games that do require players to make decisions, we can employ different decision algorithms and examine how they influence game results.
  • for newly developed games we can tune the rules to achieve reasonable game times, game fairness, etc
  • we can determine the conditions which position a player to win with, for example, 90% chance.
Similar modeling can be done on other games like the Monopoly series and other. The simulation allows for tu tuning the game so that it is not too short, no too long, it is not obvious early in the game who will win, etc.
def split(s):
    return s[0], s[1:]


ranks = {"A":6, "K":5, "Q":4, "J":3, "T":2, "N":1}

def resolve(cardA, cardB):
    if ranks[cardA] > ranks [cardB]:
        return "A"
    elif ranks[cardA] < ranks[cardB]:
        return "B"
    else:
        return "WAR"


def nextMove(cardsA, cardsB):
    print("A: " + cardsA)
    print("B: " + cardsB)
    if cardsA == "":
        print("Player B won.")
        return
    if cardsB == "":
        print("Player A won.")
        return
    else:
        firstA, cardsA = split(cardsA)
        firstB, cardsB = split(cardsB)
        outcome = resolve(firstA, firstB)
        if outcome == "A":
            nextMove(cardsA + firstA + firstB, cardsB)
        elif outcome == "B":
            nextMove(cardsA, cardsB + firstB + firstA)
        else:
            war(cardsA, cardsB, firstA + firstB)


 def war(cardsA, cardsB, stake):
    if len(cardsA) == 0 and len(cardsB) == 0:
        print("Tie.")
        return
    elif len(cardsA) == 0:
        nextMove(cardsA, cardsB + stake)
    elif len(cardsB) == 0:
        nextMove(cardsA + stake, cardsB)
    elif len(cardsA) == 1 and len(cardsB) == 1:
        print("Tie.")
        return
    elif len(cardsA) == 1:
        secondA, cardsA = split(cardsA)
        secondB, cardsB = split(cardsB)
        stake = stake + secondA + secondB
        nextMove(cardsA, cardsB + stake)
    elif len(cardsB) == 1:
        secondA, cardsA = split(cardsA)
        secondB, cardsB = split(cardsB)
        stake = stake + secondA + secondB
        nextMove(cardsA + stake, cardsB)
    else:
        secondA, cardsA = split(cardsA)
        secondB, cardsB = split(cardsB)
        thirdA, cardsA = split(cardsA)
        thirdB, cardsB = split(cardsB)
        stake = stake + secondA + secondB + thirdA + thirdB
        outcome = resolve(thirdA, thirdB)
        if outcome == "A":
            nextMove(cardsA + stake, cardsB)
        elif outcome == "B":
            nextMove(cardsA, cardsB + stake)
        else:
            war(cardsA, cardsB, stake)

See also