Activity 8: Simulation of a State Tree
Due: On git by Thursday, Apr. 6, 2017 at 9:30am
Team: This is a solo assignment; you should type all the code to your solution. However, feel free to get help from others/Google/etc.
Grading: This assignment is the mid-week activity for Experience 8, worth 10 points. There is no partial credit.

Introduction

In lecture, you learned a new two-player game with a very simple rule set:

  • Each game starts with 10 marks
  • Player 1 and Player 2 alternate turns:
    • Each turn, a player may pick up 1 or 2 marks
  • The player who picks up the last mark wins

In lecture, you played several rounds of this game and, together, we developed a state space for this game. We decided that each state is described by two features: the current player's turn and the number of marks available.

From there, we developed a compact notation for this state space: p#-$, where # is the current player (either 1 or 2) and $ is the number of marks available.

As an example, p1-7 notates that it is Player 1's turn and there are 7 marks left on the table. Visually, this implies that the game is at this state:


Part 1: Setup

The code that was finished in class has been provided as the starting code for this activity, in the exp_activity8 branch:

git fetch release
git merge release/exp_activity8 master -m "merge"

Part 2: Creating the State Space Graph

Open the jupyter notebook in your exp_activity8/py directory called Nim Game.ipynb. Create the game state space described in lecture (and at the intro of this activity).

Each node must a valid game state and the collection of all nodes is every possible game state. Each edge is a valid move between states.

When the game begins at p1-10, Player 1 may pick up one or two marks. Therefore, p1-10 has edges to p2-9 and p2-8. Visually, this full graph is rendered below:



Every path through the graph is a valid game. One path, for example, is the following:

p1-10 ➜ p2-8 ➜ p1-7 ➜ p2-6 ➜ p1-4 ➜ p2-3 ➜ p1-1 ➜ p2-0

We can also represent this path through the state space graph visually:

When you have created all of the nodes and edges, a few simple test cases have been provided for you to ensure you've completed this part correctly.


Part 3: Simulating Games to Learn Edge Weights

The goal of this activity is to have the machine learn the best edges to take in a game. To do this, we will simulate thousands of games and record which edges contributed to the win.

The code to update the winning edges of the game has been provided for you. You must create the generateGamePath function that generates a path through the game. For example, the following is a valid path: ["p1-10", "p2-8", "p1-7", "p2-6", "p1-4", "p2-3", "p1-1", "p2-0"]

Need more resources?

Part 4: The Visualization

After you have completed the code in the Jupyter notebook, running the CS 205 workbook will show a graph of your result:


Submission

This activity is submitted digitally via git. View detailed submission instructions here.