二人棋局博弈分析与算法修正

"PB17000297_罗晏宸3" 在这个问题中，我们探讨了一个简单的二人棋类游戏，其中玩家A和玩家B轮流移动棋子，目标是让自己的棋子到达对方的终点。游戏结束时，先到达终点的玩家得分，A得+1，B得-1。题目涉及到以下几个关键知识点： 1. **博弈树**：图2展示了游戏的状态空间，以(sA, sB)表示棋子位置的状态。游戏从初始状态(1, 4)开始，每个节点代表一个可能的棋局状态，箭头表示玩家的合法移动。终止状态用方框表示，其中包含游戏的值。 2. **极小极大值算法**：这是一种用于二人零和博弈的策略，其中玩家A（最大化者）试图最大化结果，而玩家B（最小化者）试图最小化结果。在图3中，每个节点的圆圈中标注了对应的极小极大值，表示在假设对手最优策略的情况下，该节点的预期值。对于未知值“?”，我们假设玩家A总是选择能获胜的路径，即认为其值在-1和+1之间，除非所有后续节点都是“?”。 3. **循环状态与失败**：在标准的极小极大算法中，深度优先搜索可能会遇到已经访问过的状态，即循环状态。在这种情况下，算法会陷入无限循环，无法完成搜索。为了解决这个问题，我们需要识别并记录已经访问过的状态，避免重复计算。 4. **修正的极小极大算法**：为了处理循环状态，我们可以使用迭代深化或者记忆化搜索，记录已访问过的状态及其值。一旦发现循环，可以直接使用之前计算的结果，而不是重新计算。这种方法并不保证对所有包含循环的游戏都能给出最优决策，但至少可以解决当前游戏的问题。 5. **n方格游戏的胜负分析**：在d部分，我们被要求证明当n为偶数时A总是能赢，n为奇数时A总会输。这涉及到博弈论中的完美信息游戏和先手优势。对于偶数方格，A可以通过始终保持棋子在偶数位置来确保胜利，因为每次移动都会改变棋子位置的奇偶性。而如果是奇数方格，B可以在A到达中间位置后复制A的每一步，使得A无法达到终点。 通过以上的分析，我们不仅理解了游戏的规则和博弈树的构造，还学习了如何应用极小极大算法解决此类问题，并探讨了算法的局限性和改进方法。对于n方格游戏的胜负条件，我们可以得出结论，游戏的胜负取决于初始位置与方格数的奇偶性。