Abstract: In this post we look at how Dijkstra’s algorithm can be used to find the shortest path between two cities in Ticket to Ride. This can be used to find the optimal route for Destination Tickets, an important aspect of gameplay in Ticket to Ride.
Ticket to Ride is a modern day classic. In Ticket to Ride, two to five players try and traverse North America by building a railroad, connecting cities, and completing tickets. The game was designed by Alan R. Moon, and published by Days of Wonder. Ticket to Ride has seen mass market successes, in part because of its simple rules. One of the key parts of the game is Destination Tickets – cards that give bonus points to the player if the cities are connected. It is this mechanic that we will take a look at, and use Dijkstra’s algorithm to “solve”.
Much of Ticket to Ride can be analyzed through graph theory. In fact, the entire game board is basically a weighted graph.
Each city is a node, connected to other cities by colored routes. The routes can be thought of as edges, with their associated weight being the amount of trains required to claim the route. As for the color system, that is beyond the scope of this post, but may be touched on in a later post.
Our goal is to write a program that will find the most optimal path between any two cities on the Ticket to Ride board, assuming that no other routes have been claimed. By doing so, we should be able to increase the amount of destination tickets we can score in one game of Ticket to Ride. To do this, we will use Dijkstra’s Algorithm.
Dijkstra’s algorithm is a popular computer science algorithm used to find the shortest paths between nodes in a weighted graph. There are multiple versions of Dijkstra’s algorithm, but for our purposes we will focus on the original.
First, we must create a graph based on the Ticket to Ride map. To do so, I have created two main objects – Cities and Routes. Cities are nodes, each containing two instance variables, a name and a list of all possible routes(edges) that are connected to the City. I have also implemented three member functions. Two getters, one for each of the instance variables and third for adding a Route to the City. The code for Cities is seen below:
class City:
# Class init requires the Cities name and a list of all Routes that touch it.
def __init__(self, nameOfCity, listOfRoutes=None):
if listOfRoutes is None:
listOfRoutes = list()
self.name = nameOfCity
self.routes = listOfRoutes
# Getters
def getName(self):
return self.name
# Gets all possible Destinations with cost, returned in a list of tuples
def getAllDestinations(self):
allDestinations = []
for route in self.routes:
if route.getCity1() != self.name:
destination = route.getCity1()
else:
destination = route.getCity2()
cost = route.getCost()
allDestinations.append((destination, cost))
return allDestinations
# Setters
def addRoute(self, newRoute):
self.routes.append(newRoute)
For Routes(edges) I have also created a unique class. The class has 4 instance variables, the two cities it connects, its length or cost, and the color of the route. For this project, the color is not needed, but will be used in a future post. Each instance variable has a getter method, and the code can be seen below.
class Route:
#Constructor
def __init__(self, city1, city2, cost, color = "Grey"):
self.city1 = city1
self.city2 = city2
self.cost = cost
self.color = color
#Getters
def getCost(self):
return self.cost
def getCity1(self):
return self.city1
def getCity2(self):
return self.city2
def getColor(self):
return self.colorThen, to create the model of the board, one must build a set of Cities and Routes, modeled on the specific board you wish to analyze. I have done so for the USA board, and the full code for that can be seen in the GitHub repository linked at the bottom.
Finally, we must implement Dijkstra’s algorithm. Sudo code for the algorithm can be seen below. The code is based on the code given by the Wikipedia Page on Dijkstra’s algorithm
function Dijkstra(Graph, source):
create vertex set Q
for each vertex v in Graph:
dist[v] ← INFINITY
prev[v] ← UNDEFINED
add v to Q
dist[source] ← 0
while Q is not empty:
u ← vertex in Q with min dist[u]
remove u from Q
for each neighbor v of u: // only v that are still in Q
alt ← dist[u] + length(u, v)
if alt < dist[v]:
dist[v] ← alt
prev[v] ← u
return dist[], prev[]Our implementation has a couple of important things I wish to discuss. First, I have added two lines after we remove the smallest distance city, from the current set of unexplored cities. This is because we only care about finding the shortest path to our destination. Since Dijkstra’s algorithm makes no attempt at directly finding our destination, only exploring every path in order from shortest to longest, once our destination is “u” we can break from the loop. Second, for formatting reasons, I have added a couple lines to the end. These grab the distance from our start to destination, and using a traceback through previous, get an ordered list of the cities we visit on said path. I also reverse the list to have it go from start to finish. My full implementation can be seen below:
def findShortestPath(map, city1, city2):
# Sets initial values
# Current set of unexplored Cities
citySet = []
# Shortest distance for X city to city1/source node
distance = {}
# The previous node we visit to find this node through its shortest path
previous = {}
for city in map:
distance[city.getName()] = 1000
previous[city.getName()] = None
citySet.append(city)
distance[city1] = 0
# Main Loop
while len(citySet) != 0:
# Searches citySet for the city with the least distance[u] value
u = citySet[0]
for city in citySet:
if distance[city.getName()] <= distance[u.getName()]:
u = city
# Removes city from set of unexplored nodes as we are exploring it now
citySet.remove(u)
# Added since we only care about finding the shortest path to city2, not all nodes
if u.getName() == city2:
break
# Updates all nodes currently not explored
possibleDestinations = u.getAllDestinations()
for destination in possibleDestinations:
altRoute = distance[u.getName()] + destination[1]
if altRoute < distance[destination[0]]:
distance[destination[0]] = altRoute
previous[destination[0]] = u.getName()
# Using a trace back through previous we can get the reverse from city1 to city2
pathToCity = []
u = city2
while u != None:
pathToCity.append(u)
u = previous[u]
# Reverse the path
pathToCity.reverse()
# We can just return the distance to city2 as distance is a measurement of the shortest path from city1 to x node
return distance[city2], pathToCityFinal Thoughts:
Quite a simple week, as Dijkstra’s is Graph Theory 101. Originally, I had planned on looking at another solved game this week. However, with New Years fast approaching I found myself short on time and chose a “quicker” topic. I will probably revisit Ticket to Ride on a couple of occasions, as it is a great excuse to look at graph algorithms. At some point, I also plan to revisit the standard game, and either implement a full Ticket to Ride AI, or write a modified Dijkstra’s that takes the color of the route into account. Next week should be another classic abstract strategy game, one that has a little more depth than Tic-Tac-Toe
The Board Game Scholar 