For this project, you will use Reinforcement Learning to train a neural network to play Tic-Tac-Toe.
The starter code is available at tictactoe.py. You will need to use PyTorch 0.3+ for this project (you can use
torch.__version__ to see which version you are using). The starter code contains the Tic-Tac-Toe environment and other helpful code.
Environment class provides functionality to play the game of Tic-Tac-Toe. Look at the code. How is the grid represented? What do the attributes
Create a new environment, and play a game of Tic-Tac-Toe against yourself by calling the
render() methods. Display the text output in your report.
Policy class is incomplete. Complete the implementation so that your policy is a neural network with one hidden layer. Include the new code you wrote in your report.
Even though Tic-Tac-Toe has a 3×3 grid, we will represent our state as a 27-dimensional vector. You can see how the 27-dimensional state is generated in the
select_action function. In your report, state what each of the 27 dimensions mean.
The output of this policy should be a 9-dimensional vector. Explain what the value in each dimension means.
Is this policy stochastic or deterministic?
finish_episode computes the backward pass for a single episode, in our case a single game of Tic-Tac-Toe.
Note: You may notice that
finish_episode normalizes the returns to mean 0 and standard deviation 1. This is done to reduce the gradient norm and to train faster.
Include your implementation in your report.
Note that we pass a list of
saved_logprobs for the entire episode to
finish_episode. When using Policy Gradient, we cannot compute the backward pass to update weights until the entire episode is complete. Explain why this is the case: why can we not update weights in the middle of an episode?
We did not set up the environment to return rewards directly. Instead, when an action is played, the Tic-Tac-Toe environment returns a status. The
get_reward function determines the reward for each status.
get_reward function to what you think the reward should be to be able to train the policy to play Tic-Tac-Toe. Include your modified function in your report. For your reference, here are the status meanings:
STATUS_VALID_MOVE: Move was on an empty position, game is not over, opponent’s turn.
STATUS_INVALID_MOVE: Move was on a non-empty position and was ignored
STATUS_WIN: Move was a valid, winning move, and the game is over
STATUS_TIE: Move was valid, no more empty positions on board, game is over.
STATUS_LOSE: Opponenet wins the game, game is over
STATUS_DONE: You should never actually see this
Explain the choices that you made in 4(a). Are there positive rewards? Negative rewards? Zero rewards? Why? Explain how you chose the magnitude of the positive and negative rewards.
After you have completed parts 1-4, you should be able to train your model using the
train() function. Train your model until your average return stops improving. The average returns can be fairly noisy, so you should train for at least 50000 episodes. You may change any hyperparameters in this function, but clearly indicate in part (a) if you have done so. You may have to return to Part 4 if your choice of rewards was poor.
Note that this function checkpoints learned model weights of the policy throughout training. We will use this in later parts.
Plot a training curve: your x-axis should be episodes, and your y-axis should be the average return. Clearly indicate if you have changed any hyperparameters and why.
One hyperparameter that you should optimize is the number of hidden units in your policy. Tune this hyperparameter by trying at least 3 values. Report on your findings
One of the first things that your policy should learn is to stop playing invalid moves. At around what episode did your agent learn that? State how you got the answer.
Use your learned policy to play 100 games against
random. How many did your agent win / lose / tie? Display five games that your trained agent plays against the random policy. Explain any strategies that you think your agent has learned.
Use the model checkpoints saved throughout training to explore how the win / lose / tie rate changed throughout training. In your report, include graphs that illustrate this, as well as your conclusions in English.
For your final trained model, show π(a|s0), the learned distribution over the first move. (You may use the
first_move_distr function provided) What has your model learned? Does the distribution make sense?
Explore how the distribution over the first move has changed throughout training.
Your learned policy should do fairly well against a random policy, but may not win consistently. What are some of the mistakes that your agent made?
The project should be implemented using Python 2 or 3 and should be runnable on the CS Teaching Labs computers. Your report should be in PDF format. You should use LaTeX to generate the report, and submit the .tex file as well. A sample template is on the course website. You will submit at least the following files:
tictactoe.pdf. You may submit more files as well. You may submit
ipynb files in place of
Reproducibility counts! We should be able to obtain all the graphs and figures in your report by running your code. Submissions that are not reproducible will not receive full marks. If your graphs/reported numbers cannot be reproduced by running the code, you may be docked up to 20%. (Of course, if the code is simply incomplete, you may lose even more.) Suggestion: if you are using randomness anywhere, use
You must use LaTeX to generate the report. LaTeX is the tool used to generate virtually all technical reports and research papers in machine learning, and students report that after they get used to writing reports in LaTeX, they start using LaTeX for all their course reports. In addition, using LaTeX facilitates the production of reproducible results.
You are free to use any of the code available from the CSC411 course website.
Readability counts! If your code isn’t readable or your report doesn’t make sense, they are not that useful. In addition, the TA can’t read them. You will lose marks for those things.
It is perfectly fine to discuss general ideas with other people, if you acknowledge ideas in your report that are not your own. However, you must not look at other people’s code, or show your code to other people, and you must not look at other people’s reports and derivations, or show your report and derivations to other people. All of those things are academic offences.