A6: Connect-N

The development of software for two-player board games is one of the earliest applications of artificial intelligence. Versions of Tic-Tac-Toe, Checkers, and Chess were implemented on some of the first electronic computers. Modern implementations of most two-player games can now beat even the best human players, though remarkably, most computer players are built on the same core ideas as their earliest ancestors.

In this assignment, you will complete the core classes for an implementation of Milton-Bradley’s Connect 4. The original version of the game uses a set of 42 checkers-like pieces, 21 red and 21 black. The game board is a 6 row by 7-column board, oriented vertically. Players take turns dropping pieces into one of the columns, which falls straight down to the lowest unoccupied row. A player wins the game by completing a run of four consecutive pieces of their color, horizontally, vertically, or along either of the diagonals (top left or top right). If all rows and columns are filled without a win, the game ends in a tie.

In our version, Connect-N the number of rows and columns in the game board, along with the minimum length run required to win, are all user-configurable. And while we will not test you on this, it is possible to extend the game to have more than two players.

Just getting a game together that will work for human players can be a challenge, but the real fun is in the construction of an AI that can play the game with reasonable skill. Developing a tournament-strength computer player is beyond the scope of this class (though it is possible to make one that never loses), but even the simple approach you’ll use here can produce surpisingly good play.

This assignment includes material that we have not covered by the time the assignment was posted. However, if you follow the micro-deadlines, you will always have seen the material necessary to do the current task.

Authors: W. White, J. Lasseter

Learning Objectives

This assignment is designed to help you understand the following concepts.

  • It gives you practice with writing your own classes.
  • It gives you practice with writing code spread across many files.
  • It illustrates the importance of class invariants.
  • It gives you practice with using data encapsulation in classes.
  • It gives you practice with both both 1-dimensional and 2-dimensional data.
  • It gives you experience with structuring your code with helper functions.
  • It gives you practice with code reuse through inheritance and the construction of subclasses.
  • It gives you experience writing code for simple artificial intelligence.

Table of Contents

Academic Integrity and Collaboration

This is a brand new assignment; you are the inaugural year. Hence, we are pretty confident that there are no solutions for this assignment available online. This means our concerns about academic integrity are limited to cases where students either violate the collaboration policy, or use AI code assistance. To prevent either of these, we will be using Moss to check for instances of plagiarism.

We also ask that you do not enable violations of academic policy. Do not post your code to Pastebin, GitHub, or any other publicly accessible site.

Collaboration Policy

You may do this assignment with one other person. If you are going to work together, form your group on CMS as soon as possible. If you do this assignment with another person, you must work together. It is against the rules for one person to do some programming on this assignment without the other person sitting nearby and helping.

With the exception of your CMS-registered partner, we ask that you do not look at anyone else’s code or show your code to anyone else (except a CS1110 staff member) in any form whatsoever. This includes posting your code on Ed Discussions to ask for help. It is okay to post error messages on online, but not code. If we need to see your code,we will ask for it.

Connect-N

The Game Rules

The game board is defined by three values:

  • The number of rows (the height)
  • The number of columns (the width)
  • The number needed in a run (the streak)

As the game must allow for wins in all directions, the required streak can never be larger than the number of rows or the number of columns.

Players alternate turns, dropping pieces into a column. The piece will fall down to the first available row. This continues until one of the two players achieves a streak. If so, that player wins the game. If the board fills before that happens, the game ends in a tie.

By default the pieces in our game will have colors red and blue (not black). However, you can change them to any colors that you want once the assignment is done.

An Example Game

As a simple example, suppose we have a game with three rows and four columns. To win this game, we will require the player to make a streak of three (the largest possible streak on this board).

To start this game, the red player drops a piece in the first column. The piece falls to the bottom row.

The blue player responds by dropping a piece in the second column. This piece also falls to the bottom row.

The red player decided to play on top of the blue player by dropping a piece in the second column. This piece falls to the second row, as there is already a piece in the first row.

The blue player sees an opportunity to improve their run by dropping a piece in the third column.

The red player realizes that they need to block the blue player from winning. So they place a piece in the final column, stopping the streak from happening.

The blue decides to try for a vertical streak by placing a piece in the third column. As there is already a piece in the bottom row, this piece falls to the second row.

The red player also places a piece in the third column. This piece falls to the third row, as there are already two pieces in this column. Not only does this block the blue player from creating a streak, this actually creates a diagonal streak from the bottom left corner. The red player has now won the game.

Computer Players

Connect Four (and Connect-N in general) belongs to a family of turn-based games that include chess, checkers, tic-tac-toe, and a few others. These games all share some important characteristics.

No Information Hiding: At every turn, each player has complete knowledge about the entire state of the game. This is in contrast with many card games, including poker, bridge, and so on.

No Randomness: There are no components such as card shuffling, spinners, or dice that produce random values. At every turn, the available moves are completely determined by the moves that have already been played.

