modeling-practice

Modeling Practice: UNO in C# Part 3 - Final Steps and Playing The Game

Note: This post is the third in a three-part series which attempts to model the card game UNO as a C# application. Here's Part One and Part Two. You may want to use the GitHub repository to follow along.

In the previous parts of this series we first saw how to play UNO and how to model the cards and moved on to how to model the player behavior. In this post, the last part of the series, we're going to take the results from the first two parts and combine them together to make a fully-working UNO-playing robot.

Well, UNO-playing C# application anyway. What? I can dream.

The Game Manager

The most critical component that we haven't yet built is a class called GameManager. In a real UNO game, the players themselves are responsible for keeping track of everybody else following the rules. However, in our model, we'll need a non-player class to do this, as well as control the game flow and keep track of which player's turn is next.

Here's the skeleton of the GameManager class. The next step will be to establish what each of these methods actually do.

public class GameManager  
{
    public List<Player> Players { get; set; }
    public CardDeck DrawPile { get; set; }
    public List<Card> DiscardPile { get; set; }

    public GameManager(int numPlayers) { }
    public void PlayGame() { }
    private void AddToDiscardPile(PlayerTurn currentTurn) { }
}

Creating the Game

The first method is just the GameManager class's constructor, which we will use to set up the game being played. The only input to this method is an int numPlayers, which is the number of players that will be playing the game.

Given the number of players, the GameManager must set up the game, which consists of:

  1. Creating the deck of cards.
  2. Dealing seven cards to each player.
  3. Placing a single card from the draw pile into the discard pile.

Here's how our constructor does this:

public GameManager(int numPlayers)  
{
    Players = new List<Player>();
    DrawPile = new CardDeck();
    DrawPile.Shuffle();

    //Create the players
    for (int i = 1; i <= numPlayers; i++)
    {
        Players.Add(new Player()
        {
            Position = i
        });
    }

    int maxCards = 7 * Players.Count;
    int dealtCards = 0;

    //Deal 7 cards to each player
    while(dealtCards < maxCards)
    {
        for(int i = 0; i < numPlayers; i ++)
        {
            Players[i].Hand.Add(DrawPile.Cards.First());
            DrawPile.Cards.RemoveAt(0);
            dealtCards++;
        }
    }

    //Add a single card to the discard pile
    DiscardPile = new List<Card>();
    DiscardPile.Add(DrawPile.Cards.First());
    DrawPile.Cards.RemoveAt(0);

    //Game rules do not allow the first discard to be a wild.
    while(DiscardPile.First().Value == CardValue.Wild || DiscardPile.First().Value == CardValue.DrawFour)
    {
        DiscardPile.Insert(0, DrawPile.Cards.First());
        DrawPile.Cards.RemoveAt(0);
    }

    //And now we're ready to play!
}

With all that setup out of the way, we can finally let GameManager start an actual game!

Playing the Game

GameManager kicks off the game by telling Player 1 to take his turn. Play must then proceed (to Player 2, then Player 3, so on) until somebody plays a Reverse card. At that point, we need GameManager to note that a Reverse card was played and reverse the turn order.

GameManager also needs to stop the game when a player no longer has any cards in his/her hand.

We can implement the actual playing of the game using the PlayGame() and AddToDiscardPile() methods like so:

public void PlayGame()  
{
    int i = 0;
    bool isAscending = true;

    //First, let's show what each player starts with
    foreach (var player in Players)
    {
        player.ShowHand();
    }

    //Game won't start until user presses Enter
    Console.ReadLine();

    //We need a "mock" PlayerTurn representing the first discard
    PlayerTurn currentTurn = new PlayerTurn()
    {
        Result = TurnResult.GameStart,
        Card = DiscardPile.First(),
        DeclaredColor = DiscardPile.First().Color
    };

    Console.WriteLine("First card is a " + currentTurn.Card.DisplayValue + ".");

    //Game continues until somebody has no cards in their hand
    while(!Players.Any(x => !x.Hand.Any()))
    {
        //If the draw pile is getting low, shuffle the discard pile into the draw pile
        if(DrawPile.Cards.Count < 4)
        {
            var currentCard = DiscardPile.First();

            //Take the discarded cards, shuffle them, and make them the new draw pile.
            DrawPile.Cards = DiscardPile.Skip(1).ToList();
            DrawPile.Shuffle();

            //Reset the discard pile to only have the current card.
            DiscardPile = new List<Card>();
            DiscardPile.Add(currentCard);

            Console.WriteLine("Shuffling cards!");
        }

        //Now the current player can take their turn
        var currentPlayer = Players[i];
        currentTurn = Players[i].PlayTurn(currentTurn, DrawPile);

        //We must add the current player's discarded card to the discard pile.
        AddToDiscardPile(currentTurn);

        //When somebody plays a reverse card, we need to reverse the turn order
        if (currentTurn.Result == TurnResult.Reversed)
        {
            isAscending = !isAscending;
        }

        //Now we figure out who has the next turn.
        if (isAscending)
        {
            i++;
            if (i >= Players.Count) //Reset player counter
            {
                i = 0;
            }
        }
        else
        {
            i--;
            if (i < 0)
            {
                i = Players.Count - 1;
            }
        }        
    }

    //Let's see who won the game!
    var winningPlayer = Players.Where(x => !x.Hand.Any()).First();
    Console.WriteLine("Player " + winningPlayer.Position.ToString() + " wins!!");

    //Finally, calculate and display each player's score
    foreach(var player in Players)
    {
        Console.WriteLine("Player " + player.Position.ToString() + " has " + player.Hand.Sum(x => x.Score).ToString() + " points in his hand.");
    }
}

private void AddToDiscardPile(PlayerTurn currentTurn)  
{
    if (currentTurn.Result == TurnResult.PlayedCard
            || currentTurn.Result == TurnResult.DrawTwo
            || currentTurn.Result == TurnResult.Skip
            || currentTurn.Result == TurnResult.WildCard
            || currentTurn.Result == TurnResult.WildDrawFour
            || currentTurn.Result == TurnResult.Reversed)
    {
        DiscardPile.Insert(0, currentTurn.Card);
    }
}

Whew! We are finally done with our code. All that's left to do now is to run a sample game!

Running a Sample Game

With all the code in place, let's run the app a few times to make sure it works the way we think it does.

