In the simple version of the game (better called the subtraction game) you start with a variable number of counters (stones, coins, matches, paper clips); two players take turns to pick up 1..n counters (where n is given by the computer or agreed upon by the players). The person who picks up the last counter(s) is the winner (or in the misere - inverse - game, the winner).

The winning strategy is simple: see Jim Loy's Nim page (http://www.jimloy.com/puzz/nim.htm). Let's run the game backwards from your win and assume that the maximum number of counters a player can pick is 5 (i.e. players have to pick up 1..5 counters).

Strategy for a game in which you can pick 1..n counters: if you leave your oponent with a multiple of m(n+1) counters, you win. Otherwise you can loose (unless your oponent makes a mistake).

What is the opponents's optimum strategy? It's the same as yours: to leave m(n+1) counters on the table.

What's the best move if you can't leave m(n+1) counters on the table (i.e. your opponent has left m(n+1) counters on the table, whether by luck or by knowing the winning strategy)?

(This isn't a mathematical proof: it's just my idea of what to do.)

What should you (and the computer) do in a game where you're allowed to pick up 1..5 counters and there are 24..29 counters on the table ^[299] ?

What will happen if the computer lays out 60 counters and you're allowed to pick up 1..9 counters ^[300] ?

Have students play games till the first player can win every time.

