This assignment is to be done individually.
The following is offered with apologies to the vast majority of students who do their work honestly and take their university learning seriously:
Your instructor takes academic integrity seriously and has no tolerance for plagiarism or any other form of academic misconduct. Failure to respect these guidelines will result in you receiving a grade of zero on this assignment.
Acceptable collaboration between students, provided it is acknowledged explicitly in your report and code, might include:
Unacceptable collaboration and violations of academic integrity include, but are not limited to:
The game of "dynamic connect-3" is played on a 5x4 grid as follows:
Starting from the initial position illustrated below, players take turns
moving one piece of their colour by one square, either horizontally
or vertically. White plays first. Pieces can only move to unoccupied
squares. The winner is the first player to line up three of its
pieces either horizontally, vertically, or diagonally.
The threefold repetition rule applies to conclude a draw.
Implement a game-playing agent to play the game of dynamic connect-3. The agent must be capable of playing either white or black.
Your interface should be a simple text-only system, which displays the current board state as a matrix of comma-separated characters, with 0 denoting a white piece, 1 denoting a black piece, and suitably formatted whitespace denoting an empty square. For example, the starting board configuration above would be represented as follows:
0 , , , , 1 1 , , , , 0 0 , , , , 1 1 , , , , 0Each square in the grid can be labeled by its <x,y> position, with 1,1 corresponding to the top-left square. Moves are entered by specifying the position of the piece to move in the form <x,y> followed by one of the compass directions, N, S, E, W. For example, to move the black piece at the bottom left of the board one square to the right, the command would be 14E.
For this part of the assignment, implement the minimax search to evaluate the game tree. Each terminal node should be evaluated as being either a win for white or a loss for white, with corresponding large values (positive and negative).
Because it is unlikely that your program will be able to expand the search tree all the way to terminal states until late in the game, you will have to implement some form of depth-limited cutoff. The nodes at this level can be evaluated with a heuristic evaluation function that provides a meaningful value representing the "goodness" of non-terminal states as well. The initial (naive) heuristic you should use is:
H(n) = <number of runs of 2 white pieces> - <number of runs of 2 black pieces>
In your report:
In Part I of this assignment, our evaluation function was extremely simplistic. Your task in Part II is to design an improved evaluation function for non-terminal nodes and demonstrate that it leads to superior performance. For reasonable speed of play (and as necessary to compete in the in-class game tournament), your program must output its move no more than 10 seconds after input of the opponent's last move.
In your report:
It is quite possible that players with equally matched heuristics will repeatedly reach a draw. Therefore:
In actual game play, it is possible for both players to repeat the same sequence of moves, leading to a cycle in the game tree. Such cycles are costly in both time and space, reducing the efficiency of the game-playing agent. In order to avoid generating cycles of moves in the search tree, a naive solution would be to maintain an array of all board configurations (and their associated values) inspected previously. Of course, this is insufficient and impractical, but you can do better.
In order to obtain the bonus marks:
In order to permit coordination with other players for the class tournament and ensure that time constraints of 10 seconds per move are respected, your agent will communicate by TCP with the game server, running on the specified server_hostname and server_port. The instructor is running the "official" game server on 132.206.74.211 port 12345, which you are free to use for testing during development.
Your initial submission (due September 26 by 12:00) must compile (or interpret) successfully on the Trottier Engineering Linux machines and run correctly through the game server, both playing white and black, or you will not be eligible to participate in the class tournament. From past experience, please make sure you test this early in your development or you will likely be disappointed.
The first message from any player to the server must specify the gameID and colour, e.g., "game37 white". The server automatically matches white and black players using the same gameID. Each (legal) subsequent message sent to the server corresponds to a move and is echoed back to both players. Moves are specified as described above.
The server is responsible for parsing the messages, validating their syntax, and sending back replies to both players. However, it does not retain the state of the game in memory nor validate the moves. That remains your responsibility. Humans can connect to the server with telnet, e.g., telnet 132.206.74.211 12345 to play against an agent program.
For the benefit of diagnostics, the server will return human-readable error messages as appropriate. Failure to transmit a valid move to the DC4Server within the time constraints allowed by the server will result in an automatic loss of the game. Potential draw situations will be assessed by the (human) judge.
You may program your assignment in any computer language of your preference, provided it can be compiled and run on the Trottier Engineering Linux machines (TR5130GU-<x>.ece.mcgill.ca where x ∈ [1,15]). Note that we will use these for the class tournament, so you should tune your program's search depth (and conduct your timing for Part I) on these machines. To login, use your McGill UEA (first.last@mail.mcgill.ca) and your regular MCF password.
Your assignment must be submitted through moodle to allow for peer- and self-assessment. The submission must contain:
In addition to the peer- and self-assessment of your submission, your agent's performance in the class tournament will earn up to 5 points. With the inclusion of a bonus component, your assignment submissions can earn a maximum of 25 points out of a pre-bonus total of 22. The breakdown is described as follows:
| Component | Weight |
| Part I.1 | 5 |
| Part I.2 | 5 |
| Part II.3 | 5 |
| Part III.4 | 2 |
| Tournament | 5 |
| Total | 22 |
| Bonus | 3 |
Last updated on 12 September 2016
by Jeremy Cooperstock