Abstract: In this post we fully discus the current iteration of my algorithm for generating solutions to The Crew: The Quest for Planet. We look at the challenges of such and algorithm, the main flaws of its current system, and what needs to be worked on. We also discuss the Time-Complexity of this problem and what makes it hard to solve.
The Crew: The Quest for Planet Nine is a cooperative trick taking card game for 3-5 players, in which players must take tricks containing certain cards in order to win. For the past month and a half I have been attempting to write an algorithm that can generate solutions for The Crew. A more in-depth look at how exactly The Crew plays, as well as my previous work on the project can be found in my other two posts on this project. As a reminder, we are treating the problem as a perfect information problem, meaning we know everything about the game state (basically what cards players have), and our goal is to generate an algorithm that can consistently find solutions for The Crew, not prove the a solution does or does not exists. One may consider this an approximant algorithm, as it does not give any hard guaranties about if a solution does or does not exist.
The main reason we have no guarantee is that our problem is a type of computational problem referred to as NP or nondeterministic polynomial time. Essentially, this means that verifying if a solution is correct is easy, but actually finding said solution is hard. It is quite easy to show that our problem exists within NP, as a polynomial time algorithm exists for verifying the solution, simply run through the hands, making sure the solution doesn’t cheat(using the same card twice) and that those hands complete all of the objectives. However, when it comes to generating solutions, it is a much harder task.
Unfortunately, no proof can be given that this problem does not exist in P (that is to say, that finding solutions is “easy”) nor will a proof be given that this problem is NP-Complete, (although this may be covered in a future post). Instead, we shall move forward with the assumption that no polynomial algorithm exists, as I have been un able to find such an algorithm.
The simplest way to find a valid solution would to calculate all possible plays and then using our verification algorithm check to see if any possible plays satisfy all of the objectives. However, this is infeasible, as just calculating the possible first 3 possible hands results in 268,738,560,000 hands. Instead, we need to develop a system that will drastically reduce the number of possible hands.
To do this, we use a technique I call – The Critical Card Technique. For most hands played in The Crew, at most, half of the cards are actually important. Those two being the card that takes the trick, and if an objective card, if one was played this hand. (It is important to note that sometimes, a card can be the “high card” and an objective card). By using this observation we can drastically reduce how many hands we need to search.
The algorithm is divided up into two parts, the planning stage, and the execution stage. In the planning stage we check to see which players, can complete which objectives. To do this, we generate all possible hands that have the same suit (the suit of the hand is determined by the first card played) as the objective. We then iterate through all of these possible hands, and check to see if any complete the objective. The sudo code for this can be seen below.
def playerCanWinObjective(player: int, objective, playerHands):
cardOwner = findCardsOwner(objective.getCard(), playerHands)
possibleHands = generateHandsForObjective(playerHands, objective, cardOwner)
objective.setPlayer(player)
for hand in possibleHands:
if handCompletesObjective(hand, objective):
objective.setPlayer(None)
return True, hand.getWinningCard()
objective.setPlayer(None)
return False, None
We then use this data to form a bipartite graph, with the players and and objectives being the nodes, and an edge between the two of them suggesting that it is likely that player A could complete objective B. When then generate all possible matchings for this graph.
Unfortunately, this step is the first big hurdle to finding solutions to The Crew. Because we only search hands at the very start, and do no deeper searches, a majority of the time we get no possible matchings. Currently, this causes our algorithm to fail, however, future versions should have an improved system of finding if a player can win certain objectives.
It is also at this time that we identify critical cards for each of the valid matchings. Critical cards are important for two reasons. First, they help give an outline for finding valid solutions, and also prevent the playing of cards we will need later in the game.
After getting all possible matchings, we run the main algorithm. The algorithm is basically a depth first search, that uses the outline generated by the objective-draft to try and find a valid solution. We run the algorithm for all possible matchings and if we find a solution return in it. The algorithm can be seen below.
def findValidPlays(playerHands, currentLeader):
if objectiveNetwork.isComplete():
return True
for objective in objectiveNetwork.getPossibleTasks():
checkHand = playHand(playerHands, objective, currentLeader)
if not checkHand:
continue
for hand in checkHand:
objective.setComplete(True)
removePlayedCards(playerHands, hand)
handLeader = hand.getWinningPlayer()
if findValidPlays(playerHands, handLeader):
solution.append(hand)
return True
else:
objective.setComplete(False)
addPlayedCards(playerHands, hand)
return False
If we were able to find a valid matching we can generally find a solution using this algorithm. There are instances where we fail to find a solution, generally when a player is unable to play a certain card, as it is marked critical, and then are forced to play a card which changes which player wins the trick. However, most times this algorithm tends to work quite well.
The main issue with this system is the limited planning feature. Our inability to look into the future, greatly hampers our ability to properly plan. Future work would need to be done on finding efficient ways to see if players can complete objectives after certain cards are played. That is to say that a player who has only 1 Blue card and a Rocket card is able to take any Blue card after the first Blue trick has been played.
Still as a first version, the algorithm works decently and can be used to effectively complete the game. As always the full code is on my GitHub which is linked at the bottom of this post.
Final Thoughts and Conclusions: First off, this project took a lot longer that it should have. This project really got started right during Midterm season at my University, and my ability to put in hours to work on it was severely diminished. At the same time, because this is completely new ground, I had to develop the system from the ground up.
Somewhat surprisingly not a lot of papers exists on calculating contract bridge solutions, and so I was forced to develop the technique myself. At the same time, the nature of the algorithm made it somewhat hard to debug and ended up delaying both the second and final post by a couple of days.
Finally, I must say I am somewhat disappointed with how often this approach fails. I suppose that is to be expected with NP problems, but I somewhat expected a higher percentage of successes. I may return to this at a future date, to try and improve it but for now the project is being shelved. It should be able to complete all, or at least most of The Crew, and that is good enough for me.
My work with The Crew is not done however, as I a future post may be a NP-Completeness proof on The Crew, and discuss the nature of computing solutions to games. Other projects may include running a Monte-Carlo search on a medium complexity game, or developing an AI for something like Lost Cities. Anyway, thanks for reading the whole saga, and I’ll see you in the next post!
The Board Game Scholar 