I’m working on building an AI bot for the 2048 puzzle game. I want to use the minimax approach but I’m running into some issues.
The problem is that 2048 doesn’t really have a traditional opponent player. It’s more like an expectiminimax tree structure where there’s no actual minimizing player. This makes me confused about how to properly implement alpha-beta pruning.
Can alpha-beta pruning even work when there’s no minimizer in the game tree? If not, what other techniques can I use to cut down on unnecessary branches during the search process?
I’d really appreciate any advice or suggestions you might have. Thanks in advance for your help!
You’re right - traditional alpha-beta pruning doesn’t work with expectiminimax since there’s no minimizing player. The random tile placement creates chance nodes instead of adversarial ones.
But you can still optimize your search tree. I’ve built similar game AIs and expectiminimax with good pruning heuristics works well.
Use probability thresholds. If a branch has super low probability (under 0.01), just ignore it. Tiles usually spawn in predictable spots anyway.
Try iterative deepening with time limits. Set a reasonable search time and let it go as deep as possible.
Move ordering helps too. Prioritize moves that are typically better (keeping high tiles in corners) to get better estimates faster.
For 2048, use domain knowledge. If a move doesn’t change the board or causes immediate game over, prune those branches early.
This video shows a solid implementation that might help:
