Problem Set 14

Preliminaries

In your work on this assignment, make sure to abide by the collaboration policies of the course.

Don’t forget to use docstrings and comments and to take whatever other steps are needed to create readable code.

If you have questions while working on this assignment, please come to TA help hours or post them on Piazza.

Make sure to submit your work on Gradescope, following the procedures found at the end of Part I and Part II.

due by 10 p.m. EDT on Saturday, October 21, 2023

Suggseted self-deadline of Friday, October 20, 2023

See also the Frequently Asked Questions FAQ

Problem 1: A Connect Four Board class

50 points; pair-optional or group-of-three-optional

See the rules for working with a partner on pair-optional problems for details about how this type of collaboration must be structured.

This problem provides additional practice with defining new classes in Python. You will create a class that represents the board for a game of Connect Four. Later in the problem sets, you will create a computer player to play against!

Background

Connect Four is a variation of tic-tac-toe played on a 6x7 rectangular board:

The game is played by two players, and the goal is to place four checkers in a row vertically, horizontally, or diagonally. The players alternate turns and add one checker to the board at a time. However, because the board stands vertically, a checker cannot be placed in an arbitrary position on the board. Rather, a checker must be inserted at the top of one of the columns, and it “drops down” as far as it can go – until it rests on top of the existing checkers in that column, or (if it is the first checker in that column) until it reaches the bottom row of the column.

The standard board size for Connect Four is six rows of seven columns, but your Board class should be able to handle boards of any dimensions. However, for simplicity we will preserve the four-in-a-row requirement for winning the game regardless of the board size (even for boards with dimensions less than 4x4).

Your tasks

To start, open a new file in VS Code and save it as ps14pr1.py. Implement the Board class in that file by completing the tasks described below.

1. Write a constructor __init__(self, height, width) that constructs a new Board object by initializing the following three attributes:

   • an attribute height that stores the number of rows in the board, as specified by the parameter height

   • an attribute width that stores the number of columns in the board, as specified by the parameter width

   • an attribute slots that stores a reference to a two-dimensional list with height rows and width columns that will be used to store the current contents of the board. Each slot will contain one of the following characters:

     • a space character, ' ', to represent an empty slot.

     • an uppercase X character, 'X', to represent a checker from one of the two players.

     • an uppercase O character, 'O', to represent a checker from the other player. Be careful that you consistently use an uppercase O for this purpose, and not the zero ('0') character.

     The board is initially empty, so all of the slots should initially contain a space character, ' '. To ensure that you are creating separate independent rows (as opposed to copies of the reference to the same row), you could take an approach similar to the one that we took in [Problem Set 7][ps7]. However, a simpler alternative approach is to use a list comprehension:

     self.slots = [[' '] * self.width for row in range(self.height)]
     

2. Write a method __repr__(self) that returns a string representing a Board object.

   Each slot should take up one space, and all columns should be separated by vertical bar ('|') characters. Additionally, the columns should be labeled at the bottom with a column number. Here is an example for an empty 6x7 board:

   >>> b = Board(6, 7)
   >>> b
   | | | | | | | |
   | | | | | | | |
   | | | | | | | |
   | | | | | | | |
   | | | | | | | |
   | | | | | | | |
   ---------------
    0 1 2 3 4 5 6
   

   In order to keep the column numbers in line, the numbering should be done modulo ten, as this larger (5x15) example shows:

   >>> b2 = Board(5, 15)
   >>> b2
   | | | | | | | | | | | | | | | |
   | | | | | | | | | | | | | | | |
   | | | | | | | | | | | | | | | |
   | | | | | | | | | | | | | | | |
   | | | | | | | | | | | | | | | |
   -------------------------------
    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4
   

   The beginning of the __repr__ method has already been done for you below. Copy this code into your ps14pr1.py file and add the code needed to include the hyphen characters (-) at the bottom of the board and the column numbers beneath it.

   def __repr__(self):
       """ Returns a string representation for a Board object.
       """
       s = ''         # begin with an empty string
   
       # add one row of slots at a time
       for row in range(self.height):
           s += '|'   # one vertical bar at the start of the row
   
           for col in range(self.width):
               s += self.slots[row][col] + '|'
   
           s += '\n'  # newline at the end of the row
   
       # Add code here for the hyphens at the bottom of the board
       # and the numbers underneath it.
   
       return s
   

   Notes:

   • The __repr__ method needs to return a single string that represents the entire board. Therefore, the method must build the string one piece at a time and can only return the finished string at the end. It should not do any printing.

   • Recall that the string '\n' represents the newline character. Therefore, you can get multiple lines into a single string by including '\n'. For example:

     >>> s = 'I am the top line.'
     >>> s += '\n'
     >>> s += 'I am the second line!\n'
     >>> print(s)
     I am the top line.
     I am the second line!
     
     >>>
     

     This is the approach taken by the code we have given to you. You will need to take a similar approach in the code that you add to complete the method.

