Hasonlóan a minimaxhoz, a várhatóminimax esetén is alkalmazhatjuk a nyilvánvaló közelítést, vagyis valamilyen ponton levághatjuk a keresést, és a levelekre egy kiértékelő függvényt alkalmazhatunk. Úgy gondolhatnánk, hogy egy olyan játék esetén, mint az ostábla, a kiértékelő függvény elvben semmiben sem tér el a sakknál alkalmazott kiértékelő függvényektől, melyeknek most is magasabb pontot kell adniuk a jobb állásokra. Valójában azonban a véletlen csomópontok jelenléte azt jelenti, hogy sokkal körültekintőbbnek kell lennünk abban a tekintetben, hogy a kiértékelő függvény értékei mit jelentenek. A 6.12. ábra mutatja a problémát: ha a kiértékelő függvény a levelekhez az [1, 2, 3, 4] értékeket rendeli hozzá, az A₁ lépés lesz a legjobb, az [1, 20, 30, 400] értékekkel az A₂ lesz a legjobb. Ebből adódóan egy program teljesen másként viselkedik, ha átskálázzuk a kiértékelő függvény értékeket! Kiderül, hogy ha el akarjuk kerülni ezt az érzékenységet, akkor a kiértékelő függvény az egy adott állásból való győzelem valószínűségének (vagy általánosabban az állás várható hasznosságának) csak egy pozitív lineáris transzformációja lehet. Ez a bizonytalanságot is tartalmazó helyzetek fontos és általános tulajdonsága. A 16. fejezetben tovább foglalkozunk ezzel a kérdéssel.

Ha a program előre tudná a játék folyamán a későbbiekben előforduló összes kockadobás eredményét, akkor egy kockadobást is tartalmazó játék megoldása ugyanolyan lenne, mint egy kockadobást nem tartalmazó játéké, amit a minimax O(b^m) idő alatt tesz meg. Mivel a várhatóminimax figyelembe veszi az összes lehetséges kockadobás-sorozat eredményét is, annak időigénye O(b^mn^m) lesz, ahol n a különböző dobások számát jelöli.

6.12. ábra - A levélértékeken végrehajtott sorrendőrző transzformáció megváltoztatja a legjobb lépést

Még ha a fa mélységkorlátja egy kis értékű d is, a minimaxhoz képesti többletköltség miatt irreális túl messzire előrenézni a véletlen játékok többségénél. Ostáblánál n értéke 21, b pedig általában 20 körüli értéket vesz fel, de bizonyos helyzetekben akár 4000 is lehet, a dupla kockadobásoknál. Valószínűleg csak három lépésváltást tudunk kezelni.

A problémáról másféleképp is gondolkodhatunk: az alfa-béta algoritmus előnye, hogy figyelmen kívül hagyja azokat a későbbi fejleményeket, amelyek a legjobb játék során egyszerűen nem következnek be. Így a valószínű előfordulásokra koncentrál. A kockát használó játékok esetén nem léteznek valószínű lépéssorozatok, mivel adott lépések megtételéhez először a kockának kell a megfelelő oldalára esnie, hogy ezek a lépések egyáltalán megengedhetők legyenek. Ez egy általános probléma minden olyan esetben, amikor a bizonytalanság is képbe kerül: a lehetőségek óriási mértékben megsokszorozódnak, és értelmetlenné válik részletes cselekvési terveket kidolgozni, mert a világ valószínűleg nem ezek szerint fog viselkedni.

