Cでのコンピュータ決定のスピードアップの方法

Question

私はGomoku（tictactoeの5 x 5バージョン）をコンピュータで再生するアルゴリズムを理解しようとしています。 このケースでは、最も一般的に使用されるアルゴリズムがMin-max（またはAlpha-beta）であることがわかりましたが、これらは処理するのが難しいため、次のコードを使用することにしました。 。 これは、コンピュータの合理的な選択方法を示しています。

//------------------------------------------------------------ 
// computer_move() checks for all legal moves in the current | 
// position. then for each of them it calls the dfs_search() | 
// function to get the moves' score. And finally it returns | 
// the move with the best score.        | 
//------------------------------------------------------------ 

int computer_move() // 
{ 
    int best_move; // best move so far 
    int best_score = -100; // best score so far 
    int score; // current score 
    int i; 

    for (i = 0; i < 16; ++i) { // 
     if (pos[i] == EMPTY) { // if a legal move can be made 
      pos[i] = COMPUTER; // mark the move 
      score = -dfs_search(HUMAN); // 
      pos[i] = EMPTY; // take back the move 

      if (score > best_score) { 
       best_score = score; 
       best_move = i; 
      } 
     } 
    } 

    printf("Computer's move: %d\n", best_move); 
    return best_move; // return the best move found 
} 


//------------------------------------------------------------ 
// dfs_search() gets the side to move, find all legal moves | 
// for him, and for each move, it recursively calls itself. | 
// It returns a score for the position.      | 
// This recursive function continues on each variation until | 
// the game's end is found in that variation. Which means  | 
// that the variation continues until check_result() returns | 
// a value other than CONTINUE.         | 
// Note that this can be done in tic-tac-toe, since it's a | 
// deterministic game. For games like chess or checkers we | 
// can't continue the variation until reaching the game's end | 
// so we have to cut the variation at some point.    | 
//------------------------------------------------------------ 

int dfs_search(int player) // 
{ 
    int best_score = -100; 
    int score; 
    int result; 
    int i; 

    result = check_result(player); 
    if (result != CONTINUE) return result; // return the result 

    for (i = 0; i < 16; ++i) { 
     if (pos[i] == EMPTY) { 
      pos[i] = player; 
      score = -dfs_search(CHANGE_PLAYER(player)); // 
      pos[i] = EMPTY; 

      if (score > best_score) 
       best_score = score; 
     } 
    } 

    return best_score; // return the best score 
} 

3行3列の行列については、かなりうまく機能します。しかし、4×4の場合、次の石を残すには時間がかかります。長い時間を費やす理由は最初の3つまたは4つの決定なので、私は、コンピュータの最終的な選択肢（ポイント）を中心にしてベストポイントを探すようにすることが解決策になると考えました。 最初の3つまたは4つの決定の後、上記の正式なアルゴリズムは残りのいくつかの点でうまくいくでしょう。あなたはどう思いますか？また、現在のアルゴリズムを変更するためのアドバイスを提供します。

Answer 1

ゲームツリー全体を解決しようとしています。 3x3ボードには9個あります！ =ツリー内のノード数は362880ですが、コンピュータの処理には十分に小さいですが、4x4ボードには16個あります！ = 20922789888000（20.9兆）のノードで、これは合理的な時間内に訪問するには多すぎます。

ゲームツリー全体を解決せずに現在の位置のスコアを適切に推定できる検索アルゴリズムを実装することを検討してください。 GoMokuについては、私はMonte Carlo Tree Searchをお勧めします。これは、Goなどの多くのゲームにうまく適用され、バニラ形式では、固定深度のmin-max検索とalpha-betaなどの変形に必要なようにstatic evaluation functionを書く必要はありません。