Small Number of Possible Moves: At every turn, there is only one move for each unfilled column. In standard Connect Four, this means at most 7 choices.

These facts mean that it is always possible, in principle, to write a computer program to find the best move. This leads to the concept of a rating function. This function evaluates a configuration of the game board and calculates how much value it has for the player who just had their turn.

Given this function, a computer player has a pretty straightforward algorithm to determine its move choice:

for every legal move:
   try playing the move
   calculate the value of the resulting board configuration

pick the move that had the highest value

Rating Functions

The rating function takes a game board configuration and calculates how much advantage this gives to a player. In general, this calculation is done by identifying certain patterns in a board configuration that are known to give better or worse advantage. In the example below, we look at two possible moves for the blue player: one in column 1 and another in column 2 (remember that we start at 0).

Column 1 is not a great choice, as it only produces a run of length one. The choice of column 2 seems better, as it gives a run of three consecutive blue pieces. A simple rating function that measures the run length resulting from a choice would score the column 2 play above the column 1 choice.

Choosing the right patterns to look for can be pretty challenging, and the problem can become subtle very quickly. For example, an even better rating function would score a column 6 move as worse that either other two, even though it also has a run length of 3. The is because that run cannot possibly lead to a win in the example above.

As another example, consider this board where it is the blue player’s turn to chose a move.

The run length considerations for blue are the same the first example (i.e. column 2 produces a run of three, while column 1 only produces a run of length one). However, any play other than column 1 will allow red to win on their next move.

You will not consider the problem of predicting opponent’s responses in the code you write for this assignment, but incorporating opponent’s possible responses, the computer’s responses to those responses, and so on is what championship-level computer players are built to do. Though the rating function you will write is much simpler, you will have a chance to improve it for extra credit.

Assignment Source Code

Download the source code to get the source code for this assignment. As with previous assignments, you should unzip this file and put the contents in a new directory. This time you will see that the folder contains a lot of files.

You only need to pay attention to the files that start with a6. There are five of them. Two are completed and three are only stubs, waiting for you to complete them.

File Description
a6player.py The Player class, to be completed in Task 1, as well as the AIPlayer class, to be completed in Task 5.
a6board.py The Board class, to be completed in Tasks 2 and 4.
a6game.py The Game class, to be completed in Task 3
a6consts.py A module with several constants, which is completed already
a6test.py The test script for the assignment, which is completed already

The Code Organization

Classes are ideal for breaking up a complicated application into parts. We think about the application that we want to create, and identify the individual elements. Each element will be its own type, with its own attributes and methods. In this application we have many types: the player, the game board, and the game referee who controls the rules.

While we talked about how to design classes in lecture, we have made all the hard decisions for you in this assignment. That is because it is not always easy to get it right the first time. We want you to spend your time implementing rather than designing your classes. You will get a chance to do that in the next assignment.

When we design our classes, we often like to organize them in a dependency diagram. A class A depends on a class B if objects of type A need to create and call methods in objects of type B. This notion of dependency tells us the order in which we need to complete the code. If class A depends on class B, then we need to finish implementing class B before we implement class A.

The dependency diagram for our application is shown below.

You will notice that everything depends on a6consts.py. However, we have finished that for you, so you do not need to worry about that. The classes Player and Board have the same dependencies, so we could finish them in either order, as long as we finish them first (though we will do Player first as it is easier). Then we have class Game which depends on both of them. Finally, AIPlayer has the most dependencies, so we have to do them last.

You will learn more about these classes in the assignment instructions. However, we give a brief tour of them here.

Class Player

Even for human players, there are a couple of essential attributes that we need to include. Every instance of the Player class has a player name, and a player color. The name attribute is used to display the player’s name on the screen to indicate that it is their turn (or if they won the game). The color attribute stores the color of the player’s game pieces.

The player class does not do much else. As a human is responsible for deciding the moves of a player, there are no other computations necessary.

Class Board

The purpose of the board is to store the game pieces. A game piece is represented by the color name. So you can think of a board as a two-dimensional list of color names.

However, we make Board a class because it needs to do so much more than a simple list. It needs attributes for the size of the board, as well as the streak necessary to win the game. More importantly, it has methods that restrict how players can add pieces to the board, ensuring that everyone plays by the rules.

The class Board is also where we include our methods for detecting which color has won the game.

Class Game

While the class Board implements a lot of the rules of the game, someone needs to coordinate the players, making sure that they each take their proper turn. That is the purpose of the class Game. As we will learn later in the semester, this is what is known as a controller class. It does not have a lot of methods, but it is the glue that puts everything together.

Class AIPlayer

The class AIPlayer is a subclass of Player. As we said in class, it inherits all of the attributes of Player. It has no new attributes, and does not need a new initializer. However, it does override the method chooseMove which is used to chose a piece on the board. Overriding this method is what will allow you to create a computer opponent.

