Рубрики

Минимаксный алгоритм в теории игр | Комплект 1 (Введение)

Минимакс — это своего рода алгоритм обратного отслеживания , который используется в процессе принятия решений и теории игр, чтобы найти оптимальный ход для игрока, предполагая, что ваш противник также играет оптимально. Он широко используется в пошаговых играх для двух игроков, таких как крестики-нолики, нарды, манкала, шахматы и т. Д.

В Minimax оба игрока называются максимизатором и минимизатором. Максимизатор пытается получить максимально возможную оценку, в то время как минимизатор пытается сделать обратное и получить минимально возможную оценку.

С каждым состоянием доски связано значение. В данном состоянии, если максимизатор имеет преимущество, то оценка доски будет иметь тенденцию быть некоторой положительной величиной. Если минимизатор имеет преимущество в этом состоянии платы, то он будет иметь тенденцию к некоторому отрицательному значению. Значения доски рассчитываются по некоторым эвристикам, которые уникальны для каждого типа игры.

Пример:
Рассмотрим игру, которая имеет 4 конечных состояния и пути для достижения конечного состояния от корня до 4-х листьев идеального бинарного дерева, как показано ниже. Предположим, что вы максимизирующий игрок, и вы получаете первый шанс на движение, то есть вы находитесь в корне, а ваш оппонент на следующем уровне. Какой ход вы бы сделали как максимизирующий игрок, учитывая, что ваш оппонент также играет оптимально?

Поскольку это алгоритм, основанный на возврате, он пробует все возможные ходы, затем возвращается и принимает решение.

  • Максимизатор уходит налево: теперь очередь минимизаторов. Минимизатор теперь имеет выбор между 3 и 5. Будучи минимизатором, он определенно выберет наименьшее из обоих, то есть 3
  • Maximizer идет направо: теперь очередь за минимизаторами. Минимизатор теперь имеет выбор между 2 и 9. Он выберет 2, так как он является наименьшим из двух значений.

Будучи максимизатором, вы бы выбрали большее значение, равное 3. Следовательно, оптимальное движение для максимизатора — это идти ВЛЕВО, а оптимальное значение — 3.

Теперь дерево игры выглядит так:

Приведенное выше дерево показывает две возможные оценки, когда максимизатор делает левый и правый ходы.

Примечание. Даже если в правом поддереве есть значение 9, минимизатор никогда не выберет это. Мы всегда должны предполагать, что наш противник играет оптимально.

Ниже приведена реализация того же.

C ++

// Простая программа на C ++ для поиска
// максимальная оценка
// максимизировать игрок может получить.
#include<bits/stdc++.h>

using namespace std;

  
// Возвращает оптимальное значение, которое максимизатор может получить.
// глубина - текущая глубина в дереве игры.
// nodeIndex - это индекс текущего узла в показателях [].
// isMax имеет значение true, если текущий ход
// максимизатора, иначе ложь
// scores [] хранит листья дерева игр.
// h - максимальная высота дерева игр

int minimax(int depth, int nodeIndex, bool isMax,

            int scores[], int h)

{

    // Завершающее условие. т.е.

    // конечный узел достигнут

    if (depth == h)

        return scores[nodeIndex];

  

    // Если текущий ход максимизатор,

    // найти максимально достижимый

    // значение

    if (isMax)

       return max(minimax(depth+1, nodeIndex*2, false, scores, h),

            minimax(depth+1, nodeIndex*2 + 1, false, scores, h));

  

    // Остальное (если текущий ход Minimizer), найти минимальное

    // достижимая стоимость

    else

        return min(minimax(depth+1, nodeIndex*2, true, scores, h),

            minimax(depth+1, nodeIndex*2 + 1, true, scores, h));

}

  
// Утилита для поиска Log n в базе 2

int log2(int n)

{

  return (n==1)? 0 : 1 + log2(n/2);

}

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

int main()

{

    // Количество элементов в баллах должно быть

    // степень 2.

    int scores[] = {3, 5, 2, 9, 12, 5, 23, 23};

    int n = sizeof(scores)/sizeof(scores[0]);

    int h = log2(n);

    int res = minimax(0, 0, true, scores, h);

    cout << "The optimal value is : " << res << endl;

    return 0;

}

Джава

// Простая Java-программа, чтобы найти максимальную оценку, которая
// максимизировать игрок может получить.

  

import java.io.*;

  

class GFG {

    

  
// Возвращает оптимальное значение, которое максимизатор может получить.
// глубина - текущая глубина в дереве игры.
// nodeIndex - это индекс текущего узла в показателях [].
// isMax имеет значение true, если текущий ход имеет максимизатор, иначе false
// scores [] хранит листья дерева игр.
// h - максимальная высота дерева игр