3. Write a method add_checker(self, checker, col) that accepts two inputs:

   • checker, a one-character string that specifies the checker to add to the board (either 'X' or 'O').

   • col, an integer that specifies the index of the column to which the checker should be added and that adds checker to the appropriate row in column col of the board.

   We encourage you to begin your add_checker method as follows:

   def add_checker(self, checker, col):
       """ put your docstring here
       """
       assert(checker == 'X' or checker == 'O')
       assert(0 <= col < self.width)
   
       # put the rest of the method here
   

   Note that we begin with assert statements that validate the inputs for the parameters checker and col. If the condition given to assert is not true–e.g., if the input provided forchecker is something other than the string 'X' or the string 'O'–then assert will cause your code to crash with an AssertionError. Using assert in this way can help you to find and debug situations in which you accidentally pass in incorrect values for the parameter of a function.

   Other notes:

   • Remember that the checker slides down from the top of the board. Therefore, your code will have to find the appropriate row number available in column col, and place the checker in that row.

   • We reviewed a buggy version of this method in lecture that you may find it helpful to review.

   • This method does not need to check that col is a legal column number, or that there is enough space in the column col. That checking will be done in a different method.

   Examples:

   >>> b1 = Board(6, 7)
   >>> b1.add_checker('X', 0)
   >>> b1.add_checker('O', 0)
   >>> b1.add_checker('X', 0)
   >>> b1.add_checker('O', 3)
   >>> b1.add_checker('O', 4)    # cheat and let O go again!
   >>> b1.add_checker('O', 5)
   >>> b1.add_checker('O', 6)
   >>> b1
   | | | | | | | |
   | | | | | | | |
   | | | | | | | |
   |X| | | | | | |
   |O| | | | | | |
   |X| | |O|O|O|O|
   ---------------
    0 1 2 3 4 5 6
   

4. Write a method reset(self) that should reset the Board object on which it is called by setting all slots to contain a space character.

   Hint: There are two ways of writing this method. One way involves looping over all slots of the board to set them to a space character. Can you think of a simpler way?

5. Copy and paste the following method into your Board class, ensuring that proper indentation is preserved:

   def add_checkers(self, colnums):
       """ takes in a string of column numbers and places alternating
           checkers in those columns of the called Board object, 
           starting with 'X'.
       """
       checker = 'X'   # start by playing 'X'
   
       for col_str in colnums:
           col = int(col_str)
           if 0 <= col < self.width:
               self.add_checker(checker, col)
   
           # switch to the other checker
           if checker == 'X':
               checker = 'O'
           else:
               checker = 'X'
   

   The method accepts a string of column numbers, and places checkers in those columns by alternating between 'X' and 'O' checkers. It is useful for quickly creating a board to test your other methods.

   Example:

   >>> b2 = Board(3, 3)
   >>> b2.add_checkers('0200')
   >>> b2
   |O| | |
   |X| | |
   |X| |O|
   -------
    0 1 2
   

