Context-Dependence in Game Heuristics

Simply put, heuristics are rules for governing how a formal system ought to move (where “move” is understood to mean “transition from one state to another according to valid transition rules.”) But for our purposes, we should understand heuristics to have a quality of being definable fully within the system itself. In other words, the heuristic “Control the center” would have been useless to Deep Blue if the idea of “control” and the idea of “center” were impossible to define syntactically. (Note: This should be reminiscent of our similar stipulation that winning conditions be definable within the system itself — an idea mentioned here.)

Furthermore, as we have already mentioned, heuristics that govern a formal system designed to play a game (like chess) can be understood to be much more context-independent than rules of the form, “Look up your position in an opening book and make the indicated move.” It is important to note, however, that context-dependence is not a binary quality — but rather a spectrum. Consider a simple game in which two players are competing to acquire the largest number of stones, which are initially residing in a central pile. The rules are that, on your turn, you may 1) take a stone from the central pile, or 2) put a stone back into the central pile. The best strategy in this (rather boring) game should be obvious: “On your turn, take a stone. Never put one back.”

Within this simple game, the winning heuristic can be considered context-free. It doesn’t matter how many stones are in the central pile, or how many stones your opponent has, or how many previous moves have been played — you always want to take one stone. This heuristic depends on no other game-related concerns.

In chess, most (if not all) rules are more dependent on context than in the previous example. Some rules are more context-dependent than others because they have their context built into them explicitly: i.e. “If your position looks like this (context), always play this move (transition).” But most of the truly interesting heuristics are more context-independent: like, “Control the center,” and “Don’t bring your queen out early.”

Ironically, the really tricky parts of stupefying a task involve trying to apply such more-or-less context-independent heuristics in their proper context. (We should certainly note that, “more-or-less context-independent heuristics” are a far cry from context-free heuristics.) When is it best to control the center? How early is too early with regard to bringing the queen out? Should one bring out one’s queen early if that leads to controlling the center? How does one decide between two context-independent heuristics? How does one decide just how context-independent a particular heuristic is? This will be the subject of the next post.