The Test Script

We have provided a test script for this assignment. As with Assignment 4, there is no need for you to add additional test cases to this script. You will not be graded on your tests. This assignment is complex enough as it is, so we want to give you all the help that we can. With that said, this test script is not guaranteed to be complete. Passing this script will not guarantee you a perfect on the assignment.

To run the test script, simply type

  python a6test.py

just like any other test script. However, there is one additional feature. At the top of a6test.py, there is a variable TASK_LEVEL. You should assign this variable to the current task that you are working on in the instructions. This will help you focus on the code that is relevant for that task.

Alternatively, it is possible to set the TASK_LEVEL on the command line, when you run the script. For example, if you type

  python a6test.py 3

the script will run the tests for Task 3, no matter what the value of the TASK_LEVEL variable is.

The GUI Application

Until you finish Task 3, the only way to test your code is with the test script. However, once you complete Task 3, you can actually play the game Connect-N. To do that, we have provided a new tool for you.

In the source code that you have downloaded, you will see another folder named connectn. This is actually a python application. Inside this folder you will see a bunch of python files. You do not need to understand them, and we actually recommend that you do not try to read them. They will just distract you from the assignment.

To run this application, you run it like a script. But you do not run an individual file. Instead, you run the entire folder, like this

  python connectn

When you do that, you will see a screen asking you to choose the players, like this:

The purpose of this user interface is to allow you to match up humans against humans, humans against AI and even AI players against each other. You can also reassign the color for each player. To do that, click and hold on the colored rectangle. Move the mouse to select a new color. When you release, that will be the color selected.

Once you have decided on the players, click the button Start Game. That will change the screen to look like this:

If you have finished Task 3, you can fill up the game board, but not actually play a game. If you have finished Task 4, two humans can play against each other by taking turns. Finally, if you have finished Task 5, you can use this application to play against a computer opponent. At any time you can use the button Reset to start a new game with these players.

By default, the game will have 6 rows, 7 columns, and require a streak of 4 to win. You can change all of these values and the command line, like this:

  python connectn  ROWS  COLUMNS  STREAK

So to create a board with 3 rows, 4 columns, and win streak of 3, you would use the command

  python connectn 3 4 3

For this to work, the numbers must be valid. The numbers must be positive, and they cannot be greater than 20 (as that is all our graphics program will allow). In addition, the win streak cannot be greater than the minimum of the rows and the columns.

Assignment Instructions

There are two very important rules that you must obey throughout this assignment. The first is that you must enforce all precondition. We have actually provided you with several helper functions throughout the assignment to make this easy. In addition, like Assignment 4, we do not require that you include any error messages. But if any precondition is not enforced, you will lose points. Furthermore, when enforcing type preconditions, we ask that you always use isinstance instead of type.

The other important rule is not an issue with Player and Board, but it is relevant once you start working on Game and AIPlayer. That rule is that no class may access the hidden attributes of another class (e.g. the attributes that start with an underscore). We will talk about the reason for this in class. But it should never be an issue. If you need to access something inside another class, you should call a method and not access the attribute directly. A class can access its own hidden attributes, but if one class accesses the hidden attributes of another, you will lose points.

Suggested Micro-Deadlines

This is a new assignment. We have tested it on the course staff and we are confident that you can complete it. But we also recognize that this is a long assignment. It is substantially more code than the previous programming assignment. If you wait until the last minute to work on this assignment, there is absolutely no way that you will complete it.

To prevent you from doing this, we have included a suggested completion date at the end of each task. These dates are determined by how complex we think each task is. While we do not enforce these dates, we recommend that you try to hit these deadlines. Keeping these deadlines makes sure that you are making slow steady progress. This will help you enjoy the assignment more, and help you retain all the lessons that you learn from this assignment (which will be part of the second exam).

If you cannot make these deadlines, it might be a sign that you are having difficulty and need some extra help. In that case, you should see a staff member as soon as possible.

Task 1: Implement the Player class

The first thing you should do before working on this class is read the class invariant.

    # HIDDEN ATTRIBUTES
    # Attribute _name: The player name
    # Invariant: _name is a nonempty string
    #
    # Attribute _color: The player color
    # Invariant: _color is a string representing a valid color (e.g. either
    #            introcs.tk_color or introcs.web_color returns True).

Note that these attributes begin with an underscore. That means they can be accessed inside the code for Player, but nowhere else. Any other class (like Game) can only access these attributes through a getter or a setter.

This class has five methods: the initializer, two getters, one setter, and chooseMove. The specifications of all of these methods are included in the file a6player.py. The method chooseMove has been completed for you and should not be modified. This method will not be important until you complete Task 3.

Among the other methods, the getters are the most straight-forward. Most of the time, you just need to return the attribute. The initializer is also very simple, because it mainly just enforces the preconditions.

