Contents

• Assignment Overview
• Setup
• Rules of Binary Game
  • Differences between Binary Game and Binary Puzzle
• Text Commands
• Public Test Cases
• Testing Procedure
  • Examples
• What to Submit
• Do Your Own Pre-submission Test
• Marking
• Details - Read Them All!
  • Details of the play command

Cmput 455 Assignment 1

Due Sep 16, 11:55pm. Submit via eClass submission link on the main eClass course page. The link will open about a week before the deadline.
Late submission (with 20% deduction) Sep 18, 11:55pm. Submit via separate eClass link for late submissions. This link will open after the regular deadline.

• First, read the Assignments page for general questions about assignments.
• Form teams and submit your team information using this link by Sep 12 . Also see Teams.
• Also, check the Assignment 1 preview in the lecture slides.

In this assignment, you implement the rules and a random player for Binary Game, a two player game inspired by the single player Binary Puzzle. All later assignments in this course will also use this game. You implement your solution by modifying the assignment 1 starter code in file a1.py (see below). The main steps are:

1. Implement the rules of Binary Game, including creating an empty board, checking which moves are legal, detecting a win, and playing a given move.
2. Write a random Binary Game player based on the starter code.
3. Test your program on the public test cases, and on more tests of your own design.

Setup

1. First, make sure you have completed your Activities up to and including 3c. In these activities you set up Python 3 and NumPy.
2. Download and expand assignment1.tgz . Go to the directory assignment1, which contains:
   • A program a1.py as your starter code. Start with this code to implement your solution.
   • A file assignment1-public-tests.txt with sample test cases for your program.
   • A program a1test.py. Use this code to test your solution. See below for details.

Rules of Binary Game

Binary Game is played on a rectangular grid of width n and height m. The game starts with an empty grid. Two players called 1 and 2 alternate to fill one of the empty cells in the grid with a binary digit, 0 or 1, subject to the constraints below. Player 1 goes first. The player who makes the last move wins. In other words, a player who does not have any legal move loses. This will happen sooner or later as the grid fills.

The constraints on a move are:

• Triples constraint: You cannot have three consecutive 0, or three consecutive 1, in a row or column. No 000 or 111.
  • Example: in the row .00.11., the only two legal moves are to 100.11. and to .00.110. Any other move would create a triple. And after one of these two moves, no more digits can be placed in this row.
• Balance constraint: The count of both zeroes and ones in each row and column cannot exceed half the length of that row or column (rounded up for odd lengths).
  • Example: on a 5x1 board ..... , you can place at most three 0 in total, and at most three 1.
  • Example: on the 4x1 board 01.0, you can only place a 1, since there are already two 0.

To determine whether a move is legal, you have to consider both the row and the column for that move, and check that all constraints are satisfied.

Differences between Binary Game and Binary Puzzle

If you have never heard of Binary Puzzle, you can ignore this section. The main difference is that in the single player puzzle, you must fill the board completely in order to solve the puzzle and "win". However, in the two player game, you try to play in a way such that the opponent will run out of moves first. Usually, this will happen before the whole board is full, because there will often be "illegal" cells where neither playing a 0 nor a 1 is legal. An example is the middle cell on the 00.11 board.

Text Commands and Answers

We will test your program using the text commands below. The commands are already outlined in the starter code, as a stub that does nothing useful. You need to implement these commands as indicated below. Commands and answers use the following format:

command
output (0 or more lines, depending on command)
= 1

Here, the last line = 1 after output is the command status, which indicates that the command was successfully executed. If there is an error, then write a command status

= -1

instead, which indicates failure. See details and examples below.

• game n m
  

  This command creates a new game on an empty rectangular grid of width n and height m (both in the range from 1 and 20). It only requires the command status as output.

• show
  

  This command shows the current state of the grid, one line per row, followed by the command status. Example:

  show
  ..0
  1..
  = 1
  

• play x y digit
  

  Place the digit (0 or 1) at the given (x,y) coordinate. x increases from left to right, starting at 0. y increases from top to bottom, starting at 0. So the top left corner has coordinates 0 0, and the bottom right is at n-1 m-1. You need to implement basic error handling and return the proper command status. See Details of the play command below. Example:

  play 1 2 0
  = 1
  

