Sometimes it’s the simplest assignments

It’s the week before finals and I asked my C Programming class for feedback about the semester. We had productive, hour-long discussion in which everyone participated. Among the questions I asked was: which assignment did you like the most?

The answer astonished me: They had to modify a simply program we had written during lecture and add a few features to it, each time committing the changes to a Mercurial repository. When they were done, they were to push the repository to BitBucket where I would inspect the program and give them credit. Easy-peasy.

I invented that assignment at the last moment, just before lab time about two weeks ago, to fill up an hour that would have otherwise gone unused. What I figured it would have taken them about 45 minutes to do in reality took about 90 minutes. They found the assignment more challenging for a variety of reasons:

  • Many of them had used Mercurial or set up a BitBucket repository despite being shown it and given instructions to do so some two weeks prior.
  • They had never modified someone else’s program to add features.
  • They had never thought about coding in an iterative, cyclic fashion: add feature, test it, commit, repeat.

What I thought would be a trivial, almost throwaway assignment turned out for many of them to be the most practical, instructive one of the entire semester. It was not so much about using some particular C language feature that we had just learned; instead it was about the process of programming–using the tools, putting iterative development into practice, and reading third-party code.

I pointed out that in industry, this would likely be what most of their programming would be like: using a VCS and modifying an existing codebase.

It was suggested that I ought to give more assignments like this one. Add features to an existing program. Fix programs with bugs in them. Glue together parts of an incomplete program. They gave me some great ideas for collaborative projects, too.

I always figured that writing programs from scratch were the most instructive. Certainly, they said, there’s a place for that. But it’s a nice break once in awhile to puzzle over someone else’s code.

Advertisements

A preview of my winter break

Although I’m on the Distance Learning committee at my institution, I’m one of only a few faculty on the committee that doesn’t teach an online course. I joined the committee because I have an interest in a) making high-quality online courses available and b) making sure the learning management system (LMS) that we use is suitable for both online and on-ground courses. Myself, I love and crave the classroom experience, but I’m increasingly intrigued by the idea of offering an online course.

The opportunity has come up to take my Introduction to SQL course online. I’ve been hesitant to do so for one primary reason: it’s a lot of work. I would be embarrassed to put up a bunch of links to readings, assignments, tests, and call it good. That is, frankly, a waste of students’ time and money. Unfortunately, it’s what qualifies as an “online course” at many institutions–even my own. If I’m going to make an online class, I’m going to do it right, by golly. That means lots of instructional videos, Socratic-style quizzing, and peer reviewing (when appropriate).

Luckily, there are lots of role models for best practices. I sign up for  Coursera and Udacity courses simply to take a look at how the content is presented. My current favorite course is Programming Languages from Coursera, taught by Dr. Dan Grossman of the University of Washington. I can’t link to an actual video, but here is a screenshot.

Screenshot of Coursera Lecture

Highlights of his presentations:

  • In addition to Powerpoint presentations with a few key points he does lots of live coding on screen. The main window you see there is him typing in programs and running them during the lecture.
  • His face appears in the video. You can see him talking the entire time. This is huge. It’s like he’s talking to me. When there’s nothing else going on in the terminal window or on the slides, I can watch him. When students can see or hear the instructor, they are more engaged successful. I’m not camera shy.
  • The videos are relatively short (5-15 minutes each) with small quizzes scattered throughout. (Udacity rules the roost when it comes to Socratic quizzing, though.) Each week there are about 1.5 hours of videos to watch.
  • Production value is pretty low, to be honest. It’s just a screen, a talking head, and a low-quality microphone. But that’s the state of the art in online education in 2013.

Here’s one of my videos in an attempt to emulate what Grossman does. I think it came out pretty well.

I have also done some videos in the Khan Academy style: disembodied voice with a pen tablet.

My work is cut out for me this winter break. To qualify to teach the course online in the fall, I need to have 25% of the content prepared by March. (We are one of the only institutions that peer-reviews course content before it goes live. The ACCJC accrediting institutions gave us high marks for that.)

I have “new computer” lust. I’ll need a new machine to handle all this video editing, right? Right?

Buying Arduino supplies online

Arduino UNOI use the Arduino Uno in my System Programming in C course. While most of the programming projects are done on a Linux system, using the Arduinos for a couple weeks mid-semester is a nice break from text-based C. Some students are inspired to buy their own boards and want to know where to buy parts such as switches, resistors, motors, and so forth.