However, the precondition for the attribute _color are very interesting. It is not enough for _color to be a string. It also has to be a string for a valid color. You saw these in Assignment 4. You could change the color of the turtle with color names (e.g. 'red', or 'green') or web colors (e.g. '#7F00FF' or 'ffa500'). To verify that a string is a valid color, there are two functions at your disposal: introcs.is_tkcolor and introcs.is_webcolor. These functions both take a string and return a boolean. These functions are actually used in your code for Assignment 4. You might want to go back and look at how they are used in that assignment.

The final interesting method is the lone setter setName. Read the specification for this method carefully. It does something special if you pass it the empty string.

Testing it Out

To test this past of the assignment, open a6test.py and make sure that your TASK_LEVEL is set to 1. Or you can run the script using the command

  python a6test.py 1

If you pass all the tests, you are done with the task.

We highly recommend that you finish Player by Monday, October 30. This is the Monday after the assignment was posted and should give you more than enough time to read through the instructions. This is a very simple class and should not be that much more difficult than what you have completed in lab already. This also ensures that you have maximum time to work on this assignment.

Task 2: Implement a basic Board class

The class invariants for the Board class define the way that the five attributes must relate to each other in order to give a consistent representation of a game board:

    # HIDDEN ATTRIBUTES
    # Attribute _width: The number of columns in the game board
    # Invariant: _width is an int > 0
    #
    # Attribute _height: The number of rows in the game board
    # Invariant: _height is an int > 0
    #
    # Attribute: _streak: Minimum-length run of same color-pieces 
    #             needed to win
    # Invariant: _streak is an int > 0 and < min(_width,_height)
    #
    # Attribute _board: a 2d table storing the game pieces.
    # Invariant: _board is a 2d table of size _height by _width, containing
    #            strings. These strings are empty or a valid color name
    #
    # Attribute _moves: The saved moves in the game
    # Invariant: _moves is a list of (int,int) tuples and has length
    #            less than _width*_height. It's length is equal to the number
    #            of non-empty places in the board.

One aspect of these invariants means that the first dimension of the 2D list _board will store the row number, while the second dimension gives the column. This convention is known as row-major order, and was discussed in class. While it is also possible to represent tables using column-major order , we will be using row-major order for this assignment.

Your job in this task is to create just enough of the Board class that it can be used to store pieces. This will involve a lot of methods, so we have broken this task into smaller parts.

Part A: Getters and the Initializer

All of the attributes above are somewhat immutable. The first three attributes are fixed by the initializer and cannot be changed. The other two attributes can only be changed by the special methods place and undoPlace, which you will not work on right now. This means that there are no traditional setters for any of these attributes.

However, all of the attributes do begin with an underscore. That means that, if we want to access them in another class, we need to implement getters. And there are quite a few of these: getWidth, getHeight, getStreak, getColor (which accesses the elements of _board), getMoveCount and getLastMove. As with most of getters, these can all be implemented with a single line, with the exception for getColor, which needs to enforce its preconditions.

To test out the getters, you will also need to implement the initializer. This is where things get a little bit interesting. You will notice a method below the initializer called clear. This method is used to reset the board. It creates a new 2d list for _board and a new empty list for _moves. As you need to do this in the initializer as well, there is no reason to write this code twice. So implement clear before you write the initializer, and call this method as a helper in the initializer.

When you create the board, there are no pieces in the board to start with. That means it should be an nested list (of the appropriate size), where all of the entries are empty strings. Because the empty string is going to be commonly used throughout the assignment, we have provided the constant NOBODY in a6conts.py to represent this value. We recommend that you use this in your implementation of clear.

You will notice that both _board and _moves have some fairly sophisticated invariants. However, you do not need to worry about those right now, since the board starts out empty. You only need to worry about these once you start placing pieces.

Testing it Out

To test this past of the assignment, open a6test.py and make sure that your TASK_LEVEL is set to 2. Or you can run the script using the command

  python a6test.py 2

This will actually run tests for all of Task 2, so you will not pass them all. But as long as you pass the tests for Part A, you can be somewhat confident that you have finished this part of the assignment.

We recommend that you finish these first few methods of Board by Tuesday, October 31. This part of the Board class is fairly straight-forward and you should be able to finish it in another day. The purpose of making steady progress is to by yourself time for the more complex parts of the assignment.

Part B: Column Methods

When we drop a piece in the board, we need to know what rows in that column are occupied. That is the purpose of findAvailableRow. It returns the first empty row for that column (or the board height if no row is empty). Remember that a position in the board is empty if it is the empty string. If it contains a color name, it is not empty.

When computing this row, it is important that you understand that the attribute _board is essentially “upside-down”. The first row of the table is the bottom row of the board, and the last row of the table is the top row of the board. If you follow the specification for findAvailableRow exactly, this is what you are doing anyway.

