Programming Examination #2 Solution

A.  (100 points)  Othello

This examination  consists of designing and writing a single well-structured  Python program that must be committed  and pushed to your remote GitHub examination  repository  prior to the deadline. Note that your program must be named othello.py (all lower-case).

 

Late submissions  will not be accepted and will result in a zero score for the exam.

 

TA help for this examination  will not be provided.   If you have clarification  questions, they must be addressed to the graduate TA for the class.

 

The total point value will be awarded for solutions that are complete, correct, and well structured.   A "well structured"  program entails good design that employs meaningful  functional  decomposition,  appropriate comments  and general readability  (descriptive  names for variables and procedures,  appropriate  use of blank

space, etc.)   If you are not sure what this means, review the "well-structured"  program requirements  provided in

Lab2.

 

Note that your work will be graded using, and must function correctly with, the current version of Python 3 on CSE Labs UNIX machines.  If you complete this programming  exam using a different system, it is your responsibility  to ensure it works on CSELabs machines prior to submitting  it.

 

The rubric includes the following specific (accumulative)  point deductions:

 

•   Missing academic  integrity pledge                            -100 points

•   Syntax errors                                                                 -50 to -100 points

•   Misnamed  source file or incorrect repository          -25 points

•   Use of global variables                                                -25 points

•   Missing main program function                                 -25 points

 

 

 

Examination  Repository

Examination  files must be submitted  to GitHub using your remote exam repository.   Exam repositories  have already been created for each registered  student and are named using the string exam- followed by your X500 userID (e.g., exam-smit1234).   You must first clone your exam repository  in your local home directory

before submitting  the materials for this exam.  If you are having difficulty, consult the second Lab from earlier in the semester or the GitHub tutorial on the class webpage.   If your exam repository  is missing or something  is amiss, please contact the graduate TA.  DO NOT SUBMIT YOUR EXAM FILES TO YOUR LAB/EXERCISE REPOSITORY!

Background

The modern board game, Othello, is a commercially  produced version of a game that originated  in the 19th century called 'Reversi'.   It's an interesting  2-player game of strategy played on an 8x8 grid in which each player places tokens on the board in order to cover more grid cells than their opponent.   Each token is a two-sided  disk with white on one side and black on the other.  The basic premise of the game is that as each player plays a

token of his/her color (white or black), they 'flip' over all the intermediate  tokens of their opponent.   The game ends when all the grid cells have been covered with tokens, or no allowable  move can be made.

 

Read the following Wikipedia  description  of the game:

 

www.wikipedia.org/wiki/Reversi

 

The following website has an interactive  version that you can play.  You should try it to make sure you are comfortable  with how the game is played:

 

 

www.othelloonline.org

 

 

 

Program  Requirements

Using Turtle graphics, write a well-structured  Python program named othello.py that will play an interactive  game of Othello.    Your program will pit a human player against the computer.

 

Your program must do the following:

•   Include the academic  integrity pledge in the program source code (details below)

•      Use turtle graphics to implement  the graphical interface (set the turtle speed to 0 in order to speed things up).

•      The graphical display must include numeric row and column number "headers"  to assist the human player in determining  what to enter.

•      Maintain  the board state using a 2-dimensional  list (matrix) with 8 rows of 8 columns.   Each board location  must indicate if it has a black token, a white token or is unoccupied.   The upper-left  cell is board location [0][0], and the lower right cell is board location [7][7].

•      The "human" player will play black and the computer will play white.  The human player will always go first.  Your program must include a loop that will alternate between soliciting  the human player's move (row, column) and making the next "computer"  play.  The game continues until the entire board is occupied or until either player can no longer make a valid move.  The game can also be terminated prematurely  by entering a null-string  as input.

•      A message should appear when the game ends indicating  which player is the winner, along with the final score.

•      Avoid using global variables (global constants are perfectly fine).  You will need to pass the "board" matrix as an argument to the various functions that need it.

•      Solicit input using the turtle .textinput()function.   The input should consist of the row and column for the next (human) play.

•      Include a pure function: selectNextPlay(board)  that will be called to get the computer's  next play.  You can be as creative as you wish, however it is acceptable  to simply make a random choice from any of the remaining  valid moves.

•      Include  a pure Boolean  function:  isValidMove(board,row,col,color)  that will return True if the specified  row,column  is a "valid" move for the given color and False otherwise.   Note that for a move to be valid, it must satisfy three conditions:

1.    It must be unoccupied

2.    At least one of its 8 neighbors must be occupied by an opponent's  token (opposite of color)

3.    At least one of the straight lines starting from row,col and continuing  horizontally,  vertically  or diagonally  in any direction must start with an opponent's  token and end with a token matching the color argument.

•      Include a pure function: getValidMoves(board,color) that will scan every cell of the board and return a list of (row,column)  tuples that are valid plays for the indicated  token color.

•      You can find descriptions  of the .textinput()and.write()turtle functions (along with all the Turtle graphics module functions)  here:  docs.python.org/3/library/turtle.html .

 

 

Constraints:

•   You may use any built-in Python object class methods (string, list, etc.)

•   You may use imported functions and class methods from the turtle, random and math

modules only

 

 

Academic  Integrity Pledge

The first lines of your program must contain the following text (exactly as it appears), replacing the first line with your full name and X500 ID.  If this statement does not appear in your program source, you will receive a score of zero for the exam.

 

# <replace this line with your name and x500 ID (e.g., John Smith smit1234

 

# I understand  this is a graded, individual  examination  that may not be

# discussed with anyone. I also understand  that obtaining solutions or

# partial solutions from outside sources, or discussing

# any aspect of the examination  with anyone will result in failing the course.

# I further certify that this program represents  my own work. None of it was

# obtained from any source other than material presented as part of the

# course.

 

 

Suggestions:

 

•      You will find this project much easier if you employ the principles  of "top-down,  functional decomposition",  as discussed in lecture, and implement  your program as a collection  of short, simple functions.

•      The graphical display is fairly uncomplicated  if you set the world coordinates  to match the board (leaving some room for the border) and use the turtle.stamp()  method.  You simply change the turtle shape to "square" and "stamp" it at each grid cell location.   Then change the turtle shape to "circle" and "stamp" each token when it is played (in the appropriate  color)

•      You will find it useful to construct (and use!) a "helper" function that will convert "row, column" board coordinates  to "x, y" turtle coordinates!

•   The most complicated  aspect of this program is determining  the lines of opponent tokens to "flip" when

a move is made (this is also needed to determine  if a proposed move is "valid").  One way to do this is to subtract the corresponding  row and column coordinates  of the first two cells in a "line" (horizontal, vertical, diagonal) to obtain a row and column "delta value".  This delta value can be used in an

iteration loop to identify all the cells in that line.

 

•   One of the challenges  in this problem is dealing with the grid border.  For example, the cell at [0][0]

does not have 8 neighbors, it has 3.  You might find it useful to construct a helper function that returns a list of neighbors,  given a cell's row and column.  Another useful helper function would return a Boolean indicating  if a particular  row, column pair is "inGrid".