minimax

Lásd még: MiniMax

Angol

Főnév

minimax (tsz. minimaxes)

(informatika) minimax algorithm : minimax algoritmus

Minimax egy klasszikus döntési algoritmus kétjátékos, zéróösszegű játékokhoz, ahol az egyik játékos minimalizálni, a másik pedig maximalizálni próbálja a saját nyereségét. A minimax elv alapján egy játékos feltételezi, hogy az ellenfele a lehető legjobb lépést választja, és ennek tudatában próbálja optimalizálni a saját stratégiáját.

🧠 1. Mi a Minimax algoritmus?

A minimax algoritmus játékelméleti módszer, amely:

Teljesen ismert szabályú, véges, kétjátékos játékokban használható.
A döntéshozatal során minden lehetséges játékmenetet figyelembe vesz.
Feltételezi, hogy az ellenfél is tökéletesen játszik.

📐 2. Alapelve

Egy fa formájában ábrázoljuk a lehetséges játékállásokat (játékfa).
A levélcsomópontok értékei (utility értékek) azt mutatják, milyen eredményhez vezetne az adott lépés.
A játékos választási sorrendjétől függően:
- Maximáló játékos (Max) a legnagyobb értéket választja.
- Minimalizáló játékos (Min) a legkisebb értéket választja.

🌳 3. Példa játékfa

        MAX
       /   \
     MIN   MIN
    / \     / \
   3   5   2   9

A minimális játékos a saját ágain: min(3,5) = 3, min(2,9) = 2
A maximális játékos ezek közül: max(3,2) = 3 → tehát a MAX játékos a bal ágat választja.

⚙️ 4. Algoritmus (pszeudokód)

def minimax(node, depth, maximizingPlayer):
    if depth == 0 or node is leaf:
        return value of node

    if maximizingPlayer:
        maxEval = -infinity
        for child in node.children:
            eval = minimax(child, depth-1, False)
            maxEval = max(maxEval, eval)
        return maxEval
    else:
        minEval = +infinity
        for child in node.children:
            eval = minimax(child, depth-1, True)
            minEval = min(minEval, eval)
        return minEval

🎮 5. Alkalmazások

Terület	Példák
Klasszikus játékok	Sakk, dáma, amőba (tic-tac-toe)
AI játékfejlesztés	Ellenfél-szimuláció
Stratégiai döntéshozatal	Kockázatelemzés versengő helyzetekben

🚀 6. Bővítések

Módszer	Cél
Alpha–Beta pruning	Csökkenti a játékfa bejárását anélkül, hogy az eredményt befolyásolná
Iterative deepening	Fokozatos mélyítés a gyors válasz érdekében
Heurisztikus értékelés	Nem szükséges a teljes játékfa kiértékelése (pl. sakkban bábuk értéke)

⏱️ 7. Idő- és helyigény

Időkomplexitás: ${\textstyle O(b^{d})}$ ${\textstyle O(b^{d})}$
- ${\textstyle b}$ : a lépések száma (ágak száma minden csomópontban)
- ${\textstyle d}$ : a mélység (mennyi lépésre előre számolunk)
Térkomplexitás: ${\textstyle O(b\cdot d)}$ (mélységi keresés esetén)

✅ 8. Előnyök

Garantáltan optimális (ha az ellenfél is optimálisan játszik)
Egyszerű implementálni
Általánosan alkalmazható bármely kétszemélyes zéróösszegű játékra

❌ 9. Hátrányok

Kombinatorikus robbanás: nagy mélységnél számításigényes
Tökéletes információt feltételez
Nem működik jól nem determinisztikus vagy többjátékos helyzetekben (speciális módosítások szükségesek)

🧾 10. Összefoglalás

Fogalom	Leírás
Minimax	Olyan algoritmus, amely feltételezi, hogy az ellenfél a lehető legjobban játszik
Alkalmazás	Kétszemélyes, zéróösszegű játékok
Játékosok szerepe	Max – nyerni próbál, Min – veszteséget csökkent
Kimenet	Optimális lépés az adott mélységig
Bővíthető	Alpha–Beta pruning, értékelőfüggvényekkel

További információk

minimax - Szótár.net (en-hu)
minimax - Sztaki (en-hu)
minimax - Merriam–Webster
minimax - Cambridge
minimax - WordNet
minimax - Яндекс (en-ru)
minimax - Google (en-hu)
minimax - Wikidata
minimax - Wikipédia (angol)