辅导CS 165A调试C/C++程序

- 首页 >> Java编程

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. 

站长地图