Now you know enough to play Nim. It will take several more sections of this document and about 100 lines of code to get a computer to do the same thing. As you progress through the coding, note that processes taken for granted by humans, have to be made explicit for the computer. A human on reaching a branch point will evaluate all the choices, realise that most of them are pointless (I shouldn't play if there are 0 counters), and see the right thing to do. The computer has no global view of the game and only knows about manipulating bytes. You, the programmer, have to give the computer the rules of the game, including the really obvious ones.

Note

You always code in steps, and at each step, the code must work. This is called "evolutionary coding". The name derives from Darwinian Evolution, where to evolve from one organism to another, all intermediate organisms must be viable. A change (mutation) that results in a dead animal is not going to leave any descendants. Similarly your code must work after any change. The people who are paying you to code might come in one day and ask how it's going. If you can show them screens doing this and doing that, and one of them notices a screen that isn't doing anything, you can say "ah yes, I haven't written the code for that yet", and they'll go away happy. They won't be impressed if you tell them you have the best program on earth, but it doesn't run yet [301] . The other method of coding is called "intellegent design", where you design all the code from scratch, then code it all up, but have nothing that works for months, and then wonder why the final code doesn't do what you expected.

Write code (nim.py) in the following steps. Make sure your program runs at each step before you add the next step.

The user isn't always going to enter valid numbers.

This leads to the concept of valid input. The only valid inputs are min_num..max_num. Any other inputs must be trapped, without changing the state of the game, and the user allowed to try again. A tester should be able to pound on the keyboard in any random fashion without the program crashing and the tester should be presented again with the string requesting input. Any other behaviour and the code is called fragile code.

Handling errors is not easy in any language. The modern languages (like python) handle errors better than the old languages. I'm not going to take you through error handling here, however here's a bit of code that asks for user input and will only exit when a valid integer is entered.. Swipe it with your mouse, enter some valid input, invalid input, strings, reals and see what it does even if you aren't familiar with the syntax.

#!/usr/bin/python

#modelled on code from http://www.wellho.net/mouth/1236_Trying-things-in-Python.html

upper = 9
lower = 5
val = 0 #prime the while loop to run by initialising val to an invalid value

while ((val > upper) or (val < lower)):

	#uval is the user entered value
	#it will be the string representation of whatever the user entered,
	#whether it was originally an integer, float or string.

	uval = raw_input("input an integer in the range %d..%d: " % (lower, upper))
	try:
	        #is uval the string representation of an integer?
	        val = int(uval)
	except:
	        #no, it's a string or the string representation of a real. Give the user feedback.
	        print uval + " is not an integer - try again."
	else:
	#yes, val is an integer
	#if invalid value, then help user
	if ((val > upper) or (val < lower)):
	                print "error: val %d is outside range %d..%d" % (val, lower, upper)
	#else valid value, exit while loop

print val

You're about to do another round of surgery on your code. Save your current (working) version of nim.py as the next saved version num.py.v2.

Then use the above code to make a function players_turn(l,u) passing as parameters the lower and upper limits of the number of counters the player can pick up and returning the number of counters the player picked up.

Here's my function players_turn() ^[320] .

The function players_turn() doesn't know the value of counters. Part of the prompt for the user will have to come from the calling code. A ',' at the end of a print statement supresses the carriage return e.g.

>>> number = 1
>>> print "%d" % number,
1

What about the 2nd parameter? Should it be max_num? What if this results in leaving a negative number of counters? If we had such a play, was the previous play (by the computer) a winning strategy ^[321] ? Do we need to worry about this case ^[322] ? Handle this case in the calling code.

If the (counters < max_num) we can't allow the a player to pick up max_num counters. We can only allow the player to pick up counters counters. Here's code that will do this

	upper_limit=max_num	#upper_limit is only used in these lines as a temporary variable
	if (counters < upper_limit):
		upper_limit = counters
	players_resp = players_turn(min_num,upper_limit)

Python has a built-in function min(param1,param2...paramn) which returns the smallest parameter (all languages have a min() although most only take 2 arguments).

The replacement code using the built-in python function min() is

	players_resp = players_turn(min_num,min(counters, max_num))

Using min() we get this code.

	players_resp = players_turn(min_num,min(counters,max_num))

The previous conditional was executed only if the number of counters on the table was less than the number of counters you were allowed to pick up. In the proposed replacement using min(), the function min() will be executed no matter whether counters is smaller or greater than max_num. Will we still get the results we want (try it with max_num==10 with counters==5 and then counters==15) ^[323] ? Use the appropriate code to calculate the values to pass to players_turn().

You're making a nested call to a function (one function calls another function). It makes the code a little harder to read but min() is a well known function, so you should be able to handle this level of complexity.

Here's the change in the calling code in main() ^[324] .

players_turn() contains a nested call to min(). Why is this call to min() in the Nim code OK, but a nested call to compare_results() (see train wreck) is not? It's a judgement call: min() is a function available in all languages - a programmer will recognise the function, and the nesting level isn't terribly deep. You've eliminated 3 lines of conditional code, that you'd have to think about a bit to figure out what it was doing. You could have used a train wreck style call in both cases and no-one would have minded too much.

Writing code is easy for coders. Figuring out an interface that users will enjoy using is beyond most coders. There is often more code in the user interface than in the real guts of the program. At the stage in the program that you've reached, most coders will say "who cares about the users?" and walk away. However you won't get any acclaim or money if no-one uses your code, even if it's correct and does the job perfectly.

While code that doesn't work, or is badly written comes from the first circle of Hell of the programming world, code that works perfectly that no-one can or will use due to lack of documentation or a bad user interface is from the 2nd circle (see Divine Comedy http://en.wikipedia.org/wiki/The_Divine_Comedy).

In the game so far, let's say we've had the following plays

		play	counters remaining
start 			59
player		3	56
computer	5	51
player		4	47
computer	4	43	

Currently the player sees this dialogue with the history of the game scrolling off the top of the screen.

Your turn. There are 51 counters. You can pick 1..9 counters: 4
you're picking up 4 counters. There are 47 left.
the computer picked up 4 counters. There are 43 left.

Your turn. There are 43 counters. You can pick 1..9 counters: 

It would be better if the player could see the game history at each play. Here's a proposed replacement for the last line

XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXccccppppcccccppp
    '    1    '    2    '    3    '    4  ^ '    5    '    
Your turn. There are 43 counters. You can pick 1..9 counters: 

The dialogue above this new prompt would still scroll off the top of the screen, but now the player would be given a fresh summary of the game at each play. Hopefully the points conveyed in this new prompt are

To produce this prompt, we need code to hold the history of the game (i.e. the counters that the player/compute pick up at each turn).

Before doing anything with lists, make sure you understand the basic information about lists.

We'll use a list called plays[] which will hold the plays (int). Here's how we could use append() and a few other commands to store and retreive the game's history (for the moment, we aren't keeping track of the number of counters remaining in play).

#initialise plays[] as an empty list
>>> plays=[]
#add entries to list
>>> plays.append(3)
>>> plays.append(5)
>>> plays.append(4)
>>> plays.append(4)
#write out list (as a list)
>>> plays
[3, 5, 4, 4]
#how many entries are there?
>>> len(plays)
4
#write out the list as individual items
>>> for play in plays: 
...     print play
... 
3
5
4
4
>>> 

