victor@cs.vu.nl (10/16/88)
An AI program has solved Connect Four for the standard 7 x 6 board. The conclusion: White wins, was confirmed by the brute force check made by James D. Allen, which has been published in rec.games.programmer at October 1st. The program called VICTOR consists of a pure knowledge-based evaluation function which can give three values to a position: 1 won by white, 0 still unclear. -1 at least a draw for Black, This evaluation function is based on 9 strategic rules concerning the game, which all nine have been (mathematically) proven to be correct. This means that a claim made about the game-theoretical value of a position by VICTOR, is correct, although no search tree is built. If the result 1 or -1 is given, the program outputs a set of rules applied, indicating the way the result can be achieved. This way one evaluation can be used to play the game to the end without any extra calculation (unless the position was still unclear, of course). Using the evaluation function alone, it has been shown that Black can at least draw the game on any 6 x (2n) board. VICTOR found an easy strategy for these boardsizes, which can be taught to anyone within 5 minutes. Nevertheless, this strategy had not been encountered before by any humans, as far as I know. For 7 x (2n) boards a similar strategy was found, in case White does not start the game in the middle column. In these cases Black can therefore at least draw the game. Furthermore, VICTOR needed only to check a few dozen positions to show that Black can at least draw the game on the 7 x 4 board. Evaluation of a position on a 7 x 4 or 7 x 6 board costs between 0.01 and 10 CPU seconds on a Sun4. For the 7 x 6 board too many positions were unclear. For that reason a combination of Conspiracy-Number Search and Depth First Search was used to determine the game-theoretical value. This took several hundreds of hours on a Sun4. The main reason for the large amount of search needed, was the fact that in many variations, the win for White was very difficult to achieve. This caused many positions to be unclear for the evaluation function. Using the results of the search, a database will be constructed of roughly 500.000 positions with their game-theoretical value. Using this datebase, VICTOR can play against humans or other programs, winning all the time (playing White). The average move takes less than a second of calculation (search in the database or evaluation of the position by the evaluation function). Some variations are given below (columns and rows are numbered as is customary in chess): 1. d1, .. The only winning move. After 1. .., a1 wins 2. e1. Other second moves for White has not been checked yet. After 1. .., b1 wins 2. f1. Other second moves for White has not been checked yet. After 1. .., c1 wins 2. f1. Only 2 g1 has not been checked yet. All other second moves for White give Black at least a draw. After 1. .., d2 wins 2. d3. All other second moves for White give black at least a draw. A nice example of the difficulty White has to win: 1. d1, d2 2. d3, d4 3. d5, b1 4. b2! The first three moves for White are forced, while alternatives at the fourth moves of White are not checked yet. A variation which took much time to check and eventually turned out to be at least a draw for Black, was: 1. d1, c1 2. c2?, .. f1 wins, while c2 does not. 2. .., c3 Only move which gives Black the draw. 3. c4, .. White's best chance. 3. .., g1!! Only 3 .., d2 has not been checked completely, while all other third moves for Black have been shown to lose. The project has been described in my 'doctoraalscriptie' (Master thesis) which has been supervised by Prof.Dr H.J. van den Herik of the Rijksuniversiteit Limburg (The Netherlands). I will give more details if requested. Victor Allis. Vrije Universiteit van Amsterdam. The Netherlands. victor@cs.vu.nl