In C++

Project requires code to be executable. Base Code is included at the bottom for your convenience.

Base Code for your convenience:

You will write an nxn tic-tac-toe game/program that utilizes functions and arrays. Please start early and DO NOT succumb to any temptation to look for solutions or share code with others. Description \& Requirements In this project, you will write a program to allow two players to play the classic game of Tic-Tac-Toe. The first player will be represented with x and the second player with os. In this program we will provide you a skeleton outline in and ask you to implement several functions that can call to carry-out major tasks of the game (e.g. and You MUST complete the 7 functions prototyped below and fill in the necessary parts of to call the various functions where appropriate. bool getAichoiceAndupdateGrid(char grid[], int dim, char player); chargetEntryAtRC(chargrid[],intdim,intr,intc); In all these functions, we pass the array (named in but named in all the input arguments) storing the xs,os, and blank (?) spots so that the functions can examine the game state. We will use the character ? to represent blank spots, so that the user sees they are available. Remember, arrays are passed by reference and any modification in a function is made to the original, unlike scalar values (e.g. int, double, etc.) which are passed by value. Please note that as you implement these functions, you must follow the guidelines and produce the return values that are specified in the comments above each prototype in the skeleton code. Those comments act as requirements just as much as this writeup. While you are free to define and use additional functions, you must implement and use the ones defined above. Winning To win, a player must completely fill any row, column, or one of the two diagonals with their symbol (i.e. Xs or Os). As soon as this condition occurs for any player, the program should stop and print the correct message, either: The program should then exit after printing one of the two messages above (and print nothing else afterward). Draws We want to determine if the game is destined to end in a draw and end early, declaring a draw, without needing all squares to be filled in. We will define a draw as having occurred when each row, column, and each of the two diagonals have at least one x and one 0 , since that would mean it is impossible for either player to win. This should be checked after each turn and, if satisfied, the game should stop and the following message should be printed: The program should then exit after this message (and print nothing else afterward). Important: While we may be able to determine a draw will occur even earlier (before one of each symbol exists in each row/column/diagonal), please just implement this algorithm as described above. Note: These win and draw message strings (character arrays) have been created for you in and can be output with a corresponding \[ \text { cout } \ll \text { owins_msg } \ll33 tic-tac-toe grid. But to pass several of our tests you must make your code work for a generic nxn tic-tac-toe grid (where n is an odd integer from the set 3,5,7,9, or 11). The largest grid will be 1111 and thus we will need an array of at most 121 locations (this array of 121 locations is declared at the start of Grid size We want you to implement the nn version (rather than just 33 version) of the program to have you practice generalizing patterns. We will use the variable name dim to specify n, which stands for the dimension of one side of the square grid. And all of your code should be generalized to work for a given value of . Thus, a majority of your code will use values that are some function of While we allocate the array for size 121 (i.e. 1111 ), we will not use the entire array for smaller dimensions. The user will enter the dimension via at the start of the program and then main will create the initial array contents for that size. For example, if the user enters a dimension of 3 then your could should only use entries 0 through 8 in the array. When you test your code you will always need to enter that dimension value first AND a seed value for the random number generator (RNG) before the game can truly start. While tic-tac-toe is inherently 2 dimensional and would naturally lend itself to a 2D array, we are artificially forcing you to use a 1 dimensional array, for several reasons: 2. We want you to understand how higher-dimensional arrays are "linearized" to 1 -dimension 3. It provides good opportunity to use functions to abstract implementation details such as conversion between 1D and 2D coordinates. 4. It is a good application of certain arithmetic operations required to perform the desired conversion between 1D and 2D coordinates. So, to reiterate, you will use a 1D array but can use functions like: . to move back and forth between 1D and 2D indexes, whichever is most convenient for your algorithms. 1D to 2D Array access The argument to each function is a 1D array. However, we can visualize it as a 2D array if we let the first elements be the first row, the next elements be the 2 nd row, and so on. For a 33 grid, the array contents: would correspond to a tic-tac-toe grid of: To begin the game, you should initialize the array to contain ? characters which would lead to the initial output: Put more concretely, below we show the array index correspondence to the given location in a 33 grid: A 55 grid would have this correspondence to the 1D-array of 25 elements: We assume the player knows this correspondence, so you need not print or show such a grid (i.e. one with location numbers) to the user. You will print the actual game board with x,0, and ? characters. Using math to determine row and column indexing 1. Consider the problem of iterating/walking through row 0 of the grid. (Let us assume we count rows and columns starting at 0 like an array not 1). For a 33 grid: - walking the 0th row starts at and then moves to and - walking the 1st row starts at and then moves to and - walking the 2 nd row starts at and then moves to and For a 55 grid: - walking the Oth row starts at grid[0] and then moves to, grid[2], and - walking the 1st row starts at and then moves to , , and - walking the 2 nd row starts at .. - walking the 3rd row starts at - walking the 4th row starts at ... Can you generalize the pattern to enumerate the array indices that form the i-th row? The i-th row starts at what index in the array? Put your answer in terms of i and - For a 33 grid, iterating down column 0 would mean visiting indices: 0,3,6 - For a 33 grid, iterating down column 1 would mean visiting indices: 1,4,7 - For a 33 grid, iterating down column 2 would mean visiting indices: 2,5,8 - For a 55 grid, iterating down column 0 would mean visiting indices: 0,5,10,15,20 - For a 55 grid, iterating down column 1 would mean visiting indices: 1,6,11,16,21 - For a 55 grid, iterating down column 2 would mean visiting indices: 2,7,12,17,22 - and so on... Can you generalize the pattern? To iterate down column i, we should start at what index in the array? Then we should take steps of what size? Put your answer in terms of i and 3. Finally, consider how, if you had a given row and column location (i.e. row and col) you might determine what index in the 1D-array corresponds to that location. - For a 33 grid, row =0, col =1 corresponds to index - For a 33 grid, row =1, col =0 corresponds to index - For a 33 grid, row =1, col=1 corresponds to index - For a 33 grid, row =1, col=2 corresponds to index - For a 33 grid, row =2, col =0 corresponds to index - For a 33 grid, row =2, col=1 corresponds to index - For a 33 grid, row =2,col=2 corresponds to index - For a 55 grid, row =0, col=1 corresponds to index - For a 55 grid, row =1, col= corresponds to index - For a 55 grid, row =1, col=1 corresponds to index - For a 55 grid, row =1, col= corresponds to index - For a 55 grid, row =1, col = corresponds to index - For a 55 grid, row =1,col=4 corresponds to index - For a 55 grid, row=4, col= corresponds to index - For a 55 grid, row=4, col= corresponds to index - For a 55 grid, row =4,col=2 corresponds to index - For a 55 grid, row =4,4, col= corresponds to index - For a 55 grid, row =4,col=4 corresponds to index Can you generalize the pattern? Given and col numbers could you find a mathematical expression to convert to the 1D index of the square that corresponds to that row and column? Note that this relationship should help you visit the diagonals because it might be easier to consider generating two separate indices: row and col and then converting those two values to the corresponding 1D array index. 4. To summarize you should be able to complete the following conversions using simple mathematical expressions: - Given a 1D array index, call it i, (e.g. for a 55 grid suppose you are given an index between 0-24), the row and column corresponding to that location, i, can be found as: Use the answers you found above to complete the functions and With those functions, you can call them anywhere in your code that you may want to conver a 1D index to a 2D row/column index, if it is helpful. - Given a and index and the dimension of the board we can convert to the 1D array index, call it i, by performing: 0i= (in terms of row, col, and dim) Use the answer you just found to complete the function . Call this function anywhere you might find it convenient to generate two separate indices (row, column) and then to access the corresponding character (x,0, etc.) from the grid at that row/column index, returning it to the caller. Output Your grid must be drawn in a 2D format according to the examples shown below. Consider which visualization and indexing (1D or 2D) will be most natural to this task, write loops to generate those indices, and then, if necessary, use the conversion functions described above (e.g. to access the array elements. - Sample 33 Grid Output format: - Sample 5x5 Grid Output format: Notice there is a space before and after each x,0, and ?. And, if it is not clear, there are NO blank rows. The first row is immediately followed by a row of dashes (e.g. then the second row of X,O, ?, followed by another row of dashes, and so on. Getting Input To start the game, the user must enter: - the dimension of the desired grid (e.g. 3,5,,11 ) - a seed value for the random number generator) (since our grading will not use the "random"-bot, it doesn't matter what integer you type, but just give some value; the random number generator is provided to test your Al. So the game should start off as shown below (notice the user would type the when the game starts): Player X enter your square choice [024], -1 (AI), or 2 (Random): Next, we will support three modes of inputting the desired location: - The human user can select a square for the current player. This will be selected by the user typing in an integer in the range 00 to dim2121 - The Al-bot can be requested to select the "best" location for the current player. This will be selected by the user typing in the integer - A random, free location can be requested for the current player. This will be selected by the user typing in the integer 2. (We have provided this functionality and you can use it to test your Al, since your Al should perform "better" than random selections.) The first play of the game should be made by player x. Then, at each turn you should prompt the user to enter the square number that they want to choose for their location. A simple prompt such as the one shown below would suffice, but should at least show whose turn it is (Player x or 0 ) and the legal input range: 00 to dim2121. Player X enter your square choice [08],1 (AI), or 2 (Random): Important Requirements: - If the user enters an integer that lies outside the range 00 to dim2121 or (to use the Al ), then your program should quit without printing other status messages. - If the human user chooses a square that is already occupied with an x or 0 , then prompt the user to choose again (using the same prompt format shown above) and continue doing so until they choose a blank square or give an out-of-bounds location. Note: If the Al is selected, it obviously should not choose a square with an x or 0 already. See the example below of how we want to handle input of locations that have already been chosen: Player X enter your square choice [024], -1 (AI), or -2 (Random): Player o enter your square choice [024], -1 (AI), or -2 (Random): Player X enter your square choice [024],1 (AI), or 2 (Random): Player X enter your square choice [024],1 (AI), or 2 (Random): Player X enter your square choice [024], -1 (AI), or 2 (Random): Player O enter your square choice [024],1 (AI), or 2 (Random): Once an open, valid location is chosen, update the array. We have then provided code in to print out the updated board using Important: We have already inserted the call to in in between where we ask you to write the code to get the user input and where we ask you to write code to check the game status. So, unless the user entered a location outside the legal range and you exit the program, the board should be printed (via our call to I after getting an input. Consider how some or all of this task of receiving input can be extracted into a function that is called by . Feel free to organize your code as such. Al and Random When the user enters , your code should call the [prototyped below]. bool getAiChoiceAndUpdateGrid(char grid[], int dim, char player) This function should "intelligently" choose a free location and assign it to the current by updating the grid. We have a few basic requirements for what "intelligent" means and you must meet those basic requirements for full credit. - If the current player CAN win on this move, your Al must choose one of those locations that will yield a victory - If the current player CANNOT win on this move, but the opponent could win on the next move if the current player does not BLOCK, then your Al should choose that blocking location. While those are the only requirements to get full credit, they are fairly basic and we'd like you to go BEYOND that simple approach. Since the goal of this assignment is to develop algorithms, we strongly encourage you to consider how you can choose an intelligent location for the current player beyond the two rules listed above (i.e. when they can't win yet nor need to block).. Think about how you can determine how "advantageous" a location might be for the current player. While we strongly encourage you to think hard about algorithms yourself, we don't preclude you from looking up possible options online AFTER you've thought hard about the problem. You are NOT allowed to view actual implementation code but you CAN lookup high level algorithms that don't include an actual implementation. For example, an algorithm such as minimax is commonly cited. You'd be welcome to learn more about it AFTER you've thought of your own algorithm. To implement it requires data structures and code approaches that are likely above the level we have taught so we would caution you before you try to implement it (and you don't need to implement it). To repeat, as long as you meet the two basic requirements (in the bullets above) for the Al, you'll get full credit! But then we want you to be creative and create additional logic for selecting a location when the situations above do not apply. If and when you do come up with additional Al behavior beyond the two requirements, one way you can test it is by having the opponent choose random locations. Your Al should be able to draw or win. We have provided a function that will make a random selection of an open location for the current player. It is prototyped and fully implemented in the skeleton code. You can simply call the function when necessary. It should be invoked when the user enters as the input. bool getRandChoiceAndupdateGrid(char grid[], int dim, char player); We will not test it, nor use it as part of another test. It's merely there as a convenience if you want to see how well your Al is doing. If you start a game and simply feed in alternating inputs of: your Al should at least draw. Hints - For the it will likely be useful to use a 2D indexing approach by generating nested loops (one loop generating a row index and the other a column index). Remember, if you correctly completed the getEntryAtRC (char grid[], int dim, int r, function described above, you can use your row, column indices to get the corresponding character from the grid array. Take care of spacing and printing the and - (vertical and horizontal separators). You must match the spacing format shown in this document. - For ] there are several possible approaches but the easiest is likely to again take a 2D indexing approach and write one set of loops to walk down each row to see if all the locations in a row have the same x or 0 character (again, nested for loops can help generate the row, column indices and the function can retrieve the corresponding character). Only if no winner was found in any of the rows would you then need to walk down each of the columns to see if any column has all the same player letters. Finally, you can use one loop to walk each diagonal (first the top-left to bottom-right diagonal, followed by the top-right to bottom-left diagonal). Don't try to check everything at once but break the code into portions: first check rows, then columns, then diagonal 1 , then diagonal 2. In some ways this is similar to the Distributed-OR (Succeed Early / Fail Late) Idiom in that if you find just one row, column OR diagonal with all Xs or all Os, we have a winner and can return our answer. - For bool checkFordraw (char grid[], int dim) you should likely use a similar strategy as . Remember, to be a draw each row, each column, and each diagonal must have 1 of each player letter: x and 0 . IN some ways this is similar to the Distributed-AND (Fail Early / Succeed Late) Idiom in that we have to prove ALL rows, columns and diagonals have at least 1x and 1o. If we find any row that doesn't have any Os or any Xs we can stop early and it is NOT a draw yet. So you can iterate down each row looking for a row that proves it is not a draw. Then you can iterate down each column looking for a column that proves it is not a draw. Finally, you can iterate down the two diagonals separately. \#include using namespace std; I/ The following 3 functions are helper functions to convert I/ between 1D and 2D array indices. The grid itself is stored I/ as a 1D array. However, for printing, checking who won, I/ etc. it may be easier to write loops that generate separate I/ row/column indices (i.e. treating the array like a 2D array). // The functions below should be written using the hints in the I/ writeup for performing the appropriate arithmetic conversion I/ between 1D-and 2D-indices, and can then be called in any // of the other functions when you find yourself wanting to I/ convert one to the other. /** Helper function - Given the grid array and its dimension * as well as a particular row (r) and column (c), this * function performs the arithmetic to convert r and c * to a1D index and returns that character in the grid. * For example, for dim=3 and r=2,c=1, this function * should compute the corresponding index: 7 and return grid[7]. * Use this function wherever you generate, row/column * indices and want to access that element in the grid. * Pass the row/column indices as r and c, respectively. char getEntryAtRC (char grid[], int dim, int r, int c); / * Helper function - Given a1D index returns the row * that corresponds to this 1D index. Use this in * conjunction with idxTocol() anytime you have a 1D index * and want to convert to 2D indices. / int idxToRow (int idx, int dim); / * Helper function - Given a 1D index returns the column grid [ loc ]= player; return false; \} // No viable location return true; 1 * Complete the indicated parts of main(), below. // needed. / I/ To match our automated checkers' expected output, you must output II one of the messages defined above using *one* of the cout commands II (under the appropriate condition) below: I/ cout xwins_msg endl; OR I/ cout owins_msg endl; OR I/ cout draw_msg endl; II I/ Note: Our automated checkers will examine a specific number of lines I/ at the end of the program's output and expect to see the updated board I/ and game status message. You may certainly add some debug print II statements during development but they will need to be removed to II pass the automated checks