Algoritmo Minimax en Teoría de Juegos | Conjunto 2 (Introducción a la función de evaluación)

Prerrequisito: Algoritmo Minimax en Teoría de Juegos
Como se vio en el artículo anterior, cada Node de hoja tenía un valor asociado. Habíamos almacenado este valor en una array. Pero en el mundo real cuando estamos creando un programa para jugar Tic-Tac-Toe, Ajedrez, Backgammon, etc. necesitamos implementar una función que calcule el valor del tablero dependiendo de la ubicación de las piezas en el tablero. Esta función se conoce a menudo como función de evaluación . A veces también se le llama función heurística.
La función de evaluación es única para cada tipo de juego. En esta publicación, se analiza la función de evaluación del juego Tic-Tac-Toe. La idea básica detrás de la función de evaluación es dar un valor alto para un tablero si es el turno del maximizador o un valor bajo para el tablero siturno del minimizador .
Para este escenario consideremos como el maximizador y como el minimizador .
Construyamos nuestra función de evaluación: 
 

1. Si X gana en el tablero le damos un valor positivo de +10. 
    

1. Si O gana en el tablero le damos un valor negativo de -10. 
    

1. Si nadie ha ganado o el juego termina en empate, le damos un valor de +0. 
    

Podríamos haber elegido cualquier valor positivo/negativo que no sea 10. En aras de la simplicidad, elegimos 10. En aras de la simplicidad, usaremos minúsculas ‘x’ y minúsculas ‘o’ para representar a los jugadores y un guión bajo ‘_’ para representar un espacio en blanco en la pizarra. 
Si representamos nuestro tablero como una array de caracteres 2D de 3 × 3, como char board[3][3]; luego tenemos que revisar cada fila, cada columna y las diagonales para verificar si alguno de los jugadores ha sacado 3 seguidos.
 

// C++ program to compute evaluation function for
// Tic Tac Toe Game.
#include<stdio.h>
#include<algorithm>
using namespace std;
 
// Returns a value based on who is winning
// b[3][3] is the Tic-Tac-Toe board
int evaluate(char b[3][3])
{
    // Checking for Rows for X or O victory.
    for (int row = 0; row<3; row++)
    {
        if (b[row][0]==b[row][1] && b[row][1]==b[row][2])
        {
            if (b[row][0]=='x')
               return +10;
            else if (b[row][0]=='o')
               return -10;
        }
    }
 
    // Checking for Columns for X or O victory.
    for (int col = 0; col<3; col++)
    {
        if (b[0][col]==b[1][col] && b[1][col]==b[2][col])
        {
            if (b[0][col]=='x')
                return +10;
            else if (b[0][col]=='o')
                return -10;
        }
    }
 
    // Checking for Diagonals for X or O victory.
    if (b[0][0]==b[1][1] && b[1][1]==b[2][2])
    {
        if (b[0][0]=='x')
            return +10;
        else if (b[0][0]=='o')
            return -10;
    }
    if (b[0][2]==b[1][1] && b[1][1]==b[2][0])
    {
        if (b[0][2]=='x')
            return +10;
        else if (b[0][2]=='o')
            return -10;
    }
 
    // Else if none of them have won then return 0
    return 0;
}
 
// Driver code
int main()
{
    char board[3][3] =
    {
        { 'x', '_', 'o'},
        { '_', 'x', 'o'},
        { '_', '_', 'x'}
    };
 
    int value = evaluate(board);
    printf("The value of this board is %d\n", value);
    return 0;
}

// Java program to compute evaluation function for
// Tic Tac Toe Game.
 
class GFG
{
 
// Returns a value based on who is winning
// b[3][3] is the Tic-Tac-Toe board
static int evaluate(char b[][])
{
    // Checking for Rows for X or O victory.
    for (int row = 0; row < 3; row++)
    {
        if (b[row][0] == b[row][1] && b[row][1] == b[row][2])
        {
            if (b[row][0] == 'x')
            return +10;
            else if (b[row][0] == 'o')
            return -10;
        }
    }
 
    // Checking for Columns for X or O victory.
    for (int col = 0; col < 3; col++)
    {
        if (b[0][col] == b[1][col] && b[1][col] == b[2][col])
        {
            if (b[0][col] == 'x')
                return +10;
            else if (b[0][col] == 'o')
                return -10;
        }
    }
 
    // Checking for Diagonals for X or O victory.
    if (b[0][0] == b[1][1] && b[1][1] == b[2][2])
    {
        if (b[0][0] == 'x')
            return +10;
        else if (b[0][0] == 'o')
            return -10;
    }
    if (b[0][2] == b[1][1] && b[1][1] == b[2][0])
    {
        if (b[0][2] == 'x')
            return +10;
        else if (b[0][2] == 'o')
            return -10;
    }
 
    // Else if none of them have won then return 0
    return 0;
}
 
// Driver code
public static void main(String[] args)
{
    char board[][] =
    {
        { 'x', '_', 'o'},
        { '_', 'x', 'o'},
        { '_', '_', 'x'}
    };
 
    int value = evaluate(board);
    System.out.printf("The value of this board is %d\n", value);
}
}
 
// This code is contributed by PrinciRaj1992