6. Write a method can_add_to(self, col) that returns True if it is valid to place a checker in the column col on the calling Board object. Otherwise, it should return False.

   The method should make sure that col is in the range from 0 to the last column on the board and that the specified column is not full.

   Examples:

   >>> b1 = Board(2, 2)
   >>> b1
   | | |
   | | |
   -----
    0 1
   
   >>> b1.add_checker('X', 0)
   >>> b1.add_checker('O', 0)
   >>> b1
   |O| |
   |X| |
   -----
    0 1
   
   >>> b1.can_add_to(-1)
   False                        # column number is too low
   >>> b1.can_add_to(0)
   False                        # column is full
   >>> b1.can_add_to(1)
   True
   >>> b1.can_add_to(2)
   False                        # column number is too high
   

7. Write a method is_full(self) that returns True if the called Board object is completely full of checkers, and returns False otherwise.

   Hint: You may find it helpful to use the can_add_to method that you wrote above.

   Examples:

   >>> b2 = Board(2, 2)
   >>> b2.is_full()
   False
   >>> b2.add_checkers('0011')
   >>> b2
   |O|O|
   |X|X|
   -----
    0 1
   
   >>> b2.is_full()
   True
   

8. Write a method remove_checker(self, col) that removes the top checker from column col of the called Board object. If the column is empty, then the method should do nothing.

   This method may not seem useful now, but it will become very useful when you implement your own intelligent Connect Four player!

   Examples:

   >>> b3 = Board(2, 2)
   >>> b3.add_checkers('0011')
   >>> b3.remove_checker(1)
   >>> b3.remove_checker(1)
   >>> b3.remove_checker(1)     # column empty; should have no effect
   >>> b3.remove_checker(0)
   >>> b3
   | | |
   |X| |
   -----
    0 1
   

   We also encourage you to try printing or evaluating the board after each of the individual calls to remove_checker.

9. Write a method is_win_for(self, checker) that accepts a parameter checker that is either 'X' or 'O', and returns True if there are four consecutive slots containing checker on the board. Otherwise, it should return False.

   Remember that a win in Connect Four occurs when there are four consecutive checkers of the same type either horizontally, vertically, or diagonally. Moreoever, there are two diagonal orientations: going “up” from left to right, and going “down” from left to right.

   Suggested Approach
   One way to approach this method is to consider each possible anchor checker that could start a four-in-a-row run. For example, all of the “anchors” that could start a horizontal run from left to right must be in a column at least four slots away from the end of the board. This constraint will help you avoid out-of-bounds errors. Here is some starter code that illustrates this technique:

   def is_horizontal_win(self, checker):
       """ Checks for a horizontal win for the specified checker.
       """
       for row in range(self.height):
           for col in range(self.width - 3):
               # Check if the next four columns in this row
               # contain the specified checker.
               if self.slots[row][col] == checker and \
                  self.slots[row][col + 1] == checker and \
                  self.slots[row][col + 2] == checker and \
                  self.slots[row][col + 3] == checker:
                   return True
   
       # if we make it here, there were no horizontal wins
       return False
   

   Notes:

   • The backslash characters in the if condition tell Python that the line of code will continue on the next line.

   • The expression self.width - 3 keeps the checking in-bounds, since a horizontal “anchor” cannot begin at or beyond that column. Testing in different directions will require different guards against going out-of-bounds.

   We suggest that you create a separate helper function for each of the tests that you need to check to determine if the specified checker has won. We have given you is_horizontal_win; now create is_vertical_win, is_down_diagonal_win (for diagonals that go down from left to right), and is_up_diagonal_win (for diagonals that go up from left to right). Having a separate function for each type of run will make your code easier to test and understand. Once these helper functions are working, have is_win_for call them to determine what it should return.

   Hints:

   • Here again, we encourage you to begin your is_win_for function with an assert statement that validates the input for checker:

     def is_win_for(self, checker):
         """ put your docstring here
         """
         assert(checker == 'X' or checker == 'O')
     
         # call the helper functions and use their return values to
         # determine whether to return True or False
     

   • We would advise against explicitly counting checkers to see if you reach four, since the four checkers must be adjacent to each other. It’s more convenient to check for all four checkers at once, as we do in is_horizontal_win.

   Examples
   It is important that you test this method thoroughly! You should test more cases than just the ones below.

   >>> b = Board(6, 7)
   >>> b.add_checkers('00102030')
   >>> b
   | | | | | | | |
   |O| | | | | | |
   |O| | | | | | |
   |O| | | | | | |
   |O| | | | | | |
   |X|X|X|X| | | |
   ---------------
    0 1 2 3 4 5 6
   
   >>> b.is_win_for('X')
   True
   >>> b.is_win_for('O')
   True
   >>> b2 = Board(6, 7)
   >>> b2.add_checkers('23344545515')
   >>> b2
   | | | | | | | |
   | | | | | | | |
   | | | | | |X| |
   | | | | |X|X| |
   | | | |X|X|O| |
   | |O|X|O|O|O| |
   ---------------
    0 1 2 3 4 5 6
   
   >>> b2.is_win_for('X')   # up diagonal win
   True
   >>> b2.is_win_for('O')
   False
   

