Program design: Nim game

0:00- [Instructor] Let's design a program with multiple files. We wanna build a basic version of the strategy game Nim. In Nim, players take turns removing either one or two stones from a pile. Whoever removes the last stone loses. In the version we're building, we want the user to play against a computer player.

0:18That means we'll probably want a function that decides how many stones the user picks up and a function that decides how many stones the computer picks up. Let's start by creating a new module for our game components to live in. I think I'm gonna name this stones.py because, at the very least, I know I'm gonna have some functions for picking stones.

0:37I'll name one pick for user and the other pick for computer. I don't wanna get too stuck on this detail right now, so I'm gonna have the computer always pick one stone and I'll figure out a better algorithm later. The user, on the other hand, needs to pick their number of stones via input prompt.

0:56So in pick_for_user, I'll call the input function and then I'll return out the number of stones that the user entered. However, we wanna make sure that this function can only ever return one or two, so we can use a loop to validate the user's input. If they don't enter one or two, we repeat the prompt.

1:14Now that we have a couple functions sketched out, let's switch over to thinking about the main game logic. So I'll jump to the main.py file. The game continues with players picking stones until the pile runs out, which kinda sounds like a while loop. While there are still stones, play a turn.

1:31So like with all while loops, we'll initialize our pile before the loop. In the loop condition, we'll check if the pile is greater than zero. And then inside the loop body, we need to update pile. So we'll call pick_for_user and subtract that number of stones.

1:46We defined pick_for_user in the stones module. So in order to call the function, we'll need to import stones and then prefix the function name. Okay, let's pause and test that our loop works. Because there are 10 stones, if I pick up two every time, the loop should terminate after five iterations.

2:06Now let's add in the computer player's turn. Just like the user, the computer will pick a number of stones and remove those from the pile. But we can't just put this in the loop body after the user's turn, because what if the user has already picked the last stone?

2:19A computer shouldn't get another turn 'cause the game's already over. Instead, we wanna alternate players on each iteration of the loop. So we'll add a new variable to keep track of who's turn it is. Since there are only two possible states, we can make this a Boolean.

2:33If it's true, we play the user's turn. And if it's false, we play the computer's turn. Then at the bottom of the loop, we just swap it to the other player. If it's true, we change it to false. And if it's false, we change it to true. Okay, let's try this out. It seems like we have a pretty good working prototype here.

2:50So now it's time to jazz up the user interface. First, I think it would be nice if the program told us who won. We know the game is over after the loop has terminated, so we'll print out the result here. Whoever went last must have picked the last stone, but we already swapped over the turn at the bottom of the loop.

3:07So if it says it's the user's turn, then the computer picked the last stone. And to make it clear that you don't wanna pick the last stone, I'll print out the rules at the top of the program. It might also be nice to draw the pile of stones. I'll define a new function for that so I can change up how the pile looks without having to touch my main logic.

3:28The function will take in a number of stones as a parameter and return out a picture. Let's maybe draw a little circle for every stone. Then back in main.py, I can just call show and print out its result. These circles look cool, but they're a little annoying to count.

3:44So I'll go back to the show function and include a number in the picture. Now let's play test. We'll run through the program a few times and see if anything feels off. Hmm, the strategy isn't really all that interesting. If the game always starts with the same number of stones, I would just do the same thing every time.

4:03So let's randomize that pile size with a new function. That's much better, but it's still not that interesting 'cause it's pretty obvious that the computer is always picking one stone. At the very least, it can randomly return one or two, but we wanna make it a bit smarter than that.

4:21So it should take the number of remaining stones into account. If there's one stone remaining, then the computer has no choice but to pick one. If there are two stones remaining, its best option is to pick one stone so it leaves the opponent with the last stone.

4:36Similarly, if there are three stones, it should pick two. But what if there are four stones? It seems like no matter what you pick, you're kind of in a bad position because if you pick two, then your opponent can pick one and leave you with the last stone. But if you pick one, your opponent can pick two and still leave you with the last stone.

4:55This gives us some interesting insight. If the computer can leave its opponent with four stones, then it's won the game. So if the computer has five stones remaining, it should pick one to leave the opponent with four stones. And if it has six stones remaining, it should pick two.

5:10Two also leave the opponent with four stones. Okay, let's implement the algorithm that we have so far. If we have one, two, or five stones, we wanna pick one. And if we have three or six stones, we wanna pick two. Otherwise, by default, the computer will just pick randomly.

5:27Let's test real quick that all those cases work. Back in main.py, I'll call pick_for_computer with a few different arguments just to make sure I get back the return values I expect. The computer seems to be a worthy opponent now, but there's still room to optimize the computer's algorithm.

5:46What's its best move if the pile has eight stones or nine? I'll leave that as an exercise for the viewer. And there's a pattern if you map out more numbers.