Check out the project on Google Colab!
https://colab.research.google.com/drive/1xeuYIXfIWVHir8u3D_LM1K9gck9uJSR6?usp=sharing
Introduction: Ticket to Ride is a board game where 2 – 5 players compete to build rail lines across the United States. Each player is dealt destination tickets with the goal of connecting two cities across the board.
Monte Carlo Tree Search (MCTS) utilizes Monte Carlo Simulation in order generate node values/estimates to help guide a state based search. MCTS focuses on paths which appear to be more promising, narrowing the amount of nodes needed to visit in order to find a ‘winning solution.’
This AI was part of my semester project for my Artificial Intelligence class
Monte Carlo Tree Search:
Monte Carlo Tree Search is essentially separated into four processes.
- Selection – The algorithm uses an upper confidence bound (UCB) to choose which child node to explore. [2]
Upper Confidence Bound:
- Expansion – If we are visiting a node for the first time, i.e. a leaf node, then we want to do a rollout and simulate a game, otherwise choose the node with the best UCB.[2]
- Simulation – the simulation is the Monte Carlo Simulation part of the algorithm. By utilizing random playouts over and over, we can get an estimate or measure of how good a starting state is likely to be. [2] “When a Monte Carlo Simulation is complete, it yields a range of possible outcomes with the probability of each result occurring.” [3] (IBM Education, “What is Monte Carlo Simulation?”)
- Back Propagation – After we have simulated a random playout, we back propagate the results through the search tree, keeping track of wins and node visits.
Ticket to Ride AI:
The Ticket to Ride AI has at any given time an option to build a line, draw two from a face up pile, draw two from a deck or draw a destination ticket. The AI is presented with only valid options to choose from which immediately reduces the original 89 moves to something much smaller. From the given available options, the MCTS algorithm begins a search and applies the moves to create new game state ‘child nodes’ in which to explore. When leaf nodes are reached, random simulations are played out and the results, ‘wins’, and node visits are propagated back up the tree.
PSUEDOCODE
Start:
Get Available Moves
From Moves, Create Child Nodes
Begin MCTS (loop for as long as possible):
Check UCB of Child Nodes -> Move to Greatest UCB ->New Node
IF New Node is Leaf Node -> Play Random Simulation -> Back Propagate Results
ELSE IF New Node has been visited but has no children -> Generate Children
Return Move with greatest wins
After, constructing the base MCTS algorithm, I realized despite the effort by MCTS to minimize the tree traversal, the tree was still relatively large to search when trying to go deep. Especially with python’s deep copy, to retrieve meaningful results from the AI requires several hours of run time. This algorithm would run much better if utilizing parallel processing to explore and generate the new game states of the children.
To make a more efficient AI, I began removing poor decisions from the AI manually. I only gave the AI routes which were connected to previously owned lines or part of a destination ticket. I split the decision of drawing train cards, drawing destination tickets or purchasing routes and those choices were instead governed by my own heuristic choice, i.e. train cards fell below a buying threshold or destination tickets were completed. When drawing train cards, I reduced the amount of iterations needed of the MCTS because I felt that decision was less important than buying train routes and picking a destination ticket required no iterations at all.
After the substantial trimming of choices, The MCTS ran much quicker and could go much deeper at a cost of less information, which resulted in marginal AI.
Also, important to note is that Ticket to Ride is not a perfect information game. Which makes the MCTS algorithm ill prepared to account for the random chance of card draws and destination draws.
CyrusTheVirus Studios 