In object oriented programming (OOP), the instruction for doing something to an object is object.do_something(), e.g. plays.append(3). You would expect that the instruction returning the number of entries in plays[] to be plays.length(). However python (and a few other languages) use the syntax len(plays). Since length() is ambiguous (it could be the number of items, the amount of memory required to hold the data, or the total length of the strings, rather than number of strings) a better instruction, to show the number of items in a list, would be plays.count(). Understanding why len(plays) is used instead of plays.count() is a part of understanding objects. If you really, really, really understood objects you would know (it appears to be a holdover from the early days of OOP, that should have been deprecated a long time ago). For the rest of us (including me), it would appear that there still aren't enough rockets blowing up.

We want a function to update the list plays[] - call it nim_prompt(). First we need to declare plays[] and to initialise it (to the empty list) with

plays=[]

Where should plays[] be declared? If we declare/initialise plays[] inside our function nim_prompt(), then each time we call nim_prompt(), plays[] will be reinitialised (i.e. set to empty). This will defeat the purpose of plays[], which is to hold information about the state of the game (otherwise called state information).

	Note
	What is state? State (http://en.wikipedia.org/wiki/State_(computer_science)) - information about the configuration of the system. (I know this a somewhat circular definition.)

Non-object oriented languages (e.g. C), allow you to declare a local variable to be static (see Static variables http://en.wikipedia.org/wiki/Static_variable). These variables maintain their value between calls to the function (i.e. the value of the variable is persistent), allowing the function to maintain state.

In some object oriented languages, such as Python, there is no keyword or concept of static. The proper python way of maintaining state through calls, is to create an object (say nim_prompt) which has plays[] stored inside). Since objects persist throughout the existance of the program, the content of plays[] will not be reinitialised whenever a call is made to update nim_prompt().

We don't have static and we aren't doing OOP. What's left?

The oldest way of maintaining state, is to make plays[] a global variable (i.e. to declare it in global namespace), where it will only be initialised once. Being in global namespace, plays[] can be seen (and altered) by all functions. Because of the possibility that you might blunder and write code that changes the global variable in a way you didn't realise, or because someone in the future might add a function that changes a global variable, using global variables is regarded as a poor programming practice. But in the absence of better alternatives, it's the one we're going to use.

We will write a function nim_prompt() to generate the prompt after each play. Since this is a function, we can write and test it independantly of the Nim game code we've written so far. We'll need a dummy main() which feeds the neccessary info to nim_prompt() (here, that the game started with 59 counters and the subsequent 4 plays have been 3,5,4,4). When we're done, we'll move our function nim_prompt() into our game code, and add the appropriate calls to main() in our Nim code. Here's the file we'll start with (call it test_nim_prompt.py). main() has a section for global variables, which is after user defined variables (if you have them) and before main().

#!/usr/bin/python

#functions

def nim_prompt(play, counters):
	#parameters
	#play: number of counters picked up for this play
	#counters: number of counters left after play

	plays.append(play)
	print plays

# nim_prompt-----------------------

#user defined variables (if you have them)

#global variables
plays=[]

#-------------------

#main()

#In the real code these calls will come from a loop in main().
nim_prompt(3,56)
nim_prompt(5,51)
nim_prompt(4,47)
nim_prompt(4,43)

# test_nim_prompt---------------------------------

This version of nim_prompt() has little functionality beyond accepting its parameters. The function at this stage is called a stub. It allows main() to go about its business as if nim_prompt() was fully functional. We can then write code for nim_prompt() when we're ready and without disturbing main(). Another person can continue working on the original Nim code, while you work on nim_prompt().

Here's what happens when we run this code interactively under python. The first four lines of output are from the nim_prompt() instructions in the file; then at the python prompt you enter the next two plays. You can put in almost any numbers as parameters at this stage: they don't have to be consistent with the rules of Nim.

# python -i test_nim_prompt.py
[3]
[3, 5]
[3, 5, 4]
[3, 5, 4, 4]
>>> nim_prompt(10,33)
[3, 5, 4, 4, 10]
>>> nim_prompt(9,24)
[3, 5, 4, 4, 10, 9]
>>> 

Alternately we can import the function

# python
Python 2.4.3 (#1, Apr 22 2006, 01:50:16) 
[GCC 2.95.3 20010315 (release)] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> from test_nim_prompt import nim_prompt
[3]
[3, 5]
[3, 5, 4]
[3, 5, 4, 4]
>>> nim_prompt(10,33)
[3, 5, 4, 4, 10]
>>> nim_prompt(9,24)
[3, 5, 4, 4, 10, 9]
>>> 

Right about now you've probably noticed that plays[] is a global variable, and that play is passed from main() to nim_prompt() only to be used to modify plays[], which is back in global namespace. You're wondering why I didn't just have plays.append() in main() rather than go through all this bother.

It would be quite reasonable to have plays.append() in main(). It turns out once I committed myself to the poor programming practice of using a global variable, I was on the slippery slope to programmer's hell and would have no choice but to engage in more poor programming practices. You can choose whether you have plays.append() in main() or in nim_prompt(), but here are some of the factors involved -

As it turns out, we're going to accumulate enough code in nim_prompt(), that we'll be pushing it out into it's own functions as we write it.

The next step is to write code to output the current number of counters. What we're going to output a symbol (say an "X") across the screen, one for each counter. Unfortunately we can't just print "X" in a loop. Here's two attempts showing that it can't be done

>>> last_number=15
>>> for x in range(last_number):
...     print "X"
... 
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
>>> for x in range(last_number):
...     print "X",
... 
X X X X X X X X X X X X X X X
>>> 

You can't turn off the carriage return (the first part of the example). Python inserts a blank even though you told it not to do so (the second part of the example). Doing something, even when you told it not to ,is part of the spec 6.6 The Print Statement, so there! You aren't allowed to complain about it. No other language presents you with this problem.

Let's try another approach.

>>> output_string = ""
>>> last_number=15
>>> for x in range(last_number):
...     output_string += "X"
... 
>>> print output_string
XXXXXXXXXXXXXXX
>>> 

You did remember the fencepost problem? How many "X"s did we get ^[325] ?

The string output_string will become part of our prompt. output_string will have a new value each time nim_prompt() is called. Where should we declare output_string: in main() or in the function nim_prompt() ^[326] ?

Copy test_nim_prompt.py to test_nim_prompt_2.py, insert the code which generates the "X"s into your nim_prompt() and check that you get sensible output. Here's my version of the code ^[327] and here's the output showing the number of counters left (along with the content of plays[] for debugging purposes) ^[328] .

You could run this program interactively (python -i test_nim_prompt2.py) and make further calls to the function nim_prompt() from the python prompt.

Note

You always save working code. You never obliterate working code by writing over it with new code. If you're going to add/change code, you copy your last working file to a file with a new name. If you mess up, you can go back to your last working code. You only add pieces of code in small enough chunks that you can get them going in the time you have. You don't want to have to walk away from non-working code, only to return in a few days time, to spend the first 30mins wondering what you were trying to do. Some people can write 100 lines of code and have it work the first time. If you can't write more than 5 lines of code and be reasonably confident that it will work, then only write code in chunks of 5 lines. It's nice if you can write a piece of code independantly of your main code, and add it later as a function. This requires that the new piece of code doesn't need a whole lot of information/data from your already built piece of code. Modular programming requires that only small amounts of information (parameters, and return values) are passed to and from modules, so normally this isn't a limiting requirement.

The code to output the "X"s works. The code you've written is short (two lines) and no-one would quibble if you left it in nim_prompt() and continued coding. However we're going to add several more logical pieces to nim_prompt() and it's going to get quite long if we don't do something about it. Inside test_nim_prompt_2.py change the code, that writes out the number of counters, to a function show_counters(). show_counters() has these specs

Write documentation for show_counters() and nim_prompt(). Remember that the documentation should be sufficient to let another person write code that does the same job, without them seeing your code.

Test that you get the same results when you run your code. Here's my code ^[329] and here's my output ^[330] .

If this piece of code (from the code above)

	output_string = ""
	output_string += show_counters(counters)

was changed so that the first line was deleted, what change would you have to make to restore the program to its original functionality ^[331] ?

Copy test_nim_prompt_2.py to test_nim_prompt_3.py. We don't need to send multiple plays to nim_prompt() anymore - we just need to know the state at the last play. In test_nim_prompt_3.py, change main() to the following.

#main()

#nim_prompt(3,56)
#nim_prompt(5,51)
#nim_prompt(4,47)
plays=[3,5,4]

nim_prompt(4,43)
# test_nim_prompt_3----------------------

This replaces the first 3 plays with the results of the first 3 plays, i.e. an updated version of plays[]. After the last play we still have

print plays
[3, 5, 4, 4]

Next we append, to the prompt, the strings showing the computer's plays and the player's plays. (We're going to do this in stages; the initial code will produce output that isn't quite correct, but we'll fix that as we go.)

We need to write out these plays with a p (for the player's play) or a c (for the computer's play), with the most recent play being appended to the string of "X"s first and the first play being appended last. Which player made the most recent play and how do we know ^[332] ? What code would we have to use to implement this (here in pseudo code) ^[333] ?

Add code to nim_prompt() to announce the player (computer/player) who made the last (most recent) play, using the length of plays[]. Print a "p" if is was the player; print a "c" if it was the computer. For now, we're not going to determine the number of counters picked up, only who made the most recent play.

Here's my test_nim_prompt_3.py ^[334] . When you ran it, did you get the correct output ^[335] ? Now we know whether to append a string of "p"s or "c"s, to the string of "X"s, to represent the last (most recent) play/entry in plays[].

	Note
	How can we know which player made the last (most recent) play, without knowing what they played [336] ?

The last entry in plays[] determines the first characters ("p"s or "c"s) to write after the "X"s in output_string. Next we determine the number of "p"s or "c"s to write. Looking through the methods/functions available for lists, we find that the only command available to look at the last entry in a list is list.pop(). This gives us the last entry and at the same time removes (pops) that entry from the list. This last property precludes the use of plays.pop() to write out the contents of plays[]. Why (what will be the state of plays[] after we've contructed the user prompt) ^[337] ?

The only non-destructive way to look at the contents of a list is for list_entry in list:. This looks from the first to the last entry in the list

>>> plays=[3,5,4,4]
>>> for play in plays:
...     print play
... 
3
5
4
4

However, however we want to read the list from the last to the first entry.

At this stage we have to solve

These are routine problems confronted by programmers. In the next two sections we develope a solution for each of these problems (we only need one solution; either solution will do).

Looking in the functions/methods available to work on lists, we find list.reverse(). This code reverses the order of a list with

list.reverse()

You don't have to assign the result to another list (although you can); the contents of the list are now in reverse order (this is called reversing in place). How would we use this to write out the plays in nim_prompt() ^[338] ?

Copy test_nim_prompt_3.py to test_nim_prompt_4.py. Start a new function reverse_append_plays()

Here's my code ^[341] and here's the output ^[342] .

	Note
	You don't have to get code to work correctly on the first run - you just have to know what's wrong with it. First you get your code to run, then you get it to run correctly, then you get it to run fast. It's quite OK to have the wrong letters output for the players for the first attempt. You can however check that you printed the right number of letters.

Now we need to get the correct player_char as we iterate through plays[]. How might we do this?

The player_char (ex)changes each time we pick a new play from plays[]. Can you think of code that will look at the current value of player_char and set it to the other symbol (I used an if/else)? Write a piece of code (call it exchange_player_char.py) that starts with

player_char="p"

or

player_char="c"

and gives player_char the other value (this is called an exchange operation and is common in computing). Here's my code ^[343] and here's the output ^[344] .

Copy test_nim_prompt_4.py to nim_prompt_5.py and add in the code from exchange_player_char.py to give the correct output string for each play.

	Note
	You would normally leave this code in the calling function and not make a separate function. You're doing this because I'm going to show you a different way of doing the exchange and I don't want the two pieces of code to collide.

Look at nim_prompt_5.py to decide where you need to put the call to exchange_player_char(). Since python indents are white space (rather than sets of {}), it's easy to make mistakes with indenting. I commented out the printing of plays[] and the initial printing of output_string, since neither of these are needed for debugging anymore. Here's my code ^[345] and here's the output ^[346] .

Here's another way of changing player_char. Conditional statements slow down computers. It takes much longer to fetch instructions and data from memory than it does to execute them, so CPUs prefetch code in a pipeline, with all the code and data lined up ready to go. If a branch occurs, then one pipeline has to be thrown away. The time waiting to refill the pipeline slows down processing (known as a pipeline stall). The point is to have all instructions and data that will be executed in the future known now (so it can be fetched). Branching results in a pipeline stall.

In an interactive game like we're playing here, speed is not a concern. As well, since we're doing it in python, we aren't worried about speed either.

However if you wanted to avoid a conditional statement, here's how you'd do it.

First calculate the results of both branches (both the results if the number of plays is odd and is even). It turns out that calculating both branches (if they're short) of a conditional is faster than finding that you have the wrong one and having to wait for the pipeline to refill. In our case, the two branches are short and the results are simple (the result is a "p" or a "c" or for the other possibility "c" or "p"). In both cases ("p", "c"), when you first calculate player_char, calculate the other value as well.

	if (player_char == "p"):
	        not_player_char = "c"
	else:
	        not_player_char = "p"

Now after outputting each set of player_char (the first set being "cccc"), you swap player_char to the other character. You don't have to keep track of which character is being output; you just have to tell the program to swap the character after each play. Here's the swapping code (standard code for exchanging the value of two variables).

	temp = player_char
	player_char = not_player_char
	not_player_char = temp

Copy test_nim_prompt_5.py to test_nim_prompt_6.py and incorporate the new code (and comment out the old code). Here's my version of the code ^[347] . The output is the same as before.

Copy nim.py to nim_2.py. Copy the functions from test_nim_prompt_6.py into nim_2.py and modify main() to use your functions, using main() from test_nim_prompt_6.py as a guide as to what must be added to your program.

Do you need to display the new prompt after the both player's plays? Does the computer need to see the prompt after both plays? Does this help the user? Try nim_2.py only displaying the new prompt once for the pair (player/computer) of plays. What happens to the prompt if you do this ^[348] ? What's the problem and how do you fix it ^[349] ?

Here's nim_2.py ^[350] .

In the new prompt line, can you easily see the difference between a "p" and a "c"? If not change the output so that you can (e.g. make one symbol an UC). Copy nim_2.py to nim_3.py. I did a bulk find and replace of "p" to "P".

In the previous section we handled the problem of having no instruction to read the list plays[] from the back to the front, by reversing the list and reading the reversed list from the front to the back.

Here we look at ways of reading the list plays[] when pop()ing a list, removes the entries, thus destroying our record of the game. The solution is to make a copy of plays[] and pop() the entries off the end of the copy. At each step we know the length of the copy and hence who made the last play.

The next question is whether to build the new code inside a copy of nim_2.py or a copy of test_nim_prompt_6.py. If we build inside nim_2.py, to test the code, we'll have to play the game each time. However the amount of added code is small (so we won't have to play the game for long to test our code) and we won't have to do surgery transferring code from test_nim_prompt_6.py.

Inside nim_3.py make a copy of reverse_append_plays() as pop_plays(). and in the copy of the function, change all occurences of the string nim_prompt_reverse to nim_prompt_pop. Now modify nim_prompt_pop()

When you're done playing with the code, leave nim_prompt() calling either reverse_append_plays() or pop_plays().

Here's my code ^[351] .

The last piece of the new prompt is

    '    1    '    2    '    3    '    4  ^ '    5    '    

Where in nim_prompt() do we know the length of this string and the position of the "^" ^[352] ?

Write a piece of code (call it test_legend.py) with the following specs

Where will the code in test_legend.py:main() go when you merge test_legend.py with nim.py ^[353] ?

There's a minor wrinkle here. In earlier languages, strings were arrays of characters, where every character could be individually manipulated/written/read. In object oriented languages (like python), strings are constants which you can only read. The string.append() (or pop()) function/method generates a new string as part of the operation and throws the old one away. If you want to do operations on individual elements you need a list[]. After you have the characters in your list[], you copy the contents to a string.

Here are some list[] methods that will help with making the legend (from An Introduction to Python Lists. http://effbot.org/zone/python-list.htm). All of the list operations modify the list in-place. If you haven't done so already see the info in lists.

Assemble your output in legend_list[] and then convert the list to a string. Here my code ^[354] and here's the output

# ./test_legend.py
0    '    1    '    2    '    3    '    4  ^ '    5    '   

Copy nim_3.py to nim_4.py and merge test_legend_code.py with nim_4.py and test it out. Do your numbers line up correctly with the string above it? If not, what's the problem and what's a fix for it ^[355] ? Try both to see which you like. Fix your code. (Even at the end, there are fiddly little things, you hadn't thought of, that need to be fixed. A lot of thing don't quite work properly. It always happens.)

Here's my code for nim_4.py ^[356]

People will quickly give up playing an opponent that wins every time (and you won't get any money from people buying your games). In that case, we have to write a version of the code where the computer sometimes makes mistakes.

We'll change the code so that the game has 3 levels

Initially we'll hard code the level of play into the game, then later we'll let the user control the level.

Currently the computer's turn is handled by computers_turn(), which makes perfect plays. We'll change the code to first call another function play_at_level(). This code will decide whether to pass the call on to computers_turn() or to a new function which makes mistakes.

How do we get the program to make mistakes? If we want the computer to make a bad play, we tell the computer to pick a random number in the range of allowed counters. Occasionally this play will be right, but it will only be right by chance.

If we only sometimes want the computer to play badly, say 20% of the time, what do we do? We let it first decide if it's going to make a good or a bad play: it first picks randomly amongst 5 numbers (say 0..4). If the computer picks a selected number (let's say we make the number 0, which it will pick 20% of the time), then for that play, the computer makes a bad play, otherwise it plays perfectly. How would we do the coding if we wanted the computer to play badly 80% of the time, 10% of the time ^[357] ?

So there are two steps; the first to work out whether to make a good or bad play, the second to calculate the play.

Looking up Generate pseudo-random numbers (http://docs.python.org/lib/module-random.html), here's a useful function

# python
Python 2.4.3 (#1, Apr 22 2006, 01:50:16) 
[GCC 2.95.3 20010315 (release)] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> import random
>>> random.randrange(4)
3
>>> random.randrange(4)
2
>>> random.randrange(4)
3
>>> random.randrange(4)
2
>>> random.randrange(4)
1

randrange() has the same syntax as range(). random.randrange() takes upto 3 parameters ([start],stop,[step]), (so you can start the range at 1 if you want, rather than with 0 as I did in the example above). The default values for the optional parameters (the ones with []) are start=0, step=1.

Now we write a skeleton for some code: start a file set_level.py with the following specifications. (You aren't starting real coding yet - put comments where you don't have code. The code must run, but doesn't have to do anything useful at this stage.)

in main()

in play_at_level()

This is the original code (schematically). It calls computers_turn() which plays perfectly.

#functions
def computers_turn(counters,max_num):
	result = int 	#number of counters picked up
	return result

#main()

max_num=9
counters=43

number_counters=computers_turn(counters,max_num)

Let's look at what has happened when we insert play_at_level in the call chain to intercept the call to computers_turn()

Here's my skeleton. This is perfectly good code: it runs, though it doesn't do a whole lot yet. Comments will become the fully functional code.

#! /usr/bin/python

def play_at_level(level, counters, max_num):
	
	#result = computer_play_expert(counters, max_num)	#returns an int, the number of counters to pick up
	#result = computer_play_random(counters, max_num)	#returns an int, the number of counters to pick up

	result = 0	
	return result

#main()

max_num=9
counters=43
level=0

turn = play_at_level(level,counters,max_num)
print "the computer picked up %d counters" %turn
# set_level.py ----------------------

Get your version of this code to the stage where it runs.

Next copy set_level.py to set_level_2.py set up conditionals in play_at_level() so that

Here's my code ^[358] . Check that your code works for all levels (e.g. try level 5,9...).

	Note
	While if, elif, else statements are fine for small numbers of cases, if statements don't scale well - the construct would be hard to read if we had 10 levels to handle. In other languages there is a case statement to handle such situations, but python doesn't have this.

Copy set_level_2.py to set_level_3.py.

Set (level==1) and show that your code makes bad plays about 20% of the time. Here's my code ^[359] .

Copy set_level_3.py to set_level_4.py. Currently we have a commented call to computer_play_random() as the code for the computer to make a bad play. What code is needed to make a bad play and what information does this code need from the rest of the program ^[360] ?

Will this work if counters < max_num)? If not fix the code ^[361] .

This is one line of code. Does it need to be written as a function ^[362] ?

We initially assumed we'd need a function to handle a bad play, but we've just found we don't. Use this piece of code in set_level_4.py to make the bad plays. Check that you get random answers about 20% of the time for level==1 and all the time for level==2. Here's my code ^[363] .

This code is now functional except for the one line of commented code, a call to computer_play_expert(). Where will this code come from ^[364] ?

Copy nim_4.py to nim_5.py Make a list of the things you'll need to change in nim_5.py to merge set_level_4.py ^[365] .

Don't be too upset if your code doesn't work first time (mine didn't - I forgot some of the things above and there were some bugs in the code, which I fixed in the notes, so you won't see them). Try a few rounds at each level. Check that the computer plays badly when it should play badly and that you can recover when the computer makes a mistake.