Problem Set 9

Part I due by 11:59 p.m. on Thursday, April 17, 2025.
Part II due by 11:59 p.m. on Sunday, April 20, 2025.

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 to take whatever other steps are needed to create readable code.

If you have questions while working on this assignment, please come to office hours, post them on Piazza, or email cs111-staff@cs.bu.edu.

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

Part I

Creating the necessary folder

Create a subfolder called ps9 within your cs111 folder, and put all of the files for this assignment in that folder.

Problem 1: A Connect Four Board class

35 points; individual-only

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 set, 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

Getting started

Begin by downloading ps9pr1.py, saving it in your ps9 folder.

Open the file in Spyder, and you will see that we have given you some starter code for the Board class. You will implement the rest of it by completing the tasks described below.

def test():
    b = Board(6, 7)
    print(b)

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 earlier problem sets. However, a simpler alternative approach is to use a list comprehension:

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

2. We have given you some starter code for a method __repr__(self) that returns a string representing a Board object.

   The code that we have provided:

   • begins by assigning an empty string to the variable s

   • uses nested loops to gradually concatenate additional characters to s so that:

     • each element of the 2-D list slots is included in the string
     • columns are separated by vertical bar ('|') characters
     • a newline character is added at the end of each row

   • returns the final value of the string s

   You will need to add code before the return statement to add two other sets of characters to the string s.

   1. First, write the code needed to add a line of hyphen characters (-) that is wide enough to cover all of the columns. Use concrete examples to figure out the correct number of hyphens as a function of the number of columns. Here are some examples of what things should look like after you add the code needed for the hyphens:

      >>> b1 = Board(2, 2)
      
      >>> b1
      result:
      | | |
      | | |
      -----
      
      >>> b2 = Board(4, 3)
      
      >>> b2
      result:
      | | | |
      | | | |
      | | | |
      | | | |
      -------
      
      >>> b3 = Board(6, 4)
      
      >>> b3
      result:
      | | | | |
      | | | | |
      | | | | |
      | | | | |
      | | | | |
      | | | | |
      ---------
      

      Notes:

      • We encourage you to create a table that is based on the concrete examples above. It should start out looking like this:

         width  |  number of hyphens
        -----------------------------
           2              5
        

        Complete the table, and use it to determine a formula for the number of hyphens as a function of the board’s width.

      • Don’t forget that the __repr__ method should not do any printing. Instead, you should concatenate the correct number of hyphens onto the string s.

      • You will need to include a newline character ('\n') after the line of hyphens, just as we have done in the provided code at the end of every row of the board. This will cause the printed string to go down to the next line after the hyphens are printed.

   2. Next, write the code needed to add a line of numeric column labels for all of the columns.

      Here is an example for an empty 6x7 board:

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

      In order to keep the column numbers in line, the numbering should only include the units digit of the number, as this larger (5x15) example shows:

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

      Notes:

      • You will need a loop in which the loop variable takes on the indices of the columns.

      • You should use the modulus (%) operator to get the units digit. If x is an integer, (x % 10) will give you its units digit.

      • In order to concatenate a number onto the string s, you will need to first convert the number to a string using the str function.

      • You should include a single newline character ('\n') after the entire line of column numbers.

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 have given you the following starter code for this method:

   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 for checker 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. See below for some possible approaches.

   • 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(3, 4)
   
   >>> b1.add_checker('X', 0)
   
   >>> b1
   result:
   | | | | |
   | | | | |
   |X| | | |
   ---------
    0 1 2 3
   
   >>> b1.add_checker('O', 2)
   
   >>> b1
   result:
   | | | | |
   | | | | |
   |X| |O| |
   ---------
    0 1 2 3
   
   >>> b1.add_checker('X', 2)
   
   >>> b1
   result:
   | | | | |
   | | |X| |
   |X| |O| |
   ---------
    0 1 2 3
   

   Possible approaches

   • In lecture, we considered a buggy version of this method. One option would be to start with that buggy version and fix it so that it avoids the problems that we discussed.

   • You could also use a completely different approach. For example, to avoid the index errors that our buggy version produced, you could use an index-based for loop that takes on the row indices, and use a break statement to end the loop early as needed.

   • Regardless of the approach that you take, use concrete examples to help you figure out the logic – both for the loop itself and for what should happen after the loop. For example, once your loop is done, do you need to adjust the final value of the variable that you are using for the row index? If so, do you always need to adjust it, or do you need to decide whether or not to adjust it?

   Here is another set of examples that you can use for testing:

   >>> b2 = Board(6, 7)
   
   >>> b2.add_checker('X', 0)
   
   >>> b2.add_checker('O', 0)
   
   >>> b2.add_checker('X', 0)
   
   >>> b2.add_checker('O', 3)
   
   >>> b2.add_checker('O', 6)    # cheat and let O go again!
   
   >>> b2
   result:
   | | | | | | | |
   | | | | | | | |
   | | | | | | | |
   |X| | | | | | |
   |O| | | | | | |
   |X| | |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. We have given you a fully implemented method called add_checkers that is useful for debugging purposes. You do not need to change this method.

   The method accepts a string of column numbers, and it places checkers in those columns by alternating between 'X' and 'O' checkers. For example:

   >>> b2 = Board(3, 3)
   
   >>> b2.add_checkers('0200')
   
   >>> b2
   result:
   |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
   result:
   | | |
   | | |
   -----
    0 1
   
   >>> b1.add_checker('X', 0)
   
   >>> b1.add_checker('O', 0)
   
   >>> b1
   result:
   |O| |
   |X| |
   -----
    0 1
   
   >>> b1.can_add_to(-1)
   result: False                # column number is too low
   
   >>> b1.can_add_to(0)
   result: False                # column is full
   
   >>> b1.can_add_to(1)
   result: True
   
   >>> b1.can_add_to(2)
   result: 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()
   result: False
   
   >>> b2.add_checkers('0011')
   
   >>> b2
   result:
   |O|O|
   |X|X|
   -----
    0 1
   
   >>> b2.is_full()
   result: True
   
   >>> b3 = Board(4, 5)
   
   >>> b3.is_full()
   result: False
   
   >>> b3.add_checkers('01234' * 3)
   
   >>> b3
   result:
   | | | | | |
   |X|O|X|O|X|
   |O|X|O|X|O|
   |X|O|X|O|X|
   -----------
    0 1 2 3 4
   
   >>> b3.is_full()
   result: False
   
   >>> b3.add_checkers('034')
   
   >>> b3
   result:
   |X| | |O|X|
   |X|O|X|O|X|
   |O|X|O|X|O|
   |X|O|X|O|X|
   -----------
    0 1 2 3 4
   
   >>> b3.is_full()
   result: False
   
   >>> b3.add_checkers('12')
   
   >>> b3
   result:
   |X|X|O|O|X|
   |X|O|X|O|X|
   |O|X|O|X|O|
   |X|O|X|O|X|
   -----------
    0 1 2 3 4
   
   >>> b3.is_full()
   result: 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
   result:
   | | |
   |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:

   • 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.

   • 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
     

   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
   result:
   | | | | | | | |
   |O| | | | | | |
   |O| | | | | | |
   |O| | | | | | |
   |O| | | | | | |
   |X|X|X|X| | | |
   ---------------
    0 1 2 3 4 5 6
   
   >>> b.is_win_for('X')
   result: True
   
   >>> b.is_win_for('O')
   result: True
   
   >>> b2 = Board(6, 7)
   
   >>> b2.add_checkers('23344545515')
   
   >>> b2
   result:
   | | | | | | | |
   | | | | | | | |
   | | | | | |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
   result: True
   
   >>> b2.is_win_for('O')
   result: False
   