Problem 2: A Connect Four Player class

25 points; pair-optional or group-of-three-optional

In this problem, you will create a Player class to represent a player of the Connect Four game. In combination with the Board class that you wrote in Problem 1 and some code that you will write in Problem 3, this will enable you to play a game of Connect Four with a friend!

Getting started

Begin by downloading the file ps14pr2.py and opening it in VS Code. Make sure that you put the file in the same folder as your ps14pr1.py file.

Note: We have included an import statement at the top of ps14pr2.py that imports the Board class from your ps14pr1.py file. Therefore, you will be able to use Board objects and their methods as needed.

Your tasks

Implement the Player class in ps14pr2.py by completing the tasks described below.

1. Write a constructor __init__(self, checker) that constructs a new Player object by initializing the following two attributes:

   • an attribute checker – a one-character string that represents the gamepiece for the player, as specified by the parameter checker

   • an attribute num_moves – an integer that stores how many moves the player has made so far. This attribute should be initialized to zero to signify that the Player object has not yet made any Connect Four moves.

   Begin your __init__ with an assert statement like the one that we recommended for the is_win_for method in Problem 1.

2. Write a method __repr__(self) that returns a string representing a Player object. The string returned should indicate which checker the Player object is using. For example:

   >>> p1 = Player('X')
   >>> p1
   Player X
   >>> p2 = Player('O')
   >>> p2
   Player O
   

   The results of your __repr__ method should exactly match the results shown above. Remember that your __repr__ method should return a string. It should not do any printing.

3. Write a method opponent_checker(self) that returns a one-character string representing the checker of the Player object’s opponent. The method may assume that the calling Player object has a checker attribute that is either 'X' or 'O'.

   For example:

   >>> p = Player('X')
   >>> p.opponent_checker()
   'O'
   

   Important: Make sure that your return values are uppercase letters, and that you do not accidentally use a lowercase letter or a zero instead of an uppercase 'O'.

4. Write a method named next_move(self, b) that accepts a Board object b as a parameter and returns the column where the player wants to make the next move. To do this, the method should ask the user to enter a column number that represents where the user wants to place a checker on the board. The method should repeatedly ask for a column number until a valid column number is given.

   Additionally, this method should increment the number of moves that the Player object has made.

   Notes:

   • To determine whether a given column number is valid, you should use b to call one of the Board methods that you implemented in Problem 1.

   • In order to get input from the user, you should use the input function. Because input always returns a string, you will need to convert the returned string to an integer to get a column number that you can work with.

   • We provided a template for this method in lecture.

   Example:
   In the example below, the underlining is for distinguishing user input. The input you give in your program should not be underlined.

>>> p = Player('X')
>>> b1 = Board(6, 7)    # valid column numbers are 0 - 6
>>> p.next_move(b1)
Enter a column: -1
Try again!
Enter a column: 7
Try again!
Enter a column: 5
5                      # return value of method call
>>> p.num_moves        # number of moves was updated
1

