Cmput 455 Assignment 2


Due Oct 18, 11:55pm on eClass. Submit via eClass submission link on the main eClass course page.
Late submission (with 20% deduction) Oct 20, 11:55pm. Submit via separate eClass link for late submissions.

Assignment Overview

In this assignment, you develop a perfect endgame solver for the game of Gomoku. You also integrate your solver into a player, based on our starter code, which is an Assignment 1 sample solution. This player will play randomly at first, but will then play a perfect endgame as soon as it can solve the game.

To review the game Gomoku, see Assignment 1.


  1. Review the Assignments page for general questions about assignments.
  2. As in assignment 1, make sure you have Python 3, NumPy and GoGui 1.51 set up. You can review the procedures under Lecture 3 activities.
  3. Also, check the Assignment 2 preview and "more preview" in the lecture slides.
  4. Download assignment2.tgz and expand it. The directory assignment2 contains:
  5. For reference, download the Lecture 8 python codes which include solvers for TicTacToe.

Goals of the Assignment

Implement the following functionality by adding or modifying existing GTP commands:

  1. Implement a GTP command
    timelimit seconds
    The argument seconds is an integer in the range 1 <= seconds <= 100. This command sets the maximum time to use for all following genmove or solve commands, until it is changed by another timelimit command.

    Before the first timelimit command is given, the default should be set to 1 second. The public test cases show examples.

  2. Implement a new GTP command solve which attempts to compute the winner of the current position, assuming perfect play by both, within the current time limit.



    Your GTP response should be in the format:

    = winner [move]

    In the response, winner is either b, w, draw, or unknown. Write unknown if your solver cannot solve the game within the current time limit. Solving always starts with the current player (toPlay) going first. If the winner is toPlay or if its a draw, then also write a move that you found that achieves this best possible result. If there are several best moves, then write any one of them. If the winner is the opponent or unknown, then do not write any move in your GTP response. See the examples in public test cases.

  3. genmove color

    Here, the argument color is either 'b' or 'w'. A version of the genmove command is already implemented in the starter code. You should change its behavior as follows:

    1. If the game is not over yet, the program should use the solver to try to play perfectly. The solver must respect the current time limit as described under timelimit above. Note that the time limit is per move, not for the whole game.
    2. If the game is not solved within the timelimit, or if toPlay is losing, then the genmove command should just play a random move.

Public Test Cases

We have grouped our assignment2-public-tests.gtp test cases into three categories.
Easy - our simple sample solver can do them within the time limit given.
Medium - our simple solver is too slow, but our better solver can do them.
Hard - even our better solver times out. These may be good test cases for checking your time limits and your GTP response in these cases. But if you can solve them, good for you!

There are comments in the gtp file which indicate these groups. To speed up your own testing, it may make sense to separate them into smaller groups and only run the most informative ones for you.

All the tests fail for the starter code, since it does not implement the new commands. Note that our given test cases only cover a small subset of possibilities. For full evaluation, we will use a more comprehensive set of tests.

Other GTP Commands

Many other GTP commands are already implemented in the starter code. Do not break their functionality, since we will test your program using those commands, such as:

boardsize, clear_board, cpu_time, name, version, play,...

You are free to add to the implementations of these commands if you need it, e.g. depending on your approach, you may need to do something extra in the play command. But do not break the existing functionality.

These commands are used by the test script. In this assignment, for convenience we will use multiple calls to boardsize and clear_board within the same gtp file, so make sure this use case still works in your solution.

Pre-submission Test and Submission

Follow the same general steps as in assignment 1 to create your presubmission.log file and your submission, but (of course) using your assignment2 directory, assignment2.tgz as file name, and assignment2-public-tests.gtp as test. Remember to include your new presubmission.log and readme.txt.

Hints and Details - Read them All


There will again be 5 marks for this assignment.

Both sets will contain a mix of easy, medium and hard test cases. We will also test the player. The difficulty of these cases may vary, depending on which improvements you implement.

Code that does not run, or just hardcodes the public tests case by case, will receive a mark of 0. If your code needs fixes, you need to submit a revised version before the late submission deadline. TA will not attempt to fix your code under any circumstances. Use the discussion forum or consult the teaching team in case of questions.

Created: Jan 27, 2019 Last modified: Aug 6, 2021

Martin Müller