• legal x y digit
  

  Check if this move (in the same format as in play) is legal. Answer yes or no. The command status is = 1.

  Usage example (on empty 3x3 board):

  game 3 3
  = 1
  legal 0 0 0
  yes
  = 1
  

• genmove
  

  This command generates and plays a random move and gives the move as its response. The move format is the same as for play: x y digit. If there is no legal move, output resign. The command status is = 1. See Examples below.

• winner
  

  This command checks if the game is over and outputs one of the following game results:

  1
  2
  unfinished
  

  Output unfinished if the game is not over yet - the next player still has a move. The command status is = 1.

Public Test Cases

The public test cases are in file assignment1-public-tests.txt in the assignment1 directory. Most tests currently fail, since our starter program does not implement the game-specific functions. See Testing Procedure below for examples.

Note that our given test cases include only a small number of cases. For evaluation, we will use a more comprehensive set of tests.

Testing Procedure

All our tests will be on grids of size 20x20 or smaller. As in assignment1-public-tests.txt, test cases are written as text files containing a sequence of commands. Each command is followed by the expected correct answer on the next line.

What to Submit

Submit a single tgz file called assignment1.tgz which contains exactly the following (and nothing else):

A single directory assignment1 which contains all the files in your solution, namely:

1. All the files from the original assignment1 directory, but with the python code in a1.py modified to solve the assignment.
2. Your presubmission.log file.
3. A file readme.txt which lists the names and student IDs of your team. List the designated submitter first.

Do Your Own Pre-submission Test

Follow the steps below on a standard Linux undergraduate machine, and create a text file presubmission.log that shows a copy of your command line presubmission testing.

1. Make sure the content of your assignment1 folder is correct, then create your submission with a command like tar -cvzf assignment1.tgz assignment1
2. Use the Linux script command to log your testing session
3. Copy your assignment1.tgz into a new directory
4. Unpack it
5. Changed Sep 12 Run python3 ./a1test.py with your program, using assignment1-public-tests.txt as input:

   python3 a1test.py a1.py assignment1-public-tests.txt
   

6. Stop script logging here with the command exit
7. Add file presubmission.log to your assignment1, and compress it again
8. Use tar -tf for a final check of your assignment1.tgz contents. Use the checklist below
9. If you see extra files included in your tgz file that do not belong:
   • Use tar options such as --exclude=__pycache__ to get rid of them.
10. Fix any problems, then submit on eClass when you're ready

Marking

There will be total of 5 marks for this assignment.

• 1 mark for your file presubmission.log which shows the log of your correct test execution on a standard Linux undergraduate machine, and your readme.txt file (see below).
• 2 marks for passing our public test cases
• 2 marks for passing our private test cases

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.

Details - Read Them All!

• Where to implement things: Implement all your code in the assignment1 folder. You may create new files within this folder, but it might not be necessary for this assignment.
• Our tests will only use legal text commands with meaningful arguments, except for testing the error handling in the play command. You do not need to implement any other error checking.

Details of the play command

Attempt to play a given digit at the given coordinate. First check if the move is legal according to the rules of Binary Game. If it is, then play the move, update the board according to the rules, and print the default reply. If the move is not legal, then output an error message and do not change the board. The format of an error message is:

= illegal move: "copy of the input argument(s)" reason

The possible reasons for error messages are listed below. Check them in the order given and output the first error only:

• wrong number of arguments Explanation: the play command takes exactly three arguments
• wrong coordinate Explanation: one or both of the coordinates are not integers that correspond to a valid x or y coordinate
• wrong number Explanation: Any third argument that is not a digit 0 or 1
• occupied Explanation: Play in a cell that already contains a digit
• three in a row Explanation: move violates the triples constraint in rules, creates a pattern 000 or 111 in a row or column
• too many 0 Explanation: move violates the balance constraint in rules
• too many 1 Explanation: move violates the balance constraint in rules

Examples

These are some examples. More examples are in the public tests file.

game 5 1
= 1

play 0 0 1
= 1

play -1 9 a 1
= illegal move: -1 9 a 1 wrong number of arguments

game 2 2
= 1

play 0 0 0
= 1

play 1 0 0
= illegal move: 1 0 0 too many 0

game 1 1
= 1

show
.
= 1

play 0 0 1
= 1

show
1
= 1

winner
1
= 1

Last modified: Sep 5, 2024, Martin Müller