The goal of this problem is to implement the Connect-Four game between a computer and a human player. Throughoutthislab, wewillrefertothehumanplayeras “Alice”forshort. Abriefdescriptionof the Connect-Four game follows. You can find much more information about this game on the web, for example at http://mathworld.wolfram.com/Connect-Four.html. You can actually play the game against a computer at www.mathsisfun.com/games/connect4.html.
RulesoftheGame: Connect-Fourisatwo-playergameplayedonaverticalboard 7 columnsacross and 6 rows high. If you were to buy the game at a toy store, the board might look like this: See image.
Each player begins the game with 21 identical stones (alternatively called pieces, chips, tokens, etc.). The two players alternate in making moves. Throughout this lab, the stones of the player that makes the first move are marked by X, while the stones of the player that moves second are marked by O. Each move consists of a player dropping a stone into one of the seven columns. Because the board is vertical, stones dropped into a given column always slide down to the lowest unoccupied row of that column. A column that already contains 6 stones is full, and no other stones can be placed in this column (attemptingto do so constitutesan invalidmove). The objectiveof each player is to place four of his/her stones on the board so that they form a horizontal, vertical, or diagonal sequence. The first player that is able to do so wins, and the game stops at this point. If all the 7×6 = 42 stones have been placed on the board without either player winning, then the game is considered a draw.
In this lab, the function main()that implements the Connect-Four game between Alice and the com- puter is given to you in the file connect4.c, which you should download from the course website at http://ece15.ucsd.edu/Main/Homeworks.html. As you will see (on the next page), the function main()calls five other functions, namely:
You are required to implement these functions in the file connect4 functions.c. Note that for- ward declarations of these functions are also given to you, in the file connect4 functions.h which you should download from the course website. Therefore, you cannot change the function pro- totypes — that is, the name of the function, its return type, and the type(s) of its parameter(s). Descrip- tions of these five functions follow shortly, but first here is the function main()from connect4.c. See image.
Note that symbolic constants BOARD SIZE HORIZ and BOARD SIZE VERT are defined in the file connect4 functions.has 7 and 6. Now, here is a description ofthe functionscalled by main().
This function does not take any input. It prints a welcome message for Alice, and then asks her if she would like to make the first move. Here are a couple of examples: See image.
The function then reads from stdin the input typed by Alice, and clears the input buffer (in case sheenteredmorethanonecharacter)using while (getchar()!= ’\n’). IfshetypednorN, the function returns 2 indicating that Alice will be the second player to move. In all other cases, the function returns 1, givingAlice theadvantage of the first move(the computeris a gentleman).
This function receives (a pointer to) the board array as input, and then prints the current state of the board to stdout. The function expects the value of every cell in the board array to be either 0, 1, or 2, where 1 denotes stones of the first player (which should be printed as X) while 2 denotes stones of the second player (which should be printed as O). A board cell whose value is 0 corresponds to a place on the board that is not occupied by a stone of either player.
The print-out of the board to stdout should be formatted as follows. The width of every cell is three characters, and the stone occupying this cell (if any) is the middle character. Vertical lines separate between the cells in the same row, while the rows themselves are separated by a line of hyphens along with ‘+’ characters. Right under the board, the function should print the indices of the columns, with each such index centered in its column. Here is an example: See image.
This function receives (a pointer to) the board array and a player number (either 1 or 2) as in- put. It then makes a valid random move. To this end, the function should generate uniformly at random an integer m in the range 1,2,...,BOARD SIZE HORIZ using an (appropriately normalized) call to the rand() standard library function. It should then verify that this inte- ger m constitutes a valid move, by calling the function is column full(). If m is a valid move, the function should return m. If not (that is, if the m-th column is full), the function should repeat the process until a valid move is generated by rand(). Note that the function assumes that at least one cell in the array board is 0; otherwise it enters into an infinite loop! Prior to returning m, the function should also update the state of the board by making the function call update board(board,m,computer num).
Thisfunctionreceives(a pointerto)theboardarray anda playernumber(either1or2)as input. ThefunctionpromptsAliceto enterher move,reads from stdintheinputentered by Alice, then clears the input buffer using while (getchar()!= ’\n’). If Alice enters anything other than an integer in the range 1,2,...,BOARD SIZE HORIZ, the function should say “Not a valid move. Enter a column number!,” then prompt Alice again to enter her move. If Alice enters an integer m in the range 1,2,...,BOARD SIZE HORIZ, the function should verify that the corresponding column is not full by calling the function is column full(). If the column is full, the function should say “This column is full. Try again!” and again prompt Alice to enter a move. If Alice does enter a valid move m, the function updates the stateoftheboard viathecall update board(board,m,player num), and then returns m. Here is an example of a call to display board() followed by a call to player move():
This function receives as input (a pointerto)the boardarray and an integerlast move, which is interpreted as the index of the column (in the range 1,2,...,BOARD SIZE HORIZ) where the most recent stone was played. The function calls check winner() to determine whether the game has been won by either player. If so, the function should print “Player X won!” or “Player O won!” and return true. If there is no winner, the function checks whether the game is a draw (no spaces left on the board). If so, the function should print “Tie game!” and return true. Otherwise, the function returns false, indicating that the game is not yet over.
You have probably noticed that (some of) the five functions described above call upon other functions, specifically the functions:
This is a common practice in programming, wherein a given task is broken into smaller and smaller components. Concretely, this means that you are required to implement the three functions above, in the file connect4 functions.c. The forward declarations of these functions are already given in the header file connect4 functions.h. Here is their description.
This function receives as input (a pointer to) the board array and an integer m which is expected to be in the range 1,2,...,BOARD SIZE HORIZ. The function returns true if the m-th col- umn of the board is full (already contains BOARD SIZE VERT stones), and false otherwise.
This function receives as input (a pointer to) the board array, an integer m which is expected to be in the range 1,2,...,BOARD SIZE HORIZ, and an integer player num which should be either 1 or 2. It then updates the board by changing the appropriate entry in the m-th column from 0 to player num. Note that the m-th column of the board is stored in board[m-1][]. Also note that the function must determine which row in the m-th column to update (using the rule that a stone dropped into a given column always slides down to the lowest unoccupied row).
This function receives as input (a pointerto)the boardarray and an integerlast move, which is interpreted as the index of the column (in the range 1,2,...,BOARD SIZE HORIZ) where the most recent stone was played. The function then checks whether the placement of this most recent stone results in a win (four stones on the board forming a consecutive horizontal, vertical, or diagonal sequence). If so, the function returns the player number (either 1 or 2) of the winning player. If there is no winner, the function returns 0.
In addition to the eight functions described above, you are welcome to declare and implement other functions, although you are not required to do so. For example, you might wish to break down the func- tion check winner() into three functions that check for a winning sequence in each of the three possible directions: check horizontal(), check vertical(), and check diagonal(). If you do implement additional functions, you should write both the definitions and the forward decla- rations of these functions in the file connect4 functions.c.
Here is a sample run of the entire program, assuming that the executable file is called connect4. This run illustrates a situation where Alice wins the game. The user input is underlined, as usual.
To earn extra credit in this lab, you should implement a winning strategy for the Connect-Four game. The better your strategy, the more extra-credit points you are likely to receive. Specifically, you need to implement the following function:
int best move(int board[][BOARD SIZE VERT], int computer num)
in the file connect4 functions.c that you submit. A forward declaration for this function is al- readyprovidedinthefileconnect4 functions.h. Thefunctionshouldbeidenticalinitsfunction- alityto thefunctionrandom move()described on pp.4–5, withoneimportantdifference: insteadof generatingarandommove,thefunctionshouldreturnthebestmove(thatyoucan come-upwith)ineach position. Of course, if you would like your best move() function to call other functions, you are welcometodoso: declareanddefinetheseadditionalfunctionsinthefileconnect4 functions.c.
The function best move() that you submitwill be, first, tested to verify that it produces valid moves andcorrectlyupdatesthestateoftheboard(usingtheupdate board(board,m,computer num) functioncall). Allthebest move()functionsthatpassthetestwillplayagainsteachotherinaround- robin competition. Since making the first move gives a distinct advantage in the Connect-Four game, each pair of best move() functions A and B will play each other twice: once with A making the first move, and once with B making the first move. The round-robin competition will be scored as in chess: for each game played, a win is 1 point, a draw is 0.5 points for both players, a loss is 0 points.
The best move()functionthattakesfirstplace(ortiesforfirstplace)intheround-robincompetition will be awarded 100 extra-credit points. The best move() function that places last in the compe- tition will not receive any extra credit. All the other best move() functions will earn extra-credit points prorated linearly according to their rank in the competition. For example, if 21 students take part in the competition and there are no ties, then first place will earn 100 points, second place will earn 95 points, third place 90 points, ..., 19-th place 10 points, 20-th place 5 points, and last place 0 points.