Nim is a game so old that its origins have been lost. It was likely invented in China, and it is one of the oldest games known. It was also one of the first games to have a computer or electronic implementation and has been the frequent subject of assignments in computer programming classes. This program will implement the game and play one side. The code serves as an example of how to design a computer program using functions and modularity – it is an example of a top- down design.
The game starts with three rows of objects, such as sticks or coins, and there are a different number of objects in each row. In this version, there are 9, 7, and 5 sticks, which are represented by the | character. A player may remove as many objects from one row as they choose, but they must remove at least one and must take them only from one row. Players take turns removing objects, and the player taking the final one is the winner.
Playing this game involves asking the user for two numbers: the row from which to remove sticks, and how many to remove. The human player is prompted for the row, then the number. Then the computer removes some sticks (take its turn) and prints the new state.
A list named val contains the number of sticks in each row. Initially,
val = [5, 7, 9]
This is the game state, and is critical to the game as it defines what moves are possible. Also, when the state is [0,0,0] then the game is over.
When the user choses to remove N sticks from row M, the action is
val[M] = val[M] – N
Of course, N and M must be tested to make certain that M is between 0 and 2, and M is as large as val[M]. M defines the row chosen to remove sticks from, and N is the number of sticks to remove. A move can therefore be defined as a list
A program that uses functions should be built from the highest level of abstraction downwards. That is, the main program should be developed first, and should be expressed in terms of functions that do logical things, but that may not be designed or coded yet. The main program could look something like this:
val = [5, 7, 9] # the game state: 5, 7, and 9 sticks
done = False # Is the game over?
userMove = [-1, -1] # A move is a row and a number of
# sticks.
print (“The game of Nim.”)
rules() # Print the rules for the game
while not done: # Run until the game is over
displayState(val) # Show the game board
prompt(userMove) # Ask user for their move
ok = legalMove (userMove, val) # Was the playerꞌs move
# OK?
while not ok:
print (“This move is not legal.”) displayState(val)
prompt(userMove) # Ask user for their move
ok = legalMove (userMove, val)
makeMove (userMove) # Make it
if gameOver(val):
print(“You win!”) break;
print (“State after your move is “) # display it.
displayState(val)
This program is built using components (modules) that are not written yet, but that have a purpose that is defined by what the program needs. Those mod- ules/functions are as follows:
Using functions, the first thing that is needed is to display the game state. The program prints the number of sticks in each of the three rows, and does so in a graphical way, rather than just displaying the numbers on a console. Given
the situation as described so far, the non-trivial function is displayState(), which prints the current state of the game – how many sticks in each row. It will be passed a list representing the current state.
def displayState(val): # val is the list with
# the state
for j in range(0,3): # there are 3 rows;
# print each one
print (j+1, “: “, end=””) # Print the row number
for i in range(0,val[j]): # val[j] is the
# current row
print (“| “,end=””) # print a ‘|’ for each
# stick
print(“”) # print an end of line
When called at the beginning of the game, here’s what the result of a call to this function would be:
This function does a single task, uses a parameter to guide it and make it more general, and is named for what it does. These are signs of a good function. Note that the first row is labeled “1,” but it is element 0 of the list. It is common in user interfaces to adapt to the standard human numbering scheme that begins with 1 instead of 0. When the user enters a row number, care must be taken to subtract 1 from it before using it as an index.
There is no required order for writing these functions, but the next one used in the program is prompt(). This asks the user to input a row and then reads a row number, then prompts the user to enter a number of sticks to remove and then reads that value, too. The two numbers are placed into a list that was passed so that the values can be returned to the caller.
def prompt (move):
row = input (“Your move: which row? “) # Prompt for row &
# read it
sticks = input (“how many sticks?”) # Prompt for
# sticks & read
# Convert row to integer and decrement to be from 0 to 2.
move[0] = int(row)-1 # Assign to the list[0]
move[1] = int(sticks) # Assign value to list[1]
This function again does a simple task, uses a parameter, and is named appropriately.
Next is the question “Is this move legal?” A move is legal if the row is between 0 and 2 inclusive, and if the number of sticks in that row is greater than or equal to the number of sticks to be removed. The function returns True or False.
Making a move involves decreasing the specified row by the specified number of sticks. This could have been done in legalMove() if it was acceptable to do multiple things in a function. Eventually, that will be necessary, but for now, a new function will be written, named makeMove(), that implements a specified play in the game.
def makeMove(move, state):
row = move[0] # Subtract move[1] sticks from
sticks = move[1] # those that are in row
# move[0].
# Place the new number of sticks in the
state list state = state-sticks
There is a strategy that permits a player to always win. It involves computing what amounts to a parity value and making a move to ensure that parity is maintained. Consider the initial state and the state after taking two sticks from row 1:
Row 1 = 5 = 0 1 0 1 row 1 = 3 = 0 0 1 1
Row 2 = 7 = 0 1 1 1 row 2 = 7 = 0 1 1 1
Row 3 = 9 = 1 0 0 1 row 3 = 9 = 1 0 0 1
Parity 1 0 1 1 1 1 0 1
The parity is determined by looking at each digit in the binary representation of the values. In each column (digit position), the parity bit for that column is 1 if the number of 1 bit in the column is odd and 0 if it is even. This can be calculated using the exclusive-OR operator, which is ^. The strategy in Nim is to make a move that makes the parity value 0. This is always possible if parity is not 0; in the situation above, the computer might remove 5 sticks from row 3 giving the following state:
row 1 = 3 = 0 0 1 1
row 2 = 7 = 0 1 1 1
row 3 = 4 = 0 1 0 0
Parity 0 0 0 0
This is what the sketch does after every move the player makes: it makes all possible moves, computing the parity after each one. When the one with zero parity is found, it makes that move. The function eval() calculates the current parity value as val[0]^val[1]^val[2].
The computer always wins because the user always makes the first move. Alternating who moves first would make the gameplay fairer.
1. The Development Process Exposed
In the introduction to the Nim program, we said that this was an example of top-down design. This means that the larger program, or the main program, is designed first. The question should be what are the steps involved in solving this problem? The answer to that question is written down in terms of functions that have not been written yet, but that have a known and required purpose within the solution. In the Nim game, it is known that the user’s move will have to be read from the keyboard and that the current state of the game will have to be displayed, so those two functions can be presumed to be important to the solution when sketching the main program.
Once the high-level part of the program has been devised, it can be typed in and tested. The functions that are needed but are not yet written can be coded as stubs: functions that do not implement their task but that are present and prevent syntax errors. The first try at a solution of this sort does not solve the problem, but is simply a step towards the solution. In the case of Nim, the very first step could be written as follows:
Repeat
Display the game
Ask user for their move
Make user’s move
Generate computer’s move
Make computer’s move
Until someone wins
Display the winner
None of these steps are written as proper Python code, but that is acceptable for a first step. Translating this into Python comes next.
At this point in the design, neither the data structures nor algorithms used in the solution have been devised. This is merely a sequence of steps that could lead to a program that works. The functions can now be written as stubs:
def displayState(): def prompt():
print(“Display state”) print(“Enter move”)
def makeComputerMove(): def printWinner():
print (“compute a move”) print(“The winner is:”)
The output from this program might be as follows:
Display state
Enter move
Make move
Display state
Enter move
Make move
compute a move
The winner is:
The exact output will be random, depending on what the return value of gameOver() is. This code can be thought of as one iteration of the solution or as a prototype. The next step is to refine the solution by implementing one of the stubs. Each time that happens, a set of decisions is made concerning the nature of the data structures used to implement the solution: the use of a list for the game state, for instance. Three integers could have been used instead, but once the decision is made about the approach, it should be used consistently unless it becomes infeasible.
Repeatedly implementing the stubs creates new prototypes, each one more functional than the one before. Some of the functions may require an application of this same process. Complex functions can be coded in terms of other stubs, and so on. The simpler functions, such as those that calculate based only on their parameter, should be completed first and should not involve permanent design choices.
A programming process of this kind can be thought of as iterative refinement. After the first step, a complete program that compiles and runs should be refined. This can be very useful, especially when dealing with graphical user interfaces and games. The interface might well be complete before any real functionality is present, and this permits a demonstration of the concept before the program is done.
Source: Parker James R. (2021), Python: An Introduction to Programming, Mercury Learning and Information; Second edition.