The Lost Woods - Enter Ganondorf

As the examples show, great complexity emerges from simple rules. Any solution that correctly computes the answer to this problem must somehow take into account infinite strings of moves that represent 'stalemate' behavior, so any sort of brute-force approach is highly unlikely to work. A number of heuristic approaches present themselves at first glance, but again, as the examples show, these seem unlikely to produce optimal results in all cases.

In order to determine optimal behavior on Ganondorf's part, and therefore the maximum score Link can achieve, we need to be able to consider all possible behaviors in a comprehensive manner. We'll do this by composing a directed graph modeling all potential game states. What makes a game state unique?:

• Is it Link's turn, or Ganondorf's turn?
• Where is Link positoned?
• Where is Ganondorf positioned?
• Where are all the remaining Heart Pieces?
• How many has Link collected thus far?

Multiplying the cardinality of all of these pieces of information together, and declaring $N$ to be the number of Heart Pieces within a maze, we find that there are $O(2 \cdot (WH) \cdot (WH) \cdot (2^N) \cdot N) = O(W^2 H^2 N 2^N)$ possible game states approximately speaking. Given the problem constraints, this amounts to about 300k states in the worst case, so any algorithm we attempt should be close to linear if it is to succeed in reasonable time!

Computing the game state graph is doable in linear time via BFS , by starting with the initial state, and using computation of all possible subsequent states due to any of Link's / Ganondorf's available moves, properly reducing the set of Heart Pieces, and/or incrementing Link's score when one is collected. Any state which has no Heart Pieces remaining is a game-over state, so we can stop searching from those. Once we have this game state graph, which is directed , and bipartite , but definitely not acyclic , we're ready to determine optimality.

---

To solve the problem, we will ask two generic questions about the game state graph, show that they can be used to recursively answer each other in finitely many iterations, and then show that these questions allow us to compute Link's maximum score. The algorithm presented is very similar to the minimax algorithm used in game theory. We can't use it directly because our game has more than 2 possible outcomes, and because the game state graph has cycles, and therefore cannot be modeled as a tree.

The first question is, "Given a set of candidate states one may traverse, including a start node, is it possible for Link to force the game to reach any one of a set of arbitrary target states?", and the second question is, "Given a set of candidate states one may traverse, including a start node, can Ganondorf prevent the game from ever reaching any one of a set of arbitrary target states?"

Now consider the first question. Let's consider the set of candidate nodes which have at least one out-edge pointing to one of the targeted states, and of course only candidate nodes for which it is Link's turn. If Link is to reach any of the targeted states, Link must force traversal to one of these nodes. If the start node is contained within the set, the answer is 'Yes' and we're done - likewise, if the set is empty, the answer is 'No', and we're done. Otherwise, we consider the complement problem: Of all of the nodes in this set, can Ganondorf indefinitely avoid traversal to any of them? If he can, then Link cannot force traversal to any of the target nodes, but if he can't, then Link certainly can.

Let's consider the second question! We consider the set of candidate nodes for which all out-edges point to one of the targeted states, and only candidate nodes for which it is Ganondorf's turn. If Ganondorf is to avoid all of the targeted states, then Link must not be able to force traversal to any of the nodes in this set, for if he does, Ganondorf will be forced to make a move that lets Link reach the target nodes. Similar logic follows. If the set is empty, the answer is 'Yes', and we're done. Otherwise, consider the compliment: Of all the nodes in this set, can Link force traversal to any of them? If he can, then Ganondorf cannot avoid the target nodes, but if he can't, then Ganondorf can.

This leads to the following pseudo-code:

ganon_must_avoid = emptyset()
def canLinkForce(candidate_states, start, target_states):
  mustReach = candidate_states.filter(at least one out-edge points to target_states)
  candidate_states -= mustReach
  ganon_must_avoid += mustReach
  if start in mustReach:
    return True
  else if mustReach is empty:
    return False
  else:
    return !canGanonAvoid(candidate_states, start, ganon_must_avoid)

def canGanonAvoid(candidate_states, start, target_states):
  mustAvoid = candidate_states.filter(all out-edges point to target_states)
  candidate_states -= mustAvoid
  if mustAvoid is empty:
    return True
  else:
    return !canLinkForce(candidate_states, start, mustAvoid)

In this way, from a set of target_states, nodes are examined in reverse order up the graph, and discarded from the candidate set as they are determined to be either a 'win' or 'lose' node for Link/Ganondorf. Since every method call must discard at least one candidate state to recurse, and, by using the inverted game state graph for efficiency, the in-edges of every state need only be considered once, the algorithm can be executed in linear time with the right data structures, since each game state is capped at 5 out-going, and in-coming edges.

Once we have these functions, it is trivial to determine Link's maximum score. For each score Link might obtain, simply ask:

canLinkForce(all states with score < target_score, start, all states with score = target_score)

And return the maximum score for which the above function call returns True.

---

Click this link to view the scores for each maze from the input in order, sans multiplication by the index. If you were not able to get the right answer, consulting these individual results may help you find the problem (or, if I got something wrong, the bug in my own solution!)