FourInARow
0. Development
We are requiring that you do all your development in Codio and not OUTSIDE editors.
1. Background
The game of 4-in-a-row (or Connect4 by Hasbro) is a popular children’s game where two players take turns dropping colored chips into 1 of n columns (usually, n=6 but we will allow any value of n) with the goal of having 4 chips in a row (of the player’s color – we will use red and yellow). An online example is available here.
Also, here is a video overview of the project from Prof. Redekopp. Note: it is 25 minutes but should give you reasonably clarity on how to jump in.
2. The Rules
Setup
The game starts with an empty n x m board (grid) with rows numbered 0 (at the bottom) to n−1 (at the top) and columns (the x-coordinate) numbered 0 to m−1 (left to right). In our code we refer to n as the size of the y-dimension, or ydim, and m as the size of the x-dimension, or xdim. The typical children’s game uses ydim=xdim=6.
Gameplay
Players (player 0 = red and player 1 = yellow) take turns choosing a column (an x coordinate) and dropping their specific colored chips into that column.
The Goal
The winner of the game is the first player to get 4 of their chips in a line (horizontally, vertically, or diagonally). At that point the game immediately ends. A draw may occur with the game ending once all squares are full.
Modes
Our implementation will support 4 modes of play (though, you will really only have to implement 2 modes). We will specify the mode as a command line argument that you can use to control your implementation according to the following description.
· 2P or 2p (Human vs. human): Your program will use cin to receive alternating input from each choosing an x-coordinate to drop their chip. We start with input from red player then switch to yellow player and so on. This is the main mode you will implement.
· test (RandomAI vs. RandomAI): This mode uses a random selection AI for both red and yellow player. We have already implemented this random AI and we encourage you to read through it and learn from its approach. It randomly selects 1 of the columns that are not full and places the current player’s chip in that column. You need only ensure you call our random AI function for both players when in test mode. You (and our tests) can use this mode to create random board configurations to check if your code to detect a winner is functioning correctly (or potentially a draw…even though a draw is unlikely in a random game).
Randomized Testing
One common strategy in software and hardware development is randomized testing. Rather than manually defining test cases, we can randomly generate inputs and verify that the program behaves either in an expected fashion or at least does not crash.
· 1P or 1p (Human vs. UserAI): This mode uses human input for the red player and a simple AI that you will write to automatically choose a column to drop the yellow player’s pieces. Developing a sophisticated AI is a major undertaking, but we do NOT expect you to do so. Instead, we have a few basic expectations and leave any more sophisticated approach as an optional undertaking based on your interest and desire. This is a great exercise in algorithmic thinking. How could you intelligently choose where to place your chip?
For now, the only requirement is that your AI try to block the opponent if they could win on their next turn. This is the only aspect of the AI we will test. However, at the very least you should also make your AI be able to WIN if it could do so on its current turn (i.e. has 3 in a row and a blank spot that could create FOUR in a row).
· 0P or 0p (RandomAI vs. UserAI): This mode will not be tested, but is instead for you to test your UserAI. The idea is that even a simple AI that you devise should be able to beat a random AI most of the time. You can use this mode to test your AI.
3. Coding Background
3.1) Grid/Board Representation
We can envision our board/grid as a 2D array and use a Cartesian coordinate system where(y,x)=(0,0)represents the lower left corner of the board.
We flip the traditional ordering and use (y,x).
We do this since y is the row index to our 2D array and C++ programs work more efficiently when we use the ROW (y) as the first index and COLUMN (x) as the second index
y=n-1,x=0 y=n-1,x=1 ... y=n-1,x=m-1
. .
. .
. .
y=1,x=0 y=1,x=1 ... y=1,x=m-1
y=0,x=0 y=0,x=1 ... y=0,x=m-1
We use the y-coordinate first to access the appropriate row first and then the x-coordinate as the column index.
3.2) 2D Array Allocation
To allocate the grid/board, we must use dynamic allocation. This is because we do not know the size of the grid until runtime. Remember that a single call to new can only allocate a 1D array. Thus, you will need to allocate each row of the 2D array as a separate 1D array.
The way to allocate a 2D array in C++ is: use new[] once to allocate a 1D array of pointers, then using a loop containing new[] to allocate many 1D arrays whose starting addresses are stored in the pointer array elements. See the dynamic memory exercise nxmboard and deepnames on Edstem (in class exercises).
Memory leaks
Remember that you need to deallocate everything that you allocate. This means that every call to new[] needs a matching call to delete[]. Otherwise, your program will have a memory leak!
Typically, the pattern you use to allocate is the same pattern you will use to deallocate, but just in reverse order.
But what type of array should we use? Since each entry in the grid can be a RED piece, YELLOW piece, or BLANK, we will use an enum (enumerated type) to make our code more readable.
enum BoardValue { BLANK=0, RED, YELLOW};
Thus, to have a 2D dynamically allocated grid of BoardValue elements, we would need a BoardValue** pointer as the top-level variable. This would point to an array of BoardValue* and each of those would point to an array of BoardValues.
You will implement separate functions: allocateBoard(...) and deallocateBoard(...) to abstract these tasks. More info is on the next page.
3.3) Command Line arguments
This program will use command line arguments to provide some basic configuration info: NROWS (y−dim), NCOLS (x−dim), the mode: 2P/2p, 1P/1p, 0P/0p, or test, and, finally, a seed for the random AI (or if your user AI needs random numbers),
So for example, the program may be started as:
$ ./connect4 6 8 2P 42
This would indicate a 6 row by 8 column board with the game operating in two player (human vs. human) mode and a seed of 42 for the random number generator .
Recall, that to accept command line arguments the signature for main should be updated to:
int main(int argc, char* argv[])
Review your lecture slides to recall what these two arguments store and how to use them. But in short argv[0] will be the program executable name while the information of interest (6 8 2P 42) starts with argv[1]. Also, all arguments are C-strings and need to be converted to integers. Part of your task in main() is to perform. that conversion for the number of rows and columns (i.e. y-dim and x-dim) as well as the seed.
4. File Structure, Code Organization, and Solution Executable
For this project we have split the code into separate source files. We will decompose our implementation into many functions and place those functions in the file c4lib.cpp and headers in c4lib.h. The main() function which will perform. high level tasks and call the various functions will be in connect4.cpp. You will need to compile all the files together, practicing multifile compilation.
Recall that:
· undefined reference errors mean you haven’t compiled all the .cpp files
· we never compile .h files on the command line.
At this point, we would recommend you take a few minutes and look over the skeleton files we have provided to orient yourself to the various functions you will need to write and some of the arguments and data that will be passed and returned.
In particular, read the documentation of each function in the c4lib.h file.
In an effort to ensure you are clear on how the program should behave and what is expected, we have placed a pre-compiled solution executable, ./connect4-sol that you can run. This is a compiled version of our solution. If you are in doubt about how the program should handle a case, just try that case with our solution to see what we expect.
If you like, try it now. Run:
$ ./connect4-sol 6 6 2P 0
You can then play the game by typing in column numbers where you would like to place the player’s piece.
Or try the test mode with seed 111, which will run a full, random simulation of a game until someone gets 4 in a row.
$ ./connect4-sol 6 6 test 114
Randomized Testing
Once you have reviewed the skeleton code we have provided and understand the general game, you can begin your implementation. We have a suggested order of implementation described below with some notes about specific functions.
In addition to the instructions on this page, the skeleton code comments act as further guide and requirements. Follow those closely.
1. Handling Command Line arguments
In connect4.cpp, complete the handling of command-line arguments. In particular, convert the appropriate arguments so set the integer ydim (number of rows), xdim (number of columns), and the seed.
2. Allocation and Deallocation
Implement the allocation and deallocation functions in c4lib.cpp
BoardValue** allocateBoard(int ydim, int xdim);
void deallocateBoard(BoardValue** board, int ydim);
Review lecture slides and coding examples for how to perform. allocation. Recall the 2D board/grid array is made of BoardValue elements, which though they are like ints are their own type. Thus, we can also have pointers of type BoardValue* or BoardValue**.
3. Human Input
A reasonable development checkpoint goal is to be able to compile and run a simpler version of the program that allows a 2P human v. human “game” where there is no winner but players just take turns placing pieces (i.e. your program gets input and updates the board). Get something simple like this to work before trying to determine if there is a winner or draw.
To that end, next implement the getNextHumanInput() function to prompt the current player to enter (via the keyboard) the column to drop their piece. When you get the input, ensure you can legally place the current player’s chip (i.e. the column is in the range 0 to xdim-1 and that the appropriate column is not full). If it is a viable column to place a chip, update the board by placing the selected piece in the column (in the lowest row that is blank) and return false. Return true otherwise (if there is an error in the input).
bool getNextHumanInput(
BoardValue** board,
int ydim, int xdim,
int *y, int *x,
int currentPlayer);
Please notice that we pass two pointers to integers. These are output parameters that are utilizing pass-by-reference so that the function can have more than 1 "return value". We want to return the coordinates of where the player’s piece was placed. This can be helpful in our code to determine if there is a winner. More on this in a bit.
To aide in the implementation of this function and the AI functions, it would be useful to determine which row a chip would land in when dropped into a column. For this, we have a helper function prototyped and waiting for you to implement in c4lib.cpp.
int findYValue(BoardValue** board, int ydim, int x);
This function should return -1 if the given column (specified by x) is full. Otherwise, it should return the smallest blank row in that column.
One other note is that in c4lib.cpp we have a global array (you may not create other global variables) playerToValue. This array can help you convert the currentPlayer integer to the appropriate BoardValue enum.
Handling Bad Input
If there is an error with the input value as described above, the program should exit with the appropriate message: "Early exit". This will also allow a kind of "exit code". If the user wants to quite the game early, they need only enter an out-of-bounds column.
4. Initial Testing
At this point you could write a basic gameplay loop in main() to alternate getting input from each player and ensuring the placement of chips is correct. The game should quit with an invalid column input.
Setting up this initial test may require some alteration to the skeleton code. To get the test working, you may need to comment out some code or add dummy values so that your code will compile. This is likely worth it so you can flesh out early bugs now and not have to debug so much later on.
5. Winning
Now move on to implement hasWon() to determine if the current player has four in a row.
bool hasWon(
BoardValue** board,
int ydim, int xdim,
int sy, int sx,
int currentPlayer);
5.1 Approaches
You may implement this function in one of two ways. One may be easier to implement but less time efficient while the other would hold the opposite properties.
· Method 1: Scan through the entire 2D array (rows and columns) searching for 4 in a line. This method may appear like more work but may be easier to implement. Also, this method does not require the knowledge of where the current player just placed their piece (i.e. sy and sx) since we’ll look for ANY 4 pieces of the same color in a line.
· Method 2: Use the location where the current player placed their piece (i.e. sy and sx) and determine if that has created a sequence of four in a row. Rather than checking the entire board, we need only check if the new piece has created 4 consecutive pieces in a line. This should take less computation than the previous method, but may be just a bit trickier to implement.
As soon as some player has won, the game should halt (and give no more turns) and print either Red wins or Yellow wins
Whatever method you choose (and it is 100% your choice…no better grade will be achieved if you choose one over the other), read the hints in the next section.
5.2 Checking in Directions
Implementing your checks for a winner will require scanning through the 2D array in specific directions (vertical, horizontal, and diagonal). Spend some time thinking about how you might implement that. Does the scan in each direction need to be a separate loop …OR… is there a way to generalize the directional scan so that one loop (the outer loop) iterate through the directions to scan while the inner loop scans (enumerates the coordinates) in the specific direction.
To that end, consider the usefulness of the following arrays and how they might be useful.
const int NDIRS = 4;
const int xDirDelta[NDIRS] = { 0, +1, -1, +1};
const int yDirDelta[NDIRS] = {+1, 0, +1, +1};
6. Draws
Implement the isDraw() function to determine whether the game is over due to a draw, which is defined as the board being full without a winner. Return true if there is a draw and false, otherwise.
bool isDraw(
BoardValue** board,
int ydim, int xdim);
The game should quit and print Draw anytime isDraw returns true.
7. AI
Now implement your user AI. Remember, the only requirement is it must block the opponent if they could win on their next turn. We encourage you to also implement the ability to choose a winning location, if the current player can win on the next turn.
bool getUserAIInput(
BoardValue** board,
int ydim, int xdim,
int *y, int *x,
int currentPlayer);
Beyond that, we strongly encourage you to consider some basic approaches and rules of thumb for how you could select a move to make that would be most advantageous? Experiment a little as you are able and have time. Try to run your AI in 0P more to play against the provided random AI.
We leave this open ended so that it is truly your own creation and would be something you could research and improve on as you are able and incorporate into your own portfolio of work. Because it is fully your creation, you are welcome to post this function publicly if you wish (e.g. on your personal Github account…but only this function) to show to potential employers or others.
As you learn more data structures to create and store “potential” player moves to explore alternative scenarios and even implement an optimal AI using the minimax algorithm (look up more if you are interested).
8. Putting it all together
Now complete main() and its primary gameplay loop as well as ending code. Be sure you change the current player (between 0 and 1) on each iteration. (Since we are using integer values 0 and 1 to track the current player, think about how you could use a simple arithmetic expression to switch from 0 to 1 or vice versa without using an if statement.)
Once you feel you have finished your code, we encourage you to compile and run it in a few modes to test it for yourself. Don’t just jump to the automated tests. It will be much more intuitive and easier to find bugs as you test the code yourself than parsing and considering the test cases we may have come up with.
Hint: Remember what you have learned about compiling programs consisting of multiple files, and apply that when you compile this program.
Also, we strongly suggest you run your code via valgrind before you run the automated tests. It will be easier to debug in the console than in the Codio automated test output logs. Recall to run valgrind you can use this command line:
valgrind --tool=memcheck --leak-check=yes ./connect4 6 6 2P 0
or whatever command line arguments you desire.
Once you believe your code is working move on to the next page and run the automated tests to earn credit.
Manual tests
Manual tests
Don’t just jump to automated tests!. Run the program yourself several times at the command line and test various aspects. For example, play 2 Players where you control both players and see if different winning patterns will work (e.g. diagonals, verticals, horizontals, etc.). Does a scenario where a draw work? You can even then move on to the AI.
If not, add print statements or use the debugger. But until you can get simple tests like this working, please don’t proceed to automated tests.