Problem 2: A Connect Four Player class

15 points; pair-optional

This is the only problem in this assignment that you may complete with a partner. See the rules for working with a partner on pair-optional problems for details about how this type of collaboration must be structured.

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 this file: ps9pr2.py

Make sure that you put the file in the same folder as your ps9pr1.py file.

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

Your tasks

Implement the Player class in ps9pr2.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
   result: Player X
   
   >>> p2 = Player('O')
   
   >>> p2
   result: 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()
   result: '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
result: 5              # return value of method call

>>> p.num_moves        # number of moves was updated
result: 1

Submitting your work for Part I

Login to Gradescope by clicking the link in the left-hand navigation bar, and click on the box for CS 111.

You must submit the following files:

• ps9pr1.py
• ps9pr2.py

Here are the steps:

1. Click on the name of the assignment (PS 9: Part I) in the list of assignments. You should see a pop-up window with a box labeled DRAG & DROP. (If you don’t see it, click the Submit or Resubmit button at the bottom of the page.)

2. Add the files to the box labeled DRAG & DROP. You can either drag and drop the files from their folder into the box, or you can click on the box itself and browse for the files.

3. Click the Upload button.

4. You should see a box saying that your submission was successful. Click the (x) button to close that box.

5. The Autograder will perform some tests on your files. Once it is done, check the results to ensure that the tests were passed. If one or more of the tests did not pass, the name of that test will be in red, and there should be a message describing the failure. Based on those messages, make any necessary changes. Feel free to ask a staff member for help.

   Note: You will not see a complete Autograder score when you submit. That is because additional tests for at least some of the problems will be run later, after the final deadline for the submission has passed. For such problems, it is important to realize that passing all of the initial tests does not necessarily mean that you will ultimately get full credit on the problem. You should always run your own tests to convince yourself that the logic of your solutions is correct.