There are also the methods isFullColumnand isFullBoard which are related (and can even use findAvailableRow as a helper). You should implement all of these methods according to their specification.

Testing it Out

You do not need to make any additional changes to a6test.py to test these methods. They are already part of the current TASK_LEVEL. If you pass the tests for Part B, then you should be confident that you are doing well.

You should try to finish these new methods of Board by Wednesday, November 1. These methods are a little more complicated than the getters and initializer, but they are no more complicated than anything you have ever done in lab. So you should be able to finish them in one more day.

Part C: Piece Placement

Now it is time to make things interesting. The only way that someone can add a piece to the board is via the place method. That is to make sure that pieces are added to the correct row for the requested column. Note that this method returns -1 if the column is full and a piece cannot be placed.

When you place a piece, you are treating the board as a two-dimensional table. That means the first row of the table is the first row of the board. But note that this means that the board is actually “upside-down”. On the screen, the first row of the board is the bottom row, while the last row is the top row of the board.

Obviously the method place should assign a color name to the appropriate position. But actually does more than that. When you place a piece, we want to be able to undo that move with undoPlace. This requires us to remember the last move. So when we place a piece into the board at column c and row r, we add the tuple (r,c) to _moves.

Adding this feature this allows us to undo a move with undoPlace. That method looks at the last element of _moves to get a position (r,c). It then removes the color at that position. It also needs to remove this move from the list when done.

Testing it Out

When you complete these two methods, you should now be able to pass all of the tests for Task 2. But if you want, you can also test the methods directly (and this is a good idea if you are having trouble). We have implemented the method __str__ for you, which converts the board into a string that you can print on the screen. This string shows the contents of the board,

For example, start the python interactive shell and type the following:

>>> import a6board
>>> b = a6board.Board(6,7,4)
>>> print(b)
[['','','','','','',''],
 ['','','','','','',''],
 ['','','','','','',''],
 ['','','','','','',''],
 ['','','','','','',''],
 ['','','','','','','']]
>>> b.place(2,'red')
0
>>> b.place(3,'blue')
0
>>> b.place(2,'red')
1
>>> print(b)
[['    ','    ','    ','    ','    ','    ','    '],
 ['    ','    ','    ','    ','    ','    ','    '],
 ['    ','    ','    ','    ','    ','    ','    '],
 ['    ','    ','    ','    ','    ','    ','    '],
 ['    ','    ','red ','    ','    ','    ','    '],
 ['    ','    ','red ','blue','    ','    ','    ']]
>>> b.undoPlace()
>>> print(b)
[['    ','    ','    ','    ','    ','    ','    '],
 ['    ','    ','    ','    ','    ','    ','    '],
 ['    ','    ','    ','    ','    ','    ','    '],
 ['    ','    ','    ','    ','    ','    ','    '],
 ['    ','    ','    ','    ','    ','    ','    '],
 ['    ','    ','red ','blue','    ','    ','    ']]

As you can see, print the string puts the first row of the board at the bottom of the screen. This makes it easy to visualize the board while you play with the methods.

You should try to finish these last methods of Task 2 by Friday, November 3. This gives you two solid days to work on these methods. They are not long methods, but you do need to wrap your head around the relationship between _moves and _board. Plus giving you two days on this activity gives you a little breather in reward for the work that you have done so far.

Task 3: Implement the Game class

Considering its central importance in managing all of the other classes, the invariants for Game are refreshingly simple:

# HIDDEN ATTRIBUTES
    # Attribute _board: The game board
    # Invariant: _board is a Board object
    #
    # Attribute _players: The game players
    # Attribute _players: The game players
    # Invariant: _players is a (possibly empty) list of Player objects, each 
    #            with distinct colors
    #
    # Attribute _current: The index of the current player
    # Invariant: _current is an int >= 0 and < len(_players), or -1 if _players 
    #            is empty 
    #
    # Attribute _winner: The (color of) the winner of the game
    # Invariant: _winner is either None (no winner) or a color of one of the
    #            Players in _players

The one attribute that is a little unusual is _current. The attribute _playersis a list of players. But only one of those players is active at a time. The other players wait their turn until the active, or current, player makes a move. The attribute _current is an index into the list _players that tracks which of these players is the current or active one. Also note that _players can be empty. When that happens (and only when that happens), _current is -1.

Part A: Getters and the Initializer

There several getters in this class: getBoard, getPlayers, getCurrent, getWinner. Most of these are straight-forward. The only unusual one is getCurrent. Despite its name, it does not return a number. It returns either a Player object, or None.

The list of players is the only mutable attribute, so we have two methods that look like setters: addPlayer and clearPlayers. When you implement these functions, you need to pay close attention to the invariant. In particular, look at the preconditions for addPlayer. It is not enough to check that the argument is a Player object. You also have to check that the color of the player does not match that of any existing players. Fortunately, we have provided a function called is_new_player at the bottom of the file to make this easy.

