Playing chess well is tough. Programming computers to play chess well is a challenge that has been wrestled with for many decades. Several key concepts developed during the struggle have relevance, direct as well as metaphorical, to many areas of life:

  • iterative deepening — study immediate possibilities and then use the results to guide deeper analysis, rather than blindly plunging far down hypothetical avenues;
  • transposition tables — keep track of where your choices are going to lead you, and if there are multiple ways to get to the same place then you can save time by remembering, rather than re-evaluating, the consequences;
  • minimax trees — look ahead, map out the space of possibilities, and assume that the opposition will do its darndest to cause mischief at every opportunity (i.e., minimize the value of the game for you) ... so pick the branch of the tree that maximizes the minimum result, thereby making the worst-case as good as possible;
  • alpha-beta pruning — once you've looked ahead a bit and partially built a minimax tree, by evaluating choices in the right order you need not go down every branch ... since some choices will be dominated by others along the way (so with luck and good planning the search space is cut down to the square root of itself, and millions of branches can effectively be computed with only thousands of evaluations)
  • killer heuristics — if you find a good strategy (a "killer" move) in one place, try it in other situations ... it's likely to be a winner in many contexts.

On top of these not-always-intuitive techniques, there are some simple yet important tactics from classical chess wisdom:

  • watch the clock — budget your thinking time to avoid running out in a critical position;
  • know the terrain — study openings, endgames, tactical configurations, and positional elements so as to have advance knowledge and familiarity with likely challenges; and
  • control complexity — keep things chaotic and confusing when you're behind, but ruthlessly simplify when winning, to maximize an adversary's chance to make mistakes and minimize one's own problems.

Caissa, the (make-believe) goddess of chess, is watching....

Saturday, January 08, 2000 at 06:35:37 (EST) = 2000-01-08

TopicThinking - TopicProgramming - TopicRecreation

(correlates: LeetSpeek, LineariZation, MagnaFortuna, ...)