PPP Devlog: Week 9

Welcome back! Last week, we designed our heuristic algorithm for our A.I. players, and this week, we turn our attention to implementing it.

This is a very complicated algorithm with a large number of little pieces that can go wrong. Good code organization is always important, but it's especially important here. I recommend creating empty space in your existing code where you want your new code to go, and before you write any new C++, just start by writing comments describing how your code will execute at each step, according to your own thought processes and however it most makes sense to you.

I also strongly recommend judicious use of version control. I'm using Perforce, but you can use SVN, Git, or whatever system you prefer. Just make sure you have a way to commit your code after each small change you make. This way, if something goes wrong, you can test your code at every step of implementation and get more targeted information about where something went wrong. This practice has saved me from headaches many times, and I can't recommend it enough.

Once you've done all of this, you can get started writing your code. Since you've already designed the algorithm, commented it out, and set up version control, all you have to do is express those comments in C++, and commit and test after each step. It's simple.

Once you've got players visibly claiming routes they want, pat yourself on the back and be happy with what you've done. This is no small feat, and it'll be a very impressive piece of work to show off to people.

In this game, notice the Portland/Nashville destination ticket in the lower-right corner of the window. This indicates that player 1, who is placing black trains, is trying to connect the two cities, and lo and behold, it did precisely that! My output log also shows that it has a destination ticket for Denver and Pittsburgh, which it also successfully connected. On top of that, it made a point of claiming valuable 5- and 6-space routes to buff its score, like the one between Helena and Seattle, the one between Toronto and Duluth, and the one between Miami and Atlanta.  Notice, as well, that this competition can become cutthroat very quickly. Poor player 4 finished the game with a paltry 26 points. The output log shows us why: they were tasked with connecting Vancouver and Santa Fe, but they got crowded out of Vancouver by other players; Seattle was taken over by Yellow and Black, while Calgary was taken over by Yellow, Red, and Green. Blue's other destination ticket went from Miami to Los Angeles, and Blue was similarly crowded out of Miami. The railroad business is rough!

In this game, notice the Portland/Nashville destination ticket in the lower-right corner of the window. This indicates that player 1, who is placing black trains, is trying to connect the two cities, and lo and behold, it did precisely that! My output log also shows that it has a destination ticket for Denver and Pittsburgh, which it also successfully connected. On top of that, it made a point of claiming valuable 5- and 6-space routes to buff its score, like the one between Helena and Seattle, the one between Toronto and Duluth, and the one between Miami and Atlanta.

Notice, as well, that this competition can become cutthroat very quickly. Poor player 4 finished the game with a paltry 26 points. The output log shows us why: they were tasked with connecting Vancouver and Santa Fe, but they got crowded out of Vancouver by other players; Seattle was taken over by Yellow and Black, while Calgary was taken over by Yellow, Red, and Green. Blue's other destination ticket went from Miami to Los Angeles, and Blue was similarly crowded out of Miami. The railroad business is rough!

With the rest of this week, I recommend you start thinking about small tweaks you can make to improve your algorithm. For example, in my algorithm, I discovered that players would sometimes unexpectedly have lower scores than normal. This was because they would, at the last turn of the game, draw more destination tickets, even though there was no possible way to complete them with future turns. This should be disallowed. For that matter, drawing more train car cards on the last turn should also be disallowed: why would you draw cards if you know you'll never get a chance to use them? Except in very unusual circumstances, the only thing a player should be doing on their last turn is claiming a route to try and increase their score.

Another flaw is the following: you should not allow players to draw destination tickets if the game is too close to ending. We already established that this definitely shouldn't be done on the last turn, but drawing destination tickets slightly before that is still very risky. You might get stuck with a lengthy path to claim that you might not have time to get. I recommend, for the heuristic of a DrawDestinationTicketsTurn, that you return a minimum heuristic value if any player has fewer than 20 train pieces left.

Happy coding!

PPP Devlog: Week 8

Last week, we got fully functional A.I. players playing Ticket to Ride. This was only a first draft, however: the players did not make their decisions intelligently. Rather, they determined what all legal moves were and made a decision randomly based on a uniform distribution. Now, we will start the exciting task of designing more intelligent A.I. players, ones that make decisions using a combination of our own custom heuristic algorithm and Monte Carlo simulations.

Specifically, our A.I. players will, given a list of all legal moves for a turn, winnow down that list to only the N turns that have the highest heuristic value, where N is some constant value. Then, the players will iterate through this list of legal turns. For each turn in the list, the player will simulate how the game would play out after this turn, which will entail taking the turn, generating a new list of legal turns and winnowing it down to N good turns.

Notice that this forms a tree-like structure, with game states connected to other game states via branches (i.e., turns). In A.I., this is a fundamental data structure we call a decision tree.

An example of a generic decision tree.

An example of a generic decision tree.

The A.I. player will go down the tree in a depth-first fashion, following a simulation until either the game ends or until a specified maximum depth is reached in the tree. Once such a terminal state is reached, the player's score will be propagated up the tree. A node's parent will be informed that, in one of its descendants, a simulation ended, and the parent will incorporate that new score into its average measured score.

Let's look at a simple example to illustrate more clearly how this works. Suppose a player's heuristic algorithm produced N=2 good moves: claiming a route between Miami and Atlanta, or taking a wild card from the collection of face-up train car cards. The player will then simulate each. For the sake of simplicity, let's pretend the maximum depth is 2.

The player will simulate what would happen if it were to claim the route between Miami and Atlanta. Let's suppose that this gives it the normal 10 points for claiming a 5-train route and that this gives it another 15 points for completing a destination ticket, for a new total score of 70 points.