 static int minimax(int depth, int nodeIndex, boolean  isMax,

            int scores[], int h)

{

    // Завершающее условие. то есть листовой узел достигнут

    if (depth == h)

        return scores[nodeIndex];

  

    // Если текущий ход максимизатор, найти максимально достижимый

    // значение

    if (isMax)

    return Math.max(minimax(depth+1, nodeIndex*2, false, scores, h),

            minimax(depth+1, nodeIndex*2 + 1, false, scores, h));

  

    // Остальное (если текущий ход Minimizer), найти минимальное

    // достижимая стоимость

    else

        return Math.min(minimax(depth+1, nodeIndex*2, true, scores, h),

            minimax(depth+1, nodeIndex*2 + 1, true, scores, h));

}

  
// Утилита для поиска Log n в базе 2

 static int log2(int n)

{

return (n==1)? 0 : 1 + log2(n/2);

}

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

  

    public static void main (String[] args) {

            // Количество элементов в баллах должно быть

    // степень 2.

    int scores[] = {3, 5, 2, 9, 12, 5, 23, 23};

    int n = scores.length;

    int h = log2(n);

    int res = minimax(0, 0, true, scores, h);

    System.out.println( "The optimal value is : "  +res); 

          

    }

}

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

C #

// Простая программа на C #, чтобы найти максимальную оценку
// максимизировать игрок может получить.

using System;

  

public class GFG

{

      
// Возвращает оптимальное значение, которое максимизатор может получить.
// глубина - текущая глубина в дереве игры.
// nodeIndex - это индекс текущего узла в показателях [].
// isMax имеет значение true, если текущий ход имеет максимизатор, иначе false
// scores [] хранит листья дерева игр.
// h - максимальная высота дерева игр

static int minimax(int depth, int nodeIndex, bool isMax,

            int []scores, int h)

{

    // Завершающее условие. то есть листовой узел достигнут

    if (depth == h)

        return scores[nodeIndex];

  

    // Если текущий ход максимизатор, найти максимально достижимый

    // значение

    if (isMax)

    return Math.Max(minimax(depth+1, nodeIndex*2, false, scores, h),

            minimax(depth+1, nodeIndex*2 + 1, false, scores, h));

  

    // Остальное (если текущий ход Minimizer), найти минимальное

    // достижимая стоимость

    else

        return Math.Min(minimax(depth+1, nodeIndex*2, true, scores, h),

            minimax(depth+1, nodeIndex*2 + 1, true, scores, h));

}

  
// Утилита для поиска Log n в базе 2

static int log2(int n)

{

    return (n==1)? 0 : 1 + log2(n/2);

}

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

static public void Main ()

{

  

    // Количество элементов в баллах должно быть

    // степень 2.

    int []scores = {3, 5, 2, 9, 12, 5, 23, 23};

    int n = scores.Length;

    int h = log2(n);

    int res = minimax(0, 0, true, scores, h);

    Console.WriteLine( "The optimal value is : " +res); 

      
}
}

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

python3

# Простая программа на Python3 для поиска
# максимальная оценка
# максимизировать игрок может получить

import math

  

def minimax (curDepth, nodeIndex,

             maxTurn, scores, 

             targetDepth):

  

    # базовый случай: targetDepth достигнут

    if (curDepth == targetDepth): 

        return scores[nodeIndex]

      

    if (maxTurn):

        return max(minimax(curDepth + 1, nodeIndex * 2

                    False, scores, targetDepth), 

                   minimax(curDepth + 1, nodeIndex * 2 + 1

                    False, scores, targetDepth))

      

    else:

        return min(minimax(curDepth + 1, nodeIndex * 2

                     True, scores, targetDepth), 

                   minimax(curDepth + 1, nodeIndex * 2 + 1

                     True, scores, targetDepth))

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

scores = [3, 5, 2, 9, 12, 5, 23, 23]

  

treeDepth = math.log(len(scores), 2)

  

print("The optimal value is : ", end = "")

print(minimax(0, 0, True, scores, treeDepth))

  
# Этот код добавлен
# от roothadow


Выход:

The optimal value is:  12

Идея этой статьи — представить Minimax на простом примере.

  • В приведенном выше примере есть только два варианта для игрока. В общем, может быть больше вариантов. В этом случае нам нужно повторить все возможные ходы и найти максимум / минимум. Например, в Tic-Tax-Toe первый игрок может сделать 9 возможных ходов.
  • В приведенном выше примере, оценки (листья дерева игр) даны нам. Для типичной игры нам нужно вывести эти значения

Скоро мы рассмотрим Tic Tac Toe с минимаксным алгоритмом.

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

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

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

Минимаксный алгоритм в теории игр | Комплект 1 (Введение)

0.00 (0%) 0 votes