(adversary search)

Intellektitehnika uurib tüüpiliselt 2 isiku mänge, milles vastased teevad kordamööda käike ja mõlemal on täpne informatsioon mängu kohta (trips-traps-trull, kabe, male, Go, Othello).
 
 

Minimax 1

Hindamaks tippu n mängupuul, tee järgmist.

1. Konstrueeri puu alates tipust n kuni terminaalsete tippudeni.

2. Omista väärtused terminaalsetele tippudele (1 - maksimiseerija võit, -1 - minimiseerija võit).

3. Vali veel hindamata tipp, mille kõigil vahetutel järglastel on juba väärtused. Kui hindamata tippe ei ole, siis tagasta tipule n omistatud väärtus.

4. Kui valitud tipus on käigul minimiseerija, siis võta tipu väärtuseks minimaalne tema vahetute järglaste väärtustest. Kui valitud tipus on käigul maksimiseerija, siis võta tipu väärtuseks maksimaalne tema vahetute järglaste väärtustest. Mine 3.
Mälu- ja ajavajadus eksponentsiaalne.
 
 

Minimax 2

Algul ehitatakse valmis (sügavuti) üks puu haru kuni lõpptippudeni, omistades vahepealsetele tippudele väärtusi -oo või +oo. Siis hakatakse lõpptippudest tagasi ülespoole tõusma ja vahepealsete tippude väärtusi muutma.

Hindamaks tippu n mängupuul, tee järgmist.

1. Olgu L={n} - läbimata tippude nimestik.

2. Olgu x esimene tipp nimestikus L. Kui x=n ja talle on omistatud väärtus, siis tagasta see väärtus.

3. Kui x väärtus on v_x, siis olgu p tipu x vahetu eellane (parent) ning v_p tema jooksev väärtus. Kui p on minimiseerija tipp, siis võta v_p=min(v_p,v_x). Kui p on maksimiseerija tipp, siis võta v_p=max(v_p,v_x). Eemalda x nimestikust L ja mine 2.

4. Kui tipule x pole omistatud väärtust ja ta on terminaalne tipp, siis omista talle väärtus 1 (kui see on maksimiseerija võit), -1 (kui see on minimiseerija võit) või 0 (kui see on viik). Jäta x nimestikku L (et käsitleda tema vahetut eellast) ja min e 2.

5. Kui tipule x pole omistatud väärtust ja ta pole lõpptipp, siis võta v_x=-oo (kui x on maksimiseerija tipp) või v_x=+oo (kui x on minimiseerija tipp). Lisa x vahetud järglased nimestiku L algusesse ja mine 2.
Mäluvajadus lineaarne, ajavajadus eksponentsiaalne.
 
 

Minimax 3
Kasutab hinnangufunktsiooni.

Hindamaks tippu n mängupuul, tee järgmist.

1. Olgu L={n}.

2. Olgu x esimene tipp nimestikus L. Kui x=n ja talle on omistatud väärtus, siis tagasta see väärtus.

3. Kui x väärtus on v_x, siis olgu p tipu x vahetu eellane ning v_p tema jooksev väärtus. Kui p on minimiseerija tipp, siis võta v_p=min(v_p,v_x). Kui p on maksimiseerija tipp, siis võta v_p= max(v_p,v_x). Eemalda x nimestikust L ja mine 2.

4. Kui tipule x pole omistatud väärtust ja ta kas on terminaalne tipp või oled otsustanud puud temast allapoole mitte läbida, siis arvuta tema väärtus, kasutades hinnangufunktsiooni, ja mine 2.

5.Vastasel korral võta v_x=-oo (kui x on maksimiseerija tipp) või v_x=oo (kui x on minimiseerija tipp). Lisa x vahetud järglased nimestiku L algusesse ja mine 2.
 
 

a -b -otsing (harvendamine, a-b search, a -b pruning)

Hindamaks tippu n mängupuul, tee järgmist.

1. Olgu L={n}.

2. Olgu x esimene tipp nimestikus L. Kui x=n ja talle on omistatud väärtus, siis tagasta see väärtus.

3. Kui tipule x pole omistatud väärtust, siis mine 5. Kui tipule x on omistatud väärtus v_x, siis olgu p tipu x vahetu eellane. Kõigepealt tuleb määrata, kas tipu p ja tema järglased saab puust kärpida (prune): kui p on minimiseerija tipp, siis olgu a maksimaalne p kõigi vahetute naabrite (sibling) ja p eellasteks olevate minimiseerija tippude kõigi vahetute naabrite jooksvatest väärtustest. (Kui selliseid väärtusi ei ole, siis võta a =-oo .) Kui v_x<=a , siis eemalda tipp p ja kõik tema järglased (descendant) nimestikust L.
Analoogiliselt toimi juhul, kui p on maksimiseerija tipp: olgu b minimaalne p kõigi vahetute naabrite ja p eellasteks olevate maksimiseerija tippude kõigi vahetute naabrite jooksvatest väärtustest. (Kui selliseid väärtusi ei ole, siis võta b =+oo.) Kui v_x>=b , siis eemalda tipp p ja kõik tema järglased nimestikust L.

4. Kui tippu p koos tema järglastega ei saa kärpida, siis olgu v_p tipu p jooksev väärtus. Kui p on minimiseerija tipp, siis võta v_p=min(v_p,v_x). Kui p on maksimiseerija tipp, siis võta v_p=max(v _p,v_x). Eemalda x nimestikust L ja mine 2.

5. Kui tipule x pole omistatud väärtust ja ta on kas terminaalne tipp või sa oled otsustanud puud tipust x allapoole mitte läbida, siis arvuta tipu x väärtus, kasutades hinnangufunktsiooni, ja mine 2.

6. Vastasel korral võta v_x=-oo (kui x on maksimiseerija tipp) või x=+oo (kui x on minimiseerija tipp). Lisa x kõik vahetud järglased nimestiku L algusesse ja mine 2.
 

Harvendamine võib taandada otsinguruumi suurust. Halvimal juhul on võimalik, et kärpimine ebaõnnestub. (Kui järjestame iga tipu vahetud järglased nii, et esimesena kontrollitakse halvimat.) Parimal juhul kontrollitakse parimaid käike esimesena. Vaatame minimiseerija vastust, mis pole talle parim. Et seda saaks kärpida, tuleb meil kontrollida nii palju otsinguruumist, et saaks väita, et minimiseerija jaoks on see käik viga - seega kontrollime selle käigu "eitust", mis näitab, kuidas maksimiseerija saab seda ära kasutada. Et nii toimida, kontrollime ühtainsat maksimiseerija vastust - parimat. Siis kontrollime minimiseerija kõiki valikuid, kuid maksimiseerija parimat vastust igale neist jne. Hargnemistegur minimiseerija jaoks on b (puu eeldatav hargnemistegur), maksimiseerija jaoks aga 1.
Kui vaadata protsessi minimiseerija seisukohast, siis on analüüs analoogiline, üksnes mängijate rollid on vahetatud.
Tippude koguarv, mida tuleb kontrollida sügavusel d, on ligikaudu b^d/2+b^d/2=2b^d/2 (mitte aga b^d).
Seega on harvendamise puhul oluline, kuidas tipu vahetuid alluvaid järjestada. Üks võimalus - kasutada hinnangufunktsiooni.
 

Vt ka NegaScout