目的

旨在通过minimax算法及其优化算法，设计一个自动玩 2048 游戏的 AI；
项目使用Python语言实现，游戏的用户界面由Pygame搭建。

实现

运用minimax算法的时候，视玩家操作为取最大奖励的过程，环境向棋盘中随机添加“2”或“4”为取最小奖励的过程，以此构建搜索树。 \ 并运用alpha-beta剪枝减少搜索空间，优化时间；使用移动排序，使剪枝算法更快发现剪枝机会，优化剪枝效率；迭代加深，限制深度，一方面限制算法过度搜索，导致算法容易忽略当前棋盘状态，给出较差的解，另一方面，返回令人可接受的走法同时减少搜索空间，加快速度；运用置换表，储存搜索过的状态，在遇到置换表中的状态时不用再次搜索，而是直接使用置换表中的信息，相当于“空间换时间”，避免了重复的搜索工作，减少了时间。通过实验表明，置换表对于算法效率的提升是最大的。 项目还运用了启发式搜索优化，即根据人类经验，对奖励函数做出设计，以对程序决策的质量做出提升。实验证明，启发式搜索优化对程序决策的优化起到了关键作用，且不同的启发函数对整体优化的效果具有很大的差异性。

测试

测试程序能够凑出的最大数的数量。从测试结果上看，程序有较稳定的发挥，大多数时候能够达到一个高分，但是仍然能力不足，达到游戏目标的次数还是偏低。从图中得知，大部分时候程序能够到达1024，却很少到达2048，这暴露了算法的不足，仅仅依赖单一的奖励函数可能无法适应从1024到2048的突破，未来工作的主要方向可能是研究分段的奖励函数以提升程序达成游戏目标的概率。