Ticket to Ride and Dijkstra’s algorithm

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 Box

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.

Ticket to Ride USA Map

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.

A Ticket to Ride Destination Card

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.color

Then, 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], pathToCity

Final 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

Published by Freddy_Reiber

Undergrad student at UCI. Running a blog on how to use Computer Science to win in modern board games.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: