为瓷砖游戏制作AI

Making an AI for a tile game

本文关键字：AI 游戏      更新时间：2023-09-26

我制作了一个涉及"瓷砖"表的游戏，目的是将它们分组为该颜色的2乘2的块，其中有16种独特的颜色。我已经完成了游戏的这一部分，我想继续制作一个人工智能组件，为你完成游戏的最低移动次数提供建议。我决定使用2d阵列，这样它就可以识别每种颜色的位置，而不会直接影响电路板，我需要一些帮助。一旦我完成阵列，它应该做的就是识别第一块瓷砖的颜色，寻找该瓷砖的颜色并将其与周围的块交换到右下方、右下方和右下方。有人能帮忙吗？

听起来你想要做的是解决一个更简单的问题，而这个问题本身不需要人工智能。你最好的办法是为每个尝试的解决方案创建一个数组——可能是在二维数组中——并多次解决每个谜题，跟踪移动情况。数组将作为一个列表，以确保您获得独特的解决方案。

您可能希望实现递归求解算法来填充每个数组，对尝试次数或求解时间（或两者都有）设置上限，并提供具有最低圈数的解决方案作为提示。

你最终可能不会得到数学上可能的绝对最小圈数，但这至少是一个起点（通过对数学和算法优化的进一步研究，你可能会找到完美的数学解决方案）。这是一个游戏，所以玩得开心；-）。

我不确定游戏是如何工作的，我认为它的工作方式是在相邻的块之间交换颜色，直到达到完成条件。

如果你想找到最好的解决方案，你应该这样做：

FUNCTION SEARCH(StackOfMoves I,O)
   FOR EACH position in chekcboard
       FOR EACH direction in possibleMoves
          makeMove(position , direction)
          StackOfMoves->addMoveToStack(position, direction)
          IF GameCompleted()
              RETURN StackOfMoves
          ELSE 
              SEARCH(StackOfMoves)
          END IF
       END FOR
   END FOR
   RETURN StackOfMoves
END FUNCTION

编辑

悄悄地分析了它，我认为除非你设置迭代限制或条件退出，否则它不会正常工作，如果它选择了一个坏动作，它可能会一次又一次地迭代坏动作。一个条件来查看当前状态是否已经被处理，如果没有，则返回false可能会修复它，但肯定是一个更好的解决方案。我稍后会尽力给出一个更好的答案。

在我看来，您可能希望对此进行深度优先搜索。这基本上是移动，为新位置指定分数，然后返回到前一个位置或进行另一次移动。游戏中可能的移动序列可以表示为一棵树，深度首先从树的根开始计算移动，直到到达叶节点（或最大深度），然后回溯一个节点并计算下一个同级分支。这可以迭代或递归地完成。

计算每个董事会职位的分数对于任何类型的搜索都很重要。你需要知道哪个职位比其他职位好还是差。你的评分算法真的取决于比赛。在你捕捉棋子的游戏中，比如国际象棋，一个非常基本的评分算法只会为每一个棋子分配一个分值。你每个位置的分数就是你的棋子之和减去敌人棋子之和。你必须为自己的游戏想出一个评分算法。理想情况下，这将是快速计算，并将给出更好的分数，因为你接近胜利。

每个位置的分数都可以存储在数据库中，因此，如果用不同的移动顺序可以到达同一位置，则只需计算该位置的分数一次。然后，如果你在搜索中再次到达相同的位置，你就已经在数据库中获得了分数。程序通常计算板状态的散列，以索引表中的位置。

在深度优先的情况下，所需的计算量部分取决于搜索的深度。许多国际象棋程序使用一种称为迭代深化的技术，允许搜索快速生成猜测，然后在更多的搜索时间后生成更好的移动。你首先以1步的深度进行搜索。这些职位中的每一个都存储在数据库中，因此您无需重新计算分数。评估所有移动到深度1后，重新开始并评估将树移动到深度2。每次迭代都需要成倍增加的计算时间，因此迭代深化可以让你在有更多时间思考时产生更好的动作。

通过深度优先搜索和分数数据库，您可以进行分支修剪。如果在下降分支时，您确定该分支的最佳分数比您已经评估的分支差，则可以停止当前分支并回溯。这通常是在两人游戏中完成的，每个玩家都试图最大化自己的分数，并最小化对手的分数。搜索alpha-beta修剪以了解更多信息。

深度优先搜索只是一种可以使用的算法。根据游戏的不同，使用其他类型的算法可以获得更好的结果。例如，你可以使用神经网络，它可以用比赛前的训练时间代替比赛期间的搜索时间。无论如何，你可以花很多时间开发人工智能，即使是看似简单的游戏。

相关文章：