Phants all over the place @lambdaphant - Tumblr Blog

Trains is FNP

There’s a game that my family loves called Mexican Train, or just Trains. It’s gameplay has fascinated me for some time, driving me to study the mathematics of it.

The Rules

The game is usually played with a double 12 set (91 tiles). Each round is started with a double as the lead for everyone to play off – 12, 11, 10, etc down to 0.

Each player plays on their own track, with one common track. If you’re unable to lay a tile during your turn, you must draw a tile and your track becomes public and anyone may play on it.

The winner runs out of tiles first.

Strategy

A key part of winning is keeping your track private and being able to play on it. The tiles that you can’t play on your own track, you’ll want to play on other tracks as you can throughout the game.

This presents a problem:

What is the longest chain of tiles that you can play on your own track without being forced public? Can this be determined efficiently?

Generally, as I play, I find myself with tiles that I realize I could have played to make a longer chain, but now are stuck in what I call my “etc” set.

Some Theory

I had a hunch that this is an NP-complete problem – we can’t solve it quickly, but we can verify it quickly – but I didn’t know how to prove it.

My first attempt at solving was the simply treat the set as a Set.

Example:

#{ [8,12] [7,12] [4,9] [3,3] [0,1] [6,10] ... }

If we’re starting with the double 12, simply remove all 12s to their own set:

#{ [8,12] [7,12] [9,12] [11,12] }

These are your possible starting points. Take each one and find the dominoes that can pair up agains its other end. In this case, start by finding all the 8s, then recurse and start over.

This gives us a O(n!), which isn’t great. In fact, wikipedia lists it as the worst order of common functions.

I firgure mostly I don’t know Set Theory, so I don’t know the shortcuts that can be taken. Sets mostly seem to be worried about comparing elements, but domino tiles aren’t really comparable.

And so, I started looking for papers that had possibly done research in this area. It was hard because I didn’t know how to frame my problem. Had I checked wikipedia at this point, I’d have noticed that O(n!) is associated with “Solving the traveling salesman problem”, which should have given me a major tip that this is a hard problem.

Some Different Theory

I couldn’t tell how Set Theory would help me solve this problem, so I tried to reframe it as a graph. This worked surprisingly well and even helped me find relevant work.

To make is a graph, think of each node as a tile, and the edges between them only exist if two tiles share a number. This graph is necessarily undirected (playing one tile on another works both ways) and possibly cyclical. From this, we’ll find a directed, acyclical subgraph and call it a train.

What Does That Mean

Warning: math!

For a double-n set, each number appears on n+1 tiles (remember, 0), so each node/tile has n edges to other nodes for number on it. Doubles have n edges, everything else has n + n.

Visuals always help. This is what that looks like, if the “lead double” is blue:

If you pick 15 random tiles for your hand, then we can make your tiles green. Maybe they connect to the lead, maybe they don’t:

This is actually the same thing as the one above, but with all the nodes that aren’t yours missing:

Wrap It Up

If you look at that last graph, it’s easy to imagine that there’s a way to move from node to node and find a path that doesn’t cross any node more than once.

There is, and it’s apparently a well known problem in Computer Science called a Hamilton Cycle and the related Hamiltonian Path Problem. The gist is that on some graphs, there is a way to draw a line between all the nodes without crossing any nodes more than once. This can’t be done on all graphs (which is fine), but it can tell us the longest path that it was able to draw.

In other words, the core problem of Trains is actually the Hamiltonian Path Problem. It is, in fact, NP complete*, and optimizing a solution below O(n!) is very, very difficult. It can be easily brute-forced pretty quickly for set sizes of 15, but that solution doesn’t scale well. (This means my original method of attack was correct)

* It’s actually something called FNP, which is essentially NP complete for functions rather than yes-or-no questions.

Afterthoughts

If you have a hard time with Trains, don’t feel bad. If you’re playing and you think someone is taking too long, keep in mind that they’re probably trying to solve a known hard problem in their head.

Be nice. That’s good general advice too.

–

code here

Trending Blogs

Recently Viewed Blogs

Phants all over the place