Abstract: In this post we continue our development of a solution generator for The Crew: The Quest for Planet Nine. We begin to create an algorithm for choosing which objective players should take, as well as start work on an algorithm for actually generating the solutions.
For those who have not read the previous post, here is a super short summary of what exactly my goal with this project is. The Crew: The Quest for Planet Nine is a cooperative trick-taking game, in which players must work together to insure that certain players win tricks with certain hands. Our goal is to write a program the creates a specific line of plays that will complete all of our objectives.
Normally, the game is not a perfect information game. That is to say, that part of the game state is hidden from players. However, because are goal is to generate a line of play that will end in a victory, we are treating the game as if it was a perfect information game. Meaning that all game state info (what cards are in players hands) will be given to the program.
One of the first things added in this version is a new class, The objective network class. The objective networks main purpose is to help plan which lines of play we should search. This is because calculating every possible line of play would take far to long. In order to combat this, out algorithms will only generate a small number of the possible hands, which will be guided by our planning system.
On of the things that can make The Crew difficult is the objective token system. During certain missions, objective tokens may be placed on certain objectives, modifying the order than those objectives can be completed. To model this, our objective network has four different types of objectives: free, number, order, and last.
Free objectives are objectives that can be completed in an order and at any time. Generally speaking, they are the easiest objectives to complete. However, when calculating possible games states, these tend to be a problem, as the lack of forced structure means we must search many more possible game states.
Number objectives are objectives which must be completed at that number. That is to say, that if a objective has the number 2 token, it must be the second objective completed.
Order objective are similar to number objectives, but offer greater flexibility. Order objectives must be completed in the order that is assigned by the tokens, but can have other types of objectives in between. For example if an objectives is assigned the O2 (Order 2) token, it must be completed after the O1 objectives. But, other objectives can be completed inbetween.
The final type of objective token is the last token. This token simply requires that this objective be completed last.
So, in order to help limit what objectives we are attempting to complete, we have the objective network class. Much of the class is standard stuff, however the getPossibleTasks() method is critical for the entire projects, and can see down below.
def getPossibleTasks(self):
# First we update the task list, as we may have completed one last hand.
self.updateTasks()
# Check if there is a last task, and we only have 1 left
if self.lastTask is not None and self.tasksLeft == 1:
self.tasksLeft -= 1
self.currentTaskNumber += 1
return [self.lastTask]
# Check if we must solve a certain task this turn
if self.numberTasks[self.currentTaskNumber] != None:
self.tasksLeft -= 1
self.currentTaskNumber += 1
return [self.numberTasks[self.currentTaskNumber - 1]]
# If we don't have a task we must solve, then we can generate a list of possible objectives to complete.
# First we get the first item in the order task
possibleTasks = []
for task in self.orderTasks:
if task is not None:
possibleTasks.append(task)
break
# Then all of the other tasks if free tasks can be added
for task in self.freeTasks:
possibleTasks.append(task)
self.currentTaskNumber += 1
return possibleTasks
A close inspection of the code may notice that forced objectives and free/ordered objectives are handled a bit different. Because the choice of which objective to try and complete depends on the board state, the removing of free and ordered objectives from the network is done after the completion of said objective.
The second main addition to the code base is the construction of a system for objective drafting. One of the core components of strategy within The Crew, is the objective draft. Starting with the first player, players take turns picking objectives, deciding which ones they wish to complete. This process continues until all objectives have been assigned a player.
To figure out which players should take which objectives, I have created a two part system, which can be seen below.
def objectiveDraft(playerHands, objectives):
playersNeedingObjectives = []
objectiveDict = {}
for i in range(len(objectives)):
objectiveDict[i] = []
for playerInt in range(len(objectives)):
assigned = False
for i in range(len(objectives)):
if objectives[i].player is not None:
continue
if playerCanWinObjective(playerInt % 4, objectives[i], playerHands):
objectiveDict[i].append(playerInt)
assigned = True
if not assigned:
playersNeedingObjectives.append(playerInt)
print(objectiveDict)
objectivePairing = validValueParing(objectiveDict)
The code works in three parts. First we iterate through all of the objectives, and check to see which players are able to complete the objective. Those that can are added to the objectives list of potential drafters (This is stored with the python dictionary). Then, once all objectives have been checked, we use a matching algorithm, to assign objectives to players.
The implementation of this may seem a bit strange, especially that for playerInt our range is the length of the objective list. This is to insure that our value paring algorithm is able to pair accurately, as having duplicate numbers will make it impossible to accurately match pairs. Once we have done that, we can mod the playerInts by 4 to get the appropriate player.
The final part of this system, which has yet to be implemented, is the “critical” card system. In each trick there are at most 2 critical cards. These are the cards that are used the take the trick, and in some cases, the objective card. Whenever a objective is assigned to player, we mark the critical cards as critical, which should prevent them from being played in other tricks.
Final Thoughts and Conclusions: First off, apologies for not having a new post sooner. I have found myself in the midst of a mid-term season, and was unable to get much work done on the project.
As for the project itself, I feel quite good about the system that I will be using to generate the solutions. Although it is not correct, in the sense that it could be used to prove if a solution to the game state exists, it should be pretty close. Currently, the main goals are checking to see if an optimal algorithm exists for matching the values, implementing the critical card system, and then writing the algorithm that actually plays the game. Because the first two shouldn’t be to difficult, the next post on this will likely be the finished project, with the code being posted.
For future projects, I would still very much like to take a look at Reiner Knizia’s Lost Cities, however that will probably be a larger project, and take a couple of posts. I also want to return to our Ticket to Ride model, and use it to demonstrate a couple of cool graph algorithms. Finally, I would also like to try implementing a Monte Carlo tree search on an incomplete information game. This could be Lost Cities, but will likely be something else.
The Board Game Scholar 