For a game like PuyoPuyo however, no such super-human AI exists. And my "Open Source Itch" is to develop some self-learning tool for myself, and the greater PuyoPuyo community. True, there are lots of training tools and tutorials out there, such as the excellent PuyoNexus chain simulator, and the community is quite helpful when discussing strategy. But there's nothing quite like a super-human AI that automatically tells you mistakes as you're playing the game.
The first step to solving this problem is to somehow create a super-human AI. But how to do it?
With Google's success with "AlphaGo" in recent years, I've grown to trust the Monte-Carlo Tree Search algorithm, although I'm still suspicious of "Deep Learning" or other neural network methodologies, at least on consumer hardware. Clearly a legion of 100TFLOP or 200TFLOP "TPUs" in Google supercomputers change the game (as AlphaGo has demonstrated), but standard hardware is limited to 1000x less performance with ~100GFLOP AVX instructions. Even if I used a more difficult GPGPU methodology, the best $800 GPUs only get 10TFLOPs, and I'd expect training and inference to take too long under those conditions.
So my initial plans are to create this PuyoPuyo AI that plays under the classical MCTS with "light random rollouts" akin to the original MCTS "MoGo" AI.
In short, expect blogposts on the following:
- Puyo Puyo, a great little niche puzzle game
- Brief OpenCL / GPGPU discussion, and why I'm holding off on this tech for this project
- Monte-Carlo Tree Search, and how it relates to game trees.
- Optimizations I'm employing to shrink down the memory-space to better fit into L1 Cache. Faster speed means more nodes explored, which will always improve the AI's strategy
- SIMD opportunities in the MCTS algorithm.
Of course, as I learn about new opportunities, I'll write down my thoughts.
No comments:
Post a Comment