Properly stating a decision problem for a Hamiltonian cycle problem

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?

• How can you express a card game as a decision problem? – Jack M Sep 8 '18 at 22:57
• @JackM Input: "Some set of cards" $\rightarrow$ Can these cards call themselves recursively? Yes or No. – jake mckenzie Sep 9 '18 at 15:12
• But what is a "card"? What does it mean for a card to "call itself"? Do all cards call other cards? Why can't I just model this by saying that a card is basically just a 0 is it can't call itself, or a 1 if it can, and then a game is a list of bits, and the game is recursive if it contains a 1? This is an absurdly broad question. If I was one of your students I would have no idea what to do with it. The idea of modelling a card game as a graph doesn't make sense, because it's not like every card in every game "calls" some other card. That's something specific to this one hearthstone card. – Jack M Sep 9 '18 at 15:19
• Well at least in this problem, it takes combinations of cards to be able to make the game recursive. In this game this card must be played with cards previously which will call more of this card. I think most recursion happens through some transitive property A$\rightarrow$B, B$\rightarrow$A, A$\rightarrow$B, B$\rightarrow$A,.... and so on. – jake mckenzie Sep 9 '18 at 15:21
• That's the simplest example of recursion. If thought of as a graph, recursion happens when you have a cycle in the graph. If there is no cycle then there will be no recursion. – jake mckenzie Sep 9 '18 at 15:25

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?

• The rest of the assignment can be found here: github.com/jakemckenzie/AlgorithmsSeminar/blob/master/Week8/… I haven't put the answers in pdf form yet. I worked through it on a whiteboard and haven't translated them to latex yet. I was leaving the problem more ambiguous as that's how my instructor phrased a similar problem where I got the idea from. In that problem we had reducing collecting pokemon cards from card packs to vertex cover. – jake mckenzie Sep 9 '18 at 15:19
• I wanted to post that then come back latter after I thought about your answer some more. I think you answered my question adequately but I want to think about it some more. Thank you for your feedback. – jake mckenzie Sep 9 '18 at 15:23