minimax algorithm

minimax algorithm (tsz. minimax algorithms)

1. (informatika) 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.

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.

• 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.

        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.

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

• Időkomplexitás: ${\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)

• 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

• 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)

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