Playing Ticket-to-Ride like a computer programmer

Applying graph theory and network analysis in building effective strategies for playing a board game.

Published in

Towards Data Science

14 min readJul 10, 2020

Ticket-to-ride is one of the very few strategic board games and it requires that players need a lot of planning and strategy building in the process. With the simple application of network analysis and graph theory concepts, it is possible that one can play this game even more efficiently. In this article, I will share some of my results from the computational analysis on the Ticket-to-ride board game. Also, I will discuss how to build the best strategies for this game.

Before we proceed, let me clarify that this article is not to introduce the game or its rules to you, it is expected that the audience of this article is familiar with the game. Anyways, for those of you who are unfamiliar about the game and its rules, visit this page Ticket to Ride Wiki

Building the structure

We will be using the popular python package networkx to build the graph structures. To fit in the current context, cities are represented as nodes and segments between cities can be represented as edges. Then we construct the network using the below code.

Once the network is constructed, we can quickly see the basic info using the code below.

It can be noted from above that the network has 47 cities (nodes) and 90 tracks (edges).

Basic Stats

In network theory, the degree of a node is the number of edges that it is connected to, which translates to the number of tracks that a city is connected to. Based on a degree distribution chart shown below (Fig-1), it can be observed that the degree of all cities ranges between 1–7. About 15 cities have a degree of 4 and 14 cities have a degree of 3. There is only one city with a maximum degree of 7 and two cities with a degree of 6.

Also, the network theory term edges translate to the track segment, edge weight translates to the track length in the current context. From the edges distribution chart below (Fig-2) that nearly 33 edges have a track weight of 2, 26 edges with a weight of 4, 25 edges with a weight of 3. There are 2 edges with a weight of 6. There is only one edge with a weight of 8 which happens to be the track segment running between Petrograd-Stockholm. Just by claiming this route, you can buckle up 21 points.

As expected, the level of difficulty of this game increases as the number of players increase. This is evident from the below ratios.

For e.g, in a 3-player game, only 10% of the cities have a degree less than 3 which means blocking other players is difficult so that would be an easy game for each player involved. However, blocking probabilities are more in 4-player and 5-player games. In a 5-player game, a huge number of cities nearly 72% have a degree less than 5 which means there is more room for blocking strategies by other players hence the game becomes more difficult.

Fig-4 (below) shows the destination card points distribution. It can be observed that there are very few long routes about 3 destination cards with 21 points each and 3 cards with 20 points each. A vast number of cards are short routes with a big chunk about 13 cards with 8 points each.

Fig-4: Destination card points distribution

Let us now define some common properties of the network:

radius is the minimum number of edges needed to connect the most central node (city) to all others.
diameter is the minimum number of edges that will connect the two nodes that are far apart.
eccentricity is the maximum distance from a given node to all other nodes. The lower value of eccentricity means that the node is relatively closer to the center of the network while the higher value of eccentricity means that the node is relatively far from the center of the network.
center of the network is the set of nodes whose eccentricity equals the radius of the network. There are 3 cities (listed below) at the center of the network. From all of these cities, it is relatively easy to reach any part of the network.
periphery of the network is the set of nodes whose eccentricity equals the diameter of the network. There are 7 cities (listed below) at the periphery of the network. From each of these cities, it is relatively difficult to reach to the further part of the network.

Some of these network parameters are calculated as below. It can be noted from below that the network has a radius of 5, a diameter of 9.

Based on these network properties, we can make the following observations:

It is a good strategy to start your game by claiming routes around the cities with low eccentricities such as Berlin,Venezia,Munchen because its relatively easy to reach whatever direction you wish to continue as the game unfolds.
It is a good strategy to choose destination cards including any periphery cities such as Lisboa,Cadiz,Edinburgh,Erzurum,Sochi,Rostov,Moskva. These are also the cities with high eccentricities. Having one or more of these in your control increases your chances of building the longest route. Your best bet would be to have two such cities but at the opposite ends of the network.
Listed below are all those routes from periphery cities with length equal to the diameter. Considering these in your plan would be a smart strategy especially if you are on building the longest route.

Importance of some cities

Certainly, some cities are more important than others. This can be measured with a variety of centrality measures, clustering coefficient, connectivity, and efficiency.

These properties are defined below:

Degree centrality for a node is the fraction of nodes connected to it.
Betweenness centrality of a node is the sum of the fraction of all-pairs shortest paths that pass through it.
Closeness centrality of a node is the reciprocal of the sum of the shortest path distances from the current node to all other nodes.
Clustering coefficient of a node is the ratio of the number of connections in the neighborhood of a node and the number of connections if the neighborhood was fully connected. This ratio tells how well connected the neighborhood of the node is. If the neighborhood is fully connected, the clustering coefficient is 1, and a value close to 0 means that there are hardly any connections in the neighborhood.
connectivity of a node is the minimum number of nodes required to be removed to block out all the paths to the subject node. The higher value is better.

