Tic Tac Toe随机AI

Question

我正在为计算机对手构建一个具有不同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中以"增加随机性",即使这是一个逻辑愚蠢的东西,这也没有改善结果.

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

Answer 1

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

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

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

或者,您可以使用possibleMoves阵列中的所有移动开始游戏,并在使用时删除每种可能性.

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