Now, two new best moves are generated by the heuristic in this state that exists after having claimed the route from Miami to Atlanta: draw 2 random train car cards from the deck, or claim a route between Los Angeles and Las Vegas. First, the Los Angeles/Las Vegas turn is simulated, and since this produces a terminal state, as the maximum depth has been reached, the final score is tabulated, which is, let's say, 72. The value 72 is sent up to the parent. It records that it has now seen 1 simulation reach its end, and the average score is 72. Then, the turn in which two random cards are drawn is simulated. This won't change the score, so the simulation ends with a score of 70. This value then gets sent up to the parent, which combines this score of 70 with the score of 72 it saw earlier. It records that its average is now 71, and that there have been two simulations.

Next, the root node will simulate its other child's game, in which the player took one wild card from the face-up train car cards. Let's suppose, then, that the two children of this child node produce a total of 2 simulations and an average of 65 points.

Now, you might think that the player would choose the node with the highest average score, 71. In this example, you would be correct; however, there is one last wrinkle that makes these simulations true Monte Carlo simulations: a player will sometimes need to explore nodes that are rarely simulated. Suppose, for example, that a node has an average score of a very low 25, but it has only run a single simulation. Perhaps this 25 is a fluke; it would be unreasonable to write off this move as terrible, because only one simulation means there is considerable room for sampling error. It would be ill-advised to run no more simulations based on a single unlucky simulation.


Now that we understand how Monte Carlo simulation works, let's discuss the heuristic we'll be using. For this project, I've devised a system wherein each type of turn generates a heuristic value based on the helpfulness of the turn taken.

A Destination Ticket turn, in which a player draws 3 and keeps at least 1 destination ticket, has the simplest heuristic. If a player has completed all the destination tickets it is holding, then the heuristic is the maximum heuristic value; otherwise, the heuristic is the minimum heuristic value.

A Route Claim turn, in which a player claims a route, is more complex. First, one needs to consider that a claimed route will grant the player points in and of itself, with the amount of points depending on the length of the route.

Second, one needs to consider that the real value of claiming routes is that they help players work toward completing their destination tickets. This brings up an important question: is there a way to determine whether a particular route helps a player complete a destination ticket? We need a system in place that will answer this question. I recommend finding a path between cities upon a player drawing a destination ticket, using Dijkstra's algorithm. Then, once this optimal path has been established, it shall only be changed in the event that a route on that path is claimed by another player. this is a simple system, but it meets our needs. Now that we can determine whether a route is in such an optimal path, we can say that our heuristic needs to give a bonus to routes that help complete the associated destination tickets, probably with some extra weight given to routes that help work towards more valuable tickets.

Third, one needs to consider opportunity cost: claiming one route means that you can't instead claim a different route that might help work toward completing a different destination ticket. Given that not completing a destination ticket results in a penalty at the end of the game, this deserves serious consideration. Perhaps, then, we should decrease the heuristic of a turn if a route doesn't help complete a destination ticket.

So, then, it seems we now have a heuristic we can use: it's the number of points a route is worth; plus the value of all destination tickets it helps complete, multiplied by the fraction representing how complete they are; minus the value of all destination tickets it doesn't help complete, multiplied by the fraction representing how complete they are.

Finally, we need to develop a heuristic for turns in which you draw a train car card. This becomes simple once you remember that the only reason to draw train car cards is to be able to use them to claim routes. That being the case, we can co-opt our heuristic for route-claim turns, incorporating the heuristic for hypothetical turns we could take with the cards we draw, possibly with a fractional multiplier to minimize this value, in order to account for the fact that relying on claiming a route in the future is uncertain, as that route could be taken by another player before you can get to it.


Whew! That was a lot of thought, but now we have a great foundation for a heuristic we can implement for our A.I. players and iterate on in the future to make improvements as we observe the success rates of our A.I. players. The vast majority of work done this week relates to devising and implementing this heuristic algorithm.

Once that's done, we should start writing code to store the infrastructure for our decision tree. For this, we will need classes to represent nodes in the tree, obviously, and we will need the ability to add child nodes to a node and the ability to back-propagate information to a node's parent, at the very least.

We can start writing this code, but I'm afraid we won't get to use it until later, as we're out of time for now. We'll pick this up again next week.

Until then, keep coding!

PPP Devlog: Week 7

Readers, I am pleased to announce to you that this is a particularly exciting week for the Ticket to Ride project! I've been promising that we'd soon get A.I.-controlled players making random decisions in Ticket to Ride, and at long last, we have arrived! By the end of this blog post, you should have a fully functional Ticket to Ride self-playing video game in your possession. I'm sure you'll have been very proud.

Starting where we left off last week, the first thing we need to do is to update the ClaimRouteTurn class's Execute method.

As a refresher: this project is using the Action design pattern to encapsulate a Turn as an object, so as to allow our A.I. players to make a decision from an array of choices, which I am storing as a member variable on the AIPlayer object. The generation of this array of choices, then, is done by creating an object for every single possible choice, and then using information from the player to narrow down that array to only the ones that are legal. Finally, a decision is made; this week, our players simply make their decisions by selecting one with a random uniform distribution.

One of Turn's derived classes, ClaimRouteTurn, is, as the name suggests, a turn that involves claiming a route, one of three options in a turn in Ticket to Ride. Last week, this class's Execute method simply placed trains of the player's color on any available route, without regard to the legality of such a move. This time, we need to update it to reflect the rules of the game. For example, a route cannot be claimed if a player does not possess enough train pieces to place one on each space in that route. By the end of this task, you should have code that resembles this:

