CS21 Lab 5: More Advanced Functions

Written portion: due in class Friday, October 12

Programming portion: due Saturday, October 13, before midnight

Make sure all programs are saved to your cs21/labs/05 directory. Files outside this directory will not be graded.

$ update21
$ cd ~/cs21/labs/05/

Note that there is a written portion to this lab that is due Friday in class. Also make sure to finish the programming portion before you leave for Fall Break. You may not receive an extension for issues related to travel.

Programming Tips

Use a comment at the top of the file to describe the purpose of the program. (Include your name and the date.)
Use meaningful variable and function names.
Use comments for each function that include:
- a description of what the function does
- a description of the input parameter value(s)
- a description of the return value
Write your programs incrementally (a little bit at a time) and test them as you go.
Don’t assume that if your program passes the sample tests we provide that it is completely correct. Come up with your own test cases and verify that the program is producing the right output on them.

Topics for this assignment

stack diagrams
functions
lists

1. Stack Diagram

The first part of the lab involves you tracing a program with functions and showing the resulting stack that the function calls generate. This is excellent practice for what will almost certainly be a quiz question! Download the PDF, print it out, and turn it in at the start of class Friday, October 12.

2. Tic-tac-toe

In tictactoe.py, you will implement a version of the popular Tic-tac-toe game. In this game, players alternate between placing their symbol (either an “X” or an “O”) inside a 3x3 grid of squares. The first player to get “3 in a row” (either on a row, a column, or diagonally) wins.

In our version, the user will play against the computer (the Artificial Intelligence, or “AI”). The AI will always play first and use the symbol “O”, and the user will play second with a symbol “X”. The game can end with the user winning, the AI winning, or a draw.

Here are examples of these three situations:

User wins:

$ python3 tictactoe.py

***********************
Welcome to Tic-Tac-Toe!
***********************

Enter your choice like the numbers below:
-------
|0|1|2|
|3|4|5|
|6|7|8|
-------

AI chooses: 7
-------
| | | |
| | | |
| |O| |
-------

Enter 0-8 for your choice: 4
-------
| | | |
| |X| |
| |O| |
-------

AI chooses: 5
-------
| | | |
| |X|O|
| |O| |
-------

Enter 0-8 for your choice: 5
Invalid input: 5
Enter 0-8 for your choice: 10
Invalid input: 10
Enter 0-8 for your choice: -3
Invalid input: -3
Enter 0-8 for your choice: 0
-------
|X| | |
| |X|O|
| |O| |
-------

AI chooses: 3
-------
|X| | |
|O|X|O|
| |O| |
-------

Enter 0-8 for your choice: 2
-------
|X| |X|
|O|X|O|
| |O| |
-------

AI chooses: 1
-------
|X|O|X|
|O|X|O|
| |O| |
-------

Enter 0-8 for your choice: 6
-------
|X|O|X|
|O|X|O|
|X|O| |
-------

You win!

AI wins:

$ python3 tictactoe.py

***********************
Welcome to Tic-Tac-Toe!
***********************

Enter your choice like the numbers below:
-------
|0|1|2|
|3|4|5|
|6|7|8|
-------

AI chooses: 0
-------
|O| | |
| | | |
| | | |
-------

Enter 0-8 for your choice: 2
-------
|O| |X|
| | | |
| | | |
-------

AI chooses: 8
-------
|O| |X|
| | | |
| | |O|
-------

Enter 0-8 for your choice: 6
-------
|O| |X|
| | | |
|X| |O|
-------

AI chooses: 3
-------
|O| |X|
|O| | |
|X| |O|
-------

Enter 0-8 for your choice: 1
-------
|O|X|X|
|O| | |
|X| |O|
-------

AI chooses: 5
-------
|O|X|X|
|O| |O|
|X| |O|
-------

Enter 0-8 for your choice: 7
-------
|O|X|X|
|O| |O|
|X|X|O|
-------

AI chooses: 4
-------
|O|X|X|
|O|O|O|
|X|X|O|
-------

-------
|O|X|X|
|O|O|O|
|X|X|O|
-------

AI wins!

Draw:

$ python3 tictactoe.py

***********************
Welcome to Tic-Tac-Toe!
***********************

Enter your choice like the numbers below:
-------
|0|1|2|
|3|4|5|
|6|7|8|
-------

AI chooses: 2
-------
| | |O|
| | | |
| | | |
-------

Enter 0-8 for your choice: 8
-------
| | |O|
| | | |
| | |X|
-------

AI chooses: 7
-------
| | |O|
| | | |
| |O|X|
-------

Enter 0-8 for your choice: 4
-------
| | |O|
| |X| |
| |O|X|
-------

AI chooses: 5
-------
| | |O|
| |X|O|
| |O|X|
-------

Enter 0-8 for your choice: 3
-------
| | |O|
|X|X|O|
| |O|X|
-------

AI chooses: 6
-------
| | |O|
|X|X|O|
|O|O|X|
-------

Enter 0-8 for your choice: 1
-------
| |X|O|
|X|X|O|
|O|O|X|
-------

AI chooses: 0
-------
|O|X|O|
|X|X|O|
|O|O|X|
-------

It's a draw!

In order to implement tic-tac-toe we will be using a list of characters to represent the board. The board will begin as a list of 9 empty spaces:

board = [" "," "," "," "," "," "," "," "," "]

The board will be modified over the course of the game. So if the AI chooses 3, then the board will change to:

[" "," "," ","O"," "," "," "," "," "]

And then if the user plays 7, the board will look like:

[" "," "," ","O"," "," "," ","X"," "]

Strategy and Tips

