如何修复基于MCTS的Blokus游戏AI性能问题？

问题背景 #

我正在开发基于蒙特卡洛树搜索（MCTS）算法的Blokus游戏AI，已实现选择、扩展、模拟、回溯核心阶段。但AI存在严重性能问题：深入搜索游戏树或增加模拟轮次时运行极慢低效，还会破坏游戏棋子显示效果。

性能分析结论 #

经性能检测，扩展和模拟阶段耗时占比最高，其中State类的getRandomUnexploredMove()方法耗时尤为突出。我已尝试缓存移动操作，但改善效果不明显，现寻求代码优化建议以提升AI运行效率。

针对性优化建议 #

聚焦getRandomUnexploredMove()方法 #

• 预计算全量合法移动：在游戏状态初始化时就生成当前玩家的所有合法移动并存储为列表，后续直接从列表中随机选取未探索项，避免每次调用方法时重复计算合法移动的开销。
• 替换动态集合存储结构：若当前用Set或类似动态集合存储未探索移动，改用数组或普通列表，通过“选中元素与末尾元素交换+截断列表”的方式快速移除已探索项，降低随机访问与元素删除的时间成本。
• 消除冗余状态复制：检查方法内是否存在不必要的状态复制操作，尽量采用引用传递或共享不可变状态的方式，减少内存分配与数据拷贝的消耗。

扩展与模拟阶段通用优化 #

• 并行化模拟任务：将多个独立的模拟任务分配至多线程执行，利用多核CPU资源提升效率，需注意线程安全，避免共享状态的竞争问题。
• 压缩状态表示：用位掩码替代二维数组存储棋盘信息，减少内存占用同时大幅提升状态操作（如移动合法性检查）的速度。
• 加入启发式剪枝：在扩展阶段优先选择更具潜力的移动（比如占据角落、能拓展后续空间的棋子），减少无效节点的扩展数量。
• 分离计算与渲染逻辑：将AI计算放在后台线程执行，计算过程中暂停UI渲染更新，避免计算阻塞主线程导致的显示异常。

内容的提问来源于stack exchange，提问作者Hartk