Jupiter는 Monte Carlo Tree Search 알고리즘을 사용하여 인기 온라인 게임인 2048을 이기는 AI입니다.

이동 당 많은 양의 시뮬레이션이 주어지면 Jupiter는 거의 100%의 시간 동안 2048 타일을 달성할 수 있습니다.

Jupiter는 개발자이자 고등학생인 Gabriel Romualdo의 프로젝트 입니다.

알고리즘 & 성능

저는 Jupiter에서 사용되는 알고리즘과 구현에 대한 두 개의 기사를 작성했습니다:

AI에서 Monte Carlo Tree Search(MCTS) 알고리즘을 사용하여 2048(및 다른 게임)에서 승리 게임 플레이에서 AI 알고리즘의 성능 — Jupiter의 경험적 증거, 나의 2048 AI

개발에 관해서

Jupiter (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.