RICHARD SHEK 0882570 COMP 210 FINAL PROJECT (BASIC & EXTRA COMPONENTS) CONNECT 5 README PURPOSE: The purpose of this program is to take in a Connect 5 board situation and return the best possible move. The minimum requirements of this program is to place a winning move if possible, and if no winning moves are available, then place a blocking move if a situation exists for your opponent to establish a win. COMMANDS: The player simply has to press EXECUTE on the DrScheme interaction/definition window, and afterwards place a representation of a Connect 5 board in the interaction box. The board representation consists of the different stones (or blank spaces) in each square of the board, in which all the squares of the same row are grouped in a parenthesis. For example, to represent a blank 5 * 5 board, the player enters: ((- - - - -) (- - - - -) (- - - - -) (- - - - -) (- - - - -)) of course, '-s can be replaced with 'X for yourself and 'O for your opponent. REPRESENTATIONS: The board representation with lists (such as the above diagram) is used when a board is first 'entered' via the interaction window. Immediately after a board is entered, the program translates the board into matrix format. The program has the matrix definition as a vector of vectors, and it has several tailored functions that deal with searching through matrices. This program determines the best move by looking at each and every blank squares. Therefore, the representation of a 'move' is a structure that contains its x and y positions (or in matrix terms, the column and row positions) of a square (that a stone will be placed in on that chosen move), and its winning and blocking values (to be discussed further on). The x and y positions are numbers, while the winning and blocking values are either both booleans or both lists of 4 numbers. Booleans will be used in the initial, basic version of the game; lists of numbers to value a square's winning or blocking value will be used in the 'smarter' part of the program. MINIMUM REQUIREMENT STRATEGY: Within the minimum (required) program, the strategy in finding a winning or blocking move is to look through the strategic importance of every blank positions on the board. For each square/move, the program will check whether it produces a winning and/or blocking move. This itself is divided into four parts, and they are checking the horizontal, vertical, and the two diagonal (we will call them left and right diagonals) lines that runs through each particular square. If it is discovered that placing a stone on that particular position would allow the player or his/her opponent to "connect 5," then for the portions of the move structure that contain win or block-win, those positions will be filled in with true or false for each portion. A list of all blank squares will be kept. In the end, the program will filter out two lists that contains winning and blocking squares/moves. If a list (not empty) of winning squares/moves exists, then the first winning move will be returned. If there are no winning moves/squares, then the first blocking move will be returned. If no winning or blocking moves exist, then the program will simply return the first square/move in the pre-filtered list of all blank positions. SMART PROGRAM STRATEGY: The basic requirement program uses true and false to determine whether a move produces a winning or blocking result. In the "smart program," instead each move is given two numbers, one to determine its winning and the other to determine its blocking value. Ultimately, the move that has the highest winning (or blocking, if the blocking value is judged to be more important than the highest winning) value will be chosen. The first important part of the "smart" program is to check for a good winning situation. In order to do that, a complex calculation formula is used for it. The program first start to compute the values of two sides of a square (left and right for a horizontal line check, top and down for the vertical line check, etc.). The calculation is configured so that the initial value is 0 and the initial "increment" is set at 20. The increment is the number that will be added to the initial value whenever it encounters an X as a neighbor. For instance, as long as the next-door neighbors are Xs, the program will keep adding 20 to the initial value. Whenever the next neighbor is discovered to be an opponent piece or out of the matrix's bound, -5 will be added and afterwards the neighbor-checking process is ended. If in a situation in which the next neighbor is discovered to be a blank, 0 will be added to the value and the increment will be reduced by 2. To only way that a blank neighbor will earn the square/initial value a point is if the square/initial value already encountered an X as the first neighbor or if it has yet to encounter an X. These methods are used to insure that a line that has several Xs with spaces in between will have a smaller value than a line that has several Xs contiguously. For example, a horizontal row that has: - X X _ X - The _ square/position will have a winning value of 52 (20 + 20 + 1 - 5 on one side and 20 + 1 - 5 on the other), which is high, because placing an X there will give the program a good chance to win if its opponent doesn't act quickly. On the other hand, a horizontal row that has: O X X _ X O The _ square/position will have a winning value of 50 (20 + 20 + -5 on one side and 20 + - 5 on the other), high but not high enough, because placing an X there will not give a win anyways, since it has been blocked. On another case, a horizontal row that has: X - - _ - X The _ square/position will have a winning value of 27 (1 + 1 + 16 - 5 on one side and 1 + 18 - 5 on another), which is not high not only because there are few Xs on either side of the _ square but also because there are too many blanks between it and the other Xs to affect a quick potential win. The method to calculate a square/position's blocking value is similar, except that a blank space will never give any additional points to the square/position except in the case when it already encounters Os. In this case, -4 will be added to the total value and the neighbor- checking process is ended. This is becausing blocking an enemy does good only if it blocks many contiguous enemy squares, and not just blank squares. For example, a horizontal row that has: - O O O _ - Will have a value of 51 (20 + 20 + 20 + 1 -5 on one side and -5 on the other), high enough to set the alarm for a block. Because of the nature of the calculation algorithm, whenever a winning value of 52 or higher is encountered, that winning move will be chosen. Similar, a blocking value higher than 50 will also be chosen when the previous high winning value does not appear. When neither of the two above cases appear, the best overall value will be chosen. In the course of choosing the best winning or blocking value, in each of the two cases the move with the single highest value (out of its 4 horizontal, vertical, and two diagonal values) will be chosen. If two moves have the same highest value, then the one that has the highest combined (adding the horizontal, vertical, and two diagonal values) value will be chosen. If there is a tie in that case, then it will look at their opposite values (blocking values in the case of checking for a best win value, winning values in the case of checking for a best block value), first the highest opposite value and then the highest combined opposite value. POTENTIAL FLAWS Numerical calculation on a stone's value might not always produce a method that is best. For example, in a situation where a move has both high blocking and winning values, it might be deferred by a move that has a higher blocking value but low winning value. In addition, since this program only looks in the current situation, it cannot look into future possible moves, which can be a disadvantage.