While I was working on my master's degree I took an introductory course in Monte Carlo methods (STA 6866 at UF). As is typical of grad school, a final project was required - in this case something related to a Monte Carlo method not covered in the course (we used Introduction to Monte Carlo Methods in R by Robert and Casella). I chose to do a brief report on and implementation of Monte Carlo Tree Search (MCTS).
The purpose of this post is not to introduce MCTS, but rather to post what I did for the project in case others find it useful. MCTS is a method that can be used to create an artificial intelligence (AI) for games (both video games and traditional games). As a proof-of-concept, I implemented MCTS as an AI for a game of Connect Four. (It was really 'Connect Three' on a 4x4 board due to computational constraints, but the concept remains the same and the code should generalize easily.) Connect Four is not an ideal use for the MCTS AI because it is a solved game (unlike Go or Chess). I chose to use Connect Four because it is easy to code in R, easy to play, and the purpose is to demonstrate the MCTS method for AI and not to create a truly competitive AI.
The relevant files are:
- An R file that explains how to use the game and AI (OPEN-ME.R)
- R code for the Connect Three/Four/K game (can choose Player 1 vs. Player 2, Player 1 vs. AI, or AI vs. AI) (connect-game-code.R)
- R code for the MCTS AI (mcts-ai-avec-block.R contains deterministic code to make the AI play defensively if Player 1 can win in one move to make play more realistic; mcts-ai-sans-block.R does not contain the blocking code)
- R code for a 'naive' AI (selects from the available moves without doing any weighting, coded for comparison purposes) (naive-ai.R)
- A helper file previously detailed (pprint.R)
- A file containing 25000 simulated games (giving this to the MCTS AI improves its performance) (BLR-4x4-AI1-24k.txt)
- The report I wrote about MCTS for the class (pdf)
The report I wrote for class can be download here, and all of the other files are in one zip archive. If you found this useful, I'd love to hear about it. If you want me to do something else with this, also let me know.
It looks like the statistics department finally took down my old homepage. I've uploaded the files to this website instead. It may be worth repeating that this work was work done for a class, and, while I enjoyed doing it and learned a lot, I make no guarantees about the code or report.