Algoritmus Minimax: Ako vás umelá inteligencia prekoná

Takže, tu je dohoda: algoritmus Minimax je stratégia rozhodovania používaná v hrách pre dvoch hráčov, ako je Tic Tac Toe, kde sa hráči striedajú a hra má konečný počet ťahov. Cieľ algoritmu je jednoduchý: maximalizovať svoje skóre a zároveň minimalizovať skóre súpera.

V hre Tic Tac Toe sa hráč s umelou inteligenciou (nazvime ho hráč X) snaží maximalizovať svoje šance na výhru a minimalizovať šance ľudského hráča (hráč O).

Ako funguje Minimax

Algoritmus simuluje všetky možné ťahy z aktuálneho stavu hry a vyhodnocuje výsledok každého ťahu. V podstate prehrá hru až do konca vo svojej hlave a vyberie ťah, ktorý vedie k najlepšiemu možnému výsledku.

Tu je základný prehľad:

1. Rekurzívne preskúmanie: Algoritmus preskúma všetky možné ťahy pre AI aj ľudského hráča a simuluje hru, kým nedosiahne konečný stav (víťazstvo, prehra alebo remíza).
2. Bodovanie konečných stavov: V každom konečnom stave:

• Víťazstvo AI dáva kladné skóre.
• Výhra ľudského hráča znamená záporné skóre.
• Remíza znamená skóre nula.

3. Spätné sledovanie: Algoritmus spätne sleduje simulované ťahy a vyberá ťah s najvyšším skóre pre AI a najnižším skóre pre ľudského hráča.

Algoritmus Minimax v akcii

Pozrime sa, ako je algoritmus Minimax implementovaný v mojej triede AiPlayer.php:

function findBestMove(array $board): ?array
{
$bestScore = -INF;
$bestMove = null;

foreach (range(0, 2) as $row) {
foreach (range(0, 2) as $col) {
if ($board[$row][$col] === null) {
$board[$row][$col] = $this->aiPlayer;
$score = $this->minimax($board, 0, false);
$board[$row][$col] = null;

if ($skóre > $najlepšieSkóre) {
$najlepšieSkóre = $skóre;
$najlepšíŤah = [$riadok, $stĺpec];
}
}
}
}

vráť $najlepšíŤah;
}

funkcia minimax(pole $doska, int $hlbka, bool $isMaximizing): int
{
$víťaz = $this->checkWinner($doska);

if ($winner === $this->aiPlayer) {
return 10 - $depth;
} elseif ($winner === $this->humanPlayer) {
return $depth - 10;
} elseif ($this->isDraw($board)) {
return 0;
}

$bestScore = $isMaximizing ? -INF : INF;

for ($row = 0; $row < 3; $row++) {
for ($col = 0; $col < 3; $col++) {
if ($board[$row][$col] === null) {
$board[$row][$col] = $isMaximizing ? $this->aiPlayer : $this->humanPlayer;
$score = $this->minimax($board, $depth + 1, !$isMaximizing);
$board[$row][$col] = null;

$bestScore = $isMaximizing? max($bestScore, $score) : min($bestScore, $score);
}
}
}

return $bestScore;
}

Rozbor kódu

1. findBestMove(): Táto funkcia prechádza všetky možné ťahy, simuluje každý ťah pomocou algoritmu Minimax a vyberá ťah s najlepším skóre pre AI.
2. minimax(): Táto rekurzívna funkcia vyhodnocuje všetky možné výsledky hry:

• Ak hrá AI (maximalizuje), hľadá najvyššie skóre.
• Ak hrá človek (minimalizuje), hľadá najnižšie skóre.
• Algoritmus používa hĺbku na úpravu skóre, penalizuje dlhšie cesty k víťazstvu a odmeňuje rýchlejšie víťazstvá.

Prečo je Minimax skvelý (a zradný)

Krása Minimaxu spočíva v tom, že hrá optimálne. Nevýhoda? Môže byť výpočtovo náročný, najmä v hrách s veľkým počtom možných ťahov. Našťastie je Tic Tac Toe relatívne malá hra, takže tu funguje perfektne.

Bolo to prvýkrát, čo som implementoval Minimax do hry, a hoci mi to dalo trochu zabrať, konečný výsledok bol veľmi uspokojivý. Umelá inteligencia je ťažko poraziteľná (alebo takmer nemožná) a ak hráte perfektne, buď vás porazí, alebo vynúti remízu – žiadne podvodné víťazstvá!

Tak to je všetko: podrobný pohľad na to, ako funguje umelá inteligencia v mojej hre Tic Tac Toe. Je jednoduchá, efektívna a robí hru oveľa náročnejšou a zábavnejšou!

Dajte mi vedieť, ak by ste chceli vidieť viac detailov alebo ak máte akékoľvek otázky týkajúce sa implementácie. A ak niekedy porazíte umelú inteligenciu, neváhajte sa s tým pochváliť!