The first time we boot the app (there's a complete working version over on GitHub), we'll see something like this:

Well well, looks like Player 3 has a pretty good hand, what with all the wilds. But, let's run the app to see how everyone does.

And, sure enough, Player 3 ends up winning the game. Those wilds help.

Drawbacks of This Model

As I've said many times throughout this series, the point of those posts is not to model UNO precisely, the point is to take a complex real-world problem and break it down into smaller, more manageable little problems.

That said, I can identify a few ways in which, given unlimited time, I might improve this model:

  • Different player "personalities": Not every player is going to be a stupid jackass. I'd like to model different kinds of player strategy (e.g. offensive vs. defensive, hold wilds vs play them, etc.).
  • A GUI: I mean, I know the hardcore programmers among us LOVE them some command line, but really this could use a GUI to make it pop.
  • Rules modification: Different UNO sets use different kinds of rules, and I love to find a way to model lots of different rules and have the players react to them.

That said, I'm pretty darn happy with how this turned out.

Summary

The point of modeling practice is to practice. Sounds obvious, I know, but I firmly believe that the difficulty in creating complex software programs is not writing the code, but in getting the correct requirements. Modeling practice helps us consider all possibilities, and when we do it against a known game like UNO (or Candy Land or Minesweeper) we have a distinct set of rules to work against, something we often lack in real-world projects.

As always, feel free to leave any comments you may have (good or bad) in the comments section below, and check out the GitHub repository and maybe even run the app a few times. I'm quite proud of how it turned out.

Happy Coding!

Modeling Practice: UNO in C# Part 2 - Player Behavior

Note: This post is the second in a three-part series which attempts to model the card game UNO as a C# application. Here's Part One. You may want to use the GitHub repository to follow along.

Now that we have modeled the cards and the draw pile, we come to the first really tricky part of this modeling practice: we must model the players of the game AND how they will behave during the game itself.

The first part (modeling the players themselves) is simpler, and so we will do it first. A "player" in this game is really just a set of cards (the "hand"), the position that the player is sitting in (first, second, third, etc.) and the logic the player uses to decide which card to play. The simplest possible player class would then look like this:

public class Player  
{
    public List<Card> Hand { get; set; }

    //This determines the starting turn order
    public int Position { get; set; } 

    public Player()
    {
        Hand = new List<Card>();
    }
}

The problem with this simple class is that it leaves out the logic the player must use to determine which card s/he wants to play. That logic is not simple, and in my model it takes quite a few steps to work out.

Assumptions

First, we need to make some critical assumptions. There is no mathematical way to have a "perfect" game of UNO, so our players will often need to decide which card to play of two or they could play.

First, we must remember a few rules from earlier:

  • A player playing a card must match the current discard by either color or value, or play a regular Wild card.
  • A player following a Wild card must match the color declared by the person who laid that card down.
  • A player cannot use a Wild Draw Four card if another card in his/her hand can be played.

Those rules leave a lot of possible situations up to interpretation. For example, if the current discard is a Green Five and I have a Green Skip and a Yellow 5, which should I play?

I've made this model a bit simpler by assuming that my players are stupid jackasses.

That is, every time a player has to make a decision about which card to play, s/he will always play the card that causes the most pain to the next player, regardless of his/her own strategic situation. If I can play a Skip or a 7, I'm playing the Skip (and Lord help you if I have a Draw Two).

Also, if a player has no matches, they must draw a card. If that card can play, then the player will play it; otherwise, his/her turn is over and play moved to the next player.

The PlayerTurn Object

UNO is also a bit different than other games we've modeled (Candy Land, Minesweeper) because the actions of a player have a direct consequence on the next player. We will need our players to take that into account, and they must abide by whatever the "attacking" card says they do.

Therefore, in order for the player to know what action s/he must take, we need the player to be aware of what happened on the previous player's turn. To model the actions taken by a player, we will use the PlayerTurn object, which looks like this:

public class PlayerTurn  
{
    public Card Card { get; set; }
    public CardColor DeclaredColor { get; set; } //Used mainly for Wild cards
    public TurnResult Result { get; set; }
}

The TurnResult enum has all the possible situations which arise from a player completing his/her turn. Those values are as follows:

public enum TurnResult  
{
    //Start of game.
    GameStart,

    //Player played a normal number card.
    PlayedCard,

    //Player played a skip card.
    Skip,

    //Player played a draw two card.
    DrawTwo,

    //Player was forced to draw by other player's card.
    Attacked,

    //Player was forced to draw because s/he couldn't match the current discard.
    ForceDraw,

    //Player was forced to draw because s/he couldn't match the current discard, but the drawn card was playable.
    ForceDrawPlay,

    //Player played a regular wild card.
    WildCard,

    //Player played a draw-four wild card.
    WildDrawFour,

    //Player played a reverse card.
    Reversed
}

Each player takes a turn, and the action performed during that turn are represented by the PlayerTurn object. When the next player takes his/her turn, s/he will also receive the PlayerTurn object for the previous player's turn.

Player Order of Operations

With all the assumptions and the PlayerTurn object in place, let's lay out a skeleton for how our stupid jackass players will behave. Here's how each player will act during his/her turn.

  1. If the previous player "attacked" the current player (via a Skip, a Draw Two, or a Draw Four), then the current player must suffer the attack.
  2. If the current player can play an "attacking" card (within the rules), then s/he does so.
  3. If the current player can play a number card, then s/he does so.
  4. If the current player has no matching cards except a Wild card, s/he plays the Wild. The current player will then declare the color to be the one s/he has the most cards of (the declared color is random if the current player has the same number of card in two or more colors).
  5. If the current player has no cards to play, s/he draws a single card from the draw pile. If the drawn card can be played, s/he plays that card.

NOTE: In either step 2 or step 3, if the player has many possible cards to play, s/he will play the one which results in the color s/he has the most of.

All of those steps are pretty straightforward, but let me explain the reasoning behind Step 4. If we have only one card left, and that card is a Wild card, we are guaranteed to discard our final card on our next turn. Therefore, it behooves the players to hold on to Wild cards until the last possible moment.

Now comes the tricky part; how in the world do we model this?

Being Attacked

Let's start with Step 1 in our Player Order of Operations:

Step 1: If the previous player "attacked" the current player (via a Skip, a Draw Two, or a Draw Four), then the current player must suffer the attack.

The interesting thing about being "attacked" is that being attacked always results in the current player not being able to discard a card. This is why a Reverse card is not an attacking card.

So, let's create a method called ProcessAttack(), during which we will create a PlayerTurn object representing what action the current player took during his/her turn (when s/he suffered the attack).

private PlayerTurn ProcessAttack(Card currentDiscard, CardDeck drawPile)  
{
    PlayerTurn turn = new PlayerTurn();
    turn.Result = TurnResult.Attacked;

    //The player after the current player must match the card that attacked the current player; hence we pass those values through to the next PlayerTurn.
    turn.Card = currentDiscard; 
    turn.DeclaredColor = currentDiscard.Color;

    if(currentDiscard.Value == CardValue.Skip)
    {
        Console.WriteLine("Player " + Position.ToString() + " was skipped!");
    }
    else if(currentDiscard.Value == CardValue.DrawTwo)
    {
        Console.WriteLine("Player " + Position.ToString() + " must draw two cards!");
        Hand.AddRange(drawPile.Draw(2));
    }
    else if(currentDiscard.Value == CardValue.DrawFour)
    {
        Console.WriteLine("Player " + Position.ToString() + " must draw four cards!");
        Hand.AddRange(drawPile.Draw(4));
    }

    return turn;
}

On the Offensive

If the current player is not attacked, s/he will attempt to play an attacking card that matches the color or value of the current discard. Let's create several methods which will make the player decide which card to play.

public PlayerTurn PlayTurn(PlayerTurn previousTurn, CardDeck drawPile) { }

private PlayerTurn DrawCard(PlayerTurn previousTurn, CardDeck drawPile) { }

private bool HasMatch(Card card) { }

private bool HasMatch(CardColor color) { }

private PlayerTurn PlayMatchingCard(CardColor color) { }

private PlayerTurn PlayMatchingCard(Card currentDiscard) { }

private CardColor SelectDominantColor() { }  

Notice the overloads for HasMatch() and PlayMatchingCard(). One of the quirks of this model is that, whenever a player plays a Wild card, s/he declares a color to be played; the next discard can only be matched on color, not value. For my model, I decided to make matching color or value vs matching color only two completely separate "thought processes" as it were.

We'll start with a skeleton of the PlayTurn() method, since it will need to call the ProcessAttack() method we defined earlier. Here's an outline of this method:

public PlayerTurn PlayTurn(PlayerTurn previousTurn, CardDeck drawPile)  
{
    PlayerTurn turn = new PlayerTurn();

    //If the current player was attacked
    if (previousTurn.Result == TurnResult.Skip
        || previousTurn.Result == TurnResult.DrawTwo
        || previousTurn.Result == TurnResult.WildDrawFour)
    {
        return ProcessAttack(previousTurn.Card, drawPile);
    }

    //When the current discard is a Wild card
    else if ((previousTurn.Result == TurnResult.WildCard 
                || previousTurn.Result == TurnResult.Attacked 
                || previousTurn.Result == TurnResult.ForceDraw) 
                && previousTurn.Card.Color == CardColor.Wild
                && HasMatch(previousTurn.DeclaredColor))
    {
        turn = PlayMatchingCard(previousTurn.DeclaredColor);
    }

    //When the current discard is a non-wild card
    else if (HasMatch(previousTurn.Card))
    {
        turn = PlayMatchingCard(previousTurn.Card);
    }

    //When the player has no matching cards
    else //Draw a card and see if it can play
    {
        turn = DrawCard(previousTurn, drawPile);
    }

    DisplayTurn(turn);
    return turn;
}

Let's remind ourselves of Player Logic Steps 2, 3, and 4, as well as the pertinent note:

Step 2: If the player can play an "attacking" card (within the rules), then s/he does so.

Step 3: If the player can play a number card, then s/he does so.

Step 4: If the player has no matching cards except a Wild card, s/he plays the Wild. The player will then declare the color to be the one s/he has the most cards of (the color is random if the player has the same number of card in two or more colors).

NOTE: In either step 2 or step 3, if the player has many possible cards to play, s/he will play the one which results in the color s/he has the most of.

With these steps in mind, let's start building the PlayMatchingCard() methods.

Matching a Wild

If the card we need to match is a Wild, we will need to use the property DeclaredColor in the PlayerTurn object. We must play a card of that color.

Here's the code for the Wild card version of PlayMatchingCard() (the logic involved in the method is in the comments):

private PlayerTurn PlayMatchingCard(CardColor color)  
{
    var turn = new PlayerTurn();
    turn.Result = TurnResult.PlayedCard;
    var matching = Hand.Where(x => x.Color == color || x.Color == CardColor.Wild).ToList();

    //We cannot play wild draw four unless there are no other matches.  But if we can play it, we must.
    if (matching.All(x => x.Value == CardValue.DrawFour))
    {
        turn.Card = matching.First();
        turn.DeclaredColor = SelectDominantColor();
        turn.Result = TurnResult.WildCard;
        Hand.Remove(matching.First());

        return turn;
    }

    //Otherwise, we play the card that would cause the most damage to the next player.
    if (matching.Any(x => x.Value == CardValue.DrawTwo))
    {
        turn.Card = matching.First(x => x.Value == CardValue.DrawTwo);
        turn.Result = TurnResult.DrawTwo;
        turn.DeclaredColor = turn.Card.Color;
        Hand.Remove(turn.Card);

        return turn;
    }

    if (matching.Any(x => x.Value == CardValue.Skip))
    {
        turn.Card = matching.First(x => x.Value == CardValue.Skip);
        turn.Result = TurnResult.Skip;
        turn.DeclaredColor = turn.Card.Color;
        Hand.Remove(turn.Card);

        return turn;
    }

    if (matching.Any(x => x.Value == CardValue.Reverse))
    {
        turn.Card = matching.First(x => x.Value == CardValue.Reverse);
        turn.Result = TurnResult.Reversed;
        turn.DeclaredColor = turn.Card.Color;
        Hand.Remove(turn.Card);

        return turn;
    }

    //If we cannot play an "attacking" card, we play any number card
    var matchOnColor = matching.Where(x => x.Color == color);
    if (matchOnColor.Any())
    {
        turn.Card = matchOnColor.First();
        turn.DeclaredColor = turn.Card.Color;
        Hand.Remove(matchOnColor.First());

        return turn;
    }

    //We only play a regular Wild card if we have no other matches
    if (matching.Any(x => x.Value == CardValue.Wild))
    {
        turn.Card = matching.First(x => x.Value == CardValue.Wild);
        turn.DeclaredColor = SelectDominantColor();
        turn.Result = TurnResult.WildCard;
        Hand.Remove(turn.Card);

        return turn;
    }

    //This should never happen
    turn.Result = TurnResult.ForceDraw;
    return turn;
}

Matching a Non-Wild

Now we must consider the situation when the current discard is not a wild card. In my model, the code for this method is very, very similar to the Wild situation, but I couldn't figure out an appropriate way to separate them sanely. Anyway, here's the non-wild version of PlayMatchingCard():

private PlayerTurn PlayMatchingCard(Card currentDiscard)  
{
    var turn = new PlayerTurn();
    turn.Result = TurnResult.PlayedCard;
    var matching = Hand.Where(x => x.Color == currentDiscard.Color || x.Value == currentDiscard.Value || x.Color == CardColor.Wild).ToList();

    //We cannot play wild draw four unless there are no other matches.
    if(matching.All(x => x.Value == CardValue.DrawFour))
    {
        turn.Card = matching.First();
        turn.DeclaredColor = SelectDominantColor();
        turn.Result = TurnResult.WildCard;
        Hand.Remove(matching.First());

        return turn;
    }

    //Otherwise, we play the card that would cause the most damage to the next player.
    if(matching.Any(x=> x.Value == CardValue.DrawTwo))
    {
        turn.Card = matching.First(x => x.Value == CardValue.DrawTwo);
        turn.Result = TurnResult.DrawTwo;
        turn.DeclaredColor = turn.Card.Color;
        Hand.Remove(turn.Card);

        return turn;
    }

    if(matching.Any(x => x.Value == CardValue.Skip))
    {
        turn.Card = matching.First(x => x.Value == CardValue.Skip);
        turn.Result = TurnResult.Skip;
        turn.DeclaredColor = turn.Card.Color;
        Hand.Remove(turn.Card);

        return turn;
    }

    if (matching.Any(x => x.Value == CardValue.Reverse))
    {
        turn.Card = matching.First(x => x.Value == CardValue.Reverse);
        turn.Result = TurnResult.Reversed;
        turn.DeclaredColor = turn.Card.Color;
        Hand.Remove(turn.Card);

        return turn;
    }

    // At this point the player has a choice of sorts
    // Assuming he has a match on color AND a match on value 
    // (with none of the matches being attacking cards), 
    // he can choose which to play.  For this modeling practice, we'll assume 
    // that playing the match with MORE possible matches from his hand 
    // is the better option.

    var matchOnColor = matching.Where(x => x.Color == currentDiscard.Color);
    var matchOnValue = matching.Where(x => x.Value == currentDiscard.Value);
    if(matchOnColor.Any() && matchOnValue.Any())
    {
        var correspondingColor = Hand.Where(x => x.Color == matchOnColor.First().Color);
        var correspondingValue = Hand.Where(x => x.Value == matchOnValue.First().Value);
        if(correspondingColor.Count() >= correspondingValue.Count())
        {
            turn.Card = matchOnColor.First();
            turn.DeclaredColor = turn.Card.Color;
            Hand.Remove(matchOnColor.First());

            return turn;
        }
        else //Match on value
        {
            turn.Card = matchOnValue.First();
            turn.DeclaredColor = turn.Card.Color;
            Hand.Remove(matchOnValue.First());

            return turn;
        }
    }
    else if(matchOnColor.Any()) //Play the match on color
    {
        turn.Card = matchOnColor.First();
        turn.DeclaredColor = turn.Card.Color;
        Hand.Remove(matchOnColor.First());

        return turn;
    }
    else if(matchOnValue.Any()) //Play the match on value
    {
        turn.Card = matchOnValue.First();
        turn.DeclaredColor = turn.Card.Color;
        Hand.Remove(matchOnValue.First());

        return turn;
    }

    //Play regular wilds last.  If a wild becomes our last card, we win on the next turn!
    if (matching.Any(x => x.Value == CardValue.Wild))
    {
        turn.Card = matching.First(x => x.Value == CardValue.Wild);
        turn.DeclaredColor = SelectDominantColor();
        turn.Result = TurnResult.WildCard;
        Hand.Remove(turn.Card);

        return turn;
    }

    //This should never happen
    turn.Result = TurnResult.ForceDraw;
    return turn;
}

Selecting the Dominant Color

In both the Wild and non-Wild versions of this method, we see a call to SelectDominantColor(), which returns the color that appears most often in the current players' hand. Here's that method:

private CardColor SelectDominantColor()  
{
    if (!Hand.Any())
    {
        return CardColor.Wild; //Null case, causes a passthrough in the calling method
    }
    var colors = Hand.GroupBy(x => x.Color).OrderByDescending(x => x.Count());
    return colors.First().First().Color;
}

Drawing a Card

We've now completed implementation Player Logic Steps 2, 3, and 4, so let's move on to Step 5:

Step 5: If the player has no cards to play, s/he draws a single card from the draw pile. If the drawn card can be played, s/he plays that card.

We now need to implement the DrawCard() method defined earlier. This method turns out to be surprisingly simple now that PlayMatchingCard() is already implemented. Here it is:

private PlayerTurn DrawCard(PlayerTurn previousTurn, CardDeck drawPile)  
{
    PlayerTurn turn = new PlayerTurn();
    var drawnCard = drawPile.Draw(1);
    Hand.AddRange(drawnCard);

    if (HasMatch(previousTurn.Card))  //If the drawn card matches the discard, play it
    {
        turn = PlayMatchingCard(previousTurn.Card);
        turn.Result = TurnResult.ForceDrawPlay;
    }
    else
    {
        turn.Result = TurnResult.ForceDraw;
        turn.Card = previousTurn.Card;
    }

    return turn;
}

And with that, there's only one thing left to do: implement the decision tree!

Putting It All Together

Now that the individual player actions are all scripted, the only thing we have left to do is implement a method which will be called by the Game Manager (which we will implement fully in Part 3 of this series) and will make the Player decide what action to take. The method is called PlayTurn() and here it is:

public PlayerTurn PlayTurn(PlayerTurn previousTurn, CardDeck drawPile)  
{
    PlayerTurn turn = new PlayerTurn();
    if (previousTurn.Result == TurnResult.Skip
        || previousTurn.Result == TurnResult.DrawTwo
        || previousTurn.Result == TurnResult.WildDrawFour)
    {
        return ProcessAttack(previousTurn.Card, drawPile);
    }
    else if ((previousTurn.Result == TurnResult.WildCard 
                || previousTurn.Result == TurnResult.Attacked 
                || previousTurn.Result == TurnResult.ForceDraw) 
                && previousTurn.Card.Color == CardColor.Wild
                && HasMatch(previousTurn.DeclaredColor))
    {
        turn = PlayMatchingCard(previousTurn.DeclaredColor);
    }
    else if (HasMatch(previousTurn.Card))
    {
        turn = PlayMatchingCard(previousTurn.Card);
    }
    else //Draw a card and see if it can play
    {
        turn = DrawCard(previousTurn, drawPile);
    }

    DisplayTurn(turn);
    return turn;
}

Summary

Well, would you look at that! We've now completed our Players' behavior (stupid jackasses that they are), and all that's left to do is wire the entire thing together and play some UNO! In the final part of this series, we'll do just that.

Don't forget to check out the GitHub repository for this series.

Happy Coding!

Modeling Practice: UNO in C# Part 1 - Rules, Assumptions, Cards

Note: This post is the first in a three-part series based around modeling the card game UNO in a C# application. You may want to use the GitHub repository to follow along.

I often find that one of the hardest things to do in software development is take a large complex problem and break it down into smaller, more easy problems. As with nearly anything, the only way to get better at this is to practice, so today I'm introducing a new series that aims at providing a practice for both and my readers on how to take real-world problems and model them in C# applications. I'm calling them Modeling Practice.

I've written two groups of posts prior to this one that can be also be considered modeling practice. The first one was a series based around the board game Candy Land, and the second was my longest post ever which detailed how to solve many games of Minesweeper. But for this series of posts, I've decided to take on my hardest challenge yet.

In this series, we're going to model the Mattel card game UNO.

A set of sample UNO cards and the game box

I have very fond memories of this game; my family played it quite a bit when I was younger, and now playing a hand of it is one of my son's favorite things to do. However, this game is considerably more complex than either Candy Land (in which, after the cards are dealt, the winner has already been determined) or Minesweeper (which can be solved mathematically, in many cases). The problem here is that when playing UNO there is some strategy involved; part of designing this model will be making proper and careful assumptions about how these

Let's see if we can take this large problem (how can we play UNO in a C# application?) and break it down into smaller components, then actually build those components to produce a working application. (Hint: we absolutely can, and the repository for it is over on GitHub).

Assumptions and Goals

In this series, we will model the playing of a single UNO round, from the dealing of cards, to the play of the round, to the players shouting "Uno!", to assigning a score to each player at the end of the hand. What we're trying to do here is practice taking a real-world scenario and breaking it down into manageable pieces so that we can solve for those pieces individually, rather than trying to tackle the entire problem at the same time.

We will have to make some assumptions: for example, our players will never forget to yell "Uno!". But our goal is not to model every single possibility; our goal is to make some sacrifices to the demands of the real world and model a working solution to the problem at hand. We will phrase the problm like this:

How would you model a round of UNO being played?

To do that, we must first make sure we understand the rules of the game.

How To Play UNO

For those of you who might not be familiar with the game UNO, let's describe how we play a round. Those of you who do know how to play can skip to the next section.

Basic Rules

Uno! is a card game in which players attempt to remove all cards from their hands by discarding them. Each player starts the round with 7 random cards in their hand.

During a player's turn, s/he attempts to discard a card by matching it to the last-discarded card, either by playing a card with the same color, the same face value, or by playing a wild card.

When a player has one card remaining in their hand, they must shout "Uno!" If they fail to do so, and another player notices and calls them out on it, the player must draw two cards (or one, rules vary).

The Deck

The card deck in Uno is comprised of 108 cards: 25 of each color (red, green, blue, yellow) and 8 wild cards. The color cards each have a corresponding value of 0-9 or an "action" card. Action cards can do the following:

  • Skip (🚫): Skips the next player's turn.
  • Reverse (⇆): Reverses the turn order.
  • Draw Two (+2): Forces the next player to draw two cards and miss their turn.

The wild cards also come in two flavors:

  • Wild: Allows the player to declare which color the next card should be.
  • Wild Draw Four (+4): Allows the player to declare which color the next card should be AND forces the next player to draw four cards and miss their turn. This card can only be played if no other card in the player's hand can be played.

Here's a sample deck of UNO cards:

A sample deck of UNO cards, with all colors and values shown

Scoring

In a real UNO game, players are assigned a score depending on how many cards are left in their hand and the values of those cards. The cards are worth the following points:

  • 0-9: What number is shown.
  • Draw Two, Reverse, Skip: 20 points.
  • Wild, Wild Draw Four: 50 points.

The original Mattel rules state that as players reach a 500 point threshold, those players are eliminated and play continues with the remaining players. The version my family played, however, had the entire game stop when a person reached 500 points, and the person with the lowest number of points would win.

Official Rules

The official rules are a pain to find on Mattel's site, so here's a link directly to the version we'll be using. Please note that different versions of UNO occasionally use different rules as well.

Breaking Down The Problem

Now that we know the rules of the game, we can start to break our big problem down into little ones.

Let's think about this: if we wanted to play UNO in real life but had never actually played it before, what would we need? I see five different things we would need:

  • Cards: We need the physical cards to play the game.
  • Game Setup: How do we shuffle and deal the cards at the beginning of the game?
  • Players: How many players will play the game? Since we're not playing with real people, how will our fake players behave during the game?
  • Game End: How will we know when the game is over?
  • Scoring: How do we know who won?

We'll model each of these independently, starting with the cards. The game setup and the players will be modeled in Part 2 of this series, and the game end scenarios and scoring will be modeled in Part 3.

First Step: Modelling the Cards

Obviously we cannot play a game of UNO without the cards, so let's tackle the medium-sized problem of modelling the cards themselves.

Here's a sample UNO card:

A green zero card

Each card has three properties:

  1. A color
  2. A value
  3. A score

For our sample card, it's pretty clear that the color is Green, the value is 0, and the score is 0. For each of the numbered cards, the value equals the score, but for the action and wild cards, the score and value are different.

Let's model the possible colors and values using enumerations:

public enum CardColor  
{
    Red,
    Blue,
    Yellow,
    Green,
    Wild
}

public enum CardValue  
{
    Zero,
    One,
    Two,
    Three,
    Four,
    Five,
    Six,
    Seven,
    Eight,
    Nine,
    Reverse,
    Skip,
    DrawTwo,
    DrawFour,
    Wild
}

With the range of possible colors and values defined, we can build a simple class to represent a single card:

public class Card  
{
    public CardColor Color { get; set; }
    public CardValue Value { get; set; }
    public int Score { get; set; }
}

With that, we have modeled the cards themselves. Now we can begin modeling how to set up a hand of UNO.

Setting Up The Game

Here's a (totally not staged) shot of an UNO game which has been set up for four players:

(Yes, we play on the floor. It's easier for little hands to reach the draw pile than sitting at the table would be.)

There are four hands of seven cards each, one for each player, as well as a draw pile and a discard pile. Let' use my l33t paint skillz to show which is which.

In a real game, it's up the players to enforce the rules and make sure everyone plays by them. But in our model, we'll need an object to do that, and we will call this object the GameManager.

public class GameManager  
{
    public List<Player> Players { get; set; }
    public CardDeck DrawPile { get; set; }
    public List<Card> DiscardPile { get; set; }
}

We will define what the Player class is during the Strategy section, so for now let's focus on the properties DiscardPile and DrawPile.

DiscardPile is just a List<Card>, and really only exists so that we a) know what card was last discarded and b) can reshuffle the discard pile into the draw pile when the draw pile runs out of cards.

