maxconnect4 게임의 터미널 케이스는 무엇이 될까요?

Question

터미널 케이스가 이기고, 손실되고 그려지는 미니 맥스 알고리즘을 사용하여 tic-tac-toe를 이해합니다 - 10,0, -10.

어떤 프로그램이이기거나, 느슨하거나 그릴 때 프로그램이 종료됩니다. 4 개의 게임을 연결하면 3 개의 터미널 상태가 아니라 게임 종료 후 점수 판이 아닌 평가 함수에서 터미널 케이스를 어떻게 결정합니까? 평가 기능을 구현하는 방법은 무엇입니까?

int minimax(char board[3][3], int depth, bool isMax) 
{ 
int score = evaluate(board); 

// If Maximizer has won the game return his/her 
// evaluated score 
if (score == 10) 
    return score; 

// If Minimizer has won the game return his/her 
// evaluated score 
if (score == -10) 
    return score; 

// If there are no more moves and no winner then 
// it is a tie 
if (isMovesLeft(board)==false) 
    return 0; 

// If this maximizer's move 
if (isMax) 
{ 
    int best = -1000; 

    // Traverse all cells 
    for (int i = 0; i<3; i++) 
    { 
     for (int j = 0; j<3; j++) 
     { 
      // Check if cell is empty 
      if (board[i][j]=='_') 
      { 
       // Make the move 
       board[i][j] = player; 

       // Call minimax recursively and choose 
       // the maximum value 
       best = max(best, 
        minimax(board, depth+1, !isMax)); 

       // Undo the move 
       board[i][j] = '_'; 
      } 
     } 
    } 
    return best; 
} 

// If this minimizer's move 
else 
{ 
    int best = 1000; 

    // Traverse all cells 
    for (int i = 0; i<3; i++) 
    { 
     for (int j = 0; j<3; j++) 
     { 
      // Check if cell is empty 
      if (board[i][j]=='_') 
      { 
       // Make the move 
       board[i][j] = opponent; 

       // Call minimax recursively and choose 
       // the minimum value 
       best = min(best, 
         minimax(board, depth+1, !isMax)); 

       // Undo the move 
       board[i][j] = '_'; 
      } 
     } 
    } 
    return best; 
    } 
} 

그러나 connect4에 대한 , 어떻게 평가 함수를 계산합니까 그것은 (보드가 꽉 찬 경우를 제외하고) 단자의 경우를 정의하는 방법?

Answer 1

네 게임이 아니라 게임이 끝난 후 점수 판에 비해, 세 개의 터미널 상태가 없습니다으로 연결, 모든

먼저, 당신은 세 개의 터미널이없는 사를 연결 말에 잘못 단계. 그것도 역시 승리, 패배, 무승부로 끝날 수 있습니다.

문제는 연결 4가 충분히 복잡하여 터미널 단계에 도달 할 때까지 트리를 평가할 수 없다는 것입니다. 그래서 가장 기본적인 게임 (tic tac 발가락처럼)에서 게임을 미리 정한 검색 깊이가 주어지고 그 깊이 끝에있는 모든 노드가 터미널로 간주됩니다. 이 심도는 대개 반복 심화 프레임 워크에서 시간 제약에 따라 결정됩니다.

실제로 이러한 노드는 터미널이 아니므로 더 이상 0, 1 및 -1을 사용하여 노드를 평가할 수 없습니다. 대신 우리는 범위를 넓히고 임의로 높은 수를 처리하며 임의로 낮게 잃고 휴리스틱 평가 함수를 사용하여 값을 결정합니다. 하나의 가능한 휴리스틱은 한 행에 세 개가 있습니다. 더 복잡한 경우 4 개의 휴리스틱을 연결하려면이 주제에 대한 Victor Aliss의 논문을 읽으십시오.