Teorie her je rozsáhlou oblastí matematiky s řadou hlubokých výsledků. Zahrnuje složité hry s mnoha paralelně konajícími hráči, s komplikovanými vzájemnými vazbami zisků/ztrát a s řadou neznámých faktorů. Omezíme se pro začátek na jednoduché hry s dvěma hráči, kteří se střídají. Rovněž začneme se zjednodušujícím předpokladem, že stav hry je v každém okamžiku znám všem hráčům (jako šachy, na rozdíl od většiny karetních her). Konečně půjde o hry s nulovým součtem, tedy výhra jednoho znamená porážku druhého. Hráč označíme jako MAX a MIN, koncové stavy ohodnotíme např. +1 (výhra MAX), -1 (výhra MIN), 0 (remíza). 

Algoritmus Minimax:

Jde v podstatě o prohledávání stavového prostoru do hloubky s omezením hloubky. Klíčový je způsob ohodnocení jednotlivých uzlů. Listy stromu jsou ohodnoceny, jak bylo popsáno výše. Každý vnitřní uzel je ohodnocen následovně:  

• Pokud je na tahu MAX, bere se maximum z hodnoty všech přímých potomků.
• Pokud je na tahu MIN, bere se minimum  z hodnoty všech přímých potomků.

Východiskem je úvaha, že protihráč vybere pro něj nejlepší možný tah. I když to neudělá, popsaný postup nalezne vyhrávající strategii, pokud existuje.

Alfa-beta ořezávání

Slabinou algoritmu Minimax je fakt, že stavový prostor je obrovský, s rychlým větvením možných tahů, takže je algoritmus pomalý. Jak se dá zefektivnit? Princip minimaxu umožňuje některé větve prohledávacího stromu ignorovat, jakmile se ukáže, že nemůžou ovlivnit ohodnocení aktuálního uzlu.

Obr. 1. Příklad alfa-beta ořezávání. Zdroj: Wikimedia Commons, Jez9999 at the English language Wikipedia.

Na obr. 1 je příklad stromu prohledávání stavového prostoru. Po prohledání levého a prostředního podstromu víme, že hodnota kořene bude nejméně 6. Nyní prohledáváme pravý podstrom a narazíme v poduzlu na hodnotu 5. Jelikož poduzel má úroveň MIN, víme, že další prohledávání pravého šedého podstromu tuto hodnotu jedině sníží, ale určitě nezvýší. Tím pádem neovlivní hodnotu 6 v kořeni úrovně MAX. Proto pravý šedý podstrom odřízneme.

Heuristické ohodnocování uzlů

I s využitím alfa-beta ořezávání se dá většinou stavový prostor v rozumném čase prohledat jen do malé hloubky a ne až k listům, jak to vyžaduje algoritmus Minimax. Co teď? Je nutno prohledávání zastavit na určité hloubce a ohodnotit nejhlubší dosažené uzly nějakou heuristikou. Existuje řada možností, například:

• odhad podílu vyhrávajících a prohrávajících stavů v podstromu daného uzlu;
  
• "materiální" ohodnocení, např. hodnotou figur v šachách anebo jednotlivých karet (a jejich kombinací) v ruce

Vesměs ale je taková heuristika závislá na konkrétní hře a její kvalita je zásadní pro herní algoritmus. Častá strategie je vybrat slibné nebo naopak nejisté vrcholy, které mohou nejspíše ovlivnit výsledek, a ty pak prohledat do větší hloubky.