DrawPile is the more interesting property. In my model, it is a class CardDeck, which looks something like this:

public class CardDeck  
{
    public List<Card> Cards { get; set; }

    public CardDeck() { ... }
    public void Shuffle() { ... }
    public List<Card> Draw(int count) { ... }
}

Let's take each of the three methods in this class and define what we need them to do.

Creating the Cards

When the CardDeck is created, we need it to populate itself with enough cards to represent a proper UNO deck. To do this, we use the constructor to create enough cards.

Here's the full constructor, with annotated comments.

public CardDeck()  
{
    Cards = new List<Card>();

    //For every color we have defined
    foreach (CardColor color in Enum.GetValues(typeof(CardColor)))
    {
        if (color != CardColor.Wild) //Wild cards don't have a color
        {
            foreach (CardValue val in Enum.GetValues(typeof(CardValue)))
            {
                switch (val)
                {
                    case CardValue.One:
                    case CardValue.Two:
                    case CardValue.Three:
                    case CardValue.Four:
                    case CardValue.Five:
                    case CardValue.Six:
                    case CardValue.Seven:
                    case CardValue.Eight:
                    case CardValue.Nine:
                        //Add two copies of each color card 1-9
                        Cards.Add(new Card()
                        {
                            Color = color,
                            Value = val,
                            Score = (int)val
                        });
                        Cards.Add(new Card()
                        {
                            Color = color,
                            Value = val,
                            Score = (int)val
                        });
                        break;
                    case CardValue.Skip:
                    case CardValue.Reverse:
                    case CardValue.DrawTwo:
                        //Add two copies per color of Skip, Reverse, and Draw Two
                        Cards.Add(new Card()
                        {
                            Color = color,
                            Value = val,
                            Score = 20
                        });
                        Cards.Add(new Card()
                        {
                            Color = color,
                            Value = val,
                            Score = 20
                        });
                        break;

                    case CardValue.Zero:
                        //Add one copy per color for 0
                        Cards.Add(new Card()
                        {
                            Color = color,
                            Value = val,
                            Score = 0
                        });
                        break;
                }
            }
        }
        else //Handle wild cards here
        {
            //Add four regular wild cards
            for (int i = 1; i <= 4; i++)
            {
                Cards.Add(new Card()
                {
                    Color = color,
                    Value = CardValue.Wild,
                    Score = 50
                });
            }
            //Add four Draw Four Wild cards
            for (int i = 1; i <= 4; i++)
            {
                Cards.Add(new Card()
                {
                    Color = color,
                    Value = CardValue.DrawFour,
                    Score = 50
                });
            }
        }
    }
}

