# Generating Solutions to The Crew: The Quest for Planet Nine Part 1

Abstract: In this post we create the foundation needed to formulate an algorithm that generates a “solution” for the board game: The Crew: The Quest for Planet Nine. To do so, we create a number of classes to help model the game, as well as some useful calculation tools. Finally we start creating the solution generating algorithm and produce a very rough version of the algorithm.

The Crew: The Quest for Planet Nine is a cooperative trick-taking game for 3-5 players. In it, players assume the role of astronauts searching for the elusive ninth planet. The journey takes players through 50 unique missions, with each one presenting a harder challenge than the last. It was designed by Thomas Sing, and published in 2019 by KOSMOS. It has received critical acclaim since its release, at is currently ranked 44 overall on Board Game Geek.

As mentioned before, The Crew: The Quest for Planet Nine is a trick taking game. Trick taking games are generally card based games in which players play a series of “tricks”. Generally each player plays a card in a designated turn order, after which the trick is evaluated and a winner or “taker” collects the cards. Some common trick taking games include Bridge, Hearts, and Rook. What makes The Crew so special is that it, unlike all of the other games listed, is that it is cooperative. In The Crew, players work together to complete objectives, and if all objectives are completed before all cards are played, the players win. For a full explanation of the rules see this video made by Meeple University.

In order to complete objectives, players must win tricks with a certain card contained within them. For example, if a player had the objective card seen on the right, they would need to win a trick with the pink 8 in it. This does not mean that they need to win a trick with the pink 8, only that they need to win a trick in which the pink 8 was played.

Finally, in order to make it more difficult, the game limits player communication. No information can be given about what cards are contained within a players hand. However, for the sake of our calculation, we are going to (at least to start) ignore that stipulation. Instead we will be treating the game as a perfect information game. This means that all information will be available to the computer at all times. We may in another blog post try to generate possible solutions without perfect information, but for now we will compute using prefect information.

Before we go any further, I would also like to define what I am referring to when I say solution. For our context, a solution is a series of plays that result in completing all of the objectives. Our goal is to write a system that is able to calculate one such series of plays.

Finally, I would like to touch on whether this game is deterministic. I have defined deterministic in a previous post, but as a quick reminder. A deterministic system is one in which no randomness is involved in the development of future states. Now, trick taking games are not deterministic. They often rely on the shuffling of cards in attempt to randomize before dealing. The Crew is no different. However, once all the cards no other random elements are included. This means that although the game is not deterministic, once the initial state has been calculated we can treat it as such.

Before we can begin, we must first create a model of the game. My approach has been to combine dictionaries and custom class objects. For cards, hands/tricks, and objectives I have created a custom class.

The card class contains nothing special, just two member variables along with getter methods for them. The constructor does check to make sure that rocket cards(the “trump” of The Crew) are not given a value about 4, but other than that, it is quite standard stuff. Here is the code:

```class Card:

# Suit is one of four colors - blue, pink, yellow, or green, or a rocket card and represented as a char
# Value is a value from 1-9 for color cards and 1-4 for rocket cards. Represented as an int
def __init__(self, suit: str, value: int):
self._suit = suit
if self.suit == 'R' and value > 4:
raise ValueError("Rockets can only be of value 4 or less")
self._value = value

def __repr__(self):
return self._suit + str(self._value)

# Returns the suit char
def suit(self):
return self._suit

# Returns the value int
def value(self):
return self._value

```

The Hand class has a little more going on in it. The main thing is that when each card is played, a small calculation is done to see if this card is better than the current winning card, and if so replace it. This was done to allow all of the operations to act in constant time. Although, with such a small list of data, having the operations take linear time shouldn’t really increase runtime. Here is the code:

```class Hand:

# First Card Played needs to be in the init as it sets the suit for the hand
def __init__(self, firstCardPlayed):
# The list of all cards played in the hand
self.cardsPlayed = [firstCardPlayed]
# The suit for the hand
self.handSuit = firstCardPlayed.suit()
# To lower the complexity of finding the winner,
# We do the overhead during each addition of a card to the hand
self.currentWinningCard = firstCardPlayed
self.winningPlayer = 0

def __repr__(self):
return str(self.cardsPlayed) + " Winner - " + str(self.currentWinningCard)

def playCard(self, newCard):
self.cardsPlayed.append(newCard)
if newCard.suit() == self.handSuit and newCard.value() > self.currentWinningCard.value():
self.winningPlayer = len(self.cardsPlayed) - 1
self.currentWinningCard = newCard
if newCard.suit() == 'R':
if self.currentWinningCard.suit() != 'R' or self.currentWinningCard.value() < newCard.value():
self.winningPlayer = len(self.cardsPlayed) - 1
self.currentWinningCard = newCard

def getSuit(self):
return self.handSuit

def getCardsPlayedInOrder(self):
return self.cardsPlayed

def getWinningCard(self):
return self.currentWinningCard

```

Finally, the Objective class. Again, not much special here apart from a member method that checks to see if a certain hand completes the objective. In all likelihood, this method will probably be removed and replaced by a static method, but for now it can stay. Here is the class:

```class Objective:
listOfAllColors = ['B', 'P', 'G', 'Y']

# Objectives represent cards that must be won by who ever has the Objective.
# Rocket Cards are not able to be objectives
def __init__(self, suit=None, value=None):

if suit == 'R':
raise ValueError('Rocket cards cannot be objective cards')
# Generates a random Objective if nothing is passed to the constructor
if suit is None and value is None:
self._suit = self.listOfAllColors[random.randint(0, 3)]
self._value = random.randint(1, 9)
else:
self._suit = suit
self._value = value
self._completed = False

def __repr__(self):
return 'Obj - ' + self._suit + str(self._value)

# Returns the suit char
def suit(self):
return self._suit

# Returns the value int
def value(self):
return self._value

# Checks for completion when a hand is taken
def checkForComplete(self, wonHand):
for card in wonHand.getCardsPlayedInOrder():
if card.suit() == self._suit and card.value() == self._value:
self._completed = True
return True
return False

def isComplete(self):
return self._completed
```

There are also a number of static helper methods that will be used later on, but are mostly self explanatory.

With all of the framework out of the way, we can begin to try and create a way to generate these solutions. Simply generating all possible combinations of play, would take way to long, which means that another approach is will need to be taken. I have yet to decide how to approach it, and the next blog post will mainly focus on creating the algorithm.

For now, I have a very rough algorithm that kind of works for single objective states. It calculates all possible plays for the first hand, assuming that the objectives suit is lead. It then iterates through that list and once it finds one that satisfies the objective, it returns it. It is very rough algorithm but it looks something like this:

```def playGame():
playerHands = dealCards()
playerObjectives = generateObjectives()
playedHands = []

while not checkAllObjectiveCompletion(playerObjectives):
possiblePlays = {}
# Need a better way to calculate suit
print("Trying to get " + str(playerObjectives[0][0]))
possibleSuit = playerObjectives[0][0].suit()
possiblePlays[0] = getPossiblePlays(playerHands[0], possibleSuit)
for i in range(1, 4):
possiblePlays[i] = getPossiblePlays(playerHands[i], possibleSuit)
for hand in createAllPossibleHands(possiblePlays):
if checkForHandObjectiveCompletion(playerObjectives[hand.winningPlayer], hand):
playedHands.append(hand)
break
# Just for now
break
```

Final Thoughts and Conclusions: This week was mainly on getting the details of the model worked out, and building infrastructure for the program. Next week is when the real challenge begins. I plan to try and read up on people trying to calculate solutions for bridge, although I can imagine that the required run time for such computations is insane.

With school starting again, my free time has been reduced, at posts that originally took me only one week, would probably take me about a week and a half now. While I still want to continue weekly posts, the size of posts may need to decrease.

As for future posts, my main plan is to continue work on this project. It is likely that this project may take two more weeks before I feel comfortable shelving it. I may also splice a Ticket to Ride graph algorithm in there, in order to keep up the weekly posts.