C에서 컴퓨터 결정에 속도를 얻는 방법

Question

나는 컴퓨터로 Gomoku (tictactoe의 5 by 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 
} 

3x3 매트릭스의 경우 매우 잘 작동합니다. 그러나 4 x 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을 쓸 필요가 없습니다.