Decision tree solution
Click here for an image of the Decision Tree

Program solution:

# Program: nim.py
# Author: Brenda Student
# Class: CSCI 110
# Date: 9/24/08
# Assignment: Homework 2
# Purpose: Plays the game of Nim with the user.

move1 = raw_input("What is your move? ")
if move1 == "X":
    print "The board is X."
    print "I play O."
    print "The board is XO."
    move2 = raw_input("What is your next move? ")
    if move2 == "X":
        print "The board is XOX."
        print "I play OOO."
        print "The board is X0X000."
        print "I win!"
    elif move2 == "XX":
        print "The board is XOXX"
        print "I play OO"
        print "The board is XOXXOO"
        print "I win!"
    else:
        print "The board is XOXXX"
        print "I play O"
        print "The board is XOXXXO"
        print "I win!"
elif move1 == "XX":
    print "The board is XX."
    print "I play O."
    print "The board is XXO."
    move2 = raw_input("What is your next move? ")
    if move2 == "X":
        print "The board is XXOX."
        print "I play OO."
        print "The board is XX0X00."
        print "I win!"
    elif move2 == "XX":
        print "The board is XXOXX"
        print "I play O"
        print "The board is XXOXXO"
        print "I win!"
    else:
        print "The board is XXOXXX"
        print "You win!"
else:
    print "The board is XXX."
    print "I play OOO."
    print "The board is XXXOOO."
    print "I win!"