井字游戏随机人工智能（AI）

Question

我正在构建一个井字游戏，为了学习不同的算法及其实现方式，我正在尝试使用不同的AI实现作为计算机对手。我正在尝试的第一个实现也应该是最简单的，只是让计算机每次随机选择一个空位。

这种方法在某种程度上对我有用，但问题在于运行时间。每次调用aiRandMove()方法时，选择移动所需的时间越来越长，到了棋盘上已经有5个棋子（电脑和玩家共计）之后，程序似乎会停止响应（虽然实际上并不是这样）。

通过我的进一步调试，我意识到这应该是预料之中的，因为aiRandMove()方法是随机选择 X 和 Y 坐标，然后测试移动是否合法。由于开放的空间越来越少，合法的移动也越来越少，因此随机生成器需要更多次失败的尝试才能生成合法的移动。

我的问题是，是否有任何方法可以修改这个过程，至少可以减少函数执行的时间？根据我的谷歌搜索和自己解决问题的经验，我认为我没有办法优化这个过程而不损害函数的“随机性”。我想过记录计算机尝试的移动数组，但这并不能解决问题，因为这不会影响rand()生成重复数字的次数。以下是该函数的代码，这是与此问题相关的所有内容：

//Function which handles the AI making a random move requires a board
//object to test moves legality and player object to make a move with
//both are passed by reference because changes to board state and the player's
//evaluation arrays must be saved
char aiRandMove(Player &ai, Board &game){
   int tryX;
   int tryY; //Variables to store computer's attempted moves
   bool moveMade = false;
   char winner;
   while(!moveMade){
      srand(time(NULL));//Randomizes the seed for rand()
      tryX = rand() % 3;
      tryY = rand() % 3; //coordinates are random numbers between X and Y
      cout << "Trying move " << tryX << ", " << tryY << endl;
      if(game.isLegalMove(tryX, tryY)){
         winner = game.makeMove(tryX, tryY, ai);
         moveMade = true;
      }
   }
   return winner;
}

我也试过将种子函数移出while循环（这是放在while里面“增加随机性”的，尽管这有点逻辑上的愚蠢，但结果并没有改善。

如果所有其他方法都失败了，我可能会将此方法标记为“Easy”，只有随机移动，直到我确定需要阻止或进行获胜的移动。但也许还有其他随机函数可以帮助这个问题。任何想法和评论都非常感谢！

- RyHartAttack

---

也许你可以为九个井字棋方格生成有效的框，然后让随机器从1到9的范围内选择一个方格？ - Hawken MacKay Rives

对我来说，这只是基因算法的呼声。 - phyrrus9

Answer 1

您需要从等式中删除无效的移动，例如使用以下伪代码，使用数组收集有效移动：

possibleMoves = []
for each move in allMoves:
    if move is valid:
        add move to possibleMoves
move = possibleMoves[random (possibleMoves.length)]

这样做可以避免在尝试移动时多次调用随机函数，因为数组中的所有可能性都是有效的。

或者，您可以使用possibleMoves数组中的所有移动开始游戏，并在使用每个移动后删除该可能性。

您还需要了解最好只对随机数生成器进行一次种子处理，然后使用其生成的数字。每次尝试获取随机数时都使用time(0)来进行种子处理将确保您在整个一秒钟内获得相同的数字。

- paxdiablo

---

谢谢您的回答，其他人也有类似的回复，但我将这个标记为“最佳答案”，因为它提供了多种解决问题的方法，并且只给出了伪代码，留下了一些实现的空间。我也非常感激大家对随机种子的见解，我没有想到我会得到重复的值，但在查看输出后，我看到相同的输出多次出现，然后才真正改变，这可以解释这一点。再次感谢。 - RyHartAttack

Answer 2

考虑到最多只有9种选择，即使使用随机选择，也不会导致长时间的延迟。导致长时间延迟的原因是在循环内部调用srand。这将导致您的程序在一秒钟的持续时间内获得相同的随机数。该循环可能会在那一秒钟内执行数百万次（或者如果没有cout调用，则会执行数百万次）。

将srand调用移到循环外（或者更好地，在程序启动时只调用一次）。

这并不意味着您不应该考虑从随机选择中删除无法使用的移动，因为在其他类型的游戏中可能会有所不同。

- The Dark

---

正如paxdiablo在他自己的答案中指出的那样，问题不在于srand很慢，而是因为它在每次迭代中都被重新种子化为time(0)，所以rand的值每秒只改变一次。（不过解决方法是相同的。） - zneak

@zneak，这就是我说的。我甚至加粗了它 :) - The Dark

是的，你说对了。是时候去睡觉了。 - zneak

Answer 3

您可以通过创建一个免费坐标列表并在该集合中获取随机索引来将其降至非常可接受的水平。概念上：

#include <vector>

struct tictactoe_point
{
    int x, y;
};

vector<tictactoe_point> legal_points;
tictactoe_point point;
for (point.x = 0; point.x < 3; point.x++)
{
    for (point.y = 0; point.y < 3; point.y++)
    {
        if (game.isLegalMove(point.x, point.y))
        {
            legal_points.push_back(point);
        }
    }
}

point = legal_points[rand() % legal_points.size()];
game.makeMove(point.x, point.y, ai);
moveMade = true;

这个解决方案虽然不是最佳的，但是它是一个重要的改进：现在，移动所需的时间是完全可预测的。这个算法只需要一次rand调用就能完成。

每次选一个数字时都调用srand会使这个过程变得更慢，但是，你当前的解决方案的主要问题是必须反复尝试。它没有界限：它甚至可能永远都无法完成。即使srand相当缓慢，如果你知道它只会运行一次，而不是无限次，它应该是可行的（尽管不是最优的）。

有很多方法可以对此进行改进：

• 保留玩的有效坐标列表，并在玩家或AI玩时删除坐标。这样，您就不必在每个回合重新构建列表了。对于井字棋游戏来说，这不会产生太大的差异，但是如果您有一个更大的棋盘，这将产生重大的影响。
• 使用标准C++随机函数。这不是真正的算法改进，但是在C中，rand()相当烂（我知道，我知道，这是一个很长的视频，但这个家伙真的非常了解他的东西）。

- zneak

Answer 4

每次看起来慢的原因是因为AI在选择已经下过的棋子，所以它会随机地重新选择另一个非法的棋子（可能会重复）或者选择正确的棋子。

要加快程序的这部分速度，可以使用一个包含位置的集合（例如链表），在此列表上使用随机函数。当您或AI选择了一个棋子后，从列表中删除该元素。

这将消除AI选择相同棋子的重复过程。

- Xela