Backward Induction

  • Reasoning Backwards From the End: It’s a method for solving problems or analyzing sequential decision-making situations by thinking about the very last possible decision first. You figure out the optimal choice at the final step, and then use that knowledge to determine the optimal choice at the second-to-last step, then the third-to-last, and so on, all the way back to the very first decision.

Optimal play versus the mechanics of the backward induction algorithm

  • Consider the state (prev_m, i, 0). It’s Mouse’s turn. The algorithm needs to evaluate all of Mouse’s possible moves. One possible move is to node i, even though it is not optimal
  • An optimal Mouse avoids suicide. The algorithm reflects this. But for the algorithm to know that moving to i is suicide (a Cat Win), it must have the outcome of the resulting state (i, i, 1) defined as 2 beforehand
  • Initializing state[i][i][1] = 2 doesn’t mean we assume the game will reach that state under optimal play. It means we are defining the consequence if it were reached, which is necessary information for the algorithm to correctly evaluate the preceding choices and determine the optimal path (which likely avoids that state).

Gotchas

  • Exclude the edge to 0 in degrees when it is cat’s turn
  • Exclude the edge from 0 when the current turn is mouse’s turn