All the above properties can be deduced from the network as below:

The above code creates a data frame cities_df as below (only 5 rows shown below)

Fig-9: Illustration of Centralities and Clustering coefficient (only 5 rows shown)

Below are a few observations we can make from the results:

Based on degree centrality, cities Paris, Kyiv, Frankfurt have higher values whereas cities Ediburgh, Cadiz, Lisboa, Kobenhavn have a lower value. The lower value of this measure means that you need to be more cautious around those cities because there is a high probability that you may be blocked from those cities.
Based on betweenness centrality, cities Frankfurt, Wien, Budapest have higher values whereas cities such as Brest, Palermo, Cadiz have the lowest values. The higher value of this measure means that there are more shortest paths passing through those cities hence there will be more competition for routes passing through those cities. More competition again leads to blockage so you need to watch out these cities if you have any of them in your plan.
Based on closeness centrality, cities Wien, Munchen, Budapest have higher values so it is relatively easy from these to reach far ends of the network quite easily. whereas cities Cadiz, Lisboa, Edinburgh have lower value so it is relatively difficult to reach the far ends from these cities.
Based on clustering coefficient values, it is evident that the neighborhoods of cities such as Lisboa, Cadiz, Sochi, Barcelona, Brest are quite strong so even if your opponent tries to block you in one route, you will certainly be able to find your way out and move on. However, you need to be more cautious for cities such as Edinburgh, Moskva, Stockholm, Kharkov, Kobenhavn. London because their neighborhood is not strong and you may be blocked out.

Apart from centrality measures and clustering, we can also measure each city’s importance by certain attacking strategies. The importance of anything is better known only when it is gone. So, we can iteratively remove one city at a time from the network and measure the change in certain properties such as connectivity, efficiency, etc. Removing a city in this context means that your opponents have claimed all routes around that city and you are blocked out with respect to that city. This process can be done using the code below:

The above code will generate a data frame node_importance_df as shown below (only 5 rows shown):

Fig-10: Illustration of node importance (only first 5 rows shown)

Below are a few observations we can make from the node importance results:

It can be observed that the network pretty much stays connected when you remove any city except for London and Madrid. When you remove London, Edinburgh becomes unreachable and when you remove Madrid, both Lisboa and Cadiz becomes unreachable from elsewhere. So, if you are interested in either of these cities, you better watch out London or Madrid.
It is interesting to know that removing Essen raises the overall average cost to build a route by +8.24%. If you claimed all routes leading to this city, you would significantly affect all of your opponents as their cost to build increases, and consequently, their game will be slightly delayed. However, it is not good for you if the situation is the other way around.
Another interesting observation is that absence of Marsielle reduces the average connectivity by -10.35% which again is not good for your opponents as they become more vulnerable for blockage.

Importance of some track segments

In the context of the game, it is relatively hard that anyone gets blocked out for a city but its fairly easy to get blocked out on a route segment hence knowing the importance of certain edge segments is more useful in this game. The importance of each route segment can be gauged by edge betweenness centrality, and change in factors such as average connectivity, average clustering coefficient, efficiency.

Using the following code, we can calculate betweenness centrality of every edge:

Fig-11: Top-5 edges based on betweenness centrality

Fig-12: Bottom-5 edges based on betweenness centrality

Below are a few observations we can make from Fig-11 and Fig-12:

It can be observed that Budapest-Wien, Zagrab-Vienna, Wien-Munchen have a high betweenness centrality. So, certainly, there is a big competition for these segments, so you need to catch up on them relatively sooner if at all they are in your plan.
However, for segments such as Rome-Venezia, Barcelona-Marsielle, you need not stress much because their lower value of betweenness score indicates lesser competition.

Let us now assess each edge’s importance based on some attacking strategies similar to what we have done in the previous section for nodes importance. This can be done using the code below:

The above code will produce a data frame result which looks like below (only 5 rows are shown):

Fig-13: Illustration of Edge’s importance (only 5 rows shown)

Below are a few observations we can make from the edge importance results:

