A Winning Strategy for SIM
Computer programs that play games have been extensively studied in recent years. One reason for the popularity of game-playing programs is that games have well-defined problem environments and are sufficiently complex to provide a useful source of problem situations for testing different heuristic techniques. The game of SIM discussed in this paper was first introduced by Simmons . It is a two-person game played on the six vertices of a regular hexagon. Each player alternately draws one of the edges connecting a pair of vertices, each using a different color. The player who first forms a triangle of his own color loses. The objective of the game is to force one’s opponent to form a triangle without forming a triangle oneself. The possible number of edges which can be drawn in a 6-vertex graph is C(6, 2) = 6!/(4! 2!)= 15.