Once you have implemented addPlayer, the initializer is very simple. It creates the board and an empty list of players. It also initializes all other attributes to their defaults (following the class invariant).

Testing it Out

To test this past of the assignment, open a6test.py and make sure that your TASK_LEVEL is set to 3. Alternatively, you can run the script using the command

  python a6test.py 3

Once again, this will actually run tests for all of Task 3, so you will not pass them all. But passing all the tests for Part A is a good sign.

A previous version of the test script would fail, because it was testing advance, a method in Part B. A new version of the test script was uploaded on November 7 to fix this problem.

You should try to finish these first few methods of class Game by Saturday, November 4. The initializer is fairly simple, and you now have a lot of experience with these. The only complex method is addPlayer and we have provided a helper to make this simple All of this should only take you one day.

Part B: The Game Loop

It is now time to run the game. For that you will need to implement three methods: advance, takeTurn and run. The method takeTurn is simple. You get the current player’s move using the method chooseMove and place it in the board. The method advance is used to move to the next player. It does this by updating _current. When _current reaches the end of the list, it loops back to the beginning.

The method run is a while loop that continues until the game is done. It takes the turn for the current player and then advances to the next player if the game is not over. The tricky part is determining when the game is over. You will not be able to do this until you complete Task 4. So for now, you are going to take a shortcut: continue until the board is full (e.g. there is a tie).

Note that run must be prepared for the case where there are no players. If that is the case, this method does not do anything. There is also the case where takeTurn might fail to choose a column. But that can only happen when the board is full, so you do not need to add any new code to handle this case.

Testing it Out

It is still helpful to use the test script a6test.py to check this portion of your code. But at this point you can do something even more interesting. It is now possible to run the GUI application. The method run was the last method that this application needs to work properly.

Run the GUI application and make sure that you have two human players. You can now take turns dropping pieces between the two players. The game will not detect a winner, but it will stop when the board is full. Try testing your game on boards of different sizes.

It is also possible to test out a game with more than two players, if you want to see what happens in that case. The selection screen adds those two players to the game, but it does not remove any existing players. So if you start with some players in the initializer for Game (as opposed to an empty list of players), those players will be included as well. However, if you do this remember to remove those players before submission, as we are expecting Game to start with no players when we grade your submission.

You should try to finish these first few methods of class Game by Sunday, November 5. This is the last straight-forward code in this assignment, as everything past this point is a little more complex. Finishing on time will bank enough time for you to finish the whole assignment with ease.

Task 4: Complete the full Board class

By now, you have most of the application completed. In fact, if your Board class could successfully report winning runs of pieces, you would have a fully functional game for two human players. Your job in this task is to make that happen. Specifically, you should implement the remaining stub methods: findAcross, findNWSE, findSWNE, and findWins.

These four methods are likely to be more challenging, and so we are going to break it up into two parts. But before we do that, it is first worth thinking about the method findWins. This method is going to use all of the other methods as helpers.

The parameters r and c in this function is an important clue to taming this otherwise difficult problem. If playing a move results in a win, all winning streaks will include the piece that was just played. This significantly reduces the number of ways we need to check the game board. Instead of looking at every position, we can start from the location (r,c) and look in the four possible directions that a win could occur.

For example, consider the board depicted below:

In this game, blue is about to play. If the fifth column is chosen, the piece will land in position _board[3][4]. Blue wins with this move, and we can find it by looking only along the four directions that include (3,4).

To keep these methods separate from those in Task 2, we have started naming the parts below with Part D.

Part D: The Method findAcross

You should first start by implementing the function findAcross. Once you understand how this method works all of the other methods will follow quickly after. Fortunately, we have given you a very big hint. If you look, you will notice that we have completely implemented findVertical for you. Though the other methods have to deal other directions, an understanding of how findVertical works should give you the necessary insights for the others. In particular, you will notice that findVertical

  • Starts at the initial row and column
  • Searches downwards until it finds a different color, or it goes past the edge
  • Backs up one, because we want the location of the last piece that is the same color

The method findAcross is similar with two differences

  • You are searching horizontally instead of vertically
  • You need to search in two directions, not just one

The latter is because it is possible to create a winning streak by dropping a piece in the middle of a run. In the picture below, red can win by dropping a piece in column 1.

But this is easier than you think. Simply break the problem into two for-loops, one going left and the other going right.

Testing it Out

When you set TASK_LEVEL in a6test.py to 4, you activate a second set of test cases for Board to validate these new methods. Alternatively, you can access these tests by running the script as

  python a6test.py 4

As usual, the test script will attempt to validate all of the methods in Task 4, not just Part A. But right now you just need to worry about passing the Part D tests.

You should try to finish the method findAcross by Monday, November 6. This is just one method, so you should be able to do that. More importantly, once you do that, you have everything you need for the next part.

