Was wird der Terminalfall von maxconnect4 Spiel sein?

Question

Ich verstehe Tic-Tac-Toe mit Minimax-Algorithmus, wo Terminal-Fälle gewinnen, verloren und zeichnen - 10,0, -10.

Programm endet, wenn jemand gewinnt, verliert oder zeichnet. Wie verbinden vier Spiel haben nicht drei Terminal-Staaten, anstatt eine Anzeigetafel, nachdem das Spiel beendet ist, Wie ermittle ich seine Terminal Fällen von der Bewertungsfunktion? Wie implementiert man die Bewertungsfunktion?

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; 
    } 
} 

Aber für connect4, wie berechne ich Auswertungsfunktion und wie wird es Terminal Fälle definieren (außer, wenn das Brett voll ist)?

Answer 1

Als connect vier Spiel haben keine drei Endzustände, sondern als ein Anzeiger, nachdem das Spiel beendet ist,

Zunächst einmal sind Ihre falsch in vier verbinden damit nicht sagen, mit drei Anschlüssen hat Phasen. Es kann auch nur mit einem Sieg, einem Verlust oder einem Unentschieden enden.

Das Problem ist, dass Verbindung vier ist so komplex, dass es unmöglich ist, den Baum zu bewerten, bis diese Endstufen erreicht sind. Deshalb wird in Spielen, die komplizierter sind als die grundlegendsten (wie Tic Tac Toe), eine vorbestimmte Suchtiefe für die Suche gegeben, und alle Knoten am Ende dieser Tiefe werden als Terminal betrachtet. Diese Tiefe wird normalerweise durch Zeitbeschränkungen in einem iterativen Vertiefungsrahmen bestimmt.

Da diese Knoten in Wirklichkeit nicht terminal sind, können wir sie nicht mehr mit 0, 1 und -1 auswerten. Stattdessen erweitern wir unser Angebot, indem wir Gewinne als eine beliebig hohe Zahl behandeln, verlieren sie als beliebig niedrig und verwenden eine heuristische Bewertungsfunktion, um dazwischen Werte zu bestimmen. Eine mögliche Heuristik ist die Anzahl von drei in Reihen, die ein Spieler hat. Für komplexere vier Heuristiken, lesen Victor Aliss These zu diesem Thema.