bool ClaimRouteTurn::IsLegal(const Playerplayerconst
{
	const uint32_t routeLength = m_Route->Length();
	if (m_Route == nullptr || !m_Route->IsAvailable(player.TrainColor()) || player.NumberOfTrainPieces() < routeLength)
	{
		return false;
	}

	const TrainTrackColor routeColor = m_Route->TrackColor();
	bool returnValue = false;

	if (routeColor != TrainTrackColor::GREY)
	{
		returnValue = (routeColor == m_CardColor) &&
			player.TrainCarCards().ContainsCardsOfColor(routeLength, m_CardColor);
	}
	else
	{
		returnValue = player.TrainCarCards().ContainsCardsOfColor(routeLength, m_CardColor);
	}

	return returnValue;
}

void ClaimRouteTurn::Execute(PlayerplayerGameManagermanager)
{
	assert(IsLegal(player));
	manager;

	m_Route->Claim(player.TrainColor());
	const int32_t routeLength = m_Route->Length();
	const int32_t points = GameManager::TrackLengthToPoints.at(routeLength);
	player.AddPoints(points);
	player.RemoveTrainPieces(routeLength);
	player.TrainCarCards().DiscardCardsOfColor(routeLength, m_CardColor, manager.GetTrainCarCardDiscardPile());

}

Next, we will need to create the second derived class of Turn, DrawTrainCarCardsTurn, to represent a turn in which a player draws some Train Car Cards, either from the deck or from the five face-up cards. Its Execute and IsLegal methods should remove the specified cards from the specified locations and put them into the player's hand, and check to see if the player isn't trying to take cards that don't exist or trying to take a face-up Locomotive wild card in addition to another card, respectively.

I recommend creating a nested class to represent a drawing of one Train Car Card, and simply have the DrawTrainCarCardsTurn class be composed of two of these objects. Just make sure the two objects don't clash with each other legally, and you'll be fine. Oh, also, you may need to take a peek at the top card of the deck to predict which card will be drawn next, in order to allow for the possibility that a player may take a face-up card, and then immediately take the newly drawn card that replaced the first one. (As programmers, we are privy to insider information in our projects, and it is our responsibility to ensure we do not use it for ill.)

Moral implications aside, your code should eventually look something like this:

void DrawTrainCarCardsTurn::DrawTrainCarCardTurn::Execute(PlayerplayerGameManagermanager)
{
	if (m_CardColor != TrainTrackColor::INVALID)
	{
		if (m_CardColor == TrainTrackColor::UNKNOWN)
		{
			TrainCarCard card = manager.GetDeckOfTrainCarCards().DrawCard();
			card.SetPubliclyKnown(false);
			player.PutCardInHand(card);
			manager.WriteTextToFile(GameManager::TrainPieceColors.at(player.TrainColor()) +
				" has drawn a "s + GameManager::m_TrackColorToName.at(card.Color()) +
				" Train Car Card from the deck."s);
		}
		else
		{
			TrainCarCard card = manager.RemoveFaceUpCard(m_CardColor);
			card.SetPubliclyKnown(true);
			player.PutCardInHand(card);
			manager.WriteTextToFile(GameManager::TrainPieceColors.at(player.TrainColor()) +
				" has drawn a "s + GameManager::m_TrackColorToName.at(card.Color()) +
				" Train Car Card from the face-up cards."s);
		}
	}
}

bool DrawTrainCarCardsTurn::IsLegal(const Playerplayerconst
{
	const TrainTrackColor turn1Color = m_Turn1.Color();
	const TrainTrackColor turn2Color = m_Turn2.Color();
	const bool twoCardsIfWild = (turn1Color == TrainTrackColor::WILD) && (turn2Color != TrainTrackColor::INVALID);
	const bool firstIsInvalid = (turn1Color == TrainTrackColor::INVALID);
	const bool secondIsInvalidAndFirstIsntWild = (turn2Color == TrainTrackColor::INVALID) && (turn1Color != TrainTrackColor::WILD);
	const bool secondIsWild = (turn2Color == TrainTrackColor::WILD);
	return !twoCardsIfWild && !firstIsInvalid && !secondIsInvalidAndFirstIsntWild && !secondIsWild && m_Turn1.IsLegal(player) && m_Turn2.IsLegal(player);
}

void DrawTrainCarCardsTurn::Execute(PlayerplayerGameManagermanager)
{
	m_Turn1.Execute(playermanager);
	m_Turn2.Execute(playermanager);
}

The final and by far simplest derived class of Turn is DrawDestinationTicketsTurn. For this, all that needs to be done is create variables for the number of destination tickets to draw and the minimum number of tickets that the player must keep. The random A.I. player can then simply elect to take a randomly generated subset of these tickets.

After all this is done, it's time to put it all together! Write your new, more complex TakeTurn method for your A.I. player, incorporating your new classes into it. As always, thorough unit-testing is important. It's especially important here to ensure that all possible turns are accounted for and chosen amongst.

Finally, you can do some overall system testing and debugging. Smoke testing will likely be the first thing you do, just running the game until legal turns may no longer be made. This will help you roust out any remaining program-crashing bugs that unit testing didn't catch.

After you've made sure your program no longer crashes, you should set up the program so that it ends in the same way as the board game: when one player has two or fewer train pieces remaining, then each player gets one final turn before the game ends. This will allow you to do some more testing, to make sure you catch any logic errors that unit testing alone wouldn't catch. In order to ease this process, I recommend writing some output to a file with every turn that is taken to document the choices made by each player. Make sure they're all legitimate!

Congratulations! You now have the workings of an A.I.-controlled version of Ticket to Ride. The end of the game should look similar to this:

In this game, every single player except one actually had a negative score, no doubt as a result of drawing Destination Tickets and then not being smart enough to complete them. Obviously, this will improve when we incorporate Monte Carlo Tree Search and heuristics into this project later.

In this game, every single player except one actually had a negative score, no doubt as a result of drawing Destination Tickets and then not being smart enough to complete them. Obviously, this will improve when we incorporate Monte Carlo Tree Search and heuristics into this project later.

Next week, we'll dive headlong into the Monte Carlo Tree Search family of algorithms and work toward making our A.I. players a little smarter. Stay tuned!

PPP Devlog: Week 6

This week, we finished up the gathering of UI information for the Ticket To Ride window. I recommend spending a bit of time writing a tool that will give you the information you need with just a few clicks of your mouse. That's what I did: I wrote a tool that would display the pixel information of whatever the current point was that the mouse was pointing to. This gave me the x and y coordinates within the display window of the pixel that would contain the upper left corner of the rectangle to be drawn. With a click of the mouse, this tool would then store that information. I could, therefore, click the mouse once in the upper left corner of a space on the board, click the upper right corner of that space, and then the tool would use trigonometry to calculate the angle from a horizontal line that would form this upper border of the rectangle to be drawn.

Once this tool is written, you can start getting the pixel coordinates and angles of all the spaces on the board. Here's a little time-saving tip: if two spaces in the same route appear to be at roughly the same angle, don't bother measuring the angle of each space. Just measure the angle of one, or of the entire route, if all spaces form a neat line. Any discrepancies in measuring these angles individually would just be the result of slightly inaccurate pixel-clicking on your part. If two spaces look like they probably have the same angle of rotation, then you can code as if they do.

Once you've got all the pixel and rotation info and stored it in a hash map or other structure, we can start creating our players! The first step I recommend you take is to just get the turn-taking loop implemented in the game manager's Update method. My implementation, shown below, has the maximum number of players, five, taking turns after a short delay by randomly claiming one of the available routes on the board, which results in a drawing of a rectangle of that player's color on the board.

uint32_t turnStart = SDL_GetTicks();
while (GetMessage(&msg, nullptr, 0, 0))
{
    if (!TranslateAccelerator(msg.hwnd, hAccelTable, &msg))
    {
        TranslateMessage(&msg);
        DispatchMessage(&msg);
    }

    if (SDL_TICKS_PASSED(SDL_GetTicks(), turnStart + 1000))
    {
        manager.Update();
        manager.Draw();
        turnStart = SDL_GetTicks();
    }
}

void GameManager::Update()
{
    // getting actual size of window for scaling purposes
    SDL_GetWindowSize(m_SdlWin.RawWindow(), &winW, &winH);

    m_Players[m_IndexOfNextPlayer]->TakeTurn();
    m_IndexOfNextPlayer = (m_IndexOfNextPlayer + 1) % m_NumberOfPlayers;
}

Once the turn-taking loop is in place, we can write our first implementation in which players make decisions based on the rules of the game, which will start off as fairly simple, but will become more complex with each iteration. Come back next week for a description of that!

PPP Devlog: Week 5

Last week, we drew some of the assets required for Ticket to Ride. This week, we continue drawing assets, including starting the lengthy task of determining the pixel coordinates and rotational angle of each space on the board, so that they may be filled in by colored rectangles to represent train pieces placed by players.

Next up in our list of things to draw is the deck of Train Car Cards and the deck of Destination Tickets. This can most easily be done by writing a Draw method that resides in the Deck<T> class template, with arguments representing pixel coordinates, a reference to a renderer, and a representation of the image to be drawn, which will be either the backside of a Train Car Card or the backside of a Destination Ticket. My Draw method looks like this:

template <typename T>
void Deck<T>::Draw(int32_t x, int32_t y, SDL_Renderer_Safe& renderer, const string& imagePath)
{
    if (!m_Cards.empty())
    {
        SDL_Texture_Safe tex(imagePath, renderer);
        SDL_Rect rect;
        rect.x = x;
        rect.y = y;
        tex.Query(nullptr, nullptr, &rect.w, &rect.h);
        float tempWidth = static_cast<float>(rect.w);
        float tempHeight = static_cast<float>(rect.h);
        tempWidth *= GameManager::FaceUpCardScale;
        tempHeight *= GameManager::FaceUpCardScale;
        rect.w = static_cast<int>(tempWidth);
        rect.h = static_cast<int>(tempHeight);
        renderer.Copy(tex, nullptr, &rect);
    }
}

Note the use of the SDL_Texture_Safe class. This is a wrapper class I created to make SDL_Textures RAII-safe. I encapsulate a call to SDL_DestroyTexture in the destructor of this class and only use SDL_Texture_Safe objects in my code, thus eliminating the possibility of accidentally forgetting to destroy a texture and leaking memory. I highly recommend you do something similar for all SDL structures you use in several places in code, including textures, windows, and renderers.

The next task is to draw an arbitrary hand of Train Car Cards. Last week, I demonstrated that you can show Train Car Cards of different colors at different locations in the game window, and now it's time to add a Draw method to the TrainCarCardHand class. As you may remember, I recommended organizing a hand of Train Car Cards so that cards of the same color were grouped together. Now that we're drawing a hand, the benefits of this become more apparent: when stacking cards of the same color, you can count the number of, say, black cards, contiguously, and as soon as you stop seeing black cards, you can be sure that there aren't any more anywhere else in the hand. This allows you to draw each pile of cards on the screen as you encounter them while walking through the hand.

An important aspect of drawing a player's hand is rendering text, so that you can draw a number on top of a stack of cards to represent multiple cards in a hand of the same color. For this, I recommend using the SDL extension library SDL_ttf. To obtain and use SDL_ttf, I recommend following the instructions found here, which were very helpful for me. I also recommend you Google "common ttf fonts" to get a typeface you can use for your text.

By the end of all this, you should have any possible hand of Train Car Cards drawable, and at the start of the game, it should look something like this:

In this example, a player has been dealt one red card, one orange card, and two white cards at the start of the game.

In this example, a player has been dealt one red card, one orange card, and two white cards at the start of the game.

Notice, as well, that the above image has text along the top of the window providing information about each player: how many points they have, how many trains they have left, and how many Train Car Cards and Destination Tickets they're holding. This is important information to display, and now that you've got text rendering on the screen, printing this data is straightforward. Just play around with the positioning of the text boxes until you're happy with how they look.

Next, we need to draw the player's Destination Tickets. For the moment, I am randomly dealing two tickets to our players, and I am displaying just one of the tickets in the lower right-hand corner of the screen. My plan is to allow users to cycle between the tickets a player has, choosing which one is to be displayed in a given frame. You can of course choose whatever screen-space-saving system you want!

In this image, the player has drawn a Destination Ticket that connects Kansas City and Houston.

In this image, the player has drawn a Destination Ticket that connects Kansas City and Houston.

Finally, we dive into the arduous task of determining where to draw colored rectangles in our window so that each route can be visibly claimed by any player. The system I am currently using is time-consuming, so I shall attempt to find a faster system before next week's devlog, but let's discuss what I'm doing for the time being.

I first obtained .bmp images of solid colors of each of the five player colors: green, blue, red, black, and yellow. Then, I call SDL_RenderCopyEx, which allows for the rotation of textures on the screen (this is how I drew train car cards as both sideways and right-side-up). Next, for each space on the board, draw a rectangle of a fixed height and width at a fixed position with a fixed rotational angle. Repeat using trial and error until you've drawn the rectangle so that it covers a space to your satisfaction, and then store these numbers as constants somewhere in  your code. (I recommend using an unordered_map to map Routes to this information.)

Next week, we'll wrap up this final drawing task of obtaining all the route rendering information and make our first A.I. player!

PPP Devlog: Week 4

With this devlog, we leave the familiar and plunge into the exciting world of exploring a new API, as we wrap up our prep work, which has so far been done purely in C++, and start drawing things on the screen. We'll have to have some kind of visual representation of the actions our A.I. players take, so we'll need to decide on a graphics framework to use in order to draw things like the game board, the cards, and train pieces.

Before that, however, we still have some work to do in creating C++ classes to represent objects in the game. The first thing to do is to write our DiscardPile class. For this class, I'm actually using a class template DiscardPile<T> that can accept any class that derives from Card. Notice as well that, in terms of data, a DiscardPile is no more than a linked list of Card objects. I could just use the raw std::list, but then I would miss out on the opportunity to create my own useful functions and have them be callable directly from the DiscardPile objects. (We are using an object-oriented language, after all; let's take advantage of that!)

template <typename T>
    class DiscardPile final
    {
        static_assert(std::is_base_of<Card, T>::value, "T must derive from Card");

    public:
        /// <summary>
        /// This method moves a card into this DiscardPile.
        /// </summary>
        /// <param name="card">- The card to move into the pile.</param>
        void AddCard(T&& card);

        /// <summary>
        /// This method copies a card into this DiscardPile.
        /// </summary>
        /// <param name="card">- The card to copy into this DiscardPile.
        /// </param>
        void AddCard(const T& card);

        /// <summary>
        /// This method empties this DiscardPile, adds its contents to the
        /// input Deck, and shuffles the Deck.
        /// </summary>
        /// <param name="deck">- The deck into which to shuffle the contents of
        /// this DiscardPile.</param>
        void ShuffleInto(Deck<T>& deck);

    private:
        std::list<T> m_Pile;
    };

We should also create classes that represent the hands players will hold: one for Train Car Cards, and one for Destination Tickets. As is the case with the Discard Pile, these classes can just be wrappers for STL containers. I've once again chosen to use std::list.

Here's a useful tip: consider maintaining an order to the Train Car Cards in a player's hand. Players will often organize their cards in their hands in real life, clustering cards of the same color together so as to make the hand overall easier to assess, and funnily enough, we're kind of doing the same thing here. When we draw a player's hand of Train Car Cards, we can visually represent cards of the same color as piles of varying sizes, rather than as separate individual cards, in order to save screen space. When we have to draw a player's hand, then, we only have to iterate through the list once to look for cards of a specific color, and we can be sure they are all grouped together. Additionally, when we check to see whether a route is claimable, we don't have to iterate through the entire list of Train Car Cards; as soon as we hit a cluster of cards of a desired color, we know that as soon as we stop seeing cards of that color, it's guaranteed that there won't be any more. Good forethought like this can save you a lot of time and work in the long run!

    class TrainCarCardHand final
    {
    public:
        /// <summary>
        /// The default constructor has been defaulted.
        /// </summary>
        TrainCarCardHand() = default;

        /// <summary>
        /// The destructor has been defaulted.
        /// </summary>
        ~TrainCarCardHand() = default;

        /// <summary>
        /// The copy constructor has been defaulted.
        /// </summary>
        /// <param name=""></param>
        TrainCarCardHand(const TrainCarCardHand&) = default;

        /// <summary>
        /// The move constructor has been defaulted.
        /// </summary>
        /// <param name=""></param>
        TrainCarCardHand(TrainCarCardHand&&) = default;

        /// <summary>
        /// The copy assignment operator has been defaulted.
        /// </summary>
        /// <param name=""></param>
        /// <returns></returns>
        TrainCarCardHand& operator=(const TrainCarCardHand&) = default;

        /// <summary>
        /// The move assignment operator has been defaulted.
        /// </summary>
        /// <param name=""></param>
        /// <returns></returns>
        TrainCarCardHand& operator=(TrainCarCardHand&&) = default;

        /// <summary>
        /// This method adds a card to the hand in such a way that all cards
        /// maintain a strict order based on their color. All cards of one
        /// color are grouped together in the list.
        /// </summary>
        /// <param name="card">- The card to copy into the hand.</param>
        void AddCard(const TrainCarCard& card);
        
        /// <summary>
        /// This method checks to see whether the hand contains a certain
        /// number of cards of a certain color, including wild cards, which can
        /// represent any color.
        /// </summary>
        /// <param name="number">- The number of cards to check for.</param>
        /// <param name="color">- The color to look for.</param>
        /// <returns>True if there are 'number' cards that are either wild
        /// cards or are of color 'color'; false otherwise.</returns>
        bool ContainsCardsOfColor(uint32_t number, TrainTrackColor color) const;

        /// <summary>
        /// This method allows you to discard up to 'number' cards of the color
        /// 'color' from this hand and put them into the DiscardPile 'discard'.
        /// If there are not enough cards of the specified color, then wild
        /// cards will be discarded until 'number' cards have been discarded.
        /// </summary>
        /// <param name="number">- The maximum number of cards to discard.
        /// </param>
        /// <param name="color">- The color of the cards that should be
        /// discarded.</param>
        /// <param name="discard">- The DiscardPile into which to discard the
        /// cards.</param>
        void DiscardCardsOfColor(uint32_t number, TrainTrackColor color,
            DiscardPile<TrainCarCard>& discard);

    private:
        /// <summary>
        /// This is the list of TrainCarCards.
        /// </summary>
        std::list<TrainCarCard> m_Hand;

        /// <summary>
        /// This method discards cards using iterators from the list m_Hand,
        /// storing them in the discard pile and erasing them from the hand.
        /// </summary>
        /// <param name="begin"></param>
        /// <param name="end"></param>
        /// <param name="discard"></param>
        void DiscardCards(std::list<TrainCarCard>::iterator begin,
            std::list<TrainCarCard>::iterator end,
            DiscardPile<TrainCarCard>& discard);
    };

Now that we're done with creating new classes to represent Ticket to Ride, we can dive into the brave new world of GRAPHICS.

Sdl-logo.png

Your first step should be to select a framework to use, so you don't have to work with OpenGL or DirectX directly. I've chosen to use SDL, but you can use any framework you choose. Make sure you spend at least a couple of hours doing tutorials (a Hello World equivalent would be nice) and reading documentation before you jump in, and keep your eyes peeled for methods and classes that you will need for this project in particular, like drawing 2D textures at specific positions with rotation and scaling. That's one we'll use a lot.

If you now feel confident enough to use your graphics API, you can get started. Find .bmp images of the Ticket to Ride board, the Train Car Cards, and the Destination Tickets. I recommend buying the Steam version of Ticket to Ride and snipping images from that game where you can. Alternatively, you can buy a physical copy of the board game and scan the board and the cards into .bmp files. Once you've obtained all the usable textures you'll need, open up Photoshop and put the board onto a background (plain white will do for now), remembering to leave enough space for cards to be drawn around the board.

Once you've done that, you can mess around with texture positions and rotations until you have an arrangement you think looks nice and displays all necessary textures. By the end of it, you should have an image that looks something like this, which I am using in my project (I modeled it on the Steam game):

Capture.PNG

At this point, you should now have the foundations for a visual representation of Ticket To Ride, with all the important C++ classes written and the ability to draw most of the essential components. Next week, we'll dip a toe into the world of A.I., as we write our first A.I. player, albeit a rather stupid one.

Until then, code on!

PPP Devlog: Week 3

Routes, like these ones through Denver and Salt Lake City, can be individually claimed by players when they place their own colored trains on these routes. Knowing whether a single player has used their own trains to connect two arbitrary cities, no matter how far apart they are,&nbsp;is important in this project.

Routes, like these ones through Denver and Salt Lake City, can be individually claimed by players when they place their own colored trains on these routes. Knowing whether a single player has used their own trains to connect two arbitrary cities, no matter how far apart they are, is important in this project.

My first task for the week was to finish unit-testing my City class. The most important method that had yet to be tested was City::IsConnectedTo(CityName cityName, TrainPieceColor color) const. This method returns true if and only if there is some connection between one city and another city with trains of color "color".

Let's suppose you want to check to see if the player with blue trains has connected Los Angeles to Oklahoma City. Let's also suppose they've claimed the routes from Los Angeles to El Paso, El Paso to Santa Fe, and Santa Fe to Oklahoma City. If you were to call IsConnectedTo(CityName::OKLAHOMA_CITY, TrainPieceColor::BLUE) from the Los Angeles City object, the code would operate as follows.

First, you create a mapping of cities to ints, with the ints having value 0, indicating that a city has not yet been visited; 1, indicating that a city has been visited, but its adjacent cities have not yet been explored; or 2, indicating that a city and its neighbors have been visited. I initialize this mapping with all cities having an int of value 0, except for the starting city, which is initialized with 1. After the map has been created, I repeatedly look at all cities with value 1, check all of their direct neighbors with a connection of the appropriate train color, and set their value to 1 if it's currently 0. I then set the value of the original city to 2, denoting that I've explored all of its neighbors. I do this repeatedly until I either find the destination city, in which case I immediately return true, or until I have an iteration of the loop that finds no new neighbors, in which case I return false.


bool City::IsConnectedTo(shared_ptr<const City> city, TrainPieceColor color) const
{
    /*In this algorithm, I set up a mapping of cities to ints. The ints can be
    one of three values: 0, which indicates that city has not been visited at
    all; 1, which indicates that a city was just discovered in the most recent
    expansion of cities into neighboring cities; and 2, which indicates that a
    city has been visited and that all its neighbors have been discovered.*/

    /*The first step is to create this mapping.*/
    unordered_map<shared_ptr<const City>, uint8_t> cityToIntMap;
    const uint8_t zero = static_cast<uint8_t>(0u);
    const uint8_t one = static_cast<uint8_t>(1u);
    const Board& board = m_GameManager->GetBoard();
    for (const shared_ptr<const City> thisCity : board.GetCities())
    {
        if (thisCity.get() == this)
        {
            cityToIntMap.insert(make_pair(thisCity, one));
        }
        else
        {
            cityToIntMap.insert(make_pair(thisCity, zero));
        }
    }

    /*After the mapping has been created, we can repeatedly iterate through it and
    check for new cities for whom neighbors need to be explored. If a city's number
    is non-zero, that means we found a path to it somehow, meaning it is connected to
    this City. If not, then we need to check all cities with label 1. For each of
    these cities, we need to go to neighboring cities with label 0, if they are
    connected by the desired train color, and increment their label from 0 to 1.
    While doing this, we also keep track of how many new cities we discovered. If
    that number is 0, that means we've exhausted all routes out of that city. We 
    return false.*/
    bool returnValue = false;
    uint32_t newCityCounter = 0u;
    while (true)
    {
        if (cityToIntMap.at(city) != zero)
        {
            returnValue = true;
            break;
        }
        newCityCounter = 0u;
        for (auto& cityIntPair : cityToIntMap)
        {
            if (cityIntPair.second == one)
            {
                for (const shared_ptr<const Route> thisRoute :
                    board.RoutesFromCity(cityIntPair.first))
                {
                    if (thisRoute->TrainColor() == color)
                    {
                        shared_ptr&ltconst City&gt otherCityOnThisRoute;
                        const auto& citiesOnThisRoute = thisRoute->Cities();
                        if (cityIntPair.first->Name() ==
                            citiesOnThisRoute.first->Name())
                        {
                            otherCityOnThisRoute = citiesOnThisRoute.second;
                        }
                        else
                        {
                            otherCityOnThisRoute = citiesOnThisRoute.first;
                        }

                        uint8_t& otherCityInt =
                          cityToIntMap.at(otherCityOnThisRoute);
                        if (otherCityInt == zero)
                        {
                            ++newCityCounter;
                            otherCityInt = one;
                        }
                    }
                }
                cityToIntMap.at(cityIntPair.first) = static_cast<uint8_t>(2u);
                    
            }
        }
            
        if (newCityCounter == 0u)
        {
            break;
        }
    }
    return returnValue;
}

Next, I tested my Route class. This was fairly straightforward. The most important method of this class, Route::IsAvailable(TrainPieceColor color), determines whether a route is available to be claimed by trains of a particular color. If there are already trains pieces on that route, the method immediately returns false. Otherwise, the method checks to see if this Route has a twin, i.e., another Route that connects the same pair of cities. If not, then that means this Route hasn't been claimed by another player and isn't blocked due to some other rule. True is returned. If there is a twin, then we need to check its status. If there are fewer than four players, then that means a twin being occupied makes this Route unclaimable. If there are four players or more, then the Route is available to be claimed unless the same player has already claimed its twin; this is disallowed. My implementation of this logic is shown below.


bool Route::IsAvailable(TrainPieceColor color) const
{
    if (m_TrainColor != TrainPieceColor::INVALID)
    {
        return false;
    }
    bool returnValue;
    const shared_ptr<const Route> twin = Twin();
    bool hasTwin = (twin != shared_ptr<const Route>(nullptr));
    if (!hasTwin)
    {
        returnValue = true;
    }
    else
    {
        if (m_GameManager.NumberOfPlayers() <= 3u)
        {
            returnValue = (twin->m_TrainColor == TrainPieceColor::INVALID);
        }
        else
        {
            returnValue = (twin->m_TrainColor != color);
        }
    }
    return returnValue;
}


Next, I created a hierarchy of classes representing cards in the game. I designed and wrote the Card abstract base class and its two derived classes: DestinationTicket and TrainCarCard. (I explain what a Destination Ticket is below.) I also wrote the Deck<T> class template, which has important methods for decks of cards: namely, Shuffle, Draw, and AddCard. Using this template, I can create classes Deck<DestinationTicket> and Deck<TrainCarCard>. At a data level, the set of T objects is currently a std::list, but it occurs to me that I may want to replace this with a std::queue in the future: after all, I will only ever be taking cards off the top or adding them to the bottom.


template <typename T>
class Deck final
{
    static_assert(std::is_base_of<Card, T>::value, "T must derive from Card");
public:

    /// <summary>
    /// This method shuffles the Deck.
    /// </summary>
    void Shuffle();

    /// <summary>
    /// This method draws a card, removing it from the Deck and returning it.
    /// </summary>
    /// <returns>The card drawn.</returns>
    T Draw();

    /// <summary>
    /// This method adds a card to the bottom of the deck.
    /// </summary>
    /// <param name="card">- The card to be added.</param>
    void AddCard(T card);

 private:
    std::list<T> m_Cards

};

Finally, I added a static unordered_set of DestinationTickets to the NorthAmericaBoard class. This was done similarly to the unordered_set of RouteInfo objects I created to represent the routes on the board.

For those who have never played Ticket to Ride, a Destination Ticket is a card that represents a potential path between two distant cities. At the beginning of a game, all players take 2 or 3 Destination Tickets and attempt to connect the two cities specified on each of their cards. If they can accomplish this by the end of the game, the player receives a bonus; if not, they are penalized.

For example, this Destination Ticket, if held by a player, will require them to place trains of their own color such that Seattle and New York City are connected somehow. If this is done, the player receives 22 points at the end of the game; otherwise, they lose 22 points.

For example, this Destination Ticket, if held by a player, will require them to place trains of their own color such that Seattle and New York City are connected somehow. If this is done, the player receives 22 points at the end of the game; otherwise, they lose 22 points.

In the coming week, I will start by wrapping up foundational work for the game, including writing classes to represent a discard pile of cards and a Hand class. I will also finish writing and unit-testing the Board and NorthAmericaBoard classes as I see fit. The bulk of my work, however, will relate to getting the game's assets rendering on a screen using DirectX 11. By the end of next week, I aim to have the board drawn on the screen, have every card capable of being drawn on the screen, and display a visual representation of routes being claimed.

PPP Devlog: Week 2

This was my first week really delving into the writing of code for my project. Last week was all about creating a proposal and planning the project, creating a schedule and establishing goals, but now I'm really getting into the weeds of this project.

As I predicted, the setup of my Visual Studio solution took a considerable amount of time, and it was not enjoyable. Visual Studio is a wonderful tool for software developers, primarily because it has so many features and customization options for one to use. It truly makes one feel like a professional when one uses its many features. The downside of this, however, is that it requires a great deal of upfront work in order to set up and customize your solution in the way that will suit you for the rest of the development cycle. This means deciding how you want your code to be organized, how you plan to run unit tests, which platforms you intend to build for, and how you want project settings to be configured.

Project_settings.PNG

Next, I dove into the challenge of designing and writing the City class. This required me to consider some important design questions. At the forefront was the question of whether I in fact needed a City class at all. As I was designing the City class, I found that the only member variable it had was a CityName, an enum representing the name of that city; it occurred to me that I might be able to simply use CityNames instead of City objects. I decided, however, to stick with my original design and still have a dedicated City class; this would allow me to write helpful methods that could be called with a reference to a City, which is something that could not be done with an enum.

City_class.PNG

As I was writing the City class, however, I ran into a problem: I wouldn't be able to write some of the methods of City without a Board class. In my original schedule, I had not planned to write the Board class until Week 5, but I would need to start setting up a Board, which would contain City and Route information, in order to test the interplay between Cities, CityNames, and Routes. It's difficult to separate the Board from those other classes.

Board_class.PNG

Due to the unexpected shift in direction of my work during Week 2, I could be seen as having fallen short of my original goal. Yes, I did create a full database of cities and routes for the original North America board, but I didn't fully write and test the City or Route classes; they still need to be finished. On the other hand, I could be seen as having done more than what I promised. I have a Board class and a NorthAmericaBoard class fully written, and I designed the system that will make my code extensible as regards other boards, like the European board or the Germany board.

My original plan for next week was to have the Card, TrainCarCard, DestinationTicket, TreeNode, and GameState classes written and unit-tested. That's a rather ambitious goal, I think, especially when considering that I still need to finish writing and unit-testing the City and Route classes, and considering that this week will contain the potentially challenging task of determining what constitutes a "game state".

What I have learned is that I need to be more mindful of analysis paralysis, which plagued me during this week, particularly as I had to unexpectedly start writing the Board class. If I can set a hard time limit on the time I spend designing my code, then I believe I can increase the amount of work I can get done in a week. If I end up with a suboptimal design, then I will remind myself that I can go back into old code in the future and refactor if I feel so inclined.

Join me next week to see the Card-related classes and the TreeNode and GameState classes!

PPP Devlog: Intro

This is the first post I am making for my devlog about my Personal Programming Project. In this project, I will be expanding my A.I. skills by creating a C++ program that can play the board game Ticket to Ride. I will be using a Monte Carlo Tree Search algorithm that simulates a number of hypothetical games at each turn and uses sampling to determine which turn is most likely to produce a win at the end of the game.

box_image.jpg

I chose Ticket to Ride as the subject of my PPP because it seemed to be a particularly interesting case to observe regarding A.I. The problem of trying to connect two distant cities, particularly when dealing with the potential sudden blocking of routes by other players. Also, using A.I. to play board games is something I like thinking about in general and something I've done in a limited scope before: I created a Java program that could play Othello and used it as the centerpiece of my portfolio in order to be accepted into FIEA.

My first order of business will be to set up my Visual Studio solution for the rest of the semester. This won't be fun, but it will be necessary in order to make the rest of the experience more pleasant throughout the remainder of the semester.

After that, my plan is to fully write and unit test the City and Route classes and create a database of cities and routes that are on the original Ticket to Ride board. That was my original plan for the second week in the semester, but after receiving feedback that my schedule didn't leave enough time to tackle the meat of the A.I., the decision-making algorithm, I have decided that I should probably push some other things up into the second week. Perhaps I'll work on the Board class or the Card class in the second week in addition to City and Route.

Check back in one week for my Week 2 Update!