3

三目並べタイプのボードゲームでは、すでにaiで脳が壊れています。問題は、高レベルでの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ライブラリを使用できますか？

英語でごめんなさい。

4

2 に答える 2

3

再帰に自然に適合するアルゴリズムで再帰を破棄することはお勧めできません。むしろ、再帰的なソリューションをメモ化する必要があります。この一般的なトリックは、一般的なサブ問題を伴う再帰的ソリューションを桁違いに高速化します。

次の2つの一連の動きを考えてみましょう。

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回目の繰り返し状態に到達すると、プログラムは、それを初めて見た場合とまったく同じように位置を評価します。これは無駄です。3ムーブの先読みで同一の位置が4回評価されます。4ムーブの先読みでは、8回評価されます。これにより、に比例した速度低下が発生します。2^Nここで、Nは先読みの深さです。

これを修正するには、ルックアップテーブルを追加する必要があります。ゲームの状態を考えると、このテーブルは、あなたまたは対戦相手のスコアを示します（そのようなスコアが以前に計算されている場合）。再帰関数は位置キーを作成し、スコアテーブルでルックアップを試みます。答えがあれば、すぐに返されます。それ以外の場合、関数は回答を作成し、それを位置キーに格納します。次回、同じ位置が異なる一連の動きで発生した場合、答えは再利用されます。

于 2012-12-05T16:08:35.170 に答える
1

アルファベータ法を試してみることをお勧めします。ゲームの分岐係数が高い可能性があります。その場合、結果に影響を与えない領域の検索は避けたいと思うでしょう。

検索を特定の深さに制限することもできます。有能な動きを取り戻すが、それほど長くはかからない深さを選んでください。

于 2012-12-05T16:18:11.163 に答える