First and foremost, Arduino is a real organization based in Italy. They design and manufacture their own boards. It costs real money and effort to create new products. Support them whenever possible, because what they’ve done to inspire makers around the world has been phenomenal.

Local Retailers

Radio Shack sells real Arduino boards and starter kits. You’ll pay full retail price, but if you want the genuine articles and need them now, this is the place to go.

Fry’s also sells Arduino-compatible boards and kits, such as the OSEPP Uno R3+. The prices aren’t any better than Radio Shack’s, though, so my own personal preference would be to get the real thing and support Arduino.

Online US Distributors

Jameco is a great online US store. They cater to electronics hobbyists by allowing you to purchase in small quantities. Some sample products are:

Maker Shed is a mecca for anyone interested in tinkering around with robotics, wearable art, 3D printing, and drones. They are affiliated with the fabulous Make Magazine and the annual Maker Faire in the Bay Area. Look here for Arduino boards as well as good starter kits that includes a project book and all the parts necessary to build them.

SparkFun Electronics sells a plethora of development boards, including ARM, Raspberry Pi, Beagle, AVR, mbed, and of course Arduino. (SparkFun is where I bought the first set of Arduino Unos that you used in this class.) They also design and sell their own line of sensors and I/O devices, conveniently mounted on boards for easy connection.

Many Arduino kits don’t include a USB cable. Monoprice is the place to get all your cables such as HDMI, Cat5e/Cat6, USB, DisplayPort, optical, and home theater wire, as well as very inexpensive networking gear (switches, patch panels, etc.), IPS monitors, speakers, and much more. Overnight shipping is shockingly cheap. Don’t pay more than a few dollars for any cable, ever again.

Overseas Distributors

If you don’t mind waiting a week or more for your order to arrive, you can’t beat the prices of Asian distributors. They often offer free shipping and quantity discounts.

Deal Extreme sells thousands of gizmos, some of them downright weird. But buried in their vast catalog is a section titled Arduino & SCM Supplies. This is where I purchased mini breadboards and micro servo motors. Other goodies include bundles of pre-cut hookup wires, 16×2 LCD display with keypad, and power supply for breadboards.

Sain Smart sells a limited selection of Arduino-compatible boards and related accessories such as motors and sensors, as well as respectable Chinese test equipment like oscilloscopes and logic probes. This is where I bought “High Quality” Arduino Uno R3-compatible boards for $10 each. Check out the rest of their Arduino-compatible lineup, all for 50-65% less than the real Arduinos. Lots of hobbyists think these are the best clones for the price.

AliExpress is a bazaar of thousands of independent sellers under a common roof. Personally, I get choice paralysis when I browse around AliExpress — there are just too many choices, all of questionable quality and service. I have never ordered from them, but some people say this is the place to get the best deals if you can stomach it.

eBay

Many of the discrete components you used in this class I got from individual sellers on eBay. Overall, I’ve had good experiences with them, but some people have philosophical objects to using PayPal to transfer money. Your mileage may vary, as they say.

LEDs

Who doesn’t like LEDs?

All the LEDs you used are 5mm diffused round. You can get them in smaller and larger sizes, rectangular or round, diffused or concentrated.

My favorite seller is sweetflower8588. Look in the left sidebar to select the size and shape of the LEDs you want. Free shipping and it comes in about a week.

The common-cathode RGB LEDs I bought from bestshop2008hk.

Resistors

I found two distributors of resistors on eBay that I like. Both are based in the US.

The first is E-Project Electronics. They mostly sell resistors, but also a few other discrete components.

The other is FoxyTronics. Their selection of resistors is quite limited, but wow they are cheap and the free shipping is fast.

Switches

I don’t know how long this seller will be around, but here are micro push-button switches that are great for breadboards. They sell a lot of other components, but I have no other experience with them.

Servos

Deal Extreme sells a huge selection of servos.

For high-quality mid-sized servos, such as the continuous rotation servos, look no further than Parallax, just west of us in Rocklin. They don’t have a storefront, but you can go to their offices and buy parts directly from them.

HobbyKing also sells an enormous selection of servos. But shipping takes nearly forever.

Since servos are used in radio-controlled hobbies, you can also get them from nearly any hobby store that sells RC planes, boats, etc. Sometimes their prices beat the online distributors. Shop around.

Check on eBay, too.

Things that bug me about Python

