CS60 Project 5 ----------------- Due Nov 25th at midnight Connect 4...Now with AI! --------------------------------- The task of project 5 is to build a graphical computer game called 'link 4'. The game need only be played in 'player vs. computer' mode, but the computer mode in this project will require that you code an intelligent AI that attempts to defeat the player. First, the game. Link 4 ----------- This game is a turned based game played on a 2 dimensional, 6x6 symmetric board that can be thought of as standing up in front of you on a table, as opposed to lying flat. Each column has a number associated with it. |__|__|__|__|__|__| |__|__|__|__|__|__| |__|__|__|__|__|__| |__|__|__|__|__|__| |__|__|__|__|__|__| |__|__|__|__|__|__| 1 2 3 4 5 6 Each turn, the player may select a column that they wish to play in (not a specific space, just the column). The players piece then falls to the bottom of that column. For example, say the first player (P1) chooses column 4, the board after their play now is in the following state: |__|__|__|__|__|__| |__|__|__|__|__|__| |__|__|__|__|__|__| |__|__|__|__|__|__| |__|__|__|__|__|__| |__|__|__|P1|__|__| 1 2 3 4 5 6 Now the other player (P2) chooses column 3: |__|__|__|__|__|__| |__|__|__|__|__|__| |__|__|__|__|__|__| |__|__|__|__|__|__| |__|__|__|__|__|__| |__|__|P2|P1|__|__| 1 2 3 4 5 6 Now P1 chooses column 3: |__|__|__|__|__|__| |__|__|__|__|__|__| |__|__|__|__|__|__| |__|__|__|__|__|__| |__|__|P1|__|__|__| |__|__|P2|P1|__|__| 1 2 3 4 5 6 The plays can be thought of as 'dropping' a piece into a column. The piece falls until it hits another piece, or the bottom of the column. Plays continue until a player wins the game. A game is won if after a player's move, somewhere on the board 4 of their pieces are 'linked'. Pieces can be linked horizontally, vertically, or diagonally, but not some combination thereof. The following are examples of P1 winning (I've changed 'p' in 'P1' to lower case to show the winning pieces): |__|__|__|__|__|__| |__|__|__|__|__|__| |p1|__|__|__|__|__| |P2|p1|__|__|__|__| |P1|P1|p1|P2|__|__| |P2|P2|P2|p1|__|__| 1 2 3 4 5 6 |__|__|__|__|__|__| |__|__|__|__|__|__| |__|__|__|__|__|__| |__|__|__|__|__|P1| |__|__|P2|P2|__|P2| |p1|p1|p1|p1|__|P2| 1 2 3 4 5 6 |__|__|__|__|__|__| |__|__|__|__|__|p1| |__|__|__|P2|__|p1| |__|__|__|P2|__|p1| |__|__|P1|P2|P2|p1| |__|__|P2|P1|P1|P2| 1 2 3 4 5 6 Winning links of 4 can be anywhere on the board. The AI ------------------- While many AI game algorithms exist, one of the simplest for turn based, simple rule games is based on building a decision tree which evaluates every possible future board configuration and choosing the shortest path though the tree that leads to a winning state. If we think of boards having a 'state' and making a move puts the board in a new state, the first step would be to build a tree as follows, where S1 is the current state of the board: S1 S2 S3 S4 S5 S6 S7 Why are there six node in the second level? Well the computer can make one of six moves, but all must be evaluated. Next it would be the players turn, so from each of the states S2 - S7, six more nodes should be created for every possible player move: S1 S2 S3 S4 S5 S6 S7 SA SB SC SD SE SF SG SH SI SJ SK SL SM SN SO SP SQ SR ... ... ... Next it's computer's turn again, so for each state SA, SB, SC, etc the computer needs to evaluate six possible moves, etc. At each move or player move, the state needs to be checked to see if either the player or computer will win. If a state is found where the computer wins, the computer should make the play that moves the board closer to that state. The tree can built/checked for winning state every time it is the computer's turn, or it can be pre-built and traversed (searching for shortest path to win state) every time it is the computer's turn. How you handle the tree is up to you. What happens if a state occurs in which the player wins before a state in which the computer wins? Of course, the depth of the decision tree completely depends on the current board configuration, and as such the tree structure needs to be a implemented as a dynamic data structure. Program Requirements ------------------------ The project must present a graphical front end to the link 4 game. You may of course use your extensible object hierarchy from project 4! The graphical interface component must minimally show the following: - The board which can be as simple as a grid of white lines - Player pieces, which can be as simple as RED and BLUE squares which fill in grid squares. - A keyboard event function that accepts the number keys 1-6 for the user to select which column to make their play. In addition to the interface, the program must implement a computer AI which minimally includes the following: - has ability to build a dynamic decision tree of all future board states - has ability to decide on the next move based on the shortest path to a winning state. - has ability to decide that there is no way for the computer to win, and return a random move. - has ability to determine if the player will win in one move and make a blocking move The main game program must implement the following: - turned based game where the user goes first, followed by the computer AI, followed by the user, etc. - ability to detect if either player has won - ability to detect if all moves have been made (draw) - upon win or draw, the game must ask the user if they would like to play again. This interface can be implemented using stdin/stdout (as opposed to through the graphical context, which is left for extra credit). Turnin --------------------- The turnin tag for this assignment is 'project5' and must include all code/header files, a typescript showing compilation (no need to show it running), and an optional README file with special instructions for the grader. Extra Credit (10 pts) --------------------- - allow user to select size of board (must be symmetric) as command line argument - graphical component must reflect user defined board size - computer AI must be able to handle different board sizes - all interfaces are through graphical context (the play again question and user choice must happen through the graphical window, not using stdin/stdout). - AI must not only work towards moving to a winning state, but must also work towards blocking the player if it appears that the player can win before the computer can win. - README must describe the AI algorithm in detail