Ugrás a tartalomhoz

alpha-beta pruning

A Wikiszótárból, a nyitott szótárból

Angol


Főnév

alpha-beta pruning (tsz. alpha-beta prunings)

  1. (informatika) alfa-béta vágás

A mesterséges intelligenciában, különösen a játékprogramozásban (mint sakk, dáma, tic-tac-toe), gyakran használunk játékfákat a lehetséges lépések modellezésére. Ezekben a fákban minden egyes csomópont egy játékállást, minden él egy lépést jelent. A klasszikus Minimax algoritmus segítségével egy gép képes „végiggondolni” az összes lehetséges lépést és ellenlépést, majd ez alapján dönteni a legjobb akcióról.

A probléma? A játékfák gyakran exponenciálisan nagyok. Például sakkban a lehetséges játékállások száma 10^40 körül van. Ilyen méretű fát lehetetlen teljes egészében bejárni. Az Alpha–Beta metszés (pruning) a Minimax algoritmus optimalizálása: lehetővé teszi a gép számára, hogy bizonyos ágakat kihagyjon anélkül, hogy befolyásolná a végső döntést.


A Minimax algoritmus röviden

A Minimax algoritmus feltételezi, hogy két játékos (Max és Min) váltakozva lép. A Max játékos célja a lehető legnagyobb pontszám elérése, míg a Min játékos célja a Max pontszámának minimalizálása. Az algoritmus rekurzívan értékeli a fa leveleitől felfelé haladva a csomópontokat, kiválasztva minden szinten a számára optimális értéket:

  • Max lépéseinél: a maximális értéket választja a gyermekek közül.
  • Min lépéseinél: a minimális értéket választja.


Alpha–Beta pruning – a fogalom lényege

Az Alpha–Beta metszés a Minimax során történő optimalizálás, amely korai megszakításokkal csökkenti a felesleges faágak vizsgálatát. A cél: nem kell kiszámolni a teljes fát, ha már biztosak vagyunk abban, hogy egy ágat nem fog választani az ellenfél.

Két változó:

  • α (alpha): az eddigi legjobb érték, amit a Max játékos biztosítani tud.
  • β (beta): az eddigi legrosszabb érték, amit a Min játékos elfogad.

A metszés akkor történik meg, ha:

  • Egy Max csomópontban α ≥ β → Min nem fogja ezt az ágat választani.
  • Egy Min csomópontban β ≤ α → Max nem fogja ezt az ágat választani.


Példa:

Képzeljük el az alábbi játékszituációt, egy egyszerű fával:

               MAX
             /     \
           MIN     MIN
         /  \      /   \
       3    5    6     9

A Minimax szerint:

  • Az első MIN csomópontban (3,5) a minimális: 3
  • A második MIN csomópontban (6,9) a minimális: 6
  • MAX ezek közül a maximálisat választja: max(3,6) = 6

Most nézzük, hogyan metszene az Alpha–Beta:

  1. MAX indul, α = –∞, β = +∞
  2. Belép az első MIN ágba
  3. MIN belép a 3-hoz → visszajön 3 → MIN frissíti β = 3
  4. MIN most a 5-öt nézné, de MAX még nem tud jobbat, tehát folytat
  5. MIN = min(3,5) = 3 → MAX α = 3

Most belépünk a második MIN ágba:

  1. MIN belép a 6-hoz, látja: 6 > α (3), de mivel Min játékos vagyunk, és 6 már rosszabb, mint amit eddig biztosítani tudott a másik ágon keresztül (3), a 9-es ágat nem kell megnézni, mert úgysem lesz jobb → metszés történik.


A metszés hatékonysága

Ha a csomópontokat ideálisan rendezzük (a legjobbakat vizsgáljuk meg először), akkor az Alpha–Beta pruning a keresési időt O(b^(d/2))-re csökkenti, ahol:

  • b: az elágazási tényező (hány gyermek van egy csomópontnak),
  • d: a fa mélysége.

Ez nagy előrelépés a sima Minimax O(b^d) bonyolultságához képest. Ezért az Alpha–Beta pruning használata nélkülözhetetlen minden gyakorlati játék-AI esetén.


Pszeudokód

function alphabeta(node, depth, α, β, maximizingPlayer):
    if depth == 0 or node is terminal:
        return evaluate(node)

    if maximizingPlayer:
        value := –∞
        for each child of node:
            value := max(value, alphabeta(child, depth – 1, α, β, FALSE))
            α := max(α, value)
            if α ≥ β:
                break    // β-metszés
        return value
    else:
        value := +∞
        for each child of node:
            value := min(value, alphabeta(child, depth – 1, α, β, TRUE))
            β := min(β, value)
            if β ≤ α:
                break    // α-metszés
        return value

Használati területek

  • Sakk, dáma, go: minden olyan játék, ahol két játékos, tökéletes információval és váltakozó lépésekkel játszik.
  • Mesterséges intelligencia: intelligens döntéshozatalhoz szűkített keresés.
  • Robotika: döntés optimalizálás valós idejű környezetben.
  • Gazdasági szimulációk: versengő felek viselkedésének modellezése.


Korlátai

  • Nem alkalmazható jól nem determinisztikus játékokban (pl. kockadobás).
  • Nem tökéletesen működik rejtett információs játékokban (pl. póker).
  • A metszés hatékonysága érzékeny a vizsgálati sorrendre – ha rossz sorrendben nézzük a gyermekeket, kevés metszés történik.


Továbbfejlesztések

  • Iterative Deepening: mélységi keresés fokozatosan mélyítve, időhatáros.
  • Transposition Table: már kiszámolt állások eltárolása, így nem számítjuk újra.
  • Move Ordering Heurisztika: valószínűleg legjobb lépések előre hozása a sorrendben (pl. előző lépés szerinti legjobb lépés először).
  • Null Window / Aspiration Search: kis ablakú α–β keresés, gyorsabb metszésre optimalizálva.


Összegzés

Az Alpha–Beta metszés a mesterséges intelligencia és játékprogramozás egyik legfontosabb technikája. A Minimax algoritmus optimalizálása révén lehetővé teszi, hogy sokkal mélyebb kereséseket hajtsunk végre ugyanannyi erőforrással. Bár maga az algoritmus egyszerű, hatékonysága jelentősen függ az implementáció finomhangolásától és a játékfa sajátosságaitól. Mégis, a legtöbb professzionális sakkmotor és stratégiai játékalgoritmus szerves része, és évtizedek óta nélkülözhetetlen eszköze az AI-kutatásoknak.

További információk

A lap eredeti címe: „https://hu.wiktionary.org/w/index.php?title=alpha-beta_pruning&oldid=3502932”