CS 165A – Artificial Intelligence, Spring 2020
Machine Problem 2
100 points, updated 5/21
Due Thursday, June 4, 2020 11:59pm
Notes:
▪ Make sure to read the “Policy on Academic Integrity” on the course syllabus.
▪ Any updates or corrections will be posted on Piazza.
▪ You must work individually for this assignment.
▪ Each student must turn in their report and code electronically.
▪ Responsible TA for Machine Problem 2: Karl Wang ()
▪ Visit the course website for tournament status
1 Problem Definition
You are going to implement a program that plays Five-in-a-Row (also called Gobang or Gomoku) with a human
opponent. Your program should be able to search for the best move so that it ends up winning over a human
opponent (or at least make the match very challenging). Towards this end, you should explore the Minimax
algorithm and other adversarial search algorithm improvements, like alpha-beta pruning, in order to quickly
calculate the program’s next move and eventually win.
2 Five-in-a-Row
Five-in-a-Row is a strategy board game for two players, usually played with
Go pieces (black and white stones) on a go board. Black plays first and
players alternate in placing a stone of their color in an empty cell. The
winner is the first player to get an unbroken row of at least five stones
horizontally, vertically, or diagonally.
You can read this Wikipedia article on Five-in-a-Row:
https://en.wikipedia.org/wiki/Gomoku
Finally, there are many websites online where you can practice playing
Five-in-a-Row for free.
3 Technical Details
3.1 Rules
The black player places the first piece. Then each player take turn placing pieces. The first player to form a chain
of at least 5 wins. If board is full and there is no chain greater than 5, then it ends in a tie.
Your program should not take more than 30 seconds to decide each of its move, nor take more than 2 minutes to
decide all its moves. The human player is allowed as much time as they need for their move. Running out of time
means an automatic loss. Note that the grading platform is the Linux machines in CSIL. Make sure that your
program does not exceed the 30 seconds per move time limit or 2 minutes per player time limit on these machines
(it might be running faster in your laptops).
Note: Consider limiting your programs to 5 or 3 seconds per move if you are losing to the 2 minutes rule.
3.2 Input
Your program should be able to process the following two optional command line arguments:
• -n : We will allow sizes 5*5 to 26*26. If n is not specified, the default value should be 11*11.
• -l: If this option is specified, the human opponent is going to play with the light colors. If the option is not
specified, the human player will be playing with the dark colors. In both cases, the dark players move first.
Once the execution begins, your program should be able to interact with the human player through a command
line interface. The command line interface should support only one command:
• : This command is valid when it is the turn of the human player. indicates the player’s choice
of next move, and should be represented as a pair (without spaces in between) where
the indicates the column (a, b, c, …) and indicates the row (1, 2, 3, …) of the board.
If the player tries an invalid move the program should display an error message and prompt the player for a
new move again.
3.3 Output
Whenever your program makes a move, and whenever it successfully reads in a move made by its opponent, it
must print that move to the standard output in the following format:
Move played:
The referee program will look for this line in your program’s output to determine your program’s next move. You
may additionally print other outputs, such as ASCII art representation of the current board, or declare the winner
at the end of the game. These outputs will be ignored by the referee. You can check the outputs of the provided
programs to see how your output should look like in order to be compatible with the referee script.
3.4 Implementation Restrictions
You may use C/C++, Java, or Python3 for this programming assignment. You can use C/C++, Java, and Python’s
standard library. You are also allowed to use libraries that are installed on CSIL for every user, except those that
implements machine learning algorithms, such as scikit-learn. You are not allowed to use any framework or library
that is not already installed on CSIL. Also keep in mind that your submission can’t exceed 10MBs.
4 Makefile and Executable
If you are writing in C or C++, then you should write a Makefile that compiles your binary. Name the binary
“gobang”. If your choice of language is Python or Java, then you need to provide a wrapper script that executes
your code. Name this script “gobang”. For python you might have the following simple script:
#!/bin/bash
cd "${0%/*}"
python3 gobang.py $@
and for Java:
#!/bin/bash
cd "${0%/*}"
java gobang $@
The second line sets the current working directory to the directory of the script.
The “$@” in these scripts allow command line arguments to be passed through to your code.
The grader will run a game like so:
make -C light/mp2
make -C dark/mp2
./referee.py light/mp2/gobang dark/mp2/gobang
Make sure your program can be run with these commands.
5 Judging
You will be provided a ‘referee’ script that will allow for two programs to compete. Technically, each program
will have no knowledge that it plays with another program, they will both think that they compete with a human.
The referee script will be redirecting the moves of each program to the command line interface of the other
program to simulate these human players. Using the referee, you should be able to test your program with its own
self as the opponent. The referee will also enable having a tournament to find which implementation performs the
best, given the maximum of 30 seconds per move and 2 minutes per player.
In order to render your program compatible with the referee you need to have an executable and abide by the
specific input and output rules. Your program must be compatible with the referee for grading as well. Test your
code using the referee script to ensure compatibility.
6 Report Preparation
As for the report, it should be between 1 and 2 pages in length (no more than 2 pages) with at least 11pt font size
and should consist of at least the following sections:
• Architecture: Brief explanation of your code architecture (describe the classes and basic functionality)
• Search: How you search for the best move (which algorithm you use, what heuristics, optimizations, etc)
• Challenges: The challenges you faced and how you solved them
• Weaknesses: Weaknesses in your method (you cannot say the method is without flaws) and suggest ways to
overcome them.
Note that the most important part is the Search section. There should be only one pdf report which includes all the
above (no additional readme file).
7 What and How to Submit
Once you are finished developing your code, copy all necessary source files (including header files, source code
files, the pdf report, Makefile, etc.) into a directory named “mp2” and submit the directory with the turnin
command. Do not submit files individually. Note that all directory and file names are case sensitive. For this
assignment you need to issue the following command:
turnin mp2@changhai_wang mp2
7.1 Detailed Submission Guidelines
• C/C++: Include a “Makefile” which builds the program by default (e.g. typing “make” in the mp2 directory
should build the gobang executable program), your source code files (.cpp, .c, .hpp), your header files “.h” if
you have any, your PDF report, and any other files that are needed to compile and run your code successfully.
• Java: Include your source code file “.java”, class files “.class”, an executable wrapper script named “gobang”
that executes your java code, your PDF report, and any other files that are needed to build and run your code
successfully.
• Python: Include your source code files “.py”, an executable wrapper script named “gobang” that executes
your python code, your PDF report, and any other files that are needed to run your code successfully.
In all cases, regardless of language, the grader should be able to just run “make” (if code is in C/C++) and then
execute the “gobang” executable.
8 Grading
Grade Breakdown:
• 20% Complete Report
• 10% includes Makefile and/or executable that matches specification.
• 10% accepts command line arguments; produces required outputs; no segfaults, exceptions, or logic bugs
during gameplay
• 60% Gameplay performance (your program beats our program for specific values of n)
Plagiarism Warning: We are going to use software to check plagiarism. You are expected to finish the project by
yourself without using any code from others.
8.1 Performance
You will be graded based on your program’s ability to win other AI programs! The main weight of the grade
(60%) will be based on your program’s performance so you should make your search is as optimal as possible.
You will get:
• 0/60% if your program fails to beat an adversary that randomly chooses their next move
• 30/60% if your program beats an adversary that randomly chooses their next move
• 40/60% if your program implements the basic minimax algorithm with depth >= 2
• 50/60% if your program also applies alpha-beta pruning.
• 60/60% if your program beats the baseline program (minimax with depth=2 and alpha-beta pruning)
The baseline implementation is provided to you so that you can test your own program before the final submission.
9 Tournaments!
Participation in the Tournaments is optional but can gain additional credit (and fame!). There will be two kinds of
tournaments, a pre-submission tournament and a post-submission tournament. To enter both tournaments, you
need to submit a text file named “TOURNAMENT”. This file should contain a number that specifies your preferred
board size. There should be nothing else in this file besides the number. Submissions without this file will not
participate in either tournaments.
9.1 Pre-submission tournament
The pre-submission tournament will have a defending champion. Every time you submit your code, if your
submission contains the text file TOURNAMENT, your program will be tested versus the current defending
champion. If you win, you become the defending champion. If you do not win, the defending champion will
remain the same. To become the defending champion, you also need to beat our simple AI programs which form
the baseline, so you can’t become the defending champion just by implementing random moves. For every full
day you spend as the defending champion you get 2% extra credit (plus the FAME of being the defending
champion). You will be emailed the results of your submission once the match is over. Matches will be performed
at least once per day. Do not flood the turnin submission system or you will get banned from the tournament (only
submit once you have the results of your previous submission).
9.2 Post-submission tournament
The post-submission tournament will be a tournament between all final submissions that contain the text file
TOURNAMENT. The program that wins the tournament gets 50% extra credit. The two runner-ups get 30% and
20% (for second and third position).
9.3 Gobang match setup
A single match consists of 3 games. One game with board size of 11, one game where the board size if specified
by one player, and one game where the board size is specified by the other player. If you don’t specify a board
size then it will be set to 11 by default. Keep in mind that in the game where your specified size is used, you will
be playing as the Light player. In the first game where the size is 11 the order will be random.
9.4 Winning a match
The winner of a match is the player that has at least two wins (best out of three). In case of a tie in a game during
the pre-submission tournament the defending champion gets the win. In case of a tie during the post-submission
tournament the winner will be the player that took the least total time to submit their moves during the game. If
you tie with our programs during grading it will count as your win.