Problem Sets 15 and 16

Preliminaries
- Problem Set 15: A Computerized Player
- Problem Set 16: An AI Player
Submitting Your Work

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, post them on Piazza, come to TA Help hours.

Make sure to submit your work on Gradescope, following the procedures found at the end of the assignment.

PS15 due by 10:00 p.m. EDT on Friday, November 3, 2023

PS16 due by 10:00 p.m. EDT on Saturday, November 4, 2023

Important note regarding test cases and Gradescope:

You must test each function after you write it. Here are two ways to do so:
- Run your file after you finish a given function. Doing so will bring you to the Shell, where you can call the function using different inputs and check to see that you obtain the correct outputs.
- Add test calls to the bottom of your file, inside the if __name__ == '__main__' control structure. For example:
```
if __name__ == '__main__':

    print("mystery(6,7) returned", mystery(6,7))
```
  These tests will be called every time that you run the file, which will save you from having to enter the tests yourself. We have given you an example of one such test in the starter file.
You must not leave any print statements in the global scope. This will cause an error with the Gradescope autograder. Make sure all of your print statements are inside a function scope or inside the if __name__ == '__main__' control structure.

Problem Set 15: A Computerized Player

due by 10:00 p.m. EDT on Friday, November 3, 2023

100 points; pair-optional or grou-of-three-optional

Overview
This problem builds upon the work you did in Problem Set 14. You must complete Problem Set 14 before you can begin to work on Problem Set 15. In this problem you will define an unintelligent computer player – one that uses random number generator to choose its next move.

Getting started
Begin by downloading the file ps15pr1.py and opening it in VS Code. 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 ps15pr1.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

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 Set 14, 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:

Make sure that your class header specifies that RandomPlayer inherits from Player.
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.
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: :::python >>> connect_four(RandomPlayer(‘X’), RandomPlayer(‘O’))

Problem Set 16: An AI Player

due by 10:00 p.m. EDT on Saturday, November 4, 2023

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

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 the file ps16pr1.py and opening it in VS Code. 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 ps16pr1.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 1, this class should be a subclass of the Player class that you implemented in Problem Set 14, 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.

Here are the steps you should take:

Make sure that your class header specifies that AIPlayer inherits from Player.
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 Player constructor so that it can initialize the attributes that are inherited from that class:
```
    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.
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.
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
```
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]
```

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 Set 13, Problem 2][ps13pr2].

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 Gradesope to submit the following files:

your ps15pr1.py file containing your solutions for Problem Set 15
your ps16pr1.py file containing your solutions for Problem Set 16

Warnings

Make sure to use these exact file names, or Gradescope will not accept your files. If Gradescope 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 Gradescope upload page.
If you make any last-minute changes to one of your Python files (e.g., adding additional comments), you should run the file in VS Code 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, Gradescope will accept your file, but it will not be able to auto-grade it. 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.