我需要为一个给定问题选择一个算法：
游戏有两个玩家：x和o。玩家轮流行动，每局游戏开始时x先动。
玩家x从位置(1,1)开始，而o从(8,8)开始。
每回合，玩家可以像国际象棋中的皇后一样移动（向八个方向中的任何一个），只要她的路径不经过已填充或被占用的方格。移动后，玩家离开的空间被标记为已填充，并且不能再次移动。请注意，只有被占用的空间被填充，而不是整个路径。
当一个玩家无法再移动时，游戏结束，另一位玩家获胜。给定的时间是1分钟。
坐标(1,1)表示棋盘的左上角。
棋盘被指定为行列表。每行是一个条目列表：
-
是空方格
-
是已填充的方格
x是x玩家的当前位置
o是o玩家的当前位置
这会是局部搜索算法还是A*算法？这似乎与国际象棋相似，但同时我又看不出这个游戏的目标…
非常感谢！
回答：
这是一个零和游戏，有两个玩家，每个智能体都对世界有完全的“了解”。
处理此类问题的通用方法是极小极大算法。
算法的核心思想是试图为每一步找到最大保证的“价值”。这是通过在你的回合中选择“最大”可能性，在对手的回合中选择“最小”可能性来实现的（假设他也在试图最大化他的收益，因此最大化他的收益就是最小化你的收益）。
算法递归地查看所有可能的游戏状态，直到一定深度，并选择你可以采取的最佳策略。
你可能需要一些启发式函数来评估每个游戏状态（因为算法不太可能能够拥有整个游戏树，由于分支因子很大）。算法将使用这个启发式函数为你和对手选择最佳移动。
