CS4341 Project – 1 Adverserial Search (Connect-N) solution

$24.99

Original Work ?
Category: You will Instantly receive a download link for .ZIP solution file upon Payment
Share This

Description

5/5 - (4 votes)


Project Goals


The project is designing and implementing a system that plays Connect-N. The objective of Connect-N is to get N checkers in a row vertically, horizontally  or diagonally. Your program will have to use the minimax algorithm and alpha-beta pruning to determine the best move.
A variant of the Connect-N game is the Connect-four game. The task in Connect-Four is thus to get 4 checkers in a row. Connect-four is an interesting game in the sense that it is easy to understand but can involve techniques such minmax and alpha beta pruning that can provide a very interesting introduction to search and decision strategies in two player games. Connect-four was first sold in 1974 and solved mathematically by Dr Victor Allis in 1988. The broad goal of this project is to motivate search and game playing in AI.

To get an intuition about how Connect-four works (and thus connect-N), you are encouraged to play this game. It must be implicit that the difficulty level (beginner, medium, hard etc) in this game is a function of better strategies for making the next move.

This project should be done in groups of two. If you really don’t want a partner, you can do it alone. Please turn-in only one solution per group. (When turning in group work, make sure all the partners names on one everything turned in.  )

Game Description

From the link to the game above, the rules must be somewhat clear. However here is a description of the rules.

  • Board: The standard game is usually played on a 6×7 grid like shown in the wikipedia entry linked to above (For this assignment, the referee will give you different sized board, and different “N” in Connect-N.). You can imagine slots at the top of the grid into which checkers are dropped (play game above). Checkers fall down in a column either until they land on top of another checker, or until they reach the bottom level. One could correctly say that moves are fully determined by a sequence of columns, since the row is always uniquely determined by the column, and the player sequence is always alternating. Hence we will describe a move simply as a number representing the chosen column. (Note: For this project, your program should be able to handle any AxB sized board. 6×7 is just the default, and you can expect it to be the most used during testing)
  • Start: The player who gets to make the first move is chosen at random.
  • Moves: There are two kind of moves, drop and pop out. A player can choose play one move in each turn. Drop: Each player chooses a column to drop the checker into. When a checker is dropped in a column, it takes the lowest unoccupied place in that column. The first move always results in the checker being at the lowest position at some column. The second move can cause the checker to be above the checker in the previous move or the lowest position in some other column. Pop Out: A player can remove (or “pop out”) a disc of one’s own color from the bottom, if one has any discs of his or her own color on the bottom row. Popping a disc out from the bottom drops every disc above it down one space, changing their relationship with the rest of the board and changing the possibilities for a connection. Note that, for each game, a player can “pop out” a disc ONLY ONCE.  Invalid Moves: “DROP”ing on column that is already completely filled is invalid. Or choosing an undefined column. Or popping out an opponent’s discs.
  • Time Limit: There is a time limit of for each player to make a move (mentioned below).
  • End of the Game: The game ends in any of the following scenarios.
    • One of the players gets N checkers in a row (horizontally, vertically or diagonally). This player wins and the other loses.
    • The board is full but none of the players managed to get N checkers in a row. The game ends in a draw.
    • If both players have at least N checkers in a row after one move, the game will end in a draw, unless one player has more sets of N checkers in a row than the other. In that scenario the player with more sets of N checkers in a row wins.
    • If N=4 and at the end of the game one player has 4 in a row, and the other player has 5 in a row, the player with 5 in a row will win.
    • One player makes an illegal move (dropping a checker on an already filled column or dropping the checker outside the board, pop out more than once). In this case the other player wins.
    • If one player fails to respond within the time limit, then the other player wins.