Kétségtelen, hogy az olvasónak már eszébe jutott, hogy valami alfa-béta nyeséshez hasonló dolgot a véletlen csomópontokat tartalmazó játékfákra is alkalmazni lehetne. Kiderül, hogy ez valóban lehetséges. A MAX és a MIN csomópontok elemzése változatlan, de egy kis leleményességgel a véletlen csomópontokat is nyeshetjük. Tekintsük a 6.11. ábra C véletlen csomópontját, és nézzük meg, mi történik az értékével, amikor a gyermekeit vizsgáljuk és kiértékeljük. Kérdés, hogy lehetséges-e C értékére egy felső korlátot találni, még mielőtt az összes gyermekét megvizsgálnánk? (Idézzük vissza, hogy az alfa-béta nyesésnek pontosan erre van szüksége ahhoz, hogy egy csomópontot és az abból kiinduló részfát lenyeshesse.) Ez első pillantásra lehetetlennek tűnhet, mivel a C értéke a gyermekei értékének az átlaga, és amíg nem láttuk az összes kockadobás eredményét, addig ez az átlag akármi is lehet, mivel a meg nem vizsgált gyermekek akármilyen értéket felvehetnek. Ha azonban a hasznosságfüggvény lehetséges értékeit korlátok közé szorítjuk, akkor korlátokat kaphatunk az átlagra is. Például ha azt mondjuk, hogy a hasznosságértékek +3 és –3 között lehetnek, akkor a levélcsomópontok értékei már korlátosak, és a véletlen csomópont értékére az összes gyermekének megvizsgálása nélkül is adhatunk felső korlátot.

A kártyajátékok sok szempontból érdekesek, nem csupán a szerencsejáték-jellegük miatt. A játékok óriási választékából azokra fogunk összpontosítani, ahol a kártyákat a játék elején véletlen módon osztják szét, és ahol mindegyik játékos által kapott leosztás más játékosok számára nem megfigyelhető. Ilyen játék a bridzs, a whistjáték, a hearts^[57] és a póker néhány formája.

Az első pillantásra úgy tűnhet, hogy a kártyajátékok pont olyanak, mint a kockadobásos játékok. A kártyákat véletlenül osztjuk szét, és ez meghatározza a játékosok lehetséges lépéseit. Itt azonban az összes kocka a legelején gördül le! Ezt a hasonlatot próbáljuk továbbvinni. Ki fog derülni, hogy ez a gyakorlatban igen hasznos lesz. Mellesleg hibás is, igen érdekes okok miatt.

Képzeljük el, hogy két játékos, MAX és MIN, négykártyás kétkezes bridzset gyakorol, ahol minden kézleosztás látható. A leosztások az alábbiak, és MAX hív elsőnek:

MAX: ♥ 6 ♦ 6 ♣ 9 8 MIN: ♥ 4 ♠ 2 ♣ 10 5

Tegyük fel, hogy MAX ♣ 9-et játszik. MIN-nek szint kell játszania, tehát ♣ 10-et vagy ♣ 5-öt. MIN ♣ 10-et játszik és elviszi az ütést. Most MIN következik és ♠ 2-vel indul. MAX-nak nincs pikkje (és így az ütést elvinni nem tudja), következésképpen valamelyik kártyáját le kell játszania. Nyilvánvaló választás a ♦ 6, mert a két másik győztes kártya. Most függetlenül attól, hogy MIN mivel indul a következő ütésben, MAX az utolsó két ütést elviszi, és a játék két-két ütés szinten döntetlen lesz. Könnyű megmutatni a minimax megfelelő változatával (lásd 6.12. feladat), hogy MAX ♣ 9-es indulása valójában egy optimális választás.

Módosítsuk most MIN leosztását, ♥ 4-et ♦ 4-re cserélve:

MAX: ♥ 6 ♦ 6 ♣ 9 8 MIN: ♦ 4 ♠ 2 ♣ 10 5

A két eset tökéletesen szimmetrikus: a játék lefolyása azonos lesz, kivéve, hogy a második ütésnél MAX a ♥ 6-ot fogja megjátszani. A játék ugyanúgy döntetlen lesz két-két ütéssel, és a ♣ 9 optimális döntés lesz most is.

Egyelőre minden jónak tűnik. Most rejtsük el MIN kártyáinak egyikét: MAX tudja, hogy MIN-nek vagy az egyik (♥ 4-gyel), vagy a másik (♦ 4-gyel) leosztása van, de fogalma sincs melyik. MAX a következőképpen érvel:

A ♣ 9-es indulás optimális választás MIN első leosztásával szemben és hasonlóan a második leosztásával szemben is, így most is optimálisnak kell lennie, mert tudomásom szerint MIN-nél a két leosztás valamelyike van.

Amit MAX használ, azt általánosságban a „jövőbe látás szerinti átlagolásnak” nevezhetnénk. Az ötlet a cselekvés értékelése nem látott kártyák mellett oly módon, hogy először kiszámítunk minimax értékeket minden lehetséges leosztás esetére, majd várható értéket számítunk a leosztásokra nézve, azok valószínűségét felhasználva.

Ha azt gondolja, hogy ez egy értelmes stratégia (vagy ha nincs véleménye, mert nem érti a bridzset), tekintse a következő történetet:

Nyilvánvaló, nem buta döntés, ha az első két napon a B utat választjuk. Nincs olyan épelméjű személy azonban, aki a harmadik napon is maradna B-nél. Mégis pontosan ez az, amit a jövőbe látás szerinti átlagolás sugall. A B út az 1. nap és a 2. nap helyzetekben optimális, következésképpen optimális a 3. nap szituációban is, hiszen az első két eset egyike fog előfordulni. Térjünk vissza a kártyajátékunkhoz: miután MAX ♣ 9-et hív, MIN ♣ 10-zel győz. MIN ♠ 2-vel indul, mint korábban, és most MAX ott van az elágazásnál bármiféle eligazítás nélkül. Ha MAX a ♥ 6-ot játszotta meg, és MIN-nek van még ♥ 4-e, ♥ 4 lesz a győztes, és MAX a játékot elveszíti. Hasonlóan, ha MAX a ♦ 6-ot játszotta meg, és MIN-nek van még ♦ 4-e, MAX szintén veszteni fog. A ♣ 9 első ízben való hívása tehát olyan helyzethez vezet, ahol MAX-nak 50%-os esélye van a vesztésre (sokkal jobb lenne, ha a ♥ 6-ot vagy a ♦ 6-ot hívná elsőnek, döntetlent biztosítva).

A leszűrendő lecke az, hogy amikor hiányos az információ, meg kell fontolni, hogy milyen információval fogunk rendelkezni a játék minden pillanatában. MAX algoritmusával az a probléma, hogy feltételezi, hogy minden lehetséges leosztásnál a játék úgy folytatódik, mintha minden kártya látható lenne. Ahogy a példánk mutatja, ez olyan cselekvésre készteti MAX-ot, mintha minden jövőbeli bizonytalanság feloldódna, ha eljön az ideje. MAX algoritmusa sem fog soha információgyűjtéshez folyamodni (vagy a partner informálásához), mert egy-egy leosztáson belül erre nincs szüksége. Az olyan játékoknál, mint a bridzs, gyakran értelmes dolog olyan kártyával indulni, amely segíti kideríteni az ellenség leosztását, vagy a partnerünket a saját leosztásunkról informálja. Ilyen viselkedést automatikusan generálhatunk a nem tökéletes információjú játékokra kifejlesztett optimális algoritmussal. Az ilyen algoritmus nem a világállapotok terében (kártyaleosztások), hanem a hiedelmi állapotok terében (belief states) (hiedelmek, hogy kinek milyen kártyája van, milyen valószínűséggel) keres. Az algoritmust a 17. fejezetben tudjuk majd megfelelően elmagyarázni, miután felépítettük a szükséges valószínűségi apparátust. Abban a fejezetben azzal a nagyon fontos szemponttal is fogunk foglalkozni, hogy a nem tökéletes információjú játékokban az a legjobb, ha minél kevesebb információt adunk ki az ellenségnek, és ennek legjobb módszere, ha nem megjósolható módon cselekszünk. Ez az oka annak, hogy az étteremellenőrök véletlen módon választják meg az ellenőrzések időpontját.