Wikiszótár

minimax algoritmus

Magyar

Kiejtés

  • IPA: [ ˈminimɒksɒlɡoritmuʃ]

Főnév

minimax algoritmus

  1. (matematika, algoritmusok, informatika) A Minimax algoritmus egy döntéshozatali eljárás, amelyet főként kétjátékos, nullösszegű játékokban alkalmaznak, például sakkban vagy tic-tac-toe-ban. Az algoritmus célja, hogy az egyik játékos maximalizálja a saját nyereségét, míg az ellenfél ugyanakkor próbálja minimalizálni azt.


Algoritmus alapelve

  1. Oszd meg és uralkodj:
    • A játékállapotokat rekurzívan bontjuk kisebb részekre.
  2. Döntési szabály:
    • A Maximizer a legnagyobb értéket próbálja elérni.
    • A Minimizer a legkisebb értéket próbálja elérni.
  3. Kiértékelés:
    • Az algoritmus a játékfa leveleitől (végállapotok) indul, ahol az értékeket közvetlenül meghatározza az állapot hasznossága.
  4. Visszaterjedés:
    • Az állapotok értékei a játékfa leveleitől visszaterjednek a gyökérhez, ahol a Maximizer és Minimizer váltakozva választja ki a legjobb értéket.


Pszeudokód

Minimax(node, depth, maximizingPlayer):
    ha depth == 0 vagy node végállapot:
        térj vissza node értéke

    ha maximizingPlayer:
        maxEval = -végtelen
        minden child in node gyerekek:
            eval = Minimax(child, depth - 1, hamis)
            maxEval = max(maxEval, eval)
        térj vissza maxEval
    különben:
        minEval = +végtelen
        minden child in node gyerekek:
            eval = Minimax(child, depth - 1, igaz)
            minEval = min(minEval, eval)
        térj vissza minEval

Python implementáció

Alap Minimax

def minimax(position, depth, maximizingPlayer):
    if depth == 0 or is_terminal(position):
        return evaluate(position)

    if maximizingPlayer:
        maxEval = float('-inf')
        for child in get_children(position):
            eval = minimax(child, depth - 1, False)
            maxEval = max(maxEval, eval)
        return maxEval
    else:
        minEval = float('inf')
        for child in get_children(position):
            eval = minimax(child, depth - 1, True)
            minEval = min(minEval, eval)
        return minEval

Egyszerű példa: Tic-Tac-Toe

def evaluate(position):
    # Kiértékelés logikája
    # Például +1 győzelemért, -1 vereségért, 0 döntetlenért
    pass

def get_children(position):
    # Minden lehetséges lépésből származó új játékállapot
    pass

def is_terminal(position):
    # Ellenőrzi, hogy az állapot végállapot-e
    pass

C++ implementáció

#include <iostream>
#include <vector>
#include <limits>

using namespace std;

const int MAX = numeric_limits<int>::max();
const int MIN = numeric_limits<int>::min();

// Kiértékelő függvény (példa)
int evaluate(vector<vector<char>>& board) {
    // Implementálj kiértékelést
    return 0;
}

// Ellenőrizze, hogy végállapot-e
bool is_terminal(vector<vector<char>>& board) {
    // Implementálj végállapot ellenőrzést
    return false;
}

int minimax(vector<vector<char>>& board, int depth, bool maximizingPlayer) {
    if (depth == 0 || is_terminal(board)) {
        return evaluate(board);
    }

    if (maximizingPlayer) {
        int maxEval = MIN;
        // Generálj gyermekállapotokat (példa)
        for (auto& child : get_children(board)) {
            int eval = minimax(child, depth - 1, false);
            maxEval = max(maxEval, eval);
        }
        return maxEval;
    } else {
        int minEval = MAX;
        // Generálj gyermekállapotokat (példa)
        for (auto& child : get_children(board)) {
            int eval = minimax(child, depth - 1, true);
            minEval = min(minEval, eval);
        }
        return minEval;
    }
}

int main() {
    vector<vector<char>> board = {
        {'_', '_', '_'},
        {'_', '_', '_'},
        {'_', '_', '_'}
    };

    int bestValue = minimax(board, 3, true);
    cout << "A legjobb lépés értéke: " << bestValue << endl;

    return 0;
}

Optimalizáció: Alfa-Béta Metszés

Az alfa-béta metszés csökkenti a játékfa ágainak számát, amelyeket ténylegesen ki kell értékelni. Ez jelentősen javítja a teljesítményt anélkül, hogy a végeredményt befolyásolná.

Pszeudokód:

AlphaBeta(node, depth, alpha, beta, maximizingPlayer):
    ha depth == 0 vagy node végállapot:
        térj vissza node értéke

    ha maximizingPlayer:
        maxEval = -végtelen
        minden child in node gyerekek:
            eval = AlphaBeta(child, depth - 1, alpha, beta, hamis)
            maxEval = max(maxEval, eval)
            alpha = max(alpha, eval)
            ha beta <= alpha:
                törés
        térj vissza maxEval
    különben:
        minEval = +végtelen
        minden child in node gyerekek:
            eval = AlphaBeta(child, depth - 1, alpha, beta, igaz)
            minEval = min(minEval, eval)
            beta = min(beta, eval)
            ha beta <= alpha:
                törés
        térj vissza minEval

Összegzés

  • Előnyök:
    • Optimális, ha a játékfa teljesen kiértékelhető.
    • Alfa-béta metszéssel jelentős sebességnövekedés érhető el.
  • Hátrányok:
    • Nagy játékfák esetén túl lassú lehet, különösen mély fák esetén.
    • A kiértékelő függvény minősége nagyban befolyásolja az eredményeket.

A Minimax algoritmus kiváló alapot nyújt mesterséges intelligenciák fejlesztéséhez, különösen játékokban, ahol a stratégia optimalizálása kulcsfontosságú.

További információk

A lap eredeti címe: „https://hu.wiktionary.org/w/index.php?title=minimax_algoritmus&oldid=3479469”