Project Description
  1. You must implement a program that plays Connect-N.
  2. Your program must use the minimax algorithm with alpha beta pruning.
    • Use a utility function (i.e static evaluation) of your choice.
  3. If your minimax with alpha-beta pruning cannot expand the whole search tree in the time allowed, your program should use a game strategy:
    • Use a heuristic/evaluation function of your choice (remember that the evaluation function and the utility function must coincide on final board configurations).
    • Use a heuristic of your choice to avoid expanding the whole minimax tree. You can choose from those covered in the book (progressive deepening, heuristic continuation (singular-extension heuristic), and tapered search) or another one of your preference. We highly recommend using the progressive deepening heuristic.
  4. The better your evaluation function/heuristic, the better your program will play, and the better your grade in the project.
  5. Your program must produce only valid moves.
  6. Your program must follow the specification given above so that it can interface with other programs.
  7. If you want, you may implement a graphical interface for your program, that displays the configuration of the board during the game. Such an interface is NOT required.
  8. Your program must be able to handle a variable sized board. While most games will be played using the standard 6×7 board, we should be able to input different sized boards for tiebreakers. Make sure your program works as intended for most reasonable sizes.
  9. Similar to the above rule, the time limit per move must be variable as well. Most of the earlier rounds will use less time than the full 15 seconds for the finals, but we should be able to input any amount if one program clearly doesn’t dominate another.
Program Communication

Make sure you hand in a simple report that explains you attempt to test something empirically.
You are provided with a .zip file that contains an eclipse java project. This project has a referee class with a main method that you will run when testing your program.
The project has an abstract class called “Player”. You will create a class that extends player. This class is what you will initialize in the referee and what will be prompted for moves.
In the project there is also an abstract StateTree class. This class stores information relating to the state of the game. A simple class called RefereeBoard which extends this class is used by the referee to keep track of the board.
An instance of RefereeBoard is passed to the player as a parameter of the getMove method in player. This is how your code will get information on the current state of the game.

In the project there is a Move class. An instance of this class is returned by the getMove method of the  Player class which informs the Referee of what move your player would like to make.

In the project there is a class called SimplePlayer which provides a basic example of how a player would make decisions. Your player class will have a much more complex getMove method because you have to build a tree and min-max and alpha-beta prune.

Test Your Player

To test your player you can initialize your player as “player1” and/or “player2” in the Referee class, change any of the starting parameters as you see fit (rows, columns, N, timeLimit), then run the referee. The console should display the board state and information on what move your players tried to make and how long it took.

Tournament

   1. Your program must not consume computing resources during your opponent’s turn. In this spirit, when it is your opponent’s turn, your program should simply wait for your opponent’s move by waiting for the input line.
2. Both players will be executed on the same machine, and may not spawn processes on any other machine.
3. Points: You can earn bonus points (up to 10) on your project grade depending on how well you do in the tournament.
Important Points

* Separating the responsibilities for your program into different parts would be a good idea. (i.e. creating a class that extends StateTree which calculates the heuristic value of the state)
* Start with a simple player that can execute moves with the referee, then begin with the minimax algorithm.
* Think about your evaluation function carefully, it will be the difference between programs in the tournament

Empirical Valuation

We want you to do some experiment where you quantitatively evaluate an idea of yours. It could be comparing evaluation functions. It could be using an opening book, or decided to use memory to memorize states, or explore issues around the operation done each time. For this please explain in detail what you compared, and provide some empirical basis upon which you decided whether it was good, or not, or that your data could not tell you reliable. 
 
If you forget your stats take a look at this https://www.youtube.com/watch?v=pTmLQvMM-1M as its really important to me that you know if your results are reliable or not.
 

Report Submission 

For the due date see the class schedule.
Submit your solution via canvas. All the files should be compressed in .zip format (Please do not use other formats). Name of the project should ($username)_project1.zip and if you are working in a group your file name should be ($username1)_($username2)_project1.zip. You will lose 10 point for a wrong name.
Your .zip file should contain only your player and all the helper classes used by your player. When grading, the Referee, RefereeBoard, Player, StateTree and Move classes will be used as they were provided to you. So don’t create a player that relies on a different version on any of those classes.
 
Please name your classes something unique (like putting your initials at the end of every class you make) that way during the tournament we don’t run into an issue where two player have the same name.

Grading

100 Points Total
20 points: Minimax Implementation

20 points: Alpha Beta Pruning

20 points: Heuristic Evaluation Function

 
10 points:  Describe an experiment you did.  That could be comparing different evaluation functions.  Your grade will depend on the quality of your explanation not on whether your idea panned out.
30 points: Referee Interaction and Documentation. Implementation following the instruction in “Test your player section”. Your code can be run by the grader according to your documentation without extra work.

Related products