I’m working on creating an AI bot for the 2048 puzzle game and I’m trying to implement the expectiminimax algorithm. The thing is, in 2048 there’s no opposing player trying to minimize my score, so it’s more like expectiminimax without the minimizing player.
My question is about optimization techniques. Since there’s no min player in this game structure, can I still use alpha-beta pruning to make the search faster? Or does alpha-beta pruning only work when you have both maximizing and minimizing players?
If alpha-beta pruning won’t work here, what other methods can I use to cut down on unnecessary branches in my search tree? I want to make my AI run faster without checking every possible move combination.
Any advice or suggestions would be really helpful. Thanks in advance!
expectiminimax with chance nodes can use pruning, just not the standard alpha-beta kind. try the star1 algorithm or set cutoff thresholds - i usually ignore branches with less than 5% probability. good board eval functions matter more than deep searching. focus on solid heuristics for corner weighting and clustering instead.
Had this exact problem building my first 2048 bot years ago. Standard alpha-beta gets destroyed here.
Beam search with fixed width saved me. Don’t explore every branch - just keep the top N most promising moves per level. I used N=4 or 5 and it slashed search time without hurting play quality much.
Another huge time saver - precompute all tile spawn scenarios. You’ve only got two tiles (2 or 4) and limited empty spots, so precalculate probabilities instead of doing it mid-search.
I also bail early when the board gets cluttered. Less than 6 empty tiles? Just evaluate with heuristics instead of searching deeper. The game state’s too constrained for deep search to help much.
One more trick - sort moves by quick heuristic before searching. Try keeping the max tile in a corner first. Gets you better bounds faster and helps with pruning.
Expectiminimax works fine for 2048, just needs different optimization than adversarial games.
Alpha-beta pruning won’t work here because it needs alternating max/min layers, but 2048 only has max moves and chance nodes. Try expectation pruning instead - calculate upper bounds on subtree values and cut branches that can’t beat your current best move. Transposition tables are huge for 2048 since you often hit the same board state through different moves. Just memoize positions you’ve already evaluated. I’d also limit depth and use heuristics rather than searching to the end. Evaluate boards at a fixed depth using things like monotonicity, smoothness, and empty tiles. Way faster and still plays well. Throw in move ordering (check good moves first) and you’ll get decent performance without the exponential explosion.
You’re right - standard alpha-beta pruning won’t work here since there’s no adversarial opponent. But there are other pruning tricks that work great for 2048. I built something similar and had good luck with probability-based pruning. Just skip branches where the expected value drops below some threshold compared to moves you’ve already checked. You can also do depth-limited search with iterative deepening - cuts off computation when you’re running out of time. Monte Carlo tree search might be worth trying instead of expectiminimax altogether. It handles the random tile spawning naturally and runs way more efficiently than exhaustive search. Quick win: cache your game states. 2048 has tons of symmetric positions that’ll come up again during search.