Applications in Theoretical Computer Science: Skill Trees
We see above the skill tree for the game Path of Exile. The Problem that we are posed with is such. Given the Skill Tree above, what is the best path/nodes for maximum game play.
Problem: The Skill Tree Problem
Input: Given a Skill Tree in the form of a graph G and k, the number of nodes you are allowed to select.
Output: Find the most OP Path.
This is rather simple for say a game like Borderlands
Players are restricted by their level and have the option on building out three separate trees (although since they are all connected to a root node, it's basically one tree).
However, we see that this can scale up dramatically, as is the case of Path of Exile. In fact, the Skill Tree Problem is probably NP Complete since this can probably be reduced to the infamous Traveling Salesman Problem (Will attempt to prove this some other time or leave as an exercise to the reader =P)
How to Solve: NP complete problems are in the set of NP problems and the set of NP hard problems and are therefore difficult to solve.
In fact, NP stands for Non-deterministic Polynomial meaning this problem can be solved by a Non-deterministic Turing Machine in Polynomial Time. Usually, we approximate NP Complete problems through the use of dynamic programming and greedy algorithms. For practicality these approximations suffice.
We can verify a solution for an NP complete problem in polynomial time. (In the realm of Theoretical CS, if you can do anything in polynomial time, it's good). So, we can also use randomized algorithms to solve for the best Skill Tree and then verify it. Thus, I challenge you to randomize your Path of Exile Skill Tree and see how it goes.