That method is pretty straightforward, and results in us having a complete deck of UNO cards. But, something's missing. Obviously we wouldn't want to play the game without shuffling the cards first, so let's implement that Shuffle() method:

public void Shuffle()  
{
    Random r = new Random();

    List<Card> cards = Cards;

    for (int n = cards.Count - 1; n > 0; --n)
    {
        int k = r.Next(n + 1);
        Card temp = cards[n];
        cards[n] = cards[k];
        cards[k] = temp;
    }
}

(Note that this method implements the Knuth-Fisher-Yates shuffle I've written about before)

Finally, we need a Draw() method, which returns a certain number of cards from the top of the deck. Given that our collection of cards is a List<>, we can use LINQ's Take() statement to give us the cards.

public List<Card> Draw(int count)  
{
    var drawnCards = Cards.Take(count).ToList();

    //Remove the drawn cards from the draw pile
    Cards.RemoveAll(x => drawnCards.Contains(x));

    return drawnCards;
}

Ta-da! We've completed our CardDeck class, which means that we can move on to the next step: players!

Summary

In this post, we learned how to play UNO, saw my mad paint skillz put to good use, and modeled some cards. In the next post of this series, we will tackle the most complex part of this model: how the players behave.

Don't forget to check out the GitHub repository for this series!

Happy Coding!

Solving Minesweeper with C# and LINQ

Anybody who's spent any time at a Windows machine in the last 26 years has probably played a few games of Minesweeper:

A screenshot of an active Minesweeper game

I mostly work in the ASP.NET space, and I'd been wondering for a few weeks how feasible it was to build a program that could solve Minesweeper automatically, similar to what I did for the board game Candy Land a few months ago. You can see where this is going: I wrote a Minesweeper solver program using C# and LINQ queries, and it runs (if I do say so myself) pretty darn well.

Being the motor mouth that I am, I can't possibly keep this to myself. We're going to build this solver together in this post. Let's build a Minesweeper solver with C# and LINQ!

NOTE: All code examples in this post have been edited for brevity, not completeness. If you want the full, working code, check out the repository on GitHub.

What Is Minesweeper?

Minesweeper is a popular single-person computer game which pits the player against a board full of panels. These panels can be clicked on to reveal what is underneath them. Some of these panels have mines on them, and the player loses the game if s/he reveals a mine. Any panel which does not have a mine on it instead has a number which tells the player how many of the adjacent panels (including diagonals) have mines on them. If the player clicks on a panel with 0 adjacent mines, the game reveals all the adjacent panels until a revealed panel has a number in it. The player may also "flag" panels so as to mark them as containing a mine.

From all this information, the player attempts to reveal the entire board EXCEPT those panels that have mines on them. Here's a completed board:

A completed game of Minesweeper, showing all mines flagged

As you might imagine, the game gets more difficult the more densely the mines are laid out, which does not necessarily correspond to how large the board is. A huge board with only a few mines would be easy to solve, but a small board with a lot of mines is considerably more difficult.

Constructing the Game

Now that we understand the rules of the game, let's introduce some code to represent the game itself.

Panels

The smallest unit in the game are the squares that can be clicked on. I've taken to calling these "panels". In our C# project we have a class called Panel, which keeps track of its own coordinates on the board, what it contains, and its current state:

public class Panel  
{
    public int ID { get; set; }
    public int X { get; set; }
    public int Y { get; set; }
    public bool IsMine { get; set; }
    public int AdjacentMines { get; set; }
    public bool IsRevealed { get; set; }
    public bool IsFlagged { get; set; }

    public Panel(int id, int x, int y)
    {
        ...
    }
}

There are three possible states for a panel:

  • Hidden
  • Flagged
  • Revealed

The panel may contain either a mine or a count of the number of adjacent mines. X and Y represent the panel's horizontal and vertical coordinates within the board, respectively.

Once we have the Panel class, we can now build a class to represent the next game unit: the GameBoard.

GameBoard

The board need to keep track of a collection of panels. It must also track what the current status of the game is (e.g. whether the game is in progess, complete, or failed). Our GameBoard class looks like this:

public class GameBoard  
{
    public int Width { get; set; }
    public int Height { get; set; }
    public int MineCount { get; set; }
    public List<Panel> Panels { get; set; }
    public GameStatus Status { get; set; }
    public GameBoard(int width, int height, int mines)
    {
        Width = width;
        Height = height;
        MineCount = mines;
        Panels = new List<Panel>();

        int id = 1;
        for(int i = 1; i <= height; i++)
        {
            for (int j = 1; j <= width; j++)
            {
                Panels.Add(new Panel(id, j, i));
                id++;
            }
        }

        Status = GameStatus.InProgress; //Let's start the game!
    }
}

public enum GameStatus  
{
    InProgress,
    Failed,
    Completed
}

We want to be able to create a GameBoard of any size, with any number of mines. The constructor of the GameBoard object creates a List<Panel> which represents all the panels on the board.

Now, wait a minute you might think, shouldn't the GameBoard also determine where the mines are placed? It turns out that doing so causes quite a bit of player frustration, so let's see if we can alleviate their pain by dynamically generating the mine placement after they select their first move.

The User's First Move

The most annoying thing about playing Minesweeper is when this happens:

A screenshot of Minesweeper, showing that the user's second click revealed a mine.

It is entirely possible to lose the game in the first couple of moves, where the only valid strategy is to pick a panel at random. If the mines are placed randomly when the board is first created, then the user may accidentally reveal a mine on their first move. I wanted to eliminate this annoyance, and so this system doesn't actually place the mines on the board until after the user submits his first move.

In order to guarantee that the user's first move doesn't reveal a mine, and that s/he doesn't have to continue clicking randomly after the first move, I wanted an algorithm in which:

  • The player's first move does not reveal a mine AND
  • The player's first move reveals more than one panel.

In order to fit those rules within the game logic, the user's first move must always be to reveal a panel with 0 adjacent mines. There's a method in the GameBoard class called FirstMove() which implements this algorithm:

public void FirstMove(int x, int y, Random rand)  
{
    //For any board, take the user's first revealed panel + any neighbors of that panel to X depth, and mark them as unavailable for mine placement.
    var depth = 0.125 * Width; //12.5% (1/8th) of the board width becomes the depth of unavailable panels
    var neighbors = GetNeighbors(x, y, (int)depth); //Get all neighbors to specified depth
    neighbors.Add(GetPanel(x, y)); //Don't place a mine in the user's first move!

    //Select random panels from set of panels which are not excluded by the first-move rule
    var mineList = Panels.Except(neighbors).OrderBy(user => rand.Next()); 
    var mineSlots = mineList.Take(MineCount).ToList().Select(z => new { z.X, z.Y });

    //Place the mines
    foreach (var mineCoord in mineSlots)
    {
        Panels.Single(panel => panel.X == mineCoord.X && panel.Y == mineCoord.Y).IsMine = true;
    }

    //For every panel which is not a mine, determine and save the adjacent mines.
    foreach (var openPanel in Panels.Where(panel => !panel.IsMine))
    {
        var nearbyPanels = GetNeighbors(openPanel.X, openPanel.Y);
        openPanel.AdjacentMines = nearbyPanels.Count(z => z.IsMine);
    }
}

This ensures that the first move will never reveal a mine, and will always reveal more than one panel. Consequently, the user is much more likely to engage with the game rather than just quitting out of frustration.

Finding the Neighbor Panels

One of the core functionalities that need to be provided by the GameBoard is that of finding the neighbor panels for a panel at specified coordinates. For example, take a look at this game:

A screenshot of a game board, with a particular panel and its neighbors highlighted

The neighbors of that 3 panel are in all eight directions around the panel. So, we need a function which can find and return the neighbors of any given panel. Said function looks like this:

public List<Panel> GetNeighbors(int x, int y)  
{
    return GetNeighbors(x, y, 1);
}

public List<Panel> GetNeighbors(int x, int y, int depth)  
{
    var nearbyPanels = Panels.Where(panel => panel.X >= (x - depth) && panel.X <= (x + depth)
                                            && panel.Y >= (y - depth) && panel.Y <= (y + depth));
    var currentPanel = Panels.Where(panel => panel.X == x && panel.Y == y);
    return nearbyPanels.Except(currentPanel).ToList();
}

Why do we have the depth overload? Remember that the FirstMove() function requires us to mark a certain "depth" of panels from the user's first move as unavailable for mine placement.

Revealing a Panel

Now that we've got the code that creates the game board, we can start writing the code that allows the user to actually play that game. To start off, let's write a function in our GameBoard class which reveals a panel at a specified coordinate. Said function shall adhere to this methodology:

  1. Locate the specified panel and mark it as revealed.
  2. If the specified panel is a mine, end the game.
  3. If the specified panel has zero adjacent mines, reveal its neighbors in a cascade until numbered panels are revealed.
  4. Finally, check if the board is completed.
public void RevealPanel(int x, int y)  
{
    //Step 1: Find the Specified Panel
    var selectedPanel = Panels.First(panel => panel.X == x && panel.Y == y);
    selectedPanel.IsRevealed = true;
    selectedPanel.IsFlagged = false; //Revealed panels cannot be flagged

    //Step 2: If the panel is a mine, game over!
    if (selectedPanel.IsMine) Status = GameStatus.Failed;

    //Step 3: If the panel is a zero, cascade reveal neighbors
    if (!selectedPanel.IsMine && selectedPanel.AdjacentMines == 0)
    {
        RevealZeros(x, y);
    }

    //Step 4: If this move caused the game to be complete, mark it as such
    if (!selectedPanel.IsMine)
    {
        CompletionCheck();
    }
}

We also need to implement the methods RevealZeros() and CompletionCheck() called in Steps 3 and 4 respectively.

Reveal Zeros

When a user clicks on a panel with no adjacent mines, we need to cascade through all of the adjoining panels and reveal every neighbor panel until the panels have a non-zero number in them. We can accomplish this using recursion:

public void RevealZeros(int x, int y)  
{
    var neighborPanels = GetNearbyPanels(x, y).Where(panel => !panel.IsRevealed);
    foreach (var neighbor in neighborPanels)
    {
        neighbor.IsRevealed = true;
        if (neighbor.AdjacentMines == 0)
        {
            RevealZeros(neighbor.X, neighbor.Y);
        }
    }
}

Completion Check

After revealing a panel, if that panel happened to be the last hidden panel which does not contain a mine, the game is complete. We can write this method using LINQ to exclude the mined panels from the hidden panels; if the two collections contain the same items, the game is complete. Here's our CompletionCheck method:

private void CompletionCheck()  
{
    var hiddenPanels = Panels.Where(x => !x.IsRevealed).Select(x => x.ID);
    var minePanels = Panels.Where(x => x.IsMine).Select(x => x.ID);
    if (!hiddenPanels.Except(minePanels).Any())
    {
        Status = GameStatus.Completed;
    }
}

Flagging a Panel

The final piece of functionality we need to implement is flagging a panel. The user may flag any hidden panel, but the existence of a flag doesn't guarantee that that panel has a mine. Here's the method:

public void FlagPanel(int x, int y)  
{
    var panel = Panels.Where(z => z.X == x && z.Y == y).First();
    if(!panel.IsRevealed)
    {
        panel.IsFlagged = true;
    }
}

Challenges

There are two major challenges inherent in building a solver for Minesweeper, and they both deal with fundamental issues with the structure of the game itself.

Minesweeper is NP-Complete

We must first come to terms with the fact that no Minesweeper automated-solver will ever be able to solve all possible boards. This is because Minesweeper has been proven to be an NP-Complete problem, meaning that calculating a solution for all possible boards might be possible but would take an exorbitant amount of time.

Guessing Is (Eventually) Required

There are a great number of scenarios in Minesweeper that ultimately force the user to guess; that is, there is no way for the user to be absolutely certain of what panel to reveal next or where to place the next flag. Advanced solvers will use probability calculations to determine the most optimal next move whenever guessing is required; my solution does not do this. I am creating a solver to demonstrate the ideas needed, not to solve as many boards as possible.

With these two challenges in mind, let's list some goals that the solver needs to be able to fulfill.

Solving The Game

We want to build two kinds of solvers: a single-game solver and a multi-game solver. The multi-game solver will be used heavily in the analysis section of this post, and so is detailed there; this section will focus on the single-game variant.

The single-game solver should be able to:

  1. Start a game by randomly picking a panel.
  2. Use the strategies detailed below to reveal obvious panels and flag obvious mines.
  3. Allow the user to specify whether or not s/he wants the solver to use random guesses when a board becomes impossible to solve without guessing.

Game Solver Base Class

Let's start off by creating a class GameSolver, which will have properties and methods common to both the single-game and multi-game solvers.

public class GameSolver  
{
    protected int GetWidth() { ... }
    protected int GetHeight() { ... }
    protected int GetMines() { ... }
    protected void WidthErrors(int width) { ... }
    protected void HeightErrors(int height) { ... }
    protected void MinesErrors(int mines) { ... }
}

The implementation of these methods is trivial; the source code for this file can be found in the GitHub repository.

Now we can start writing our single-game solver class.

Single-Game Solver

Here's the skeleton for the single-game solver; the rest of this post will be about filling in the functionality.

public class SingleGameSolver : GameSolver  
{
    public GameBoard Board { get; set; }
    public Random Random { get; set; }

    public SingleGameSolver(Random rand)
    {
        Random = rand;
        int height = 0, width = 0, mines = 0;
        while (width <= 0)
        {
            width = GetWidth();
            WidthErrors(width);
        }

        while (height <= 0)
        {
            height = GetHeight();
            HeightErrors(height);
        }

        while (mines <= 0)
        {
            mines = GetMines();
            MinesErrors(mines);
        }

        Board = new GameBoard(width, height, mines);
    }

    public SingleGameSolver(GameBoard board, Random rand)
    {
        Board = board;
        Random = rand;
    }
}

Random Number Generation

A big part of creating the Minesweeper board is the use of a random-number generator; in this case, that generator is the Random class. However, Random is not a true random-number generator (rather being psuedo-random), so when I was coding up this project I started noticing that a lot of the boards had the same mine placement, the same first move, etc.

Turns out that Random uses the current clock ticks as a seed, and so by creating a new Random class over and over again in quick succession, I would get the same "random" numbers many times in a row. Consequently, my solution passes a single instance of Random around to where it is needed, and therefore we won't see duplicate boards or duplicate move sets when running many games in a row (as we will do in the Analysis section).

Strategies

When attempting to solve a Minesweeper board, there are many simple strategies the player can use to up the odds of their winning the game. The four strategies below were the easiest to code for and can solve a great number of easy-to-intermediate boards.

Obvious Mines

Look at this game board:

A screenshot of a beginner Minesweeper board, showing three flagged panels.

I know from looking at the board that the three panels with flags on them must be mines. How do I know this? Because for each of those panels, there is an adjacent "1" panel that has no other hidden panels around it.

In general, this strategy is summed up as: "For any number panel, if the number of hidden adjacent panels equals the number in the current panel, all the adjacent hidden panels must be mines."

In our SingleGameSolver class, we write that as the following method:

public void FlagObviousMines()  
{
    var numberPanels = Board.Panels.Where(x => x.IsRevealed && x.AdjacentMines > 0);
    foreach(var panel in numberPanels)
    {
        //For each revealed number panel on the board, get its neighbors.
        var neighborPanels = Board.GetNeighbors(panel.X, panel.Y);

        //If the total number of hidden == the number of mines revealed by this panel...
        if(neighborPanels.Count(x=>!x.IsRevealed) == panel.AdjacentMines)
        {
            //All those hidden panels must be mines, so flag them.
            foreach(var neighbor in neighborPanels.Where(x=>!x.IsRevealed))
            {
                Board.FlagPanel(neighbor.X, neighbor.Y);
            }
        }
    }
}

With the obvious mines flagged, can we determine the inverse? Can we determine, for a single panel, whether or not all the hidden neighbors are not mines? We sure can.

Obvious Number Panels

Here's another sample game in progress:

See the 2 panel whose neighbors I've highlighted? Notice that, due to other panels, we've been able to flag two of that panel's neighbors as having mines. Consequently, any remaining hidden panels must not have mines:

In general, the logic for this strategy goes like this: for any given revealed number panel, if the number of flags adjacent to that panel equals the number in the panel, then all hidden adjacent unflagged panels cannot be mines.

public void ObviousNumbers()  
{
    var numberedPanels = Board.Panels.Where(x => x.IsRevealed && x.AdjacentMines > 0);
    foreach(var numberPanel in numberedPanels)
    {
        //Foreach number panel
        var neighborPanels = Board.GetNeighbors(numberPanel.X, numberPanel.Y);

        //Get all of that panel's flagged neighbors
        var flaggedNeighbors = neighborPanels.Where(x => x.IsFlagged);

        //If the number of flagged neighbors equals the number in the current panel...
        if(flaggedNeighbors.Count() == numberPanel.AdjacentMines)
        {
            //All hidden neighbors must *not* have mines in them, so reveal them.
            foreach(var hiddenPanel in neighborPanels.Where(x=>!x.IsRevealed && !x.IsFlagged))
            {
                Board.RevealPanel(hiddenPanel.X, hiddenPanel.Y);
            }
        }
    }
}

Using just these two strategies, we can solve a lot of simple boards. But there's one other simple strategy I chose to implement: an endgame check for the number of remaining mines.

Endgame Flag Count

Near the end of the game, there's a simple way that we can determine whether or not we've solved the board. Check out this board:

A screenshot of a beginner Minesweeper board, with 10 mines flagged

On a beginner board, there are 10 mines; on this board, we have flagged 10 mines. Therefore all the remaining panels must not have mines:

A screenshot of completed beginner Minesweeper board

The endgame strategy, in short, is that if the number of flagged panels equals the number of mines on the board, all the remaining panels cannot have mines. Therefore we can reveal all of those panels:

public void Endgame()  
{
    //Count all the flagged panels.  If the number of flagged panels == the number of mines on the board, reveal all non-flagged panels.
    var flaggedPanels = Board.Panels.Where(x => x.IsFlagged).Count();
    if(flaggedPanels == Board.MineCount)
    {
        //Reveal all unrevealed, unflagged panels
        var unrevealedPanels = Board.Panels.Where(x => !x.IsFlagged && !x.IsRevealed);
        foreach(var panel in unrevealedPanels)
        {
            Board.RevealPanel(panel.X, panel.Y);
        }
    }
}

These three strategies comprise the portion of the solver that can actually solve the board. However, there's one more "strategy" (and I use the term loosely) that we need to implement.

Random Guessing

It's entirely possible (probable even, especially on harder boards) that at some point we will have to randomly reveal a panel in order to proceed with solving the board. Here's our function to do so:

public void RandomMove()  
{
    var randomID = Random.Next(1, Board.Panels.Count);
    var panel = Board.Panels.First(x => x.ID == randomID);
    while(panel.IsRevealed || panel.IsFlagged)
    {
        //We can only reveal an hidden, unflagged panel
        randomID = Random.Next(1, Board.Panels.Count);
        panel = Board.Panels.First(x => x.ID == randomID);
    }

    Board.RevealPanel(panel.X, panel.Y);
}

With these four strategies in place, there's only one more question we need to answer: how do we know if there are still possible moves we can make without guessing?

Checking For Available Moves

One additional feature of this solver is that it needs to check if there are available moves; if there are no available moves we must guess randomly. The Obvious Mines and Endgame strategies can be run at any time without fear of failing the game (since they only flag panels, they don't reveal them), therefore the only strategy we need to check is the Obvious Number Panels strategy. Here's the function for that:

public bool HasAvailableMoves()  
{
    var numberedPanels = Board.Panels.Where(x => x.IsRevealed && x.AdjacentMines > 0);
    foreach (var numberPanel in numberedPanels)
    {
        //Foreach number panel
        var neighborPanels = Board.GetNeighbors(numberPanel.X, numberPanel.Y);

        //Get all of that panel's flagged neighbors
        var flaggedNeighbors = neighborPanels.Where(x => x.IsFlagged);

        //If the number of flagged neighbors equals the number in the current panel...
        if (flaggedNeighbors.Count() == numberPanel.AdjacentMines)
        {
            return true;
        }
    }
    return false;
}

(Yes, I know this could be optimized, it's a lot of repeated code, etc. It's an example, not production code.)

Order of Operations

Now that we've got the four strategies coded up, let's determine in what order they should fire. Generally speaking, we need to flag mines first before revealing new panels so that the flagged panels are not able to be revealed. Here's the order of operations for the single game solver:

  1. While the game is not solved or failed
  2. If zero panels have been revealed, submit user's first move.
  3. Flag the obvious mines.
  4. Check for available "Obvious Number Panel" moves.
  5. Reveal the obvious number panels.
  6. Check for the endgame mine count situation.
  7. If there are no available moves, randomly reveal a panel.

In other words:

public BoardStats Solve()  
{
    //Step 1
    while (Board.Status == GameStatus.InProgress)
    {
        if (!Board.Panels.Any(x=>x.IsRevealed))
        {
            //Step 2
            FirstMove();
        }
        //Step 3
        FlagObviousMines();

        //Step 4
        if (HasAvailableMoves())
        {
            //Step 5
            ObviousNumbers();
        }
        else //No available moves, we must guess to continue
        {
            //Step 7
            RandomMove();
        }

        //Step 6
        Endgame();
    }

    //Display messages
}

Analysis

Now that we've got the game itself coded up and a single-game solver working, let's combine many game solvers to analyze how well our strategies perform on different kinds of boards. To do this, we must first create the Multi-Game Solver we mentioned earlier.

Multi-Game Solver

Before we can start solving (or at least attempting to solve) lots of Minesweeper games, we must first create a multi-game solver. The multi-game solver needs to know the following properties of the game:

  • The dimensions of the boards
  • How many mines exist on each board
  • How many boards to solve

The MultiGameSolver class in our solution looks like this:

public class MultiGameSolver : GameSolver  
{
    public int BoardWidth { get; set; }
    public int BoardHeight { get; set; }
    public int MinesCount { get; set; }
    public int BoardsCount { get; set; }

    public int GamesCompleted { get; set; }
    public int GamesFailed { get; set; }

    public MultiGameSolver()
    {
        //Get height, width, mines count, number of boards
    }

    public void Run()
    {
        Random rand = new Random();
        List<BoardStats> stats = new List<BoardStats>();
        Console.WriteLine("Solving Games...");
        for(int i = 0; i < BoardsCount; i++)
        {
            GameBoard board = new GameBoard(BoardWidth, BoardHeight, MinesCount);
            SingleGameSolver solver = new SingleGameSolver(board, rand);
            var boardStats = solver.Solve();
            stats.Add(boardStats);

            if(solver.Board.Status == Enums.GameStatus.Completed)
            {
                GamesCompleted++;
            }
            else if(solver.Board.Status == Enums.GameStatus.Failed)
            {
                GamesFailed++;
            }
        }

        Console.WriteLine("Games Completed: " + GamesCompleted.ToString());
        Console.WriteLine("Games Failed: " + GamesFailed.ToString());

        //Calculate and display stats
    }
}

We also have the BoardStats class called out above:

public class BoardStats  
{
    public double TotalPanels { get; set; }
    public double PanelsRevealed { get; set; }
    public double Mines { get; set; }
    public double FlaggedPanels { get; set; }
    public double PercentMinesFlagged { get; set; }
    public double PercentPanelsRevealed { get; set; }
}

With the Multi-Game Solver written, we can now start to get statistics for each board type, beginning with the Beginner boards.

Beginner Boards

First, let's take a look what a beginner board looks like. Here's a sample beginner board:

A screenshot of a beginner board in progress; the board is 9 panels tall and 9 panels wide with 10 hidden mines

The dimensions of a beginner board are 9 panels by 9 panels, with 10 randomly-placed mines. This gives us a board density of 12.3%. These kinds of boards should be relatively easy to solve.

We're going to run five groups of 100 boards each, and analyze the number of boards solved and failed, as well as the number of mines flagged and panels revealed. Here's the data for these runs:

Run # Games Solved Games Failed % Mines Flagged % Panels Revealed
1 83 17 90.1% 95.54%
2 85 15 90.4% 95.68%
3 82 18 90.8% 95.64%
4 80 20 90.3% 95.27%
5 77 23 87.4% 93.7%

On average, we're solving about 80%-82% of the boards, with 88%-89% of the mines correctly flagged and 95% of the panels revealed. That's pretty darn good if I do say so myself.

Let's ramp up the difficulty a bit and see how well the solver holds up.

Intermediate Boards

In Minesweeper, intermediate boards look like this:

A screenshot of an intermediate game in progress, showing 16 panels wide by 16 panels tall, with 40 mines hidden.

This time the board is 16x16 with 40 mines, given a board density of 15.6%. Let's run the same set of tests (5 runs of 100 boards each) and see how well the solver does this time.

Run # Games Solved Games Failed % Mines Flagged % Panels Revealed
1 49 51 86.82% 90.93%
2 41 59 83.75% 89.63%
3 45 55 83.58% 89.3%
4 39 61 82.88% 89.12%
5 44 56 84.4% 89.27%

This is where the results get interesting. We didn't solve more than half the intermediate boards on any run, so by that metric the solver's not doing so hot. But we still flagged approx 84% of the mines and revealed approx 89% of the panels, so we're getting a lot done before we fail the boards. What this tells me is that once the solver solves a large percentage of the board, it has to start guessing, and that's where it begins to fail.

Let's see if the this is born out by the expert level boards.

Expert Boards

Once again, here's an expert board for reference.

This time the board is 30 panels wide and 16 panels tall with a whopping 99 mines! That gives us a board density of 20.6%, the highest we've seen so far (after all, this is expert mode). With the high density, we should expect that we'll solve even less games than we did on the intermediate boards. Here's the data:

Run # Games Solved Games Failed % Mines Flagged % Panels Revealed
1 0 100 47.49% 58.59%
2 2 98 45.89% 56.57%
3 0 100 45.56% 56.17%
4 0 100 44.18% 54.86%
5 0 100 45.36% 55.29%

Well. I don't think the results could be any clearer than that. We solved 2 games out of a possible 500, so yeah, the solver's not going to get very far on these expert boards.

On the other hand, it did flag about 45% of the mines and revealed 56% of the number panels, so the solver's still making progress. It's just that with the much higher mine density, eventually the solver's going to have to make a guess, and eventually it's going to guess wrong. At this point, the simple strategies we've implemented for this solver won't help us very much except to get us started.

Summary

Our solver uses four strategies to solve Minesweeper boards:

  • Check for obvious mines
  • Check for obvious number panels
  • Check for "endgame" all mines flagged situation
  • If none of the above are available, randomly guess a panel

This solver, while not able to solve all boards, can complete a large percentage of them. It turns out that the solver does pretty darn well at the beginner boards and fairly well on the intermediate boards, but fails miserably once we get to the expert level. To be fair, that's kinda what we expected; we're not using any terribly advanced methodology here, just simple Minesweeper strategy. The fact that said strategies solve any number of the boards is amazing, frankly.

Don't forget to check out the repository for this project!

Let me know what you thought of this post: was it too deep, too shallow, too much, too little? I'd love to hear any feedback you have in the comments!

Happy Coding!