改进极小极大算法以解决回合制棋盘游戏的循环问题

针对你描述的这款两人回合制棋盘游戏（玩家可移动到相邻格子或 teleport 到未被占领的棋盘另一端，占领目标格子获得对应价值），Minimax算法出现循环问题的核心原因是存在无限重复的状态循环，以下是几种实用的修改思路：

1. 限制搜索深度 #

为Minimax设定固定的最大搜索层数，当搜索达到该层数时，不再继续递归，转而用启发式函数评估当前状态的价值。

• 针对这款游戏，启发式函数可以设计为：当前最大化玩家（A）离目标格子（5号）的距离，减去最小化玩家（B）离目标格子（1号）的距离，距离计算需考虑teleport的可行性——比如如果目标端未被占领，teleport对应的距离可直接记为1。
• 举例：A在2号、B在5号时，A无法teleport到被B占领的5号，到5号的距离为3；B可teleport到未被占领的1号，距离为1，此时启发值为3-1=2，作为当前状态的评估结果。

2. 状态重复检测（置换表） #

实现一个哈希表（置换表），存储已经搜索过的游戏状态及其对应的Minimax评估结果，当再次遇到相同状态时，直接返回已存储的结果，避免重复进入循环搜索。

• 游戏状态需要包含三个核心要素：A的位置、B的位置、当前轮到哪个玩家行动。将这三个信息组合成唯一的哈希键，对应存储的评估值。
• 举例：当玩家A从2号移动到3号，玩家B又移动回2号，再次轮到A行动时，这个状态如果之前已经计算过，就直接调用之前的结果，不会重复展开搜索。

3. 给启发式函数添加循环衰减项 #

调整启发式函数，让重复出现的状态评估值随循环次数逐渐衰减，降低循环状态的吸引力，引导算法选择非循环路径。

• 具体来说，可以在记录状态时额外统计该状态被访问的次数，每次访问时，将启发值乘以一个0.9~0.95之间的衰减系数。比如最大化玩家（A）遇到重复状态时，评估值逐渐降低，算法会倾向于选择能推进游戏的行动，而非进入循环。

4. 引入强制终止规则 #

在游戏规则层面添加终止条件，避免无限循环：

• 设定最大行动次数，比如当双方累计行动超过50次仍未分出胜负，则判定为平局，给游戏价值0，Minimax在达到该次数时直接返回平局值。
• 或者规定同一状态重复出现N次（比如3次）时，判定为平局，终止搜索。

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