Komolyan mondom ha nem lennék, engem ki kéne találni. Egy rohadt fél napot görnyedtem a játékelméletből ismert minimax algoritmus fölött és egyszerűen kénytelen voltam felfogni, hogy mi a hóhért akar ez tőlem… A dolog rendkívül egyszerű, számomra értelmezhetetlen volt a kapott pszeudo kód, ami pontosan így fest:
  1. function Minimax-Lépés(<A, kezdő, V, O>, állapot, korlát, h)
  2.     max <- -Inf
  3.     operátor <- NIL
  4.     for all o in O do
  5.         if ELŐFELTÉTEL(állapot, o) then
  6.             új-állapot <- ALKALMAZ(állapot, o)
  7.             v <- Minimax-Érték(<A, kezdő, V, O>, új-állapot, korlát – 1, h)
  8.             if v > max then
  9.                 max <- v
  10.                 operátor <- o
  11.             end if
  12.         end if
  13.     end for
  14.     return operátor
  15. end function

Hát ezzel önmagában semmi probléma nincs, az algoritmus lényege ugyanis az, hogy egy kétszemélyes véges determinisztikus stratégiai játékban egy játékos számára "elég jó" lépést ajánljon. Szóval visszaad egy operátort ami nem más mint egy lépés egy adott állásban, okké semmi gáz. És akkor jött az amin elszakadt minden cérnám és az istennek sem fért bele a fejembe, hogy mi a szent túrót szórakozik velem:

  1. function Minimax-Érték(<A, kezdő, V, OI>, állapot, mélység, h)
  2.     if állapot in V or mélység = 0 then
  3.         return h(állapot)
  4.     else if JÁTÉKOS[állapot] = J then
  5.         max <- -Inf
  6.         for all o in O do
  7.             if ELŐFELTÉTEL(állapot, o) then
  8.                 új-állapot <- ALKALMAZ(állapot, o)
  9.                 v <- Minimax-Érték(<A, kezdő, V, O>, új-állapot, mélység – 1, h)
  10.                 if v > max then
  11.                     max <- v
  12.                 end if
  13.             end if
  14.         end for
  15.         return max
  16.     else
  17.         min <- Inf
  18.         for all o in O do
  19.             if ELŐFELTÉTEL(állapot, o) then
  20.                 új-állapot <- ALKALMAZ(állapot, o)
  21.                 v <- Minimax-Érték(<A, kezdő, V, O>, új-állapot, mélység – 1, h)
  22.                 if v < min then
  23.                     min <- v
  24.                 end if
  25.             end if
  26.         end for
  27.         return min
  28.     end if
  29. end function

Na és, hogy ennek mit kellene csinálni? Hát nekem a kapott pszeudokódból minden kijön csak az nem aminek kéne. A dolog rendkívül egyszerű de az algoritmusa az számomra egy nulla. Szóval az algoritmus lényege a következő. Adott egy valamilyen játékgráf amelynek a csúcsait ki kell értékelni egy heurisztikus függvénnyel ami kb úgy működik, hogy:

  • Minél jobb az adott állás a pártfogolt játékos számára annál nagyobb pozitív értéket kap.
  • Minél jobb az adott állás az ellenfél számára annál kisebb negatív értéket fog kapni.
  • Döntetlen esetben meg egy nullához közeli értéket.

Szóval a heurisztika egy f: A -> R leképezés lenne, amivel totál semmi bajom nincs sőt nagyon jó ötletnek tartom. Az algoritmusnak meg úgy kéne működni, hogy először kiértékeli a játékgráf felépített részében a levélelemek heurisztikáit majd pedig halad tovább fölfelé a gyökér felé szintenként. Páros szinten az a játékos helyezkedik el amelynek lépést akarunk ajánlani páratlan szinten meg aki ellenünk van. A nem levél elemek heurisztikáinak kiértékelése meg szintén tök egyszerű. Egy tetszőleges n csúcs súlyának meghatározása páros szinten úgy zajlik, hogy a leszármazottai heurisztikáinak a maximumát vesszük, míg páratlan szinten pont a minimumát. Így szóba jöhet ugyan egy rekurzív függvény de ne úgy adjuk már meg környörgöm, hogy a rekurzív függvényhívás után nézzük meg, hogy na vajon az új érték milyen mer az életben rá nem kerül a vezérlés… Szóval ez betette nálam az ajtót elég rendesen, mire sikerült kibogarászni, hogy ki hol merre az nem 2 órámba telt. Vicces, hogy mikor totál feladtam, hogy ez egy marhaság akkor jöttem rá, hogy én jól gondolom de a kapott pszeudo már nem igazán. A rekurzív függvény hívás utáni if ágakkal szerette volna az oktató a maximumot illetve a minimumot keresni. Hát ez nem jött össze neki ráadásul jól megkeresrítette az életem.