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 theContinue reading “Proving The NP-Completeness of The Crew: The Quest for Planet Nine”
Author Archives: Freddy_Reiber
Ticket to Ride and the Traveling Salesperson Problem.
Abstract: In this post, we look at how to find the shortest path through a subset of nodes. We reduce the problem to the Traveling Salesperson Problem, and show how our solution is optimal. There is also a discussion on what NP-hard problems are, and why finding a solution to our problem is hard. TicketContinue reading “Ticket to Ride and the Traveling Salesperson Problem.”
Generating Solutions to The Crew: The Quest for Planet Nine Final
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 andContinue reading “Generating Solutions to The Crew: The Quest for Planet Nine Final”
Generating Solutions to The Crew: The Quest for Planet Nine Part 2
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,Continue reading “Generating Solutions to The Crew: The Quest for Planet Nine Part 2”
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 solutionContinue reading “Generating Solutions to The Crew: The Quest for Planet Nine Part 1”
A Chopsticks Solution Part 1
Abstract: In this post, we start writing a solution to a variation of the hand game “Chopsticks”. In this post, we create a graph that maps all of the possible moves and states. We also implement a version of minimax called negamax. Chopsticks is a popular hand game for two or more players. In Chopsticks,Continue reading “A Chopsticks Solution Part 1”
Ticket to Ride and Dijkstra’s algorithm
Abstract: In this post we look at how Dijkstra’s algorithm can be used to find the shortest path between two cities in Ticket to Ride. This can be used to find the optimal route for Destination Tickets, an important aspect of gameplay in Ticket to Ride. Ticket to Ride is a modern day classic. InContinue reading “Ticket to Ride and Dijkstra’s algorithm”
Tic-Tac-Toe and Minimax
Abstract: In this post, we discuss some of the important terms of basic game theory, and using the Minimax algorithm, create a strong solution for the abstract-strategy game of Tic-Tac-Toe. Tic-Tac-Toe, from a game design standpoint, is horrible. It lacks any real decision making, and assuming all players act optimally, will always end in aContinue reading “Tic-Tac-Toe and Minimax”
The Board Game Scholar 