Coding: Nim

This exercise's goal is to get you comfortable with the software we will be using in this course and different types of programming errors (a very common occurrence!).

Recall from the last activity, we investigated an winning strategy for the two-player game Nim. Only now that you are confident in your solution (and can solve the puzzle yourself) are you ready to express that solution precisely enough as code.

To make a playable game, there is a file of code that you will likely not understand, but rather

Getting Started

• Download this zip file to your computer and move it to a folder on your computer where you want to keep your programs for this course
• Unzip/Unarchive the file if you need to by double-clicking on it (your computer may do this automatically when downloading)
• Open PyCharm, press the Open button (or select File → Open), navigate to where you saved the folder, and select it
• You will need to Trust the project before it can be opened

Play the Game

In the Project Explorer panel, click the arrow beside the lab_nim project to expand the folder and show the 4 Python files inside that work together to make the complete game program:

• Chip.py: determines how a chip is drawn
• Nim.py: determines the rules and the winner of the game
• SmartPlayer.py: determines the computer's strategy for playing the game
• UserPlayer.py: determines interaction with a user choosing to play the game

We will be focusing on the file SmartPlayer.py for today. For practice with drawing using a turtle, you can also play around with Chip.py.

Right-click on the file Nim.py in the Project Explorer and select Run Nim to play the game (you are welcome to look at this code, but likely most of it will not make sense yet).

• To begin the game, you will see a popup window that asks how many chips you want to play with (you can type in any number)
• After this, the computer will choose some number of chips to take, and ask you to take a turn
• Click “1” or “2” as your choice for how many chips to take when it is your turn
• Play the game all the way through — at this point you can probably beat the computer most of the time
• After it is over, click anywhere in the window to quit the game

Examine the SmartPlayer code

Right now you should find it very easy to beat the computer when you play, but our goal is to write the worst video game of all time — a game the computer never loses!

Double-click on the SmartPlayer.py file to open it and you will see the code it is running. Let’s examine how it works.

At the top are comments, text that is ignored by the computer, that include when the file was started, the author's name(s), as well as notes about what the file is supposed to do. Also, notice that the words in the file are different colors: green are comments, orange are python keywords (like def and return), yellow are function names, gray are variable names, etc.

Then there are two blocks of code called functions, named sequence of statements that accomplish a task, that define the things the code knows how to do. In this case, a smart Nim player needs to understand two things:

• goFirst: how to decide if it should go first
• move: how to decide if it should take one or two chips

The functions themselves are very simple, but try to describe the SmartPlayer's strategy based on its code. As a reminder, the word return means “the answer is”.

Change the SmartPlayer code (Step 5: Translate to code)

It seems the “SmartPlayer” code is not very smart yet. Let’s change some things.

Change 1: In the goFirst function, it returns False which means the computer always chooses to go second, no matter the starting number of chips. Change the code so the it always goes first instead. What is the opposite of False?

Change 2: In the move function, it returns 2 which means the computer always takes two chips, no matter the situation. Instead we want to return the remainder when the number of chips is divided by 3. Change the line to:

return 2 numchips // 3

Now try to run the program. At this point, PyCharm will try to validate that your code is written with the correct syntax. You should see a red squiggly/wavy line between the number 2 and the word numchips and you should see that an error has occurred with the message: 

SyntaxError: invalid syntax

This is an example of the most common programming error: a syntax, parsing, or compilation error. You know you have encountered a syntax error when the error occurs before the program is able to begin running.

Change the line to remove the 2:

return numchips // 3

You should see a red squiggly/wavy line under the word numchips. If you try to run the code anyway, you will be able to play the game until that line of code is reached and then you should see should an error has occurred with the message:

NameError: name 'numchips' is not defined

This is an example of the second kind of programming error: a runtime error or exception. It is also sometimes called a fatal error. If you have ever had a program “crash” this is probably the kind of error it encountered. In a runtime error, the code compiles and then it runs — up to a point when something unexpected occurs. Specifically, NameError usually means there is a typo of some sort: a misspelled or mis-capitalized a word, or just used the wrong word. It is important when programming to be exact — earlier in the code it referred to numChips (capital C), so you must match that word exactly in this line.  

Change the line to capitalize the C:

return numChips // 3

Run the code again and this time you should be able to play the game again.

More Kinds of Errors (Step 6: Test it)

Run the code again, but when it asks for the number of chips, type out the word “thirteen”.

You will see the program stop with an error message:

ValueError: invalid literal for int() with base 10: 'thirteen'

This is another example of a runtime error. Our code is not set up to handle input that is not a number and has to stop. When any error occurs, read the entire message to get an idea of what went wrong. In our case, there is no real error in the code — we just did not write code to handle that kind of input. For now we will not change the code.

Run the code again and start with 13 chips (the number this time!) and examine how many chips the computer chooses to take.

According to our logic, the answer should be 1 (the remainder of 13 divided by 3). But the computer chooses 4 chips, which is not even a legal move!

This is an example of the third kind of programming error: a logic error. This is the most difficult error to find and fix because the computer does not know there is a problem. With other kinds of errors, the programming environment gives a message about what the problem might be and what line it occurred on. With a logic error, it is up to you, the programmer, to know the correct answer and check it. It is very important to test the program with all kinds of input to make sure there are no logic errors.

Make it Work (Step 7: Debug)

Open the SmartPlayer code again and examine the line in the move function once more:

return numChips // 3

This code means "get the quotient when dividing the number of chips by 3", not get the remainder. Since 13 / 3 is 4 with a remainder of 1, the code returned 4.

Change this line to:

return numChips % 3

The percent sign in Python means “mod” or remainder. Now the code should correctly choose 1 or 2 chips to remove each time. Compile and run the code to confirm this.

While the smart player should now play optimally, it is still possible for the user to win the game if the game starts with a number of chips that is a multiple of 3. In this case, the smart player should choose not to go first — requiring the user to go first. For this change, look in the goFirst function. Change the return line to add this Boolean check (an expression whose only result is either True or False):

return numChips % 3 != 0

This code says that the computer should go first only when the remainder of the number of chips divided by 3 is not zero. In other words, if it is not a multiple of three chips, then go first.

Now play the game. If done correctly, the computer should never lose. If you are able to beat the computer, use your new debugging skills to fix it.