You can observe that the network is only disconnected when you remove the edge London-Edinburgh and when that happens only Edinburgh becomes unreachable. However, the network is not impacted by any other edges.
When Kobenhavn-Essen goes out of the picture, the average shortest path cost increases by 7.34%.
It can be observed that average connectivity is considerably impacted by almost every edge removal with the most impact caused by removing the edge Rostov-Kharkov when average connectivity drops by 8.47%.
The neighborhood also is deeply affected when you remove edges such as Lisboa-Cadiz, Cadiz-Madrid, Lisboa-Madrid which is evident from the huge drops in the network’s average clustering coefficient values.
Also, the efficiency drop 2.81% is caused when you remove the edge London-Edinburgh.

Destination Card Profitability Analysis

What if you know the art of picking the right cards? Of course, that is quite possible but only if you know the underlying numbers. Using the code below we can calculate the shortest path characteristics of all the destination cards.

The above code will generate a data frame as below (only 10 rows shown):

Fig-14: Destination cards shortest path characteristics

Below are a few observations we can make from the shortest path results:

It can be observed that all long routes (card points >=20) fetch you around 50–54 final points if you get to do the shortest paths. You still will be left out with nearly half of your locomotives besides doing the shortest path in one of these routes because it costs you only around 20–21 locomotives at the max.
Also, it is interesting to know that the route Edinburgh-Athina (21) may seem more attractive over Lisboa-Danzig (20) because of the extra card point but the shortest path of Lisboa-Danzig will fetch you 50 points whereas Edinburgh-Athina fetches you only 48 points. This is, in fact, more evident in the shorest path profitability the ratio which essentially explains how profitable is that route. It is simply the ratio of total final points and the cost for it which is the number of locomotives you used to build that route. Also from the table, it is evident that the most profitable shortest path route is Palermo-Constantinople which would cost you only 8 locomotives for a return of 25 points. That would be a good short route card to grab besides one long route.
Another interesting factor to look at is the connectivity which in this case applies to all the associated routes. It indicates the minimum number of edges to remove for blocking out all paths between a given source and destination nodes. The higher it is the better. It can be observed that Berlin-Bucuresti is by far the most robust route because it takes 5 edges for anyone to block you out. In the longer routes, Edinburgh-Athina, Kobenhavn-Erzurum, Cadiz-Stockholm are more vulnerable for blockage because of fo their lower edge connectivity values. So, you got to play with more caution if you were to do any of these routes.

Alternate Scoring Strategies

On any route, the shortest path completion requires the least number of locomotives but does not necessarily fetch you maximum points. During the course of the game, its quite common for the players to make slight detours especially for gaining few extra points.

Let us analyze the route Palermo-Moskva in more detail. From the destination card analysis, we can see that the shortest path for the route Palermo-Moskva fetches you a total of 54 points at the cost of 20 locomotives. However, if you have more time, you are more likely to plan a detour for gaining extra points. So how do you do that? Well, here you need to carefully consider various features associated with every alternate path so as to make good gains. For e.g, if there is not much time left in the game, you might want to select a path that has less path length because completing every segment of the path length costs you a turn. Also, you should be able to cover the cost of your selected path so path cost becomes an important factor in selecting an optimal path sometimes. Sometimes, path profitability makes more sense especially when you want more return on your investment.

Deducing all the alternate routes between given source and destination requires finding all simple paths throughout the network which could sometimes lead to an indefinite time especially for large networks. Hence we will only find all those alternate paths which are just 2 segments more than the shortest path which simplifies our process. Below is the code fragment which essentially does that.

Using the above method, we generate all the alternate paths for the route Palermo-Moskva You can carefully analyze the below paths and select the most optimal path depending on your criteria. Similarly, alternate paths can be deduced for any given route.

Fig-15: Palermo-Moskva Alternate scoring options

Blocking Strategies

In the previous section, we have seen alternate scoring strategies. However, you need to be aware of what it takes for others to block you to complete your desired route. Using Mininum edge cut for any route, we can find out the list of most critical edges if all are blocked would mean that you cannot complete that route.

For example for the same route discussed above Palermo-Moskva, it takes 3 edges for anyone to knock you down. In other words, it essentially means that you need to make smart choices to build on these edges relatively sooner and leaving less chance for others to block you.

From the minimum edge cut analysis, we can make the following observations:

Berlin-Bucurest and Paris-Wien are the most robust because it takes 5 turns for anyone to block on these. This means that you can relatively play with ease on these destination cards, without the stress of being blocked.
Edinburgh-Athina is the most vulnerable route because it takes only 1 edge for anyone to block you from completing your destination card.

Conclusion

While each one of you has a different take on the game, it is always good to know the details discussed here such as when to go for shortest path and when to take a detour from the shortest path in favor of some extra points, etc, how to block someone or how to avoid being blocked, what segments to watch out and what segments you can stress less about, etc. etc. Hopefully, you enjoyed reading this article.

All the code used in this analysis can be downloaded from this Github repository.