Wikiszótár

alfa-béta vágás

Magyar

Kiejtés

  • IPA: [ ˈɒlfɒbeːtɒvaːɡaːʃ]

Főnév

alfa-béta vágás

  1. (informatika, algoritmusok) Az alfa-béta vágás egy optimalizációs technika a minimax algoritmushoz, amelyet kétjátékos, nulla összegű játékok (pl. sakk, dáma) esetében alkalmaznak. Az algoritmus célja, hogy csökkentse a vizsgálandó csomópontok számát a játékfa keresése során, anélkül, hogy az eredmény pontossága csökkenne.


Elmélet

  1. Minimax algoritmus:
    • Az algoritmus egy játékfa minden állapotát kiértékeli, és a gyökércsomóponthoz visszavezeti az optimális lépést.
    • A játékosok Max és Min váltakozva próbálják maximalizálni, illetve minimalizálni a játék végső nyereségét.
  2. Alfa-béta vágás:
    • Az alfa (()) a maximális alsó korlátot tartalmazza, amit a Max játékos el tud érni.
    • A béta (()) a minimális felső korlátot tartalmazza, amit a Min játékos el tud érni.
    • Ha egy csomópont bizonyosan nem vezet jobb eredményhez, mint amit a korábbi csomópontok már garantáltak (()), akkor azt a részt nem kell tovább vizsgálni (vágás).
  3. Hatékonyság:
    • Az alfa-béta vágás csökkenti a keresési tér méretét.
    • Az optimális sorrendben vizsgált csomópontok esetében az időkomplexitás (O(b^{d/2})), ahol (b) az elágazási tényező, (d) pedig a keresési mélység.


Pszeudokód

AlphaBeta(node, depth, ?, ß, maximizingPlayer):
    ha depth == 0 vagy node terminális állapot:
        térj vissza node értéke

    ha maximizingPlayer:
        maxEval = -?
        minden child in node gyerekei:
            eval = AlphaBeta(child, depth-1, ?, ß, False)
            maxEval = max(maxEval, eval)
            ? = max(?, eval)
            ha ß ? ?:
                törés  // Vágás
        térj vissza maxEval
    különben:
        minEval = +?
        minden child in node gyerekei:
            eval = AlphaBeta(child, depth-1, ?, ß, True)
            minEval = min(minEval, eval)
            ß = min(ß, eval)
            ha ß ? ?:
                törés  // Vágás
        térj vissza minEval

Python implementáció

def alpha_beta(node, depth, alpha, beta, maximizing_player, evaluate, get_children):
    if depth == 0 or node.is_terminal():
        return evaluate(node)

    if maximizing_player:
        max_eval = float('-inf')
        for child in get_children(node):
            eval = alpha_beta(child, depth - 1, alpha, beta, False, evaluate, get_children)
            max_eval = max(max_eval, eval)
            alpha = max(alpha, eval)
            if beta <= alpha:
                break  # Vágás
        return max_eval
    else:
        min_eval = float('inf')
        for child in get_children(node):
            eval = alpha_beta(child, depth - 1, alpha, beta, True, evaluate, get_children)
            min_eval = min(min_eval, eval)
            beta = min(beta, eval)
            if beta <= alpha:
                break  # Vágás
        return min_eval

# Példa dummy osztályokkal
class Node:
    def __init__(self, value=None, children=None):
        self.value = value
        self.children = children if children else []

    def is_terminal(self):
        return self.value is not None

def evaluate(node):
    return node.value

def get_children(node):
    return node.children

# Példa játékfa
tree = Node(children=[
    Node(value=3),
    Node(children=[
        Node(value=5),
        Node(value=6),
    ]),
    Node(children=[
        Node(value=7),
        Node(value=4),
    ])
])

result = alpha_beta(tree, depth=3, alpha=float('-inf'), beta=float('inf'), maximizing_player=True, evaluate=evaluate, get_children=get_children)
print("Legjobb érték:", result)

Kimenet: 

Legjobb érték: 7

C++ implementáció

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

using namespace std;

struct Node {
    int value;
    vector<Node*> children;

    Node(int val = 0) : value(val) {}
    bool is_terminal() const {
        return children.empty();
    }
};

int alpha_beta(Node* node, int depth, int alpha, int beta, bool maximizing_player) {
    if (depth == 0 || node->is_terminal()) {
        return node->value;
    }

    if (maximizing_player) {
        int max_eval = numeric_limits<int>::min();
        for (Node* child : node->children) {
            int eval = alpha_beta(child, depth - 1, alpha, beta, false);
            max_eval = max(max_eval, eval);
            alpha = max(alpha, eval);
            if (beta <= alpha) {
                break;  // Vágás
            }
        }
        return max_eval;
    } else {
        int min_eval = numeric_limits<int>::max();
        for (Node* child : node->children) {
            int eval = alpha_beta(child, depth - 1, alpha, beta, true);
            min_eval = min(min_eval, eval);
            beta = min(beta, eval);
            if (beta <= alpha) {
                break;  // Vágás
            }
        }
        return min_eval;
    }
}

int main() {
    // Példa játékfa
    Node* root = new Node();
    root->children.push_back(new Node(3));
    Node* branch1 = new Node();
    branch1->children.push_back(new Node(5));
    branch1->children.push_back(new Node(6));
    root->children.push_back(branch1);
    Node* branch2 = new Node();
    branch2->children.push_back(new Node(7));
    branch2->children.push_back(new Node(4));
    root->children.push_back(branch2);

    int result = alpha_beta(root, 3, numeric_limits<int>::min(), numeric_limits<int>::max(), true);
    cout << "Legjobb érték: " << result << endl;

    return 0;
}

Kimenet: 

Legjobb érték: 7

Összegzés

Előnyök:

  1. Gyorsabb keresés: Jelentősen csökkenti a minimax keresési tér méretét.
  2. Optimalizáció: Ugyanazt az eredményt adja, mint a minimax, de hatékonyabb.

Hátrányok:

  1. Sorrend befolyásolhatja a teljesítményt: Az optimális csomópontsorrend maximalizálja az alfa-béta vágás hatékonyságát.
  2. Komplexitás: Implementációja bonyolultabb, mint a tiszta minimaxé.

Az alfa-béta vágás kulcsfontosságú a mesterséges intelligenciában, különösen kétjátékos stratégiai játékok fejlesztésekor (pl. sakk, dáma, amőba).

Fordítások

Tartalom

További információk

A lap eredeti címe: „https://hu.wiktionary.org/w/index.php?title=alfa-béta_vágás&oldid=3479511”