6. If needed, use the Resubmit button at the bottom of the page to resubmit your work. Important: Every time that you make a submission, you should submit all of the files for that Gradescope assignment, even if some of them have not changed since your last submission.

7. Near the top of the page, click on the box labeled Code. Then click on the name of each file to view its contents. Check to make sure that the files contain the code that you want us to grade.

Part II

Problem 3: Playing the game!

20 points; individual-only

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 Problem 4, you will create an AI computer player!

Begin by downloading this file: ps9pr3.py

Make sure that you put it in the same folder as your other files for PS 9.

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

Task 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!

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 console. For example:

>>> b1 = Board(2, 4)

>>> b1.add_checkers('001122')

>>> b1
result:
|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!
result: 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!
result: True                # return value

>>> b1.remove_checker(3)

>>> b1.remove_checker(3)    # call this twice!

>>> b1
result:
|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

result: 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!
result: 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.

Task 2
Define a class called RandomPlayer that can be used for an unintelligent computer player that chooses at random from the available columns.

This class should be a subclass of the Player class that you implemented in Problem 2, and you should take full advantage of inheritance. In particular, you should not need to include any attributes in your RandomPlayer class, because all of the necessary attributes (the player’s checker, and its count of the number of moves) will be inherited from Player.

Similarly, you should not need to redefine the __repr__ or opponent_checker methods, because they will be inherited from Player, and we don’t want these methods to behave any differently for a RandomPlayer than they do for a Player.

However, you will need to do the following:

1. Make sure that your class header specifies that RandomPlayer inherits from Player.

2. Because all of the attributes of a RandomPlayer are inherited from Player, you will not need to define a constructor for this class. Rather, we can just use the constructor that is inherited from Player.

3. Write a method next_move(self, b) that overrides (i.e., replaces) the next_move method that is inherited from Player. Rather than asking the user for the next move, this version of next_move should choose at random from the columns in the board b that are not yet full, and return the index of that randomly selected column. You may assume that this method will only be called in cases in which there is at least one available column.

   In addition, make sure that you increment the number of moves that the RandomPlayer object has made.

Notes:

• To ensure that the method does not select the index of a column that is already full, we recommend that you begin by constructing a list containing the indices of all available columns — i.e., all columns to which you can still add a checker. For example, let’s say that the parameter board represents the following board:

  |O| | |X| | | |
  |X| | |O| | | |
  |X| | |O| |O| |
  |X|X| |O|X|X|O|
  |O|X|O|X|X|O|X|
  |O|O|X|O|O|O|X|
  ---------------
   0 1 2 3 4 5 6
  

  The list of available columns in this case would be [1,2,4,5,6].

  To build this list, you should consider the columns one at a time, and add the index of any available column to the list. This can be done using a loop, or you might want to use a list comprehension instead. We also encourage you to take advantage of one of your Board methods to determine if a given column is available!

