/*************************************************************************** ** ** ** Connect-4 Algorithm ** ** ** ** Version 3.11 ** ** ** ** By Keith Pomakis ** ** (pomakis@pobox.com) ** ** ** ** November, 2009 ** ** ** **************************************************************************** ** $Id: c4.txt,v 3.11 2009/11/03 14:42:12 pomakis Exp pomakis $ ***************************************************************************/ The files "c4.c" and "c4.h" provide the functions necessary to implement a front-end-independent Connect-4 game. Multiple board sizes are supported. It is also possible to specify the number of pieces necessary to connect in a row in order to win. Therefore one can play Connect-3, Connect-5, etc. An efficient tree-searching algorithm (making use of alpha-beta cutoff decisions) has been implemented to insure that the computer plays as quickly as possible. The file "game.c" is also being distributed, which illustrates how the Connect-4 functions can be used to construct an implementation of an actual game. This file was quickly written just to get an actual implementation up and running; it is NOT the reason for this distribution. The idea is for people to create their own front-ends for this algorithm. The functions have been designed to be general enough to be used with any front-end one wishes to design. The documentation describing each function can be found in the source code itself, "c4.c". I believe the comments in this file are clear and explanatory enough not to warrant an external documentation file. The sample front-end, "game.c", contains no documentation (hey, I've got other work to do, you know!). History ------- I developed this particular algorithm back in October 1992 for an Artificial Intelligence assignment. At the time, I implemented it in LISP. One year later I decided to convert the algorithm to C code so that I could use it as the smarts of a graphical front-end to the game. In performing the conversion, I took care to make the code as generic as possible. Version 1.0 (Fall, 1993) initial C implementation Version 2.0 (March, 1995) released when John Tromp (tromp@daisy.uwaterloo.ca) pointed out to me that I was only implementing "shallow" alpha-beta cutoffs and showed me how to implement "deep" cutoffs. Thanks, John! Version 2.1 (October, 1995) fixed a bug in the is_winner() function that occurred when the value of player was something other than 0 or 1. Version 3.0 (November, 1995) a complete overhaul. Most of the guts remain the same, and it is just as efficient, but the interface functions have changed. Version 3.1 (May, 1996) fine-tuned some of the innards, making the average computer move take 1/3 of the time it used to. Minor changes were made to the functional interface. Version 3.2 (June, 1996) fine-tuned the innards a bit more, making it a bit more efficient. Version 3.3 (November, 1996) fine-tuned the innards a bit more. Also, the poll interval is now specified in terms of CPU time rather than tree depth. Thanks to Miles Michelson (milesmi@uclink4.berkeley.edu) for making this suggestion. Version 3.4 (April, 1997) modified the order in which the game tree is searched, making the average computer move take 1/5 of the time it used to. Thanks to William Krick (krick@elvis.rowan.edu) for suggesting this. Also fixed a bug that could be triggered when a board width or height smaller than the number of pieces required in a row to win is specified. Version 3.5 (April, 1998) fine-tuned the innards a wee bit more, making it a bit more efficient. Thanks to Stefan Bellon (bellonsn@trick.informatik.uni-stuttgart.de) for pointing out the appropriate change. Version 3.6 (April, 1999) hard-coded the first move of a standard 7x6 game of Connect-4 to be the middle column (proven by Victor Allis in his Master's thesis ("ftp://ftp.cs.vu.nl/pub/victor/connect4.ps") to be the best first move). Version 3.7 (May, 2000) rearranged one of the internal data structures, making the average computer move take about 80% of the time it used to. Also added the c4_get_version() function. Version 3.8 (December, 2003) fine-tuned the evaluate() function a bit, making the average computer move take about 88% of the time it used to. Thanks to Steve Hassenplug (hassenplug@mail.com) for suggesting this change. Version 3.9 (December, 2004) fixed c4_is_tie() so that it doesn't incorrectly return TRUE if the last move was a win. Also simplified/tweaked a couple of minor things. Thanks to Barend Scholtus (rbscholtus@hotmail.com) for suggesting these changes. Version 3.10 (April, 2005) tweaked the algorithm a bit so that the computer is a bit smarter about the evaluation of tie states. Thanks to Nemanja Dizdarevic (propane@ptt.yu) for suggesting this change. Version 3.11 (November, 2009) now uses the C99 bool type, and other minor cosmetic changes. Legal Stuff, etc. ----------------- I am releasing these functions to the public domain. Therefore, people can use them, copy them, distribute them, modify them, and do whatever they want with them. If you find any bugs (gasp!) or have any questions or comments about the functions or about the algorithm itself, you can contact me via e-mail. My address is "pomakis@pobox.com". I'd be interested in hearing what you think! Oh, one other thing... I've put a lot of work into these functions, so I'd appreciate it if you kept my name attached to them when distributing or modifying them. If you actually use these functions for anything, give me credit somewhere! The Algorithm (not exactly as implemented, but algorithmically equivalent) ------------- All array indexes are zero-based. Global variables: x = the board width. y = the board height. n = the number to connect. level[2] = the skill level of the computer players, where applicable. board[x][y] = the board, where board[i][j] contains the value: 0 if player 0 occupies position i,j 1 if player 1 occupies position i,j C4_NONE if neither player occupies position i,j. z = the number of possible n-in-a-row areas on the board in which a winning connection can be made. This equals: 4*x*y - 3*x*n - 3*y*n + 3*x + 3*y - 4*n + 2*n*n + 2. Each n-in-a-row area on the board in which a winning connection can be made is given a unique number from 0 to z-1. Each space on the board is told which n-in-a-row areas it is part of. This is done with the array... map[x][y] = an array in which each element is a list specifying, for each corresponding board space, which n-in-a-row areas it is part of. stats[2][z] = an array containing statistics of each player. Statistics for player 0 are contained in stats[0], while statistics for player 1 are contained in stats[1]. stats[a][b] will contain 0 if the n-in-a-row area b is no longer a winning possibility for player a. Otherwise it will contain 2^p, where p is the number of pieces player a has in this area. ----------------------------------------------------------------------------- Upper-level Algorithm: set up map[][] array set every element in board[][] to C4_NONE set every element in stats[][] to 1 set player to either 0 or 1 while game is not over col = get_desired_col(player) drop_piece(player, col) if is_winner(player) or is_tie() game is over endif player = 1 - player endwhile ----------------------------------------------------------------------------- get_desired_col(player): if player is human return number from user interface else return best_move(player, level[player]) endif ----------------------------------------------------------------------------- best_move(player, depth): /* recursive! */ minimax search of possible future board states, using alpha-beta cutoff techniques to limit unnecessary searches. Look up these techniques in any AI book. The "goodness" of a board state at any point in time, from the point of view of the current player, is equal to score(player) - score(1-player), where score(p) = sum of stats[p]. ----------------------------------------------------------------------------- drop_piece(player, col): row = row the token will end up in after falling down the column board[col][row] = player for each element q in map[col][row] stats[player][q] = stats[player][q] * 2 stats[1-player][q] = 0 endfor ----------------------------------------------------------------------------- is_winner(player): for each element s in stats[player] if s = 2^n then return TRUE endfor return FALSE ----------------------------------------------------------------------------- is_tie(): if no element of board[][] is C4_NONE return TRUE else return FALSE endif ----------------------------------------------------------------------------- sample map[x][y] for x = 7, y = 6, and n = 4: +---------+---------+---------+---------+---------+---------+---------+ |20,26,59 |20,21,29,|20,21,22,|20,21,22,|21,22,23,|22,23,41,|23,44,56 | | |62 |32,65 |23,35,47,|38,50 |53 | | 5 | | | |68 | | | | | | | | | | | | | | | | | | | | +---------+---------+---------+---------+---------+---------+---------+ |16,25,26,|16,17,28,|16,17,18,|16,17,18,|17,18,19,|18,19,40,|19,43,44,| |58 |29,59,61 |31,32,47,|19,34,35,|37,38,49,|41,52,56 |55 | 4 | | |62,64 |46,50,65,|53,68 | | | | | | |67 | | | | | | | | | | | | +---------+---------+---------+---------+---------+---------+---------+ |12,24,25,|12,13,27,|12,13,14,|12,13,14,|13,14,15,|14,15,39,|15,42,43,| |26,57 |28,29,47,|30,31,32,|15,33,34,|36,37,38,|40,41,51,|44,54 | 3 | |58,60 |46,50,59,|35,45,49,|48,52,56,|55,68 | | | | |61,63 |53,62,64,|65,67 | | | | | | |66 | | | | +---------+---------+---------+---------+---------+---------+---------+ |8,24,25, |8,9,27, |8,9,10, |8,9,10, |9,10,11, |10,11,39,|11,42,43,| |26,47 |28,29,46,|30,31,32,|11,33,34,|36,37,38,|40,41,54,|44,68 | 2 | |50,57 |45,49,53,|35,48,52,|51,55,62,|65,67 | | | | |58,60 |56,59,61,|64,66 | | | | | | |63 | | | | +---------+---------+---------+---------+---------+---------+---------+ |4,24,25, |4,5,27, |4,5,6,30,|4,5,6,7, |5,6,7,36,|6,7,39, |7,42,43, | |46 |28,45,49 |31,48,52,|33,34,51,|37,54,61,|40,64,66 |67 | 1 | | |57 |55,58,60 |63 | | | | | | | | | | | | | | | | | | | +---------+---------+---------+---------+---------+---------+---------+ |0,24,45 |0,1,27, |0,1,2,30,|0,1,2,3, |1,2,3,36,|2,3,39,63|3,42,66 | | |48 |51 |33,54,57 |60 | | | 0 | | | | | | | | | | | | | | | | | | | | | | | | +---------+---------+---------+---------+---------+---------+---------+ 0 1 2 3 4 5 6 0 - 23: horizontal wins 24 - 44: vertical wins 45 - 56: forward diagonal wins 57 - 68: backward diagonal wins ----------------------------------------------------------------------------- The sample map that I show above is just to show what the map[x][y] array should look like for a 7x6 board of Connect-4 (even though it's usually filled in dynamically using a few iterative loops). The numbers in this array are labels on the winnable n-in-a-row areas of the board. This is useful so that when a piece is dropped into an arbitrary board position, the algorithm can determine very quickly which n-in-a-row areas have become more likely destined for a win for the player, and, as importantly, which n-in-a-row areas are no longer possibilities for the opposing player. The numbers in the map[x][y] array are indexes into a pair of parallel single-dimensional arrays which keep track of how likely each n-in-a-row area is to be the winning area for each player. I call this the stats array. The "score" of a player is merely the sum of the stats array of the player. Subtracting one score from another determines how well a player is doing relative to the opposing player. You throw these numbers into your general run-of-the-mill minimax algorithm, throw in some alpha-beta cutoff logic for efficiency, and that, in a nutshell, is the secret to my algorithm.