Your cart is currently empty!
Guidelines This is a programming assignment. You will be provided sample inputs and outputs (see below). Please understand that the goal of the samples is to check that you can correctly parse the problem definitions and generate a correctly formatted output. The samples are very simple and it should not be assumed that if…
Guidelines
This is a programming assignment. You will be provided sample inputs and outputs (see below). Please understand that the goal of the samples is to check that you can correctly parse the problem definitions and generate a correctly formatted output. The samples are very simple and it should not be assumed that if your program works on the samples it will work on all test cases. There will be more complex test cases and it is your task to make sure that your program will work correctly on any valid input. You are encouraged to try your own test cases to check how your program would behave in some complex special case that you might think of. Since each homework is checked via an automated A.I. script, your output should match the specified format exactly. Failure to do so will most certainly cost some points. The output format is simple and examples are provided. You should upload and test your code on vocareum.com, and you will submit it there. You may use any of the programming languages provided by vocareum.com.
Grading
Your code will be tested as follows: Your program should not require any command-line argument. It should read a text file called “input.txt” in the current directory that contains a problem definition. It should write a file “output.txt” with your solution to the same current directory. Format for input.txt and output.txt is specified below. End-of-line character is LF (since vocareum is a Unix system and follows the Unix convention).
Note that if your code does not compile, or somehow fails to load and parse input.txt, or writes an incorrectly formatted output.txt, or no output.txt at all, or OuTpUt.TxT, you will get zero points. Anything you write to stdout or stderr will be ignored and is ok to leave in the code you
submit (but it will likely slow you down). Please test your program with the provided sample files to avoid any problem.
Academic Honesty and Integrity
All homework material is checked vigorously for dishonesty using several methods. All detected violations of academic honesty are forwarded to the Office of Student Judicial Affairs. To be safe you are urged to err on the side of caution. Do not copy work from another student or off the web. Keep in mind that sanctions for dishonesty are reflected in your permanent record and can negatively impact your future success. As a general guide:
Do not copy code or written material from another student. Even single lines of code should not be copied.
Do not collaborate on this assignment. The assignment is to be solved individually.
Do not copy code off the web. This is easier to detect than you may think.
Do not share any custom test cases you may create to check your program’s behavior in more complex scenarios than the simplistic ones considered below.
Do not copy code from past students. We keep copies of past work to check for this. Even though this problem differs from those of previous years, do not try to copy from homeworks of previous years.
Do not ask on piazza how to implement some function for this homework, or how to calculate something needed for this homework.
Do not post code on piazza asking whether or not it is correct. This is a violation of academic integrity because it biases other students who may read your post. Do not post test cases on piazza asking for what the correct solution should be.
Do ask the professor or TAs if you are unsure about whether certain actions constitute dishonesty. It is better to be safe than sorry.
Project description
In this project, we will play the game of Halma, an adversarial game with some similarities to checkers. The game uses a 16×16 checkered gameboard. Each player starts with 19 game pieces clustered in diagonally opposite corners of the board. To win the game, a player needs to transfer all of their pieces from their starting corner to the opposite corner, into the positions that were initially occupied by the opponent. Note that this original rule of the game is subject to spoiling, as a player may choose to not move some pieces at all, thereby preventing the opponent from occupying those locations. Note that the spoiling player cannot win either (because some pieces remain in their original corner and thus cannot be used to occupy all positions in the opposite corner). Here, to prevent spoiling, we modify the goal of the game to be to occupy all of the opponent’s starting positions which the opponent is not still occupying. See http://www.cyningstan.com/post/922/unspoiling-halma for more about this rule modification.
In more details (from https://en.wikipedia.org/wiki/Halma):
Setup for two players:
Note: we only consider the two-player variant here; this game can also be played by four players but we will not explore this here.
The initial setup is shown below for black and white players. We will always use this exact initial setup in this homework.
Play sequence:
We first describe the typical play for humans. We will then describe some minor modifications for how we will play this game with artificial agents.
o One move to an empty square:
Below we show examples of valid moves (in green) and invalid moves (in red). At left, the isolated white piece can move to any of its empty 8 neighbors. At right, the central white piece can jump over one adjacent piece if there is an empty cell on the other side. After one jump is executed, possibly several other valid jumps can follow with the same piece and be combined in one move; this is shown in the sequence of jumps that start with a down-right jump for the central piece. Note that additional valid moves exist that are not shown (e.g., the central white piece could move to some adjacent empty location).
Note the invalid moves: red arrow going left: cannot jump over one or more empty spaces plus
one or more pieces. Red arrow going left-down: cannot jump over one or more pieces plus one
or more empty spaces. Red arrow going down: cannot jump over more than one piece.
Playing with agents
In this homework, your agent will play against another agent, either created by the TAs, or created by another student in the class. For grading, we will use two scenarios:
Note that we make a difference between single moves and playing full games because in single moves it is advisable to use all remaining play time for that move. While playing games, however, you should think about how to divide your remaining play time across possibly many moves throughout the game.
In addition to grading, we will run a competition where your agent plays against agents created by the other students in the class. This will not affect grade. But the top agents will be referred to a contact at Google for an informal introduction. There will also be a prize for the grand winner.
Agent vs agent games:
Playing against another agent will be organized as follows (both when your agent plays against the reference minimax agent, or against another student’s agent):
A master game playing agent will be implemented by the grading team. This agent will:
or your move is invalid according to the rules of the game, your agent loses the game.
winning agent will be declared the winner of this game.
Input and output file formats:
Input: The file input.txt in the current directory of your program will be formatted as follows:
First line:
Second line:
A string SINGLE or GAME to let you know whether you are playing a single move
(and can use all of the available time for it) of playing a full game with potentially
many moves (in which case you should strategically decide how to best allocate
your time across moves).
A string BLACK or WHITE indicating which color you play. The colors will always be
organized on the board as follows:
(black starts in the top-left corner and white in the bottom-right).
Third line: A strictly positive floating point number indicating the amount of total play time remaining for your agent.
Next 16 lines: Description of the game board, with 16 lines of 16 symbols each:
For example:
SINGLE
WHITE
100.0
BBBBB………..
BBBBB………..
BBBB…………
BBB………….
BB…………..
…………….
…………….
…………….
…………….
…………….
…………….
…………..WW
………….WWW
…………WWWW
………..WWWWW
………..WWWWW
In this example, your agent plays a single move as white color and has 100.0 seconds. The board configuration is just the one from the start of the game.
Output: The file output.txt which your program creates in the current directory should be formatted as follows:
1 or more lines: Describing your move(s). There are two possible types of moves (see above):
E 11,15 10,15
This moves the leftmost white piece on the bottom row of the board to the left. The resulting board would look like this, given the above input.txt:
BBBBB………..
BBBBB………..
BBBB…………
BBB………….
BB…………..
…………….
…………….
…………….
…………….
…………….
…………….
…………..WW
………….WWW
…………WWWW
………..WWWWW
……….W.WWWW
Or it could contain:
J 12,15 10,13
which is a jump along the left-up diagonal for a bottom piece. Note that here we have only one jump, but there could be several (one per line in output.txt) if the board configuration allows (see example 3 below). The board would look like this after this jump, given the above input.txt:
BBBBB………..
BBBBB………..
BBBB…………
BBB………….
BB…………..
…………….
…………….
…………….
…………….
…………….
…………….
…………..WW
………….WWW
……….W.WWWW
………..WWWWW
………..W.WWW
Notes and hints:
We expect that simple content in a format of your choice would be sufficient, but if you want to save/load complex data structures, have a look at things like boost::serialization or the C++11, header-only cereal library at https://github.com/USCiLab/cereal (written by our former students).
Example 1:
For this input.txt:
SINGLE
WHITE
100.0
WWWWW………..
WWWWW………..
WWW………….
WWW.W………..
WW…………..
…………….
…………….
…………….
…………….
…………….
…………….
……….B…BB
………….BBB
………….BBB
………..BBBBB
………..BBBBB
one possible correct output.txt is:
E 4,3 3,2
Example 2:
For this input.txt:
SINGLE
WHITE
6.6
WWWWW………..
WW.WW………..
WWWW…………
WWW.W………..
WW…………..
…………….
…………….
…………….
…………….
…………….
…………….
…………B.BB
………..B.BBB
………….B.B
………..BBBBB
………..BBBBB
one possible correct output.txt is:
J 4,3 2,1
Example 3:
For this input.txt:
SINGLE
BLACK | |
23.33 | |
WWWWW | ……….. |
W.W.W | ……….. |
WWW…………. | W………. |
WW… | |
WW…. | W……… |
……………. |
…….W……..
…………….
…………….
………BW…..
………..B….
…………..BB
…………BBBB
…………B.BB
………….BBB
………..BBBBB
one possible correct output.txt is:
J 9,9 11,9
J 11,9 11,11
J 11,11 13,13