シミュレーション数:
2048を打ち負かすモンテカルロベースのAI
シミュレーション数:
Jupiterは、 Monte Carlo Tree Searchアルゴリズムを使用して、人気のオンラインゲーム2048を打ち負かすAIです。
移動ごとに大量のシミュレーションを行うことで、Jupiterはほぼ100%の確率で2048タイルを達成することができます。
Jupiterは、開発者であり高校生であるGabriel Romualdoのプロジェクトです。
私はJupiterで使用されているアルゴリズムとその実装について2つの記事を書きました:
AI で Monte Carlo Tree Search (MCTS) アルゴリズムを使用して 2048 (および他のゲーム) に勝つ。 ゲームプレイにおけるAIアルゴリズムのパフォーマンス — Jupiterの経験的な証拠、私の2048 AIJupiter (formerly known as Jacob) started as a small AI project in January 2018. I got the idea of using Monte Carlo simulations and search trees as a method to play 2048 from this StackOverflow answer.
I wrote a basic clone of what was described in the answer and built on the idea with an interactive console and my own 2048 game implementation, in contrast to the existing open sourced game code used in other AI projects. At this time, Jupiter ran on the main JavaScript thread, and had decent performance and speed: it was able to run ~800 Monte Carlo simulations of possible games per second. Running the game at 200 simulations per move gave roughly 4 moves per second. This amount of simulations reaches the winning 2048 tile about 65-75% of the time.
In August 2020, I took a look at the project once again and noticed the potential to improve both performance and speed of the AI. I did some more research on Monte Carlo simulations and search trees, notably watching a great lecture by MIT Prof. Guttag in MIT's 6.0002 undergraduate course. In the one and a half years since I had first started the project, I'd also learned and used numerous modern JavaScript features, frameworks, and libraries. This put in me the unique position to use these new skills to extend this project vastly from performance, speed, bundle size, and design perspectives.
So, I spent time refactoring existing code and replacing older algorithms with newer and more performant ones. In particular, I took advantage of modern JavaScript features like Web Workers to differ tasks to new threads and utilize concurrency capabilities. I also added Webpack to the project for the automated speed and bundle size optimizations built into many of its loaders. With new CSS and design skills I had learned over the past one and half years, I built a new design for the site, with a clearer console and mobile responsiveness. And finally, among many other features, I added "tile milestones" to let users know how fast the AI had reached certain tiles in the game.
With the numerous updates to the project in 2020, Jupiter was now able to run ~2650 simulations of possible games per second. Running the game at 200 simulations per move gave around 13 moves per second. This indicated that performance had more than tripled with the new updates. Moreover, a new addition to the code allowed for performance to grow and scale horizontally by adding Web Workers and threads as general computing speed increases over time.
All in all, the two year gap in which I learned invaluable frontend development and programming skills allowed me to improve the AI drastically in many areas while maintaining the original, extremely effective Monte Carlo based algorithm which stayed the same throughout the development process.
I hope you like the project! If you'd like to read more about me or see more of my projects, check out my personal website and blog at xtrp.io.
— Gabriel Romualdo, August 2020
Jupiter is licensed under the MIT License. Code for the AI, site, and 2048 game code was written by Gabriel Romualdo, with some colors used from the original 2048 project. The original idea for the AI algorithm used comes from this StackOverflow answer.