Tic Tac Toe随机AI

问题描述 投票：3回答：4

我正在为计算机对手构建一个具有不同AI实现的Tic Tac Toe游戏，以便学习不同的算法以及如何实现它们。我尝试的第一个应该是最简单的只是让计算机每次都选择一个随机空间。

这在一定程度上对我有用，问题就变成了运行时间。每次调用aiRandMove()方法时，需要更长时间才能选择移动到船上5次移动（cpu +用户组合）之后，程序似乎挂起（尽管从技术上讲并非如此） 。

在我进一步调试后，我意识到这应该是预期的，因为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中以“增加随机性”，即使这是一个逻辑愚蠢的东西，这也没有改善结果。

如果所有其他方法都失败了，我可能会将此方法标记为“简单”并且只有随机移动，直到我可以判断是否需要阻止或取得胜利。但也许还有其他随机功能可能有助于这一努力。任何和所有的想法和评论都非常感谢！

c++ random runtime artificial-intelligence tic-tac-toe
4个回答
7
投票

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

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

这消除了每次尝试移动时多次调用随机数的可能性，因为数组中的所有可能性都是有效的。

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

您还需要了解，最好为一个随机数生成器播种一次，然后只使用它生成的数字。每当你试图获得一个随机数时，用time(0)播种它将确保你获得相同的数字一整秒。

3
投票

鉴于最多只有9种选择，即使使用随机选择，也不会造成长时间延迟。导致长延迟的原因是在循环内调用srand。这导致您的程序在一秒钟内获得相同的随机数。循环可能在那一秒内执行了数百万次（或者没有cout调用）

将srand调用移到循环之外（或者更好，只需在程序开始时调用一次）。

这并不是说你不应该考虑从随机选择中移除不可用移动的方法，因为它可能对其他类型的游戏产生影响。

2
投票

您可以通过创建自由坐标列表并在该集合中获取随机索引来将其降低到非常可接受的水平。概念：

#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 ++随机函数。这不是一个真正的算法改进，但rand() in C is pretty crappy（我知道，我知道，这是一个很长的视频，但这个人真的非常了解他的东西）。
1
投票

每次移动似乎变慢的原因是因为AI正在采取已经进行的移动，因此它会随机重新选择另一个非法移动（可能会重复）或者选择正确的方格。

要加快程序的这一部分，您可以拥有一个包含位置的集合（例如，链表），在此列表中使用随机函数。当您选择移动或AI从列表中删除元素时。

这将消除AI选择相同方块的重复过程。

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.