# Python3 program to compute evaluation
# function for Tic Tac Toe Game.
 
# Returns a value based on who is winning
# b[3][3] is the Tic-Tac-Toe board
def evaluate(b):
  
    # Checking for Rows for X or O victory.
    for row in range(0, 3):
      
        if b[row][0] == b[row][1] and b[row][1] == b[row][2]:
          
            if b[row][0] == 'x':
                return 10
            else if b[row][0] == 'o':
                return -10
 
    # Checking for Columns for X or O victory.
    for col in range(0, 3):
      
        if b[0][col] == b[1][col] and b[1][col] == b[2][col]:
          
            if b[0][col]=='x':
                return 10
            else if b[0][col] == 'o':
                return -10
 
    # Checking for Diagonals for X or O victory.
    if b[0][0] == b[1][1] and b[1][1] == b[2][2]:
      
        if b[0][0] == 'x':
            return 10
        else if b[0][0] == 'o':
            return -10
      
    if b[0][2] == b[1][1] and b[1][1] == b[2][0]:
      
        if b[0][2] == 'x':
            return 10
        else if b[0][2] == 'o':
            return -10
      
    # Else if none of them have won then return 0
    return 0
  
# Driver code
if __name__ == "__main__":
  
    board = [['x', '_', 'o'],
             ['_', 'x', 'o'],
             ['_', '_', 'x']]
      
    value = evaluate(board)
    print("The value of this board is", value)
 
# This code is contributed by Rituraj Jain

// C# program to compute evaluation function for
// Tic Tac Toe Game.
using System;
 
class GFG
{
 
// Returns a value based on who is winning
// b[3,3] is the Tic-Tac-Toe board
static int evaluate(char [,]b)
{
    // Checking for Rows for X or O victory.
    for (int row = 0; row < 3; row++)
    {
        if (b[row, 0] == b[row, 1] && b[row, 1] == b[row, 2])
        {
            if (b[row, 0] == 'x')
            return +10;
            else if (b[row, 0] == 'o')
            return -10;
        }
    }
 
    // Checking for Columns for X or O victory.
    for (int col = 0; col < 3; col++)
    {
        if (b[0, col] == b[1, col] && b[1, col] == b[2, col])
        {
            if (b[0, col] == 'x')
                return +10;
            else if (b[0, col] == 'o')
                return -10;
        }
    }
 
    // Checking for Diagonals for X or O victory.
    if (b[0, 0] == b[1, 1] && b[1, 1] == b[2, 2])
    {
        if (b[0, 0] == 'x')
            return +10;
        else if (b[0, 0] == 'o')
            return -10;
    }
    if (b[0, 2] == b[1, 1] && b[1, 1] == b[2, 0])
    {
        if (b[0, 2] == 'x')
            return +10;
        else if (b[0, 2] == 'o')
            return -10;
    }
 
    // Else if none of them have won then return 0
    return 0;
}
 
// Driver code
public static void Main(String[] args)
{
    char [,]board =
    {
        { 'x', '_', 'o'},
        { '_', 'x', 'o'},
        { '_', '_', 'x'}
    };
 
    int value = evaluate(board);
    Console.Write("The value of this board is {0}\n", value);
}
}
 
// This code is contributed by Rajput-Ji

<script>
// Javascript program to compute evaluation function for
// Tic Tac Toe Game.
 
// Returns a value based on who is winning
// b[3][3] is the Tic-Tac-Toe board
function evaluate(b)
{
 
    // Checking for Rows for X or O victory.
    for (let row = 0; row < 3; row++)
    {
        if (b[row][0] == b[row][1] && b[row][1] == b[row][2])
        {
            if (b[row][0] == 'x')
                return +10;
            else if (b[row][0] == 'o')
                return -10;
        }
    }
   
    // Checking for Columns for X or O victory.
    for (let col = 0; col < 3; col++)
    {
        if (b[0][col] == b[1][col] && b[1][col] == b[2][col])
        {
            if (b[0][col] == 'x')
                return +10;
            else if (b[0][col] == 'o')
                return -10;
        }
    }
   
    // Checking for Diagonals for X or O victory.
    if (b[0][0] == b[1][1] && b[1][1] == b[2][2])
    {
        if (b[0][0] == 'x')
            return +10;
        else if (b[0][0] == 'o')
            return -10;
    }
    if (b[0][2] == b[1][1] && b[1][1] == b[2][0])
    {
        if (b[0][2] == 'x')
            return +10;
        else if (b[0][2] == 'o')
            return -10;
    }
   
    // Else if none of them have won then return 0
    return 0;
}
 
// Driver code
let board=[[ 'x', '_', 'o'],
        [ '_', 'x', 'o'],
        [ '_', '_', 'x']];
 
let value = evaluate(board);
document.write("The value of this board is "+ value+"<br>");
 
// This code is contributed by avanitrachhadiya2155
</script>

Producción : 

The value of this board is 10

La idea de este artículo es entender cómo escribir una función de evaluación simple para el juego Tic-Tac-Toe. En el próximo artículo veremos cómo combinar esta función de evaluación con la función minimax. Manténganse al tanto.
Este artículo está escrito por  Akshay L. Aradhya . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo y enviarlo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.