Abstract: In this post I prove the NP-Completeness of The Crew: The Quest for Planet Nine. First we define the unbounded version of the problem statement along with what a brief review on NP as a complexity group. Next, I show a reduction from the Hamilton Path Problem. Finally, a proof is given on the correctness of the reduction.
In a previous post, I mentioned the possibility of proving the NP-Completeness of The Crew: The Quest for Planet Nine. After working on it for a while, I have finally found a proof using reduction. Before I present the reduction, I will present a bit of background info before on The Crew: The Quest for Planet Nine as the last post was on a different game.
The Crew: The Quest for Planet Nine (for the rest of the post I will be referring to it as simply The Crew) is a cooperative trick-taking game designed by Thomas Sing, and published by KOSMOS games. Its main gameplay loop is largely the same as other trick-taking games (hearts, bridge, etc.) with players playing cards in a series of “tricks” and the player with the highest-ranked card taking that trick. The Crew is unique, however, as instead of having teams of players competing against each other, all players are working to achieve the same goal. The goal is to have certain players win tricks containing certain cards.
In order to prove The Crew is NP-Complete we first need to change the problem statement slightly. There are three main axes in which The Crew as a computational problem can bounded. If this were a formal paper, full definitions of the entire problem statement would be given, but because this a blog post, they will be discussed in loser terms.
The first area we could potentially bound is the player count. In a typical game of The Crew, the player count is within the range of 3-5. However, in our instance of The Crew, we will allow an infinite number of players. The second area for a potential bound would be the number of suits. In The Crew, the deck players play with consists of 4 main suits: Blue, Pink, Green, Yellow along with a significantly smaller Rocket suit (this functions as a “trump” suit.) We will also allow for an unlimited number of suits, excluding the Rocket suit (We will show that this is not relevant later on). The final realm in which we could bound or problem is the number of cards within the suit. There are bounds for this area which I have found, but for the general problem statement, we will treat it as unbounded. Additionally, we will treat this problem as a perfect information problem, that is to say, that at all times we know what cards are in everyone’s hand.
To prove that a problem is NP-Complete it must meet the following two conditions. First, there must exist a polynomial-time algorithm for verifying a solution is correct. Second, the problem must be NP-Hard. Colloquially, this means that NP-Complete problems are the “hardest” problems in NP. Showing that a polynomial-time algorithm exists for The Crew is trivial. Because the game is cooperative, given a sequence of tricks and a distribution of cards and objectives, we can just run through each trick. For each trick we do the following three things: 1. That whoever won the previous trick starts this trick, 2. That all players have the cards played in the trick(after we remove those cards from each players hand) and 3. Check if any objectives have been satisfied, if so mark them. Once that is done, simply check to see if any of the objectives are still unsatisfied. If yes, than return false. If all objectives are satisfied, then return True.
Proving that The Crew is NP-Hard is a bit more difficult. The common way to prove that a problem is NP-Hard is to use reduction as a proof technique. Basically we take an instance of known NP-Hard problem and convert into a version of our problem statement. Then, we show that our conversion method does not change the outcome of the problem. That is to say that if our NP-Hard problem is unsolvable our instance of The Crew is also unsolvable, or vice versa. For a great and full explanation of NP-Hardness profs I would suggest Algorithms by Jeff Erickson. This is essentially a proof by contradiction as if we know that no easy solution exists for a certain problem, then it should follow that our problem has no efficient solution.
As mentioned before we will be reducing from the Hamilton Path Problem. The Hamilton Path Problem is the following. Given a Graph G, does a path exists that visits each vertex once and only once. For a proof that this problem is HP-Hard, see the following little black book.
Our reduction is as follows. First, we treat each node in G as a player. When then deal that player a card (S,V) (suit and value), where S is an unused suit and V is a the number of adjacent nodes. We also give that player the objective corresponding to that card. We then deal cards to all adjacent players in an arbitrary order, where the card is (S, V – number of dealt cards in that suit). Once all nodes are processed we deal “junk” cards to all players whose hands are smaller than then number of nodes.
An example of our reduction is now shown. Lets assume that our graph G is the graph shown above. If that is the case, our instance of The Crew is the following. This uses the notation of objectives being shown in parenthesis, and J being a junk card. (Also pardon the bad drawing, I was unsure how to best display this)
To show that this is a valid reduction, we now must show that our instance of The Crew is satisfiable if and only if our the Hamilton Path Problem is solvable for G. This is relatively simply. Because each player represents a node, and that player can only be reached by a adjacent player, we know that if a Hamilton path exists, then our version of The Crew is satisfiable. On the other hand, because the maximum number of tricks is the number of nodes/players, in order for each players objective to be satisfied, all players must take a trick only once. This combined with the earlier definition insures that if we have a valid instance of The Crew, then a Hamilton Path exists within our graph.
Thus, I have proven the NP-Completeness of The Crew: The Quest for Planet Nine. As mentioned before, trump cards are a none issue when proving the NP-Completeness. Because our reduction only allows for v (number of vertices) number of tricks, if at any point a trick is taken with a trump, that solution is not valid. Thus having a “trump” suit does not matter.
Final Thoughts and Conclusions: Not much to say here. The lack of posts is mainly due to school work picking up. Proving the NP-Completeness of board games is quite fun, albeit time consuming, and I will likely attempt to prove more board games in the future. Honestly, almost all co-op games are likely NP-Complete, at least when unbounded. As for my next post, I am unsure. It may be something historic as I am planning on writing a paper on the evolution of table-top games. But we shall see.
The Board Game Scholar 