In lecture, you learned a new two-player game with a very simple rule set:
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:
The code that was finished in class has been provided as the starting code for this activity, in the exp_activity8 branch:
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:
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.
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"]
After you have completed the code in the Jupyter notebook, running the CS 205 workbook will show a graph of your result:
This activity is submitted digitally via git. View detailed submission instructions here.