• We have included an import statement for the random module so that you can use the appropriate function to make a random choice from the list of available columns.

Testing your RandomPlayer class
You can test your new class from the console. For example:

>>> p = RandomPlayer('X')

>>> p
result: Player X      # uses the inherited __repr__

>>> p.opponent_checker()
'O'           # uses the inherited version of this method

>>> b = Board(2, 4)

>>> b.add_checkers('001223')

>>> b
result:
|O| |X| |
|X|X|O|O|
---------
 0 1 2 3

>>> p.next_move(b)
result: 3             # can be either 1 or 3

>>> p.next_move(b)
result: 1             # can be either 1 or 3

>>> p.next_move(b)
result: 1             # can be either 1 or 3

>>> b.add_checker('O', 1)

>>> b
result:
|O|O|X| |
|X|X|O|O|
---------
 0 1 2 3

>>> p.next_move(b)
result: 3             # must be 3!

>>> p.next_move(b)
result: 3             # must be 3!

>>> b.add_checker('X', 3)

>>> b.remove_checker(2)

>>> b
result:
|O|O| |X|
|X|X|O|O|
---------
 0 1 2 3

>>> p.next_move(b)
result: 2             # must be 2!

>>> p.next_move(b)
result: 2             # must be 2!

You should also test it from within the context of the connect_four function that we have given you. To play against a random player, enter something like this:

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

You’ll see that it’s pretty easy to win against someone who chooses randomly!

You could also pit two random players against each other and see who wins:

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

Problem 4: An AI Player

30 points; individual-only

We will finish the material needed for this problem on Wednesday.

Overview
In this problem you will define a more “intelligent” computer player – one that uses techniques from artificial intelligence (AI) to choose its next move.

In particular, this “AI player” will look ahead some number of moves into the future to assess the impact of each possible move that it could make for its next move, and it will assign a score to each possible move. And since each move corresponds to a column number, it will effectively assign a score to each column.

The possible column scores are:

• -1 for a column that is already full

• 0 for a column that, if chosen as the next move, will result in a loss for the player at some point during the number of moves that the player looks ahead.

• 100 for a column that, if chosen as the next move, will result in a win for the player at some point during the number of moves that the player looks ahead.

• 50 for a column that, if chosen as the next move, will result in neither a win nor a loss for the player at any point during the number of moves that the player looks ahead.

After obtaining a list of scores for each column, it will choose as its next move the column with the maximum score. This will be the player’s judgment of its best possible move.

If there are ties, the player will use one of the following tiebreaking strategies, each of which is represented by a single-word string:

• 'LEFT': out of all the columns that are tied for the highest score, pick the leftmost one.
• 'RIGHT': out of all the columns that are tied for the highest score, pick the rightmost one.
• 'RANDOM': out of all the columns that are tied for the highest score, pick one of them at random.

When looking ahead, the player will assume that its opponent is using a comparable strategy – assigning scores to columns based on some degree of lookahead, and choosing what it judges to be the best possible move for itself.

Getting started
Begin by downloading this file:

ps9pr4.py

Make sure that you put the file in the same folder as your other files for this problem sets.

We have included an import statement at the top of ps9pr4.py that should allow you to use the other code that you have written for this assignment — in particular, the Board and Player classes.

Your tasks
You will define a class called AIPlayer that takes the approach outlined above (and in more detail below) to choose its next move.

Like the RandomPlayer class that you implemented for Problem 3, this class should be a subclass of the Player class that you implemented in Problem 2, and you should take full advantage of inheritance.

In addition to the attributes inherited from Player, an AIPlayer object should include two new attributes:

• one called tiebreak that stores a string specifying the player’s tiebreaking strategy ('LEFT', 'RIGHT', or 'RANDOM')

• one called lookahead that stores an integer specifying how many moves the player looks ahead in order to evaluate possible moves.

AIPlayer will inherit the methods of the Player class, but it will override some of them so that it can change their behavior. In addition, AIPlayer will include two new methods that were not needed in Player.

The steps you should take are outlined below.

1. Make sure that your class header specifies that AIPlayer inherits from Player.