Part E: Detecting Wins

At this point you should understand how findAcross works. It is now time to work on findSWNE and findNWSE. To understand these methods, look at the illustration below.

In this illustration we have our starting point (r,c) show all of our runs horizontally and diagonally. The horizontal run goes from (r1,c1) to (r1,c2). The run for findSWNE goes from (r5,c5) to (r4,c4). Similarly, the run for findNWSE goes from (r3,c3) to (r6,c6). With that information you should be able to define those two methods.

To implement findWins, you simply need to use all of these functions as helpers. In particular, findWins searches for a winning streak in the following order:

  • vertically
  • horizontally
  • diagonally from SW to NE
  • diagonally from NW to SE

The method returns the first win that at finds.

Once you have finished that method, there is one more thing to do. You want to update the Game class to use these new methods. In particular, you have to modify the run method so that its while-loop ends properly. Before, you were stopping the loop when the board fills. Now you should stop the loop when someone wins the game. Also, when that happens, you should set the _winner attribute to indicate who one. But be careful! Ties are still possible and you need to be prepared for them.

Testing it Out

The remainder of the tests in a6test.py will help verify that you have completed this task. However, the code is now getting complicated enough that we are not going to guarantee that those tests are anywhere near complete. Our tests miss a lot of places where you could make a mistake.

Fortunately, there is a better way to test! You can now play a real game. Run connectn and try a game between two human players. Play against yourself or another person. Try to win in all sorts of different ways and make sure that your code works correctly.

This part of the code is a major step and the first real hurdle for the assignment. Therefore, we are suggesting you take two days to get it right, finishing by Wednesday, November 8. If you can do that, the end of the assignment is in sight.

Task 5: Implement the AIPlayer class

For the final task of this assignment, you will implement the AIPlayer class. Once you have done this, you will have an application that allows you to play Connect-N with two human players, a human versus an AI Player, or even two AIs against each other. This is the most challenging part of the assignment, but also the most interesting.

Since AIPlayer is a subclass of Player, it inherits all of its attributes. The class invariants for those attributes will apply in AIPlayer as well. Since it has no additional attributes of its own, these are the only invariants to maintain.

Your job here is to override the chooseMove method, together with the five hidden methods in the AIPlayer class. Unlike the Player version of chooseMove, this one takes a bit more work.

Part A: The Rating Function

As we described above, the rating function are the key to implementing an AI for the game. We need some way to give a score to a move. In our implementation, the AI player is going to chose a move that produces the longest possible run (i.e. it will try to get as close as possible to a streak).

To do that we first need two methods. The _score method takes a run (e.g. the result of one of the find methods in Task 4) and computes its length. For the most part this is simple as you can rely on the dist function that we have provided. However, remember that you do need to enforce all preconditions as well. The helper function is_valid_run at the bottom of a6player.py is useful here.

The real work is done by _evaluate, which is the actual rating function. This function looks for the longest run in all directions from (r,c) and returns the length of that run. To implement this, you will use the find methods from Task 4. But those methods want a minimum length, and we don’t know what our minimum length should be yet (as we are just looking for runs, not streaks). So you will need to loop over all possible minimum lengths up the streak size, which is the maximum.

There are two special cases to be aware of for the method _evaluate. If a move is a win, you should give it the maximum possible score. That is the value SCORE_WIN defined in a6consts.py. Also, if you can find no runs, you should return SCORE_BAD, which is the minimum possible score defined in a6consts.py.

For example, given the board configuration below, if blue is the next palyer, the seven possible moves (from left to right) should have scores of 2, 2, 2, 2, SCORE_WIN, SCORE_BAD, and SCORE_BAD.

For the board at below, the scores should be SCORE_BAD, SCORE_BAD, 3, 2, 2, 2, and 3.

Testing it Out

There is one last TASK_LEVEL for the script a6test.py, and that is level 5. You can run that last sequence of tests by either setting that variable to 5, or by running the script as

  python a6test.py 5

Once again, this will include all the tests for Task 5, but you just need to pay attention to the tests for Part A. While these tests are not guaranteed to be complete, they are good at catching common errors.

You should try to finish these methods by Thursday, November 9. Only the _evaluate method is complicated, and that is just putting together functions that you have previously defined as helpers.

Part B: Move Evaluation

It is now time to evaluate possible moves. The method _evaluate is capable of scoring a move after it is made. But we want to compute a score before. How do we do this?

This was the purpose of the undoPlace method that we implemented in Task 2. The AIPlayer can place a piece, score the move, and then undo the placement, making as if it never happened. If the AI player does that for every column, computing a score each time, they can determine the best move.

We break this process up into three methods: _gatherMoves, _evaluateMoves and _findBestMoves. The first method creates a dictionary of all possible moves. The keys are columns and the values are the score. For this method, we assume that all scores are SCORE_BAD. Why a dictionary? Because not all columns are valid moves. Some columns are full. We do not want a column to be a key in the dictionary if it is full.

