我已经因为井字游戏类型的棋盘游戏AI而头疼了。问题是AI在高难度级别上的性能非常慢（即使在低难度级别上也不够快）。
AI使用递归方法从可用的移动中找到最佳移动。
以下是一些代码：
@impelementation AIClass- (NSMutableArray *)findLegalMoves{ // 这里是查找可用合法移动的代码 // 遍历棋盘数组}- (float)scoreOpponentsTurn:(float)min max:(float)max depth:(int)depth{ moveType t; // moveType是.h文件中定义的结构体 // 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 - 评估启发式参数总和 } 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]; // 这里我有一些条件来决定当前移动是否是最佳的 } // 然后从最佳移动中随机选择一个并将其赋值给move变量 return move;} @end如果合法移动的数量达到3个或更多（随着递归搜索的增加），这个算法运行得非常慢。
这是我第一次尝试使用Objective-C。以下是我对如何提高性能的一些猜测：
- 去掉递归（但我看不到其他解决方案）
- 使用多线程（如何做？）
- 或许使用某个AI库？
抱歉我的英语不好。
回答：
在适合递归的算法中去掉递归并不是一个好主意。相反，你需要记忆化你的递归解法。这种常见技巧可以将具有共同子问题的递归解法的速度提高数个数量级。
考虑以下两个移动序列：
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是你的预判深度。
解决这个问题需要添加一个查找表。给定游戏的状态，这个表将为你或对手提供之前计算过的分数。你的递归函数将构建一个位置键，并尝试在分数表中查找。如果答案存在，它将立即返回。否则，你的函数将构造答案，并将其存储在位置键上。下次通过不同的移动序列再次出现相同的位置时，答案将被重用。