2. Write a constructor __init__(self, checker, tiebreak, lookahead) that constructs a new AIPlayer object. Begin the method with assert statements that validate the inputs:

   def __init__(self, checker, tiebreak, lookahead):
       """ put your docstring here
       """
       assert(checker == 'X' or checker == 'O')
       assert(tiebreak == 'LEFT' or tiebreak == 'RIGHT' or tiebreak == 'RANDOM')
       assert(lookahead >= 0)
   

   Next, call the constructor inherited from the superclass, so that it can initialize the inherited attributes:

       super().__init__(checker)
   

   Finally, your new constructor should initialize the two attributes that are not inherited from Player (see above) – assigning them the values that are passed in as parameters.

   Make sure that you do not redefine the inherited attributes by trying to assign something to them here.

3. Write a method __repr__(self) that returns a string representing an AIPlayer object. This method will override/replace the __repr__ method that is inherited from Player. In addition to indicating which checker the AIPlayer object is using, the returned string should also indicate the player’s tiebreaking strategy and lookahead. For example:

   >>> p1 = AIPlayer('X', 'LEFT', 1)
   
   >>> p1
   result: Player X (LEFT, 1)
   
   >>> p2 = AIPlayer('O', 'RANDOM', 2)
   
   >>> p2
   result: Player O (RANDOM, 2)
   

   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.

4. Write a method max_score_column(self, scores) that takes a list scores containing a score for each column of the board, and that returns the index of the column with the maximum score. If one or more columns are tied for the maximum score, the method should apply the called AIPlayer‘s tiebreaking strategy to break the tie. Make sure that you return the index of the appropriate column, and not the column’s score.

   Notes:

   • One good way to implement this method is to first determine the maximum score in scores (you can use the built-in max function for this), and to then create a list containing the indices of all elements in scores that match this maximum score. For example, if scores consisted of the list [50,50,50,50,50,50,50], the list of indices that you would build would be [0,1,2,3,4,5,6], because all of these scores are tied for the maximum score. If scores consisted of the list [50,100,100,50,50,100,50], you would build the list of indices [1,2,5]. Then once you have this list of indices, you can choose from the list based on the AIPlayer‘s tiebreaking strategy.

   • If you take this approach, then you don’t really need to worry about whether there is a tie. You can always use the tiebreaking strategy when choosing from the list of indices that you construct!

   • We have included an import statement for the random module so that you can use the appropriate function to make a random choice for players that use the 'RANDOM' tiebreaking strategy.

   Examples:

   >>> scores = [0, 0, 50, 0, 50, 50, 0]
   
   >>> p1 = AIPlayer('X', 'LEFT', 1)
   
   >>> p1.max_score_column(scores)
   result: 2
   
   >>> p2 = AIPlayer('X', 'RIGHT', 1)
   
   >>> p2.max_score_column(scores)
   result: 5
   

