Properly stating a decision problem for a Hamiltonian cycle problem

computer sciencedecision-problemsgraph theoryhamiltonian-pathnp-complete

I'm running an algorithms seminar and I'm trying to express the Hamiltonian cycle problem in a new way that is exciting to students. I know that many of them play a game called Hearthstone and I'm trying to express a problem in that game as a decision problem.

Essentially in most card games they break down and stop being fun when a mechanic, that the designer didn't anticipate, adds recursion. In Hearthstone and Yu-Gi-Oh! that problem is expressed well in this video. In the packet that I give them I explain how the mechanic works and how it leads to recursion, then I ask them the following:

  1. Express the mechanic that leads to recursion in a card game formally with input and output states as a decision problem.

  2. Show this problem is in NP by giving a verification algorithm for this problem and proving that algorithm is correct.

  3. The Hamiltonian cycle problem is already known to be NP-complete. We can show that the recursion problem in card games is NP complete by reducing the Hamiltonian cycle problem to the card game recursion problem. Do so by first giving a reduction of Hamiltonian cycle problem to card game recursion problem. The reduction takes input to Hamiltonian cycle problem and converts it into input to the card game recursion problem. Then prove your reduction is correct.

My main question is: Did I state anything incorrectly and would you change anything about my formulation of the problem?

Best Answer

This sounds like a fun idea. I have a few thoughts that might help debug the assignment and make it better. (Part of the problem might be that I don't have enough information about the rest of the assignment, so feel free to correct me.)

  • I would include mention of player choice in the definition of recursion. For example: "Recursion effects happen in a card game when a chain of automatic effects trigger in a loop, with no player being able to break the cycle or choose an alternative."
  • Runaway recursion is not exactly a looping process in terms of game states, because quantities like the number of cards in your library, or your amount of remaining life, etc. may change. Therefore, the loopiness is more about the automatic triggering relation between different effects (A triggers B triggers C triggers A). This makes the problem statement a bit abstract—I'm not immediately sure how to represent effects and their triggering relations.

  • The decision problem is a little ambiguous (which might be intentional to allow for creativity, or which could be made more precise to help students.) For example, we might want to formulate the problem as: (1) Can you make a pair of decks out of Hearthstone cards that could lead to a recursion condition? (2) Can these two decks, when shuffled and during the course of play, lead to a recursion condition? (3) At this exact point in the game, is there an action that a player can take that will lead to a recursion condition?

    All of these alternatives amount to basically the same kind of NP problem, but having a precise implementation can help. I think (3) is most appealing to me because the only thing you're searching through is the side-effects of the players' currently available actions.

  • Do you have a specific recursion-causing mechanic in mind, such as the Shudderwock? Otherwise, it seems a bit open-ended if you have to map graphs onto some particular game state between two players that has a runaway recursion effect if the graph is Hamiltonian and otherwise doesn't. I'm not sure if you have a more specific mapping in mind.

  • It might help to provide a contextual reason why a decision procedure is appropriate here; e.g. as part of game design, you might try to compute whether a player can take any action that will lead to a recursion effect.

Do you have sample answers to questions 1 and 2, and the reduction in 3?

Related Question