CS 111
Spring 2018

Old version

This is the CS 111 site as it appeared on May 10, 2018.

Problem Set 9

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 Apollo, following the procedures found at the end of the assignment.

Part I

due by 11:59 p.m. on Thursday, April 12, 2018

Problem 0: Reading and response

5 points; individual-only

This week’s reading describes recent work in the field of user interfaces that seeks to make human search more flexible and intelligent: pivot searching.

The article, by journalist Charles Q. Choi, is here.

After reading the article, write a response that addresses one of the following prompts:

  1. Suppose that pivot searching were readily available to you. To what extent could you imagine using it? Do you feel it would make you more productive – or would this type of search remain largely unused in the way you interact with computation and electronic materials?

  2. In the conference paper on pivot searching, the authors point out that the approach may especially help particular types of professionals, e.g., it would allow doctors “to search on the context (symptoms) of other patients, thus discovering diagnoses, treatments and other relevant information” and would allow lawyers to “leverage a context search tool based on cases, allowing them to search on client name, arguments made, resources cited, and then seeing the contexts in which they were applied.” Do you find these imagined applications believable and/or compelling? Could you imagine other endeavors where context-based searches would be even more beneficial?

Put your response in a file named ps9pr0.txt. Don’t forget that the file you submit must be a plain-text file.

Problem 1: A Connect Four Board class

30 points; pair-optional

This is the only problem of the 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.

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

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

Important

If you add test code to your ps9pr1.py file, please put it in one or more separate test functions, which you can then call to do the testing.

For example, you could begin your test function with something like this:

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

Having test functions is not required. However, you should not have any test code in the global scope (i.e., outside of a function).

  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, Problem 3. 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 ps9pr1.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 checkershould 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 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.

    • 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

15 points; individual-only

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 ps9pr2.py and opening it in IDLE. 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.

Important

If you add test code to your ps9pr2.py file, please put it in one or more separate test functions, which you can then call to do the testing. Having test functions is not required. However, you should not have any test code in the global scope (i.e., outside of a function). See the note in Problem 1 for more detail.

  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, board) that accepts a Board object 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 make use a method in the Board class 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.

    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

Part II

due by 11:59 p.m. on Sunday, April 15, 2018

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 the file ps9pr3.py and opening it in IDLE. Make sure that you put the file in the same folder as your ps9pr1.py and ps9pr2.py files.

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.

Your tasks

The steps that you should take are described below.

Important

If you add test code to your ps9pr3.py file, please put it in one or more separate test functions, which you can then call to do the testing. Having test functions is not required. However, you should not have any test code in the global scope (i.e., outside of a function). See the note in Problem 1 for more detail.

  1. 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!

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

    The function will perform all of the steps involved in processing a single move by the specified player on the specified board. 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 the player’s next move by using 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 the appropriate Board method.

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

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

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

  1. 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, board) 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 specified board 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 Shell. For example:

    >>> p = RandomPlayer('X')
>>> p
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
|O| |X| |
|X|X|O|O|
---------
 0 1 2 3

>>> p.next_move(b)
3             # can be either 1 or 3
>>> p.next_move(b)
1             # can be either 1 or 3
>>> p.next_move(b)
1             # can be either 1 or 3
>>> b.add_checker('O', 1)
>>> b
|O|O|X| |
|X|X|O|O|
---------
 0 1 2 3

>>> p.next_move(b)
3             # must be 3!
>>> p.next_move(b)
3             # must be 3!
>>> b.add_checker('X', 3)
>>> b.remove_checker(2)
>>> b
|O|O| |X|
|X|X|O|O|
---------
 0 1 2 3

>>> p.next_move(b)
2             # must be 2!
>>> p.next_move(b)
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

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:

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:

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 the file ps9pr4.py and opening it in IDLE. Make sure that you put the file in the same folder as your other files for this problem set.

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:

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.

Important

If you add test code to your ps9pr4.py file, please put it in one or more separate test functions, which you can then call to do the testing. Having test functions is not required. However, you should not have any test code in the global scope (i.e., outside of a function). See the note in Problem 1 for more detail.

  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
Player X (LEFT, 1)
>>> p2 = AIPlayer('O', 'RANDOM', 2)
>>> p2
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)
2
>>> p2 = AIPlayer('X', 'RIGHT', 1)
>>> p2.max_score_column(scores)
5

  5. Write a method scores_for(self, board) that takes a Board object board and determines the called AIPlayer‘s scores for the columns in board. 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 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 board, 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 board is already a win for the called AIPlayer (i.e., for self), use a score of 100 for the current column.
    3. Otherwise, if board 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 Board method.

      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 board 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
| | | | | | | |
| | | | | | | |
| | | | |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)
[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)
[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)
[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)
[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)
[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)
[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)
[0, 0, 0, 100, 0, 0, 0]

  6. Write a method next_move(self, board) 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
| | | | | | | |
| | | | | | | |
| | | | |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)
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)
6
# With the larger lookahead, X knows it must pick column 3!
>>> AIPlayer('X', 'LEFT', 2).next_move(b)
3      
# The tiebreaking strategy doesn't matter if there's only one best move!
>>> AIPlayer('X', 'RIGHT', 2).next_move(b)
3      
>>> AIPlayer('X', 'RANDOM', 2).next_move(b)
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!
|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!
|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!
|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

You should use WebSubmit to submit the following files:

Warnings

  • Make sure to use these exact file names, or Apollo will not accept your files. If Apollo reports that a file does not have the correct name, you should rename the file using the name listed in the assignment or on the Apollo upload page.

  • Before submitting your files, make sure that your BU username is visible at the top of the Apollo page. If you don’t see your username, click the Log out button and login again.

  • If you make any last-minute changes to one of your Python files (e.g., adding additional comments), you should run the file in IDLE after you make the changes to ensure that it still runs correctly. Even seemingly minor changes can cause your code to become unrunnable.

  • If you submit an unrunnable file, Apollo will accept your file, but it will print a warning message. If time permits, you are strongly encouraged to fix your file and resubmit. Otherwise, your code will fail most if not all of our tests.

  • If you encounter problems with Apollo, click the Log Out button, close your browser and try again. If possible, you may also want to wait an hour or two before retrying. If you are unable to submit and it is close to the deadline, email your homework before the deadline to cs111-staff@cs.bu.edu.

Here are the steps:

  1. Login to Apollo, using the link in the left-hand navigation bar. You will need to use your Kerberos user name and password.
  2. Check to see that your BU username is at the top of the Apollo page. If it isn’t, click the Log out button and login again.
  3. Find the appropriate problem set section on the main page and click Upload files.
  4. For each file that you want to submit, find the matching upload section for the file. Make sure that you use the right section for each file. You may upload any number of files at a time.
  5. Click the Upload button at the bottom of the page.
  6. Review the upload results. If Apollo reports any issues, return to the upload page by clicking the link at the top of the results page, and try the upload again, per Apollo’s advice.
  7. Once all of your files have been successfully uploaded, return to the upload page by clicking the link at the top of the results page. The upload page will show you when you uploaded each file, and it will give you a way to view or download the uploaded file. Click on the link for each file so that you can ensure that you submitted the correct file.

Warning

Apollo will automatically close submissions for a given file when its final deadline has passed. We will not accept any file after Apollo has disabled its upload form, so please check your submission carefully following the instructions in Step 7 above.