The method _evaluateMoves takes this dictionary and computes a score (using _evaluate) for each key in the dictionary. That means this is the method responsible for making a move, scoring it, and then undoing the move. In addition, you have to enforce the precondition for the dictionary. Fortunately, we have provided a function is_valid_dict to make that part easy.

Finally, the method _findBestMoves choses the best move. It loops over the dictionary and picks the column with the highest score. If there is a tie, it returns all of the best moves as a list.

Testing it Out

You still have not quite implemented enough to play against an AI player, so you still need to rely on a6test.py to do your testing for this part. And while these tests are not complete, they will get you far enough to do some testing in the next part.

These methods are the last major hurdle for the assignment, so we are going to give you two days to complete them. You should finish them by Saturday, November 11. If you are on target with this deadline, you will have no problem completing this assignment.

Part C: Move Selection

Now that you have determined the best move, it is time to carry it out. You need to override chooseMove in AIPlayer. This method will find the all of the best moves. If there is more than one, it will pick one at random using the random.choice. It will then execute the move. To execute the move, it will call the function set_choice in module connectn. This function takes a color name and a column as an argument. It communicates to the UI where to put the piece.

Of course, now that you have a working AI player, you want to test it out. But fortunately, since AIPlayer is a subclass of Player, you do not need to make changes to you code to get this to happen. Simply start up connectn and select the AI player as one of the two players. These two players have the same methods, so the run method still works as normal. This is the power of subclasses.

Testing it Out

At this stage you should be able to run the script a6test.py with no errors. But that is not the point! It is time to play Connect-N against the computer. Start up the GUI application and make one of the players an AI player.

But we should warn you about the AI player. It makes pretty terrible choices. It will find a winning move if one exists, but the simplistic “move with longest run” approach will often fail against a skilled player. The examples given in the discussion of rating functions illustrate this.

We should also warn you about a very common error that we have seen in testing. Sometimes you have made it this far, but the game seems to hang once it reaches the AI player’s turn. That generally means you forgot to call the set_choice function defined in connectn. You have to do that, or the GUI will not know what choice the AI player made.

If you have been following all of the recommended deadlines so far, you will finish this part by Sunday, November 12. That will give you two more days (yes, we extended the deadline) to fully test everything and clean-up your code before submission. And if you are ahead of schedule, you can even think about working on extra credit.

Extra Credit

You have gotten a taste of how to create an AI player. But it is pretty crappy. Do you have ideas on how to improve it? For example, can you create an AI player that can prevent a loss to blue in the example below?

Can you create an AI that realizes a run of almost winning length is useless if there is no possibility of extending it? Or one that can spot a move that creates a double threat (i.e. a run one short of winning with usable empty spots on either end)? Are there other strategies that we have not mentioned?

If you have ideas on how to improve the AI, you should complete the class BetterAIPlayer, which is provided for you as a stub in a6player.py. We will award extra credit for this. However, be warned that we are not going to award more than 4 points, and most people who complete this will only get two points. This is meant to be a challenge for people that aced the rest of the assignment, not a way to boost your grade. So do not waste your time implementing a min-max strategy if your base implementation is not solid.

You will notice that the stub for BetterAIPlayer is a subclass of AIPlayer. That way, allows it inherit all of the methods of that class. You do not want to have to reimplement all of the methods from AIPlayer. Indeed, all you really need to do in BetterAIPlayer is override the rating function _evaluate, as well as the method _evaluateMoves, which choses which moves to evaluate. You can add new methods if you want, but these two methods are what you should focus on to improve the player.

We do not have any tests in a6test.py to help you with this part of the assignment. But you can test your new player in the GUI application. Simply check Better AI player as one of the opponents, and watch it play.

Finishing Touches

Once you have everything working you should go back and make sure that your program meets the class coding conventions. In particular, you should check that the following are all true:

  • You have indented with spaces, not tabs (Pulsar handles this automatically).
  • Functions are each separated by two blank lines.
  • Lines are short enough (~80 characters) that horizontal scrolling is not necessary.
  • Docstrings are only used for specifications, not general comments.
  • Your name(s) and netid(s) are in the comments at the top of the modules.

You should also make sure that the Game class starts with an empty list of players, as you might have changed that during testing.

We only want you to upload the three files you modified: a6game.py, a6board.py, and a6player.py. We do not want any other files, even if you added more tests to a6test.py. Upload these files to CMS by the due date: Tuesday, November 14.

Completing the Survey

One last time, we need you to do a survey. The survey should be done individually (even if you worked in a group). As always, the survey will ask about things such as how long you spent on the assignment and your impression of the difficulty. Please try to complete the survey within a day of turning in this assignment. Remember that participation in surveys comprises 1% of your final grade.