Comp210: Principles of Computing and Programming
Fall 2004 -- Connect-N Algorithms   

Good algorithms for game playing

Programs that just satisfy the minimal requirements for full credit are not necessarily spectacularly skilled Connect-N players. Here are two basic approaches to improve play.

More information is available in Lab14.

Write a board valuation function which takes a board as input, and returns a value between (say) -100 and +100, representing how good the current position seems to be for White. For example, -20 denotes an (apparently) slight advantage for Black, while +100 might indicate a won game (or a guaranteed win) for White. An infinitely smart valuation function might always return +100 or -100, depending on which player has a forced win.³. Your function, though, will probably have to generate a value based on heuristics: for instance, having several sequences of three which aren't totally blocked might lead to a high valuation. Designing a good valuation function is an art.

Once you have a valuation function, you can use it to play the game: For each possible move, see what your valuation function rates each one, and choose one with the highest value. (How much does this process mimic how you play the game?)

Minimax

Human players also make further improvements: You can consider not just at your possible moves, but also the opponent's possible responses, evaluating each resulting board. It's reasonable to assume that opponent will probably choose the move which gives you the worst resulting position. Thus you want to choose the first-move which gives the maximum valuation, assuming the second-move is chosen so that it gives you the minimum valuation.

You can generalize this strategy to look more than two moves into the future, using generative recursion to enumerate sequences of moves. This method is known as "min-max", since you alternate your moves (choosing maximum values) with your opponent's (choosing minimum values). A good reference for the min-max method, appears here.

Note that this min-max approach still rests upon a static board valuation function⁴. While searching many moves ahead is a powerful method, you first want a smart valuation function. You are encouraged to implement min-max, but first write a function which only considers the one next move.

Since a minimax search can be very expensive in terms of computer time, the referee program will enforce the restriction that each move be made within a time limit (at least ^N/₅ seconds, where N is the number of locations on the board), on the workstations in Ryon. Those programs that fail to satisfy this requirement during the tournament will default their game. There are numerous ways to refine the basic minimax search, in order to speed it up. The most common is alpha-beta pruning.

³ Or 0, if one of the players can't force a win, but can force a draw. Is it really true that one of those three values must hold? (back)
⁴ By static board valuation function, we mean a function which valuates the board as-is, without searching through possible moves. This distinction is made because in general, a valuation function might search ahead, but it needs a base case to stop: the static-board valuation function. (back)