Рубрики

Минимаксный алгоритм в теории игр | Комплект 2 (Введение в функцию оценки)

Условие: минимаксный алгоритм в теории игр

Как видно из вышеприведенной статьи, каждый листовой узел имеет значение, связанное с ним. Мы сохранили это значение в массиве. Но в реальном мире, когда мы создаем программу для игры в Tic-Tac-Toe, Chess, Backgamon и т. Д., Нам нужно реализовать функцию, которая вычисляет стоимость доски в зависимости от размещения фигур на доске. Эта функция часто называется оценочной функцией . Иногда его также называют эвристической функцией.

Функция оценки уникальна для каждого типа игры. В этом посте обсуждается функция оценки для игры в крестики-нолики. Основная идея функции оценки состоит в том, чтобы задать высокое значение для платы, если поворот максимизатора , или низкое значение для доски, если поворот минимизатора .

Для этого сценария давайте рассмотрим X как максимизатор и O как минимизатор .

Давайте построим нашу функцию оценки:

  1. Если X выигрывает на доске, мы даем ей положительное значение +10.
  2. Если O выигрывает на доске, мы даем ей отрицательное значение -10.
  3. Если никто не выиграл или игра заканчивается вничью, мы даем значение +0.

Мы могли бы выбрать любое положительное / отрицательное значение, отличное от 10. Для простоты мы выбрали 10, для простоты мы будем использовать нижний регистр 'x' и нижний регистр 'o' для представления игроков и подчеркивание '_' представлять пустое место на доске.

Если мы представим нашу доску в виде трехмерной матрицы символов 3 × 3, например, char board [3] [3]; затем мы должны проверить каждый ряд, каждый столбец и диагонали, чтобы проверить, получил ли кто-либо из игроков 3 в ряду.

C ++

// C ++ программа для вычисления функции оценки для
// Крестики-нолики.
#include<stdio.h>
#include<algorithm>

using namespace std;

  
// Возвращает значение в зависимости от того, кто выигрывает
// b [3] [3] - доска Tic-Tac-Toe

int evaluate(char b[3][3])

{

    // Проверка строк на победу X или O.

    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;

        }

    }

  

    // Проверка столбцов для победы X или O.

    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;

        }

    }

  

    // Проверка диагоналей на победу X или O.

    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;

    }

  

    // Иначе, если ни один из них не выиграл, вернуть 0

    return 0;

}

  
// Код драйвера

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-программа для вычисления функции оценки
// Крестики-нолики.

  

class GFG

{

  
// Возвращает значение в зависимости от того, кто выигрывает
// b [3] [3] - доска Tic-Tac-Toe

static int evaluate(char b[][])

{

    // Проверка строк на победу X или O.

    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;

        }

    }

  

    // Проверка столбцов для победы X или O.

    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;

        }

    }

  

    // Проверка диагоналей на победу X или O.

    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;

    }

  

    // Иначе, если ни один из них не выиграл, вернуть 0

    return 0;

}

  
// Код драйвера

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

}
}

  
// Этот код предоставлен PrinciRaj1992

python3

# Python3 программа для вычисления оценки
# функция для Tic Tac Toe Game.

  
# Возвращает значение в зависимости от того, кто выигрывает
# b [3] [3] это доска Tic-Tac-Toe

def evaluate(b): 

   

    # Проверка строк на X или O победа.

    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 

            elif b[row][0] == 'o'

                return -10 

  

    # Проверка столбцов для победы X или O.

    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 

            elif b[0][col] == 'o'

                return -10 

  

    # Проверка диагоналей на победу X или O.

    if b[0][0] == b[1][1] and b[1][1] == b[2][2]: 

       

        if b[0][0] == 'x'

            return 10 

        elif 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 

        elif b[0][2] == 'o'

            return -10 

       

    # В противном случае, если никто из них не выиграл, верните 0

    return 0 

   
# Код драйвера

if __name__ == "__main__"

   

    board = [['x', '_', 'o'], 

             ['_', 'x', 'o'], 

             ['_', '_', 'x']] 

       

    value = evaluate(board) 

    print("The value of this board is", value) 

  
# Этот код предоставлен Rituraj Jain

C #

// C # программа для вычисления функции оценки для
// Крестики-нолики.

using System;

  

class GFG

{

  
// Возвращает значение в зависимости от того, кто выигрывает
// b [3,3] доска Tic-Tac-Toe

static int evaluate(char [,]b)

{

    // Проверка строк на победу X или O.

    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;

        }

    }

  

    // Проверка столбцов для победы X или O.

    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;

        }

    }

  

    // Проверка диагоналей на победу X или O.

    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;

    }

  

    // Иначе, если ни один из них не выиграл, вернуть 0

    return 0;

}

  
// Код драйвера

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

}
}

  
// Этот код предоставлен Rajput-Ji

Выход :

The value of this board is 10

Идея этой статьи состоит в том, чтобы понять, как написать простую оценочную функцию для игры Tic-Tac-Toe. В следующей статье мы увидим, как объединить эту функцию оценки с минимаксной функцией. Будьте на связи.

Эта статья написана Акшай Л. Арадхья . Если вам нравится GeeksforGeeks и вы хотите внести свой вклад, вы также можете написать статью и отправить ее по почте на contrib@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Минимаксный алгоритм в теории игр | Комплект 2 (Введение в функцию оценки)

0.00 (0%) 0 votes