3

对于井字棋类型的棋盘游戏，我已经被人工智能打破了。问题是高水平的人工智能性能缓慢（即使是低水平也没有那么快）。

AI 使用递归方法从可用移动的数量中找到最佳移动。

这是一些代码：

@impelementation AIClass

- (NSMutableArray *)findLegalMoves
{
   // Here is code that finds available legal moves
   // Loop over board array
}

- (float)scoreOpponentsTurn:(float)min max:(float)max depth:(int)depth
{
   moveType t; // moveType is struct defined in .h file 
               // typedef struct { int x, y; } moveType
   NSMutableArray *moves = [self findLegalMoves];
   for ( NSValue *val in moves ) {
      [val getValue:&it]
      float score = [self scoreMove:it min:min max:max depth:depth];
      if ( score > min ) {
         min = score; 
      }
      if ( score > max ) { 
         min = 1000000000;
      }
   }
   return min;
}

- (float)scoreMove:(moveType)m min:(float)min max:(float)max depth:(int)depth
{
   NSMutableArray *changes = [[NSMutableArray alloc] init];
   NSMutableArray *undo = [[NSMutableArray alloc] init];
   float score;
   [self.board evaluateChangesOnCol:m.x Row:m.y];
   if ( [self.board checkForWin:&changes undo:&undo] ) {
       score = 1000000000 + [self calcH]; //calcH - evals heuristic like sum of params
   } else if ( depth > 0 ) { 
       score = - [self scoreOpponentsTurn:-1000000000 max:-min depth:depth - 1];
   } else {
       score = [self calcH]; 
   }
   [self.board applyChanges:undo];
}

- (moveType)findBestMove
{
   NSMutableArray *legalMoves = [self findLegalMoves];
   NSMutableArray *bestMoves = [[NSMutableArray alloc] init];
   int min = -1000000000;
   int max = 1000000000;
   moveType move;
   for ( NSValue *moveIt in legalMoves ) {
      [moveIt getValue:&move];
      float score = [self scoreMove:move min:min max:max depth:depth];
      // Here i have some conditions to decide current move is best or not
   }
   // and pick random move from best moves and assign it to move variable
   return move;
}    

@end

如果合法移动的数量像 3 或更多（通过递归搜索它会增长），则该算法的运行速度非常慢。

这是我的第一次 Objective-C 体验。以下是我对如何提高性能的猜测：

  1. 删除递归（但我没有看到其他解决方案）
  2. 使用多线程（如何？）
  3. 可以使用一些ai库吗？

对不起我的英语不好。

4

2 回答 2

3

在自然适合递归的算法中抛弃递归并不是一个好主意。相反，您需要记住您的递归解决方案。这种常见的技巧将具有常见子问题的递归解决方案加速了几个数量级。

考虑这两个动作序列：

x:(1,1) o:(2,1) x:(1,0) o:(2,0)

和

x:(1,0) o:(2,0) x:(1,1) o:(2,1)

序列不同，但它们到达相同的最终状态：

|   | x | o
------------
|   | x | o

这是缓慢的根本原因：当您的程序第二次到达重复状态时，它会准确地评估位置，就好像它是第一次看到它一样。这很浪费：具有三步前瞻的相同位置将被评估四次；使用四步前瞻，它们将被评估八次，依此类推。这会导致慢速与 成比例2^N，其中N是您的前瞻深度。

解决这个问题需要添加一个查找表。给定游戏状态，此表将为您或对手提供得分，如果之前已计算过此类得分。您的递归函数将构建一个位置键，并尝试在分数表中查找。如果答案在那里，它将立即返回。否则，您的函数将构造答案，并将其存储在位置键中。下次通过不同系列的动作出现相同的位置时，答案将被重复使用。

于 2012-12-05T16:08:35.170 回答
1

您可能想尝试Alpha-beta pruning。您的游戏可能具有较高的分支因子，在这种情况下，您需要避免搜索不会影响结果的区域。

您还可以将搜索限制在一定深度。选择一个可以检索到有效动作但不会花费太长时间的深度。

于 2012-12-05T16:18:11.163 回答