Problem 3: Playing the game!

25 points; pair-optional or group-of-three-optional

In this problem you’ll begin by completing a simple Connect Four client that will allow you to play the game against a friend. Then you will implement a simple, unintelligent computer player that you can play against instead. In another problem set, you will create an AI computer player!

Begin by downloading the file ps14pr3.py and opening it in VS Code. Make sure that you put the file in the same folder as your ps14pr1.py and ps14pr2.py files.

Note: We have included import statements at the top of ps14pr3.py that import the Board class from your ps14pr1.py file and the Player class from you ps14pr2.py file. Therefore, you will be able to use those classes as needed.

Your tasks

The steps that you should take are described below.

0. We have given you the “main” function of the game – a function named connect_four. It takes two Player objects, and it will be used to run a game of Connect Four between those two Players. Begin by reading over this function. You will see that it takes some preliminary steps, and that it then enters a loop that repeatedly processes one move by each player. However, the function needed to process a move still needs to be written. That is your next task!

1. Write a function process_move(p, b) that takes two parameters: a Player object p for the player whose move is being processed, and a Board object b for the board on which the game is being played.

   The function will perform all of the steps involved in processing a single move by player p on board b. These steps are enumerated below. Note that the function should not be very long, because it should take advantage of the methods in the Player object and Board object that it has been given. Those methods will do almost all of the work for you!

   Here are the steps that the function should perform:

   1. Print a message that specifies whose turn it is:

      Player X's turn
      

      or

      Player O's turn
      

      Important: You should not need an if statement here. Simply take advantage of the __repr__ method in player to obtain its string representation.

   2. Obtain player p‘s next move by using p to call the appropriate Player method. Store the move (i.e., the selected column number) in an appropriately named variable.

   3. Apply the move to the board by using b to call the appropriate Board method.

   4. Print a blank line, and then print board b.

   5. Check to see if the move resulted in a win or a tie by using the appropriate methods in b.

      • If it is a win, print a message that looks like this:

        Player X wins in 8 moves.
        Congratulations!
        

        and return True.

      • If it is a tie, print It's a tie! and return True.

   6. If it is neither a win nor a tie, the method should simply return False.

   Make sure that the method returns the appropriate value — either True or False.

   Testing process_move
   You can test process_move on its own from the Shell. For example:

>>> b1 = Board(2, 4)
>>> b1.add_checkers('001122')
>>> b1
|O|O|O| |
|X|X|X| |
---------
 0 1 2 3

>>> process_move(Player('X'), b1)
Player X's turn
Enter a column: 3

|O|O|O| |
|X|X|X|X|
---------
 0 1 2 3

Player X wins in 1 moves.   # we made the other 3 moves for Player X!
Congratulations!
True                        # return value of process_move
>>> process_move(Player('O'), b1)
Player O's turn
Enter a column: 3

|O|O|O|O|
|X|X|X|X|
---------
 0 1 2 3

Player O wins in 1 moves.   # we made the other 3 moves!
Congratulations!
True                        # return value
>>> b1.remove_checker(3)
>>> b1.remove_checker(3)     # call this twice!
>>> b1
|O|O|O| |
|X|X|X| |
---------
 0 1 2 3

>>> process_move(Player('O'), b1)
Player O's turn
Enter a column: 3

|O|O|O| |
|X|X|X|O|
---------
 0 1 2 3

False       # return value
>>> process_move(Player('X'), b1)
Player X's turn
Enter a column: 3

|O|O|O|X|
|X|X|X|O|
---------
 0 1 2 3

It's a tie!
True        # return value

You should also test it from within the context of the connect_four function that we have given you. Simply enter the following:

>>> connect_four(Player('X'), Player('O'))

and then play against a friend, or against yourself! Use Ctrl-C if you need to end the game prematurely.

Submitting Your Work

You should use Gradesope to submit the following files:

• your ps14pr1.py file containing your solutions for Problem 1
• your ps14pr2.py file containing your solutions for Problem 2
• your ps14pr3.py file containing your solutions for Problem 3