I’m working on an AI for the game 2048 and want to use the minimax algorithm. The thing is, the search tree for 2048 looks more like an Expectiminimax tree without the Min role. This has me scratching my head.
Can I still use alpha-beta pruning if there’s no Min role? If not, what other ways are there to cut down on unnecessary searches?
I’ve been racking my brain trying to figure out how to make this more efficient. Any ideas or suggestions would be super helpful. I’m really interested to hear what others think about this problem.
Thanks in advance for any input!
I’ve actually tackled this exact problem in my own 2048 AI project. You’re right that the traditional alpha-beta pruning doesn’t directly apply here due to the lack of a true Min player. However, you can still optimize your search.
What worked well for me was implementing a form of pruning based on probability thresholds. Since the ‘chance’ nodes (where new tiles spawn) have known probabilities, you can cut off branches that have a very low likelihood of occurring. This significantly reduced my search space without sacrificing much accuracy.
Another approach I found effective was using heuristic-based move ordering. By evaluating moves quickly with a simple heuristic first, then searching the most promising ones deeper, I was able to get better pruning overall.
Lastly, don’t underestimate the power of good board evaluation and depth-limited search. A well-tuned evaluation function can often outperform deeper searches, especially given 2048’s time constraints.
Hope this helps point you in the right direction. Good luck with your AI!