5. Write a method scores_for(self, b) that takes a Board object b and determines the called AIPlayer‘s scores for the columns in b. Each column should be assigned one of the four possible scores discussed in the Overview at the start of this problem, based on the called AIPlayer‘s lookahead value. The method should return a list containing one score for each column.

   This method should take advantage of both the other methods in the called AIPlayers object (including the inherited ones) and the methods in the Board object b that it is given as a parameter. Don’t repeat work that can be done using one of those methods!

   You should begin by creating a list (call it scores) that is long enough to store a score for each column. You can use list multiplication for this, and it doesn’t really matter what initial value you use for the elements of the list.

   You should then loop over all of the columns in b, determine a score for each column, and assign the score to the appropriate element of scores. Here is an outline of the logic:

   1. If the current column is full, use a score of -1 for it. In other words, assign -1 to the appropriate element of your scores list.
   2. Otherwise, if b is already a win for the called AIPlayer (i.e., for self), use a score of 100 for the current column.
   3. Otherwise, if b is already a win for the player’s opponent, use a score of 0 for the current column.
   4. Otherwise, if the player has a lookahead of 0, use a score of 50 for the column. (Remember, a lookahead of 0 means that the player is only assessing the current board, and since we already checked for wins or losses, the current board must be neither a win nor a loss.)

   5. Otherwise, we need to look ahead! This involves taking several steps:

      1. Add one of the called AIPlayer‘s checkers to the current column using the appropriate method in the board b.

      2. Determine what scores the opponent would give to the resulting board. To do so, create an opponent (an AIPlayer object) with the same tiebreaking strategy as self, but with a lookahead that is one less than the one used by self. Make a recursive call to determine the scores that this created opponent would give to the current board (the one that resulted from adding a checker to the current column).

      3. Following the approach discussed in lecture, use the opponent’s scores (the scores returned by the recursive call) to determine what score self should use for the current column.

      4. Remove the checker that was placed in this column so that you can restore the board b to its prior state.

   Once the loop has considered all of the columns, the method should return the complete list of scores.

   Examples:

   >>> b = Board(6, 7)
   
   >>> b.add_checkers('1211244445')
   
   >>> b
   result:
   | | | | | | | |
   | | | | | | | |
   | | | | |X| | |
   | |O| | |O| | |
   | |X|X| |X| | |
   | |X|O| |O|O| |
   ---------------
    0 1 2 3 4 5 6
   
   # A lookahead of 0 doesn't see threats!
   >>> AIPlayer('X', 'LEFT', 0).scores_for(b)
   result: [50, 50, 50, 50, 50, 50, 50]
   
   # A lookahead of 1 sees immediate wins.
   # (O would win if it put a checker in column 3.)
   >>> AIPlayer('O', 'LEFT', 1).scores_for(b)
   result: [50, 50, 50, 100, 50, 50, 50]
   
   # But a lookahead of 1 doesn't see possible losses!
   # (X doesn't see that O can win if column 3 is left open.)
   >>> AIPlayer('X', 'LEFT', 1).scores_for(b)
   result: [50, 50, 50, 50, 50, 50, 50]
   
   # A lookahead of 2 sees possible losses.
   # (All moves by X other than column 3 leave it open to a loss.
   # note that X's score for 3 is 50 instead of 100, because it
   # assumes that O will follow X's move to 3 with its own move to 3,
   # which will block X's possible horizontal win.)
   >>> AIPlayer('X', 'LEFT', 2).scores_for(b)
   result: [0, 0, 0, 50, 0, 0, 0]
   
   # A lookahead of 3 sees set-up wins!
   # (If X chooses column 3, O will block its horizontal win, but
   # then X can get a diagonal win by choosing column 3 again!)
   >>> AIPlayer('X', 'LEFT', 3).scores_for(b)
   result: [0, 0, 0, 100, 0, 0, 0]
   
   # With a lookahead of 3, O doesn't see the danger of not
   # choosing 3 for its next move (hence the 50s in columns
   # other than column 3).
   >>> AIPlayer('O', 'LEFT', 3).scores_for(b)
   result: [50, 50, 50, 100, 50, 50, 50]
   
   # With a lookahead of 4, O **does** see the danger of not
   # choosing 3 for its next move (hence the 0s in columns
   # other than column 3).
   >>> AIPlayer('O', 'LEFT', 4).scores_for(b)
   result: [0, 0, 0, 100, 0, 0, 0]
   

6. Write a method next_move(self, b) that overrides (i.e., replaces) the next_move method that is inherited from Player. Rather than asking the user for the next move, this version of next_move should return the called AIPlayer‘s judgment of its best possible move. This method won’t need to do much work, because it should use your scores_for and max_score_column methods to determine the column number that should be returned.

   In addition, make sure that you increment the number of moves that the AIPlayer object has made.

   Examples:

   >>> b = Board(6, 7)
   
   >>> b.add_checkers('1211244445')
   
   >>> b
   result:
   | | | | | | | |
   | | | | | | | |
   | | | | |X| | |
   | |O| | |O| | |
   | |X|X| |X| | |
   | |X|O| |O|O| |
   ---------------
    0 1 2 3 4 5 6
   
   # With a lookahead of 1, gives all columns a score of 50, and its
   # tiebreaking strategy leads it to pick the leftmost one.
   >>> AIPlayer('X', 'LEFT', 1).next_move(b)
   result: 0
   
   # Same lookahead means all columns are still tied, but a different
   # tiebreaking stategy that leads it to pick the rightmost column.
   >>> AIPlayer('X', 'RIGHT', 1).next_move(b)
   result: 6
   
   # With the larger lookahead, X knows it must pick column 3!
   >>> AIPlayer('X', 'LEFT', 2).next_move(b)
   result: 3
   
   # The tiebreaking strategy doesn't matter if there's only one best move!
   >>> AIPlayer('X', 'RIGHT', 2).next_move(b)
   result: 3
   
   >>> AIPlayer('X', 'RANDOM', 2).next_move(b)
   result: 3
   

Playing the game with AIPlayer objects!
Because our AIPlayer class inherits from Player, we can use it in conjunction with our connect_four function from Problem 3.

You can play against an AIPlayer by doing something like:

>>> connect_four(Player('X'), AIPlayer('O', 'RANDOM', 3))

Below some examples in which two AIPlayer objects play against each other. And because we’re using non-random tiebreaking strategies for both players, you should obtain the same results.

>>> connect_four(AIPlayer('X', 'LEFT', 0), AIPlayer('O', 'LEFT', 0))
# omitting everything but the final result...

Player X (LEFT, 0) wins in 10 moves.
Congratulations!
result:
|O|O|O| | | | |
|X|X|X| | | | |
|O|O|O| | | | |
|X|X|X| | | | |
|O|O|O| | | | |
|X|X|X|X| | | |
---------------
 0 1 2 3 4 5 6

>>> connect_four(AIPlayer('X', 'LEFT', 1), AIPlayer('O', 'LEFT', 1))
# omitting everything but the final result...

Player X (LEFT, 1) wins in 8 moves.
Congratulations!
result:
|O|O| | | | | |
|X|X| | | | | |
|O|O| | | | | |
|X|X| | | | | |
|O|O|O| | | | |
|X|X|X|X| | | |
---------------
 0 1 2 3 4 5 6

# The player with the larger lookahead doesn't always win!
>>> connect_four(AIPlayer('X', 'LEFT', 3), AIPlayer('O', 'LEFT', 2))
# omitting everything but the final result...

Player O (LEFT, 2) wins in 19 moves.
Congratulations!
result:
|O|O|X|X|O|O| |
|X|X|O|O|X|X| |
|O|O|X|X|O|O| |
|X|X|O|O|X|X| |
|O|O|X|O|O|O|O|
|X|X|X|O|X|X|X|
---------------
 0 1 2 3 4 5 6

Submitting your work for Part II

Login to Gradescope by clicking the link in the left-hand navigation bar, and click on the box for CS 111.

Submit your ps9pr3.py and ps9pr4.py files under the assignment labeled PS 9: Part II using these steps:

1. Click on the name of the assignment in the list of assignments. You should see a pop-up window with a box labeled DRAG & DROP. (If you don’t see it, click the Submit or Resubmit button at the bottom of the page.)

2. Add both files to the box labeled DRAG & DROP. You can either drag and drop the files from their folder into the box, or you can click on the box itself and browse for the files.

3. Click the Upload button.

4. You should see a box saying that your submission was successful. Click the (x) button to close that box.

5. The Autograder will perform some tests on your files. Once it is done, check the results to ensure that the tests were passed. If one or more of the tests did not pass, the name of that test will be in red, and there should be a message describing the failure. Based on those messages, make any necessary changes. Feel free to ask a staff member for help.

   Note: You will not see a complete Autograder score when you submit. That is because additional tests for at least some of the problems will be run later, after the final deadline for the submission has passed. For such problems, it is important to realize that passing all of the initial tests does not necessarily mean that you will ultimately get full credit on the problem. You should always run your own tests to convince yourself that the logic of your solutions is correct.

6. If needed, use the Resubmit button at the bottom of the page to resubmit your work. Important: Every time that you make a submission, you should submit all of the files for that Gradescope assignment, even if some of them have not changed since your last submission.

7. Near the top of the page, click on the box labeled Code. Then click on the name of each file to view its contents. Check to make sure that the files contain the code that you want us to grade.

Last updated on April 28, 2025.