Python, love it or hate it, is a bizarre mix of procedural, functional, and object-oriented syntax. There are lots of things to like about it, but also lots of things to dislike. Here are some of my peeves. I’m sure I’m not the only one.

Versions

What do Windows and Python have in common? Everyone uses the prior, obsolete version and whines about the new version. Python 3 has been out for what, five years now, and people still prefer Python 2.x for everything?

Is version 3.x the Vista of Python?

Sets

This is a set of three numbers: {1, 2, 3}
This is a set of three strings: {‘pizza’, ‘hot dog’, ‘soda’}
This is not the empty set: {}. No, that’s a dictionary. What you meant to write was set(), of course.

Speaking of dictionaries…
Use braces to define an empty dictionary:
>>> D = {}
Use square brackets to access it.
>>> D[‘foo’] = ‘bar’
>>> D[‘foo’]
‘bar’
But get the contents of the dictionary and see it using braces:
>>> D
{‘foo’: ‘bar’}
Sometimes you have to use a method with dictionaries:
>>> D.keys()
dict_keys([‘foo’])
And other times you must use a function:
>>> len(D)
1

The Perl monger in me dies a little bit when I see that.

Strings

Want to convert a string into a list of characters? Use the list function, which I guess is OK:
>>> list(‘hello’)
[‘h’, ‘e’, ‘l’, ‘l’, ‘o’]

Want to convert that list back into a string? Use the join method of a string object:
>>> ”.join([‘h’, ‘e’, ‘l’, ‘l’, ‘o’])
‘hello’

IDLE

Want to give your language the impression that it’s slow: make the primary user interface as glacial as possible. Why is IDLE scrolling sooooo slow?

How about porting a native GUI toolkit to Python so it doesn’t have to rely on Tck/Tk? I can’t tell you how much frustration me and my students have had because the Tk implementation was borked, or there was some weird interaction between Python and Tk. At least Python 3.3.3 for the Mac comes with Tk built in now, but it has bloated the download size tremendously.

But then again…

I’ve still chosen to use Python 3 in my discrete structures course. It has a rich set of datatypes (lists, sets, tuples), comprehensions, a REPL, is cross-platform, is a “cool” and “hip” language, and amazes Java programmers with its handling of large integers.

I just try not to show my students the dark underbelly parts of Python that drives me crazy.

Cheating, round 1

cheating

The assignment was to write a C function that trims the newline character off a string, if it is present. The function takes a string as an argument, trims it in place, and returns nothing.

Here’s what one student turned in:

void trim(char *s)
char *tr ( char *s )
{
  int i = 0;
  int j = strlen ( s ) - 1;
  int k = 0;

  while ( isspace ( s[i] ) && s[i] != '' )
    i++;

  while ( isspace ( s[j] ) && j >= 0 )
    j--;

  while ( i <= j )
    s[k++] = s[i++];

  s[k] = '';

  return s;
}

Announcement to all students: we teachers can use Google, too.

What the $heck?

Did you know the dollar sign ($) is a valid character in a Java variable name? Imagine my surprise when a student showed me the method he wrote. It’s supposed to calculate the amount of tip to leave at a restaurant table.

/**
 * Given the dollar amount of the bill, return 15% tip.
 */
public double tip(double $)
{
    return $ * 0.15;
}

I was so sure this was a bug in the IDE that I submitted a bug report. Then I read the Java spec on identifier names.

Computational Games, part 3

If you’ve been following along, you should have a working Java program that builds the entire game tree for the “1, 2, … 10” two-player game. We are now going to add some code to compute each node’s win/loss status.

(This is the third part of a series on computational games. Read part 1 and part 2 before tackling the code here.)

Start by refactoring the class to add a winLoss attribute. Its values will be W (win), L (loss), or ? (don’t know yet). Also modify the constructor and toString methods accordingly. The changes are highlighted in green.

public class OneTwoTen
{
    int player;
    int pile;
    OneTwoTen add1;
    OneTwoTen add2;
    char winLoss;

    public OneTwoTen(int player, int pile)
    {
        this.player = player;
        this.pile = pile;
        this.add1 = null;
        this.add2 = null;
        this.winLoss = '?';
    }

