Connect Four is a turn-based game normally played with an upright 6 x 7 (height x width) rectangular grid cage in which checkers are dropped through holes in the top. Playing: Each player is represented by a color: Red or Black. Play begins with an empty grid and the selection of the player to move first. The first player chooses any of the seven columns to drop one piece of his/her color into. Play then alternates with each player dropping one checker of his/her color into any column in the grid that is not full. If the number of checkers in any one column reaches 6, then the column is full: no more checkers may be dropped into that column. Note that because they are "dropped," the pieces are subject to the forces of gravity: A piece may never be suspended in "midair." It must be resting either directly atop of another piece (red or black), or on the bottom row of the grid (row 0). Winning: A player wins by connecting four (or more) of his/her pieces in a straight line inside the grid; this is called a connect-four. A connect-four may be horizontal or vertical (diagonal is an optional enhancement and not part of the original requirements); regardless, if four pieces of one color are adjacent to one another in a straight line, the player represented by that color wins immediately. In the following three grids below, the black player wins. (Positions are given in [row, column] format) In the unlikely event that both players have dropped all of their 21 pieces into the grid, and neither player has a connect-four, then the game is a tie: neither player wins. Before playing again after a win or a tie, all checkers must be removed from the grid. computer strategy for playing The computer player's strategy is an unsophisticated one: Each turn, the computer is governed by these three guidelines: 1) If the computer can win (i.e. achieve a connect-four), then the computer should do so. 2) If the computer cannot win, and the opposing color has three checkers connected in such a way that a connect-four will be possible for the opposing color to construct during the next turn, the computer attempts to "block" the future win. This is done by dropping a checker on either end of a horizontal three-checker line, or on top of a 3-checker column (thus preventing the human opponent from using that grid position during the next turn). If there is more than one possible "block" to make, the computer may choose whichever it wishes (using either a random selection or some other basis). 3) If neither condition 1 nor 2 is true, then the computer drops a checker into a random column that is not full. Hints for the guidelines: Since both guideline 1 and 2 involve searching for a future connect-four and determining the fourth column to drop a checker into for the winning move, most of the work for both of these guidelines can be handled by one function. The only difference is that guideline 1 would call this function by passing-in the color of the computer's checkers, whereas guideline 2 would pass-in the color of the opponent's checkers. Attaining/Blocking Vertical Connect-4s It might be easiest first to examine the color of the "top" checker in each column. Since a checker dropped into a column will always land on top of the checkers already stacked, this means that it is only necessary to count "down" (moving from a higher row to a lower one) three rows to determine if a column holds a vertical connect-3. (which will become a connect-4 once a checker is dropped into that column) Attaining/Blocking Horizontal Connect-4s Since there are seven columns, there are only four configurations that you will need to examine in order to find a potential horizontal connect-4 in any given row. The first begins at column [0] and ends at column [3]. The second begins at column [1] and ends at column [4]. The third: column [2] ... column [5]. The fourth: column [3] ... column [6]. You will need a "placeholder" variable to keep track of an empty position in a row that can be used to obtain a connect 4. In order to be an acceptable fourth/winning column for a given, row, the position - denoted by grid[row,col] - must be both (a) empty; and (b) a position that is playable (valid) during the current turn. column 5 is the only acceptable winning column for row 3. Column 2 cannot be used as a fourth-column because a checker dropped into that column would land at position [0,2], and therefore could not be used by row 3 in constructing a horizontal connect-4. Consequently, when determining if four positions in any row constitute an almost- completed connect-4, all empty positions that are "hovering in mid-air" should be ignored. (Examples of "midair" positions in the above grid are [1,2], [2,2], [4,5].) Implementation You should construct this program in two parts. For the first part, you will concentrate on creating code that will play a single connect-four game, after choosing whether the the computer will be red or black. After completing this part, you will then place that code into a function called Play() and create code so that the user can have a game playing "session" in which s/he can play as many games as they wish, and the program will keep track of the wins and losses for both the player and the computer. The first part: The Playing Board: Although a two-dimensional array is an obvious choice for the board, for this project, the board will be represented by a single array of length 42. Position [0,0] in the board will be postion 0 in the array. In general, each [row,col] position can be calculated by the function (row * 7) + col. You will need to create functions to manipulate the checkers on the game grid, check for a winning position and implement the computer's playing strategy. You may also wish to declare a second array of length 7 (perhaps called "Top") which will store the row number of the lowest empty space in the given column (for example, if column 2 is empty, the value for Top[2] would be 0, If there are three checkers in column 0, then the value for Top[0] will be 3). However, the program can also be implemented without this second array. You may wish to #define values for RED and BLACK and declare static variables for the number of rows and columns: static const int NUM_ROWS = 6, // number of rows in grid (representing height of board) NUM_COLS = 7; // number of columns in grid (representing width of board) The board can be declared as: char grid [NUM_ROWS * NUM_COLS]; //playing grid in which each position is empty, red, or black. Some suggested functions are: void Initialize(char *grid, char *Top, char initColor); // pre: RNG has been seeded. initColor is the color of the computer player (RED or BLACK) // post: The bottom row of the grid has been initialized to EMPTY. compColor is initialized to // initColor. humanColor is initialized. bool dropPiece(char *grid, char *Top, const int col, const char color); // pre: color equals RED or BLACK // post: If col is a legal grid column AND the column can hold the newly dropped checker: the checker // of the specified color is dropped into col and the function returns true. Else returns false. char checkForWin(char *grid); // post: return RED or BLACK to indicate the color of the connect-four. If no connect-four is // found, return EMPTY. If the grid is full, return 'F'. void computerMove(char *grid); // pre: There is no connect-four currently in the game grid. (i.e. the game is not over) // post: The computer player drops a piece into a column according to the defined computer strategy. void printBoard(char *grid); // pre: grid is a valid connect-four board array // post: the board grid is printed to the screen static const int NUM_ROWS = 6, // number of rows in grid (representing height of board) NUM_COLS = 7; // number of columns in grid (representing width of board) char compColor, // color of the computer player's checkers humanColor; // color of the human player's checkers int getNextRow(char *Top, const int col); // post: This function returns the first unoccupied row of column 'col'. It's used for determining // the row at which a checker would "land" if dropped into the 'col' column. int getWinningMove(const char color); // pre: color equals RED or BLACK. // post: If there are three pieces of the 'color' on the board such that a connect-four is // possible in the very next move, return the column of the fourth position in the // not-yet-achieved connect-four. (This function might make it easier to implement // guidelines 1 and 2 of the computer player's strategy) The second part: Once you have the game programmed and are able to play against the computer, you will wrap the code to play the game in a function called Play(). Below is the declaration for this function: char Play(char compColor); // post: This function allows one or two people to play Connect 4. The function returns // the color of the winning player (RED or BLACK). If there is a tie, 0 is returned. You will also need to declare variables to keep track of the number of games played, and the number of wins, losses, and ties for both the computer and the human player (Hint: Do you need win/loss/tie variables for both the computer and the human player?). Additional Requirements Allow the user(s) to play more than one game of Connect 4. Each time a player wins, one point should be added to the appropriate player's score. The program should ask the user(s) to specify the number of points to play to; once a player reaches that number, the program should announce the final winner. The user should not be able to specify a particular grid position in which to place a checker. (After all, humans don't play the game that way! :) Instead, the user should specify as input only the column s/he wishes to "drop" a checker into. Your program then determines where that checker should "land."