objective-c - 性能缓慢的 ai objective-c iOS

Question

对于井字棋类的棋盘游戏，我的大脑已经被 ai 弄坏了。 问题是人工智能在高水平上的表现很慢(即使是低水平也没有那么快)。

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 库吗？

对不起我的英语。

Answer 1

在自然适合递归的算法中抛弃递归并不是一个好主意。相反，您需要 memoize你的递归解决方案。这个常用技巧可将常见子问题的递归解决方案加快几个数量级。

考虑这两个 Action 序列:

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 是您的前瞻深度。

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