Minimax algoritmi (myös nimitystä MinMax algoritmi ) on algoritmi, joka koskee peliteorian kahden pelaajan nolla-summa (ja täysi-informaatio) pelien minimoida enimmäistappio (eli sanoa pahimmassa tapauksessa). Suurelle peliperheelle von Neumannin minimx-lause varmistaa tällaisen algoritmin olemassaolon, vaikka käytännössä sen löytäminen ei ole usein helppoa. Hex- peli on esimerkki siitä, että tällaisen algoritmin olemassaolo todetaan ja osoittaa, että ensimmäinen pelaaja voi aina voittaa ilman, että tätä strategiaa tunnetaan.
Se saa tietokoneen käymään läpi kaikki mahdollisuudet rajalliseen määrään siirtoja ja antamaan heille arvon, joka ottaa huomioon pelaajan ja hänen vastustajansa edut. Paras valinta on silloin valinta, joka minimoi pelaajan tappiot olettaen, että vastustaja pyrkii päinvastoin maksimoimaan ne (peli on nolla).
On olemassa erilaisia algoritmeja perustuvat MinMax optimoida etsiä parhaan tilanteen rajoittamalla solmujen vieraillut pelin puussa , tunnetuin on alfa-beeta karsimisesta . Käytännössä puu on usein liian suuri tutkittavaksi (kuten shakki- tai mennäpelissä ). Sitten tutkitaan vain murto-osa puusta.
Hyvin suurten puiden kohdalla tekoälyä (asiantuntijajärjestelmä, arviointi oppimalla esimerkeistä jne.) Voidaan käyttää tiettyjen oksien karsimiseen niiden hyödyllisyyden arvioinnin perusteella. Tätä käytetään esimerkiksi go-kontekstissa.
Minimumx-algoritmi vierailee pelipuussa jäljittäen juurelle arvon (nimeltään "pelin arvo"), joka lasketaan rekursiivisesti seuraavasti:
Yllä olevassa kaaviossa harmaat solmut edustavat pelaajan solmuja ja siniset vastakkaisia solmuja. Solmun A arvon määrittämiseksi valitsemme solmujoukon B maksimiarvon (A on pelaajasolmu). Siksi on tarpeen määrittää niiden solmujen B arvot, jotka kukin saavat lapsiinsa tallennetun vähimmäisarvon (solmut B ovat vastakkaisia). Solmut C ovat lehtiä, joten niiden arvo voidaan laskea arviointitoiminnolla.
Solmu A ottaa sen vuoksi arvon 5. Pelaajan on siis pelattava siirto tuoden se kohtaan B2. Puuta tarkkailemalla ymmärrämme, että algoritmi katsoo, että vastustaja pelaa parhaalla mahdollisella tavalla: hän ottaa minimin. Ilman tätä predikaatti, olisimme valita solmu C 1 , joka tarjoaa suurimman vahvistuksen ja seuraava siirto valitun johtaisi B1. Mutta sitten otamme riskin, että vastustaja pelaa C3: ta, joka tarjoaa vain 3: n voiton.
Käytännössä sijainnin P teoreettista arvoa ei yleensä voida laskea. Tämän seurauksena arvostusfunktiota sovelletaan muihin kuin terminaalisiin positioihin. Katsotaan, että mitä pidemmälle arviointitoimintoa käytetään juuresta, sitä parempi on laskennan tulos. Toisin sanoen tarkastelemalla useampia peräkkäisiä aivohalvauksia oletamme saavan paremman likiarvon teoreettisesta arvosta ja siten paremman liikkeen valinnan.
Jos f ( p ): n ottama arvojoukko on symmetrinen nollan suhteen, funktio g ( p ) voidaan määrittää siten, että:
Joten määritämme negamaxin tästä uudesta toiminnosta:
Samasta esimerkistä kuin Minmax-algoritmille, tässä on tuloksena oleva puu:
Rajoitetun syvyyden minimx-algoritmin pseudokoodi on esitetty alla:
function minimax(node, depth, maximizingPlayer) is if depth = 0 or node is a terminal node then return the heuristic value of node if maximizingPlayer then value := −∞ for each child of node do value := max(value, minimax(child, depth − 1, FALSE)) return value else (* minimizing player *) value := +∞ for each child of node do value := min(value, minimax(child, depth − 1, TRUE)) return value (* Initial call *) minimax(origin, depth, TRUE)Valinnaisessa tilastoteoriassa meillä on estimaattori δ, jonka tavoitteena on löytää parametri θ ∈ Θ . Tässä yhteydessä θ 'minimx', jos:
Tämä algoritmi voidaan optimoida toteuttamalla tekniikka, joka tunnetaan nimellä alfa-beeta-karsiminen . Alfa-beeta-algoritmi nopeuttaa minimx-hakutoimintoa poistamalla tapaukset, joita ei käytetä. Tässä menetelmässä käytetään sitä, että kaikki muut puun tasot maksimoidaan ja kaikki muut tasot minimoidaan.