    public String toString()
    {
        return "(" + player + ", " + pile + ", " + winLoss + ")";
    }

All the other methods remain as they are.  Don’t you love nicely modularized code that “just works” when you make changes?

We can’t know whether a particular node is a win or a loss until we know what its children are. So we’ll do this from the bottom up as described in part 1 of this series.

The leaves are handled specially: they are automatically losses. (By the way, this is only true for games where the goal is to be first to finish. In other games, such as “Even or Odd,” the goal is to have an even number of tokens regardless of who took the last one. Therefore, the leaves are not strictly losses.)

For all other nodes, we call doWinLoss on the children, then figure out if there are any losses among them. If there are, we are a win. Otherwise, a loss.

public void doWinLoss()
{
    if (add1 == null && add2 == null) winLoss = 'L';
    else
    {
        if (add1 != null) add1.doWinLoss();
        if (add2 != null) add2.doWinLoss();

        if ( ((add1 != null) && (add1.winLoss == 'L'))  ||
             ((add2 != null) && (add2.winLoss == 'L')) )
             winLoss = 'W';
        else
             winLoss = 'L';
    }
}

That’s all there is to it! Run it like this:

OneTwoTen root = new OneTwoTen(1,0);
root.buildTree();
root.doWinLoss();
root.printTree();

You should see that the root (1,0) node is labeled with a W to indicate it is a winning position — the first player is guaranteed a way to win. All other nodes will be labeled according to the rules discussed in part 1.

Want to try this on your own? Modify the program to implement the Even or Odd game. Here are the rules:

  • Start with 15 tokens in the pile. Each player maintains their own piles, initially with zero tokens in them.
  • At each turn, a player can take one, two, or three tokens from the central pile and adds them to their pile.
  • The game is over when the central pile is empty.
  • The winner is the player with an even number in their pile, regardless of who took the last tokens or who has more.

Some key points to consider when writing the program:

  • Each node will have three children because you can take 1, 2, or 3.
  • The win/loss status of the leaves depend on who has an even number and are therefore not automatically losses.
  • The in-order traversal of the tree won’t be pretty. You might be better off with a pre-order traversal: display the node first, then call printTree on each of the children.

When you’re done, you’ll be able to answer the central questions: will the first player win or lose the game? What moves should each player make?

In later posts, we’ll tackle some harder problems:

  • “Loopy” games, in which a move may take you back to a state you’ve already seen. Checkers is a well-known example of a loopy game — once a piece is kinged, it can move back and forth on the board.
  • You may have noticed a lot of duplication among the nodes. A total of 232 states are in the tree, but there are only twenty-one distinct states. How can we avoid computing and storing the duplicates? This will help us deal with games that have a lot of states.

Along the way, you’ll learn some more advanced data structures, such as HashMaps, and Java techniques for using them effectively.

Computational Games, part 2

Let’s see about coding up the “1, 2, … 10” game so the computer can arrive at the same conclusion we did: that player 1 is going to win the game.

Read Computational Games, Part 1 for the background material.

Each node in the tree is represented with:

  • The player number (1 or 2)
  • The number of tokens remaining in the pile
  • Pointers to the child nodes

(By the way, the content of this blog is aimed at university/college freshman and sophomores. The code is straightforward with not a lot of fancy syntax until it’s needed.)

Let’s define a Java class to represent a OneTwoTen node. We’ll also provide a convenient constructor for setting the attribute values and a toString for displaying them.

public class OneTwoTen
{
    int player;
    int pile;
    OneTwoTen add1;
    OneTwoTen add2;

    public OneTwoTen(int player, int pile)
    {
        this.player = player;
        this.pile = pile;
        this.add1 = null;
        this.add2 = null;
    }