It is incredibly important that you use incremental development. First read through the entire lab writeup below. This outline is a good starting point - you should complete one step at a time, thoroughly test it to see if your program works, and only move on after getting it to work. The ninjas and lab instructors will ask you to backtrack and do incremental development if you do not follow this strategy.
If you try to implement the whole program at once, it will likely take a lot of time and energy to fix the bugs that accumulate.

Recommended strategy: we recommend writing main first, assuming all your helper functions are working perfectly. Then write the signatures of each of the functions (function name and parameters), and get them working in a very minimal way. For example, displayBoard could just print the list directly, and userTurn could always modify the 0th cell. Once you get the function “stubs” working, implement and test each function in turn (in whichever order makes sense to you).

Main Function

Your main() function should use the functions below to do the bulk of the work.
The general outline of the program is as follows:

Print out a welcome message and a board that has the numbers filled it. If you like, you may put these welcome printouts inside a function. Note that you should use your displayBoard(..) function for this part, but instead of passing in the empty board, use a list of the first 9 integers (represented as strings). Here is an example that you may use (but think about how you could build this up using a loop).

sample_board = ["0","1","2","3","4","5","6","7","8"]

Set up initial variables before entering the game loop. You will need at least the board and a way to keep track of whether someone has won yet.
Set up your game loop. Each time through the loop, either the user will play, or the AI will play. We recommend using a for loop so that the loop index variable can be used to see whether it’s the AI turn or the user turn. However, you are welcome to use a while loop if you prefer. Make sure that the board is modified during each turn. If one of the players has won and the for loop is not over yet, simply do not do anything within the loop.

Here is an example of a for loop that prints out numbers in a list until the first 5 is reached. In this code, after a 5 is found, nothing happens within the loop, we simply “run it out”. This loop makes use of a boolean flag, but it is not a while loop, since we may never find a 5. Think about how to use this example as a template for your game loop.

my_lst = [7,10,8,3,5,4,3,5,8]
found_five = False
for i in range(len(my_lst)):
    if not found_five:
        if my_lst[i] == 5:
            found_five = True
            print("Found 5!")
        else:
            print(my_lst[i])

# output:
7
10
8
3
Found 5!

After the game play is over, print the outcome of the game to the screen (AI wins, user wins, or a draw).

Helper Functions

You are required to use functions for this lab, and they must match the specifications given here. You should read this all the way through and only start programming when you have a good understanding of how main() will use each of the other functions:

aiTurn(board): this function takes in a list of characters and modifies the board to reflect the AI’s chosen cell (no return value). The cells are numbered 0-8, inclusive. The choice cannot be a cell that is already taken by a symbol. You are welcome to make an “intelligent” AI, but the recommended approach is to make the computer choose a cell randomly. Have the computer choose random cells until if finds one that is free, then mutate the board to reflect this choice. In addition, print out the AI’s choice. Example:

AI chooses: 7

userTurn(board): this function again takes in a list of characters and modifies the board to reflect the user’s chosen cell (no return value). You may assume the user will enter an integer. However, you should check that:
1. The integer is between 0 and 8, inclusive.
2. The cell is not already taken by a symbol.

Keep asking the user to choose an integer until they choose a valid cell. For example, if there were already a symbol in the 5 cell, the user choice might look like this:

Enter 0-8 for your choice: 5
Invalid input: 5
Enter 0-8 for your choice: 10
Invalid input: 10
Enter 0-8 for your choice: -3
Invalid input: -3
Enter 0-8 for your choice: 0

displayBoard(board): this function prints the current board to the screen. It takes in the list of characters, and there is no return value. For this function, you should use a for loop to print each row in turn. As a reminder, you can use range with multiple arguments. If three arguments are given, we interpret them as range(<start>,<stop>,<step>). For example:

>>> list(range(0,10,2)) # start at 0, go up to but not including 10, count by 2's
[0,2,4,6,8]

We recommend using string formatting and indexing to print each row. Here is a similar example that prints out the names of the CS21 ninjas:

ninjas = ['Ayaka   ', 'Christie', 'Kendre  ', 'Kenny   ', 'Maleyah ', 'Mikey   ',
          'Rohan   ', 'Shayne  ', 'Sky     ', 'Tai     ', 'Tristan ', 'Zach    ']

print("-"*28)
for i in range(0,12,3):
    print("|%s|%s|%s|" % (ninjas[i],ninjas[i+1],ninjas[i+2]))
print("-"*28)
print()

# output:
----------------------------
|Ayaka   |Christie|Kendre  |
|Kenny   |Maleyah |Mikey   |
|Rohan   |Shayne  |Sky     |
|Tai     |Tristan |Zach    |
----------------------------

isWinner(board, symbol) - this function takes in the board (list of characters) and a symbol (single character). It returns a boolean: True if the player represented by this symbol has won the game, and False if they have not. For example, if the board looks like this:

-------
|O|X|X|
|O|O|O|
|X|X|O|
-------

and symbol is “O”, then you should return True. But if symbol is “X”, you should return False. There are a lot of cases to check for this function. You should use a for loop to check the rows and another for loop to check the columns. The diagonals can be checked separately. This function should NOT return True if the game is a draw, it should still return False.

Extra Challenges

There are several ways to extend tic-tac-toe! Here are a few, but feel free to be creative:

Make a copy of your program in megatic.py that allows the user to specify the dimensions of the board. Think about how to modify your functions to handle a square board of any size.
Make a copy of your program in smarttic.py that implements an AI with a better strategy than randomly guessing.

3. Answer the Questionnaire

Each lab has a short questionnaire at the end. Please edit the QUESTIONS-05.txt file in your cs21/labs/05 directory and answer the questions in that file.

Turning in Your Labs

Don’t forget to run handin21 to turn in your lab files! You may run handin21 as many times as you want. Each time it will turn in any new work. We recommend running handin21 after you complete each program or after you complete significant work on any one program.