    public String toString()
    {
        return "(" + this.player + ", " + this.pile + ")";
    }
}

Here’s how to define a few nodes:

OneTwoTen n1 = new OneTwoTen(1, 0);    // The initial state
OneTwoTen n2 = new OneTwoTen(2, 10);   // One of the leaf nodes
OneTwoTen n3 = new OneTwoTen(1, 6);    // A mid-game node

(I use BlueJ for a lot of my coding. Its Code Pad feature lets me simply type in statements like the ones above. With BlueJ, I can quickly test code without laboriously defining a main method. If you’re not using BlueJ, you’ll need to put the statements into a main.)

We can inspect the nodes, again in the CodePad:

> n1.player
1 (int)
> n1.pile
0 (int)
> n2.player
2 (int)
> n2.pile
10 (int)
> n1.toString()
“(1, 0)” (String)
> n3.toString()
“(1, 6)” (String)

Next, define a method called spawn that creates a node’s children. For a node where the pile is 10, there’s nothing to do. If the pile is 9, only one child is created. In all other cases, both children are spawned.

The otherPlayer method is a helper. It simply returns the number of the other player.

public void spawn()
{
    if (pile == 10) return;   // Nothing to do for the leaves
    else if (pile == 9)
    {
        // Only one child here
        add1 = new OneTwoTen(otherPlayer(), pile + 1);
    }
    else
    {
        add1 = new OneTwoTen(otherPlayer(), pile + 1);
        add2 = new OneTwoTen(otherPlayer(), pile + 2);
    }
}

public int otherPlayer()
{
    if (player == 1) return 2;
    else return 1;
}

Try it out:

> OneTwoTen n1 = new OneTwoTen(1, 0);
> n1.spawn();
> n1.add1.toString()
“(2, 1)” (String)
> n1.add2.toString()
“(2, 2)” (String)

Looks good! To build the whole tree, we’ll spawn a node’s children, then call buildTree on each of the children, telling each one to build their own trees.

public void buildTree()
{
    spawn();
    if (add1 != null) add1.buildTree();
    if (add2 != null) add2.buildTree();
}

Did it work? Let’s see…

> OneTwoTen n1 = new OneTwoTen(1, 0);
> n1.buildTree();
> n1.add1.add1.toString()
“(1, 2)” (String)
> n1.add1.add2.toString()
“(1, 3)” (String)
> n1.add1.add1.add1.toString()
“(2, 3)” (String)
> n1.add1.add1.add2.toString()
“(2, 4)” (String)

Sure looks like it! It would be nice to see the whole tree, though. The next method below prints the tree, but it’s sideways. You’ll need to turn your head 90 degrees to the left to see it.

The first printTree method takes an integer argument that tells it how far to indent the node. It calls printTree on the take2 node (so it appears on the right side of the sideways tree), then prints itself, then calls printTree on the take1 node. This is called an in-order traversal.

The second no-argument method just calls the first one with an indent of 0.

public void printTree(int indent)
{        
    if (add2 != null) add2.printTree(indent + 1);

    for (int i = 0; i < indent; i++) System.out.print("   ");
    System.out.println(toString());

    if (add1 != null) add1.printTree(indent + 1);
}

public void printTree()
{
    printTree(0);
}

I’ll leave it to you to call printTree after building the tree and seeing the fruits of your (well, my) labor.

In the next post, I’ll show you how to assign the win-loss label to each node.

Computational Games, part 1

Consider this simple, two-player game. The rules are easy:

  • Both players take turns adding tokens to a central pile, which starts empty.
  • Each player on their turn can add either one or two tokens.
  • The player who adds the tenth token wins.

Go ahead: find a friend and play this game. You don’t even need tokens to play; on your turn just announce how many you’re adding to the pile and what the new value of the pile is. Play the game a few times.

I’ll wait here.

Got it? Great!

While you were playing, you probably discovered that when the score reached a certain point, it became evident that one of the players was going to win no matter what the other did. In other words, the game was essentially over at some point before the score reached ten. There are a few such points in the game. I’ll leave it to you to discover where they are.

This game, which we’ll call “1, 2, … 10,” falls under the category of computational games. With such games, we can use a computer to map out all possible states and moves and completely solve them. Once solved and armed with the tree of all possible moves, a human (or computer) can be unbeatable.

Other computational games include:, Tic-Tac-Toe (or Naughts and Crosses), Othello, Checkers, Connect 4, Nim, Mancala, Chess, and Go. They share a common set of characteristics:

  • Fixed number of players
  • All players have full information; nothing is hidden from any of the players
  • No randomization, such as dice rolls or drawing cards from a shuffled deck

Many beloved games are not computational games, such as poker (hidden cards and randomization), Chutes and Ladders (randomization), Yahtzee (dice rolls), Stratego (hidden pieces), and Hangman. It doesn’t mean we can’t write computer programs to play these games; they just don’t fall under the category of computational games.

Now that we know what computational games are, let’s set about visualizing them as trees.

We’ll represent each state of the 1, 2, … 10 game as a pair of integers: the player number (1 or 2) and how many tokens are in the pile. The initial state is (1, 0). Each state has two possible next moves, the result of adding 1 or 2 to the pile. (Except near the end of the game, where some of the states have only one possible next move.) Here are the first few turns of the game.

The first two moves of the game.

Notice that each row alternates between player 1 and 2. In the top row (the initial state), it is player 1’s turn. The middle row is player 2’s turn. And the bottom row is player 1’s turn.

Some terminology and concepts are worth going over:

In computer science, each of the boxes is called a node. The whole thing is called a tree, even though it is typically drawn upside-down. The topmost node is the root. The nodes at the bottom are called leaves. Each parent node has at least one child, except the leaves that have no children. The root of the tree has no parent.

Let’s draw a few more moves. As you can see, the tree is lop-sided: there are more moves on the left side of the tree because each move increments the score by one, whereas the right side increments by two.

The full game. Not all moves are shown.

At the bottom of the tree are all the end-game states, where the score is 10. We will label each of the states depending on whether they are a winning state or a losing one.

Normally you’d think of the “10” states as wins, but look closely: they are actually losses. Consider the (2,10) state at the far right. It is player 2’s turn and the score is 10. Therefore, player 2 has lost the game because, in reality, the other player won by placing the last two tokens. If player 2 finds himself in that position, he has lost. We label (2,10) as a loss.

Indeed, each of the “10” states are losses for that particular player. All the (1,10) states are losses for player 1 and all the (2,10) states are losses for player 2. We’ll color the losing states red.

The losing states (the “10” states) are colored red.

Now, if the leaf states are losses, the ones immediately above (their parents) them must be wins. Take a look at the (1,8) state just above the losing (2,10) at the far right. It must be a win for player 1 because all she has to do is play two tokens and force player 2 to lose. Player 1 is guaranteed to win from this position.

(I should make it clear at this point that both players are playing to win. No one makes a boneheaded move. Of course player 1 could lose by playing only one token, but she’d be stupid to do so. She’s going to win by playing two tokens.)

The (2,9) states are likewise wins for player 2. He’s guaranteed to win by putting player 1 into a losing position.

In fact, all states that are parents of a losing state are wins. We will color all of them green.

All states with a losing child are wins (green).

What about the other nodes? Consider the (1,7) position, whose children are (2,8) and (2,9). How should we color it?

Unfortunately, it is a loss for player 1 because no matter what move she makes, player 2 will win. We must color the (1,7) node red to signify it is a losing position. The (2,7) state near the middle of the drawing is also a losing state by similar reasoning.

I hope you discovered this tidbit while you were playing the game with a friend. If it was your turn and the score was 7, you were going to lose no matter what you did. (In fact, it wasn’t a game of trying to be first to reach 10; instead the goal was to be first to reach 7.) All “7” states are losses and we should color them red.

All the “7” states are losses (red).

At this point, we can establish a couple of general rules for identifying whether a state is a win or a loss:

  • A state is a win if at least one child state is a loss.
  • A state is a loss if all child states are wins.
  • A state is a draw if there are no losing children and at least one of them is a draw.

The third rule (draw) doesn’t apply to this game because it cannot end in a draw. I’ve included it here for future reference.

Note that to identify whether a particular state is a win or a loss, you don’t need to look any further down the tree than the next move. Start by labeling the leaf states (the ones at the bottom) and work your way up to the root of the tree, applying the three rules above. This leads us to the final coloring.

The final coloring of the game tree.

Something amazing has happened here: the initial state (1,0) is a win! Put another way: player 1 is going to win the game if she doesn’t make any mistakes. Every time.

What move should she make to assure herself of a win? She should aim to force player 2 to lose by playing one token. Player 2, finding himself in the losing (2,1) state, can do nothing to guarantee himself a win.

Armed with this complete game tree, both players can use the information to try to win the game. All they have to do is look for their current position in the tree and see if there are any moves that put the other player into a losing state. If there is at least one, take it. But if there are none, perhaps they should just resign. Or hope the other player goofs up.

What’s next? Try playing the games described below. See if you can figure out whether the first or second player wins, and what the winning strategies are.

Even or Odd: Start with 15 tokens in the pile. Each player takes turn removing one, two, or three tokens from the pile and keeping them. When all the tokens have been removed, the winner is the player who ends up with an even number of tokens.

Nim: Start with three piles of tokens of 3, 4, and 5, respectively. Each player can remove any number of tokens from any one pile on their move. The winner is the player who removes the last token.

To code up the “1, 2, … 10” game in Java, continue to part 2.

I’m indebted to Dr. Daniel Garcia of UC Berkeley whose Games Crafters undergraduate research group introduced me to the field of computational game theory.