12.3. Korlátozás és elágazás (Branch and bound)

A kétszemélyes játékok esetén valamilyen kezdőállapotból kiindulva, a játékosok felváltva lépnek, s véges számú lépés után valamilyen végállapotba jutnak. A játékban nincs szerepe a szerencsének, s játék szabályai határozzák meg, hogy az adott végállapotban ki a győztes. Ilyen játékok például a sakk, a dáma, a go, de nem

Function HUFFMAN(C) 
Input: C ábécé gyakoriságokkal 
Output: egy fa, melyből leolvasható a kódolás 
1  n = C.hossz 
2  Q = C 
3  for i = 1 to n − 1 do 
4     z = PONTOT-LÉTESÍT() 
5     x = KIVESZ-MIN(Q) 
6     y = KIVESZ-MIN(Q) 
7     z.bal = x 
8     z.jobb = y 
9     z.f = x.f + y.f 
10    BESZÚR(Q,z) 
11 endfor 
12 return KIVESZ-MIN(Q)

ilyen a backgammon (ostábla). Ilyen játék Grundy-féle játék is, ahol egy n érméb ől álló oszlopból indulunk. A játékosok felváltva lépnek, s egy lépésben egy oszlopot két eltérő magasságú oszlopra kell bontani. Ha ez nem lehetséges, a soron következő játékos vesztett. Az 1. ábrán látható a 7 érmével kezdődő játék lehetséges kimenetei. Minden egyes szám egy oszlopot jelent, így például a 322 azt jelenti, hogy van egy három, és két kettő magasságú oszlopunk. A két játékost Aval és B-vel jelöljük. Az ábráról látható, hogy az A kezd, s a legbaloldalibb ágon haladva az A nem tud tovább lépni, míg a legjobboldali ágon a B. Mely játékos érheti el, hogy mindenképpen győzzön? Az 12.3.1. ábrán látható fa leveleit aszerint

12.1. ábra - 12.3.1. ábra. Grundy-féle játék fája 7 érme esetén

12.3.1. ábra. Grundy-féle játék fája 7 érme esetén

nevezzük el a 12.3.2. ábrán, hogy az adott ághoz tartozó játék esetén ki a nyerő. A nem levél csúcs esetén, ha csak egy fia van, akkor az apának is ugyanaz lesz az elnevezése. Több fiú esetén, mivel mindkét játékos nyerni akar, ha az A szinten levő apának van A jelű fia, akkor az apa is A jelű lesz, különben B. Hasonlóan, ha a B szinten levő apának minden fia A jelű, akkor az apa is A jelű, egyébként B jelű. Mivel a fa gyökere B jelű, így a kezdő játékos mindenképpen veszít, ha a második játékos okosan játszik. A játékfa felcimkézését elméletileg minden említett játék esetén fel lehetne írni. Így kiderülhetne az is, hogy sakkban a kezdő vagy a másik játékosnak van nagyobb esélye a nyerésre.

12.2. ábra - 12.3.2. ábra. A felcimkézett Grundy-féle játékfa

12.3.2. ábra. A felcimkézett Grundy-féle játékfa

Viszont mivel a szabályok alapján egy 80 szintes fát kellene elkészíteni, amely rendszerint több mint 10 irányban ágazik el minden csúcsban, időtlen időkig eltartana a fa elkészítése és felcímkézése. Épp ezért a sakkprogramok nem készítik el az egész fát, csak annak egy kicsi részét (úgy 8-10 szintet). Ezután minden egyes pozícióhoz hozzárendelnek egy számot, amely arra utal, hogy az állás mennyire jó a program számára. (Nagy pozitív számok a nyerő, a nagy negatív számok s vesztes helyzetekre utalnak.) Egy ilyen részfát mutat a 12.3.3. ábra. A soron következő játékos természesen a legnagyobb értékű álláshoz szeretne eljutni, de az ellenfele ebben akadályozza. A játékos maximalizálni szeretné az adott állásban elérhető értéket, az ellenfél pedig minimalizálni. Ennek megfelelően számolhatjuk ki az apa értékét a fiai értékéből a minimum vagy a maximum függvényt alkalmazva, attól függően, hogy az apa páratlan vagy páros távolságra van-e a gyökértől (12.3.4. ábra). A gyökér értéke és a fiai értéke alapján könnyen megadható, hogy mely lépést kell választani, hogy a legjobbat hozzuk ki az adott állásból.

A minimax módszerrel (minimális-maximális értékek meghatározásánál) minden csúcs esetén ki kell számolni a csúcs értékét. Ez viszont gyakran felesleges. S mivel a játékprogram erőssége a megvizsgált szintek számával arányos, a programozók minden felesleges vizsgálatot szeretnének kiiktatni, hogy ugyanannyi idő alatt több szintet is megvizsgálhasson a programuk. Ezért minden program alkalmazza az alfa - béta vágást (12.3.5. ábra). Ugyanazt a fát használjuk mint korábban, s ugyanazokat a minimax értékeket is kell megkapnunk, csak kevesebb számolással. Mivel a számozott szint feletti szint minimum szint, az a-val jelölt csúcs értéke min(5,−1), azaz a = −1.

12.3. ábra - 12.3.3. ábra. Játékfa-részlet

12.3.3. ábra. Játékfa-részlet

12.4. ábra - 12.3.4. ábra. Minimax értékek

12.3.4. ábra. Minimax értékek

Miután m = max(a, b, c), így a m, tehát −1 m. A b értéke is minimummal határozható meg, így b = 3, s mivel b m, tehát 3 m. Hasonlóan c = 3, s mivel a c az m utolsó fia, kiderült, hogy m = 3. Ezért miután q = min(m, n, o), q m, azaz q 3. Miután csak egy fia van, d = 2, s innen 2 n. Mivel a q meghatározásakor minimumot kell használni, s n értéke még lehet kisebb az m értékénél, tovább folytatjuk ebben az ágban. Az e fiait megvizsgálva kiderül, hogy e = 5, tehát 5 n. Azaz a m ≤ n, tehát q meghatározásánál nincs szükség az n pontos értékére, az f meghatározását egy az egyben kihagyhatjuk ( béta vágás). Az o meghatározásához először a g értékét kell megadni, s ez 4 lesz. Innen 4 o, de így m ≤ o, tehát az o pontos értéke sem érdekes, kihagyható mind a h, mind az i meghatározása. Miután a q összes fiát megvizsgáltuk, kapjuk a q = 3 eredményt. Minthogy s = max(q, r), 3 s. r értékéhez mindenképpen szükség van a p, s ehhez a j értékére. Könnyen adódik a j = 1. A k meghatározásánál minimumot számolunk, s mivel az első fiúnál szereplő 0 érték miatt k 0, a p kiszámításánál már szóba se jöhetne a k, így a további fiaival nem kellene törődni, de nincs is több fia. Az l viszont érdekesebb, mert l 2, ami még nagyobb lehet j-nél, s mivel itt is csak ez az egy fiú van, l = 2, s p = l = 2 Innen r 2, s ebből biztos, hogy r q, tehát az r pontos értéke már nem is fontos, a többi fiával felesleges foglalkozni (alfa vágás). A gyakorlat azt mutatja, hogy nagyjából a csúcsok felének a vizsgálatától eltekinthetünk ezt a módszert használva.

12.5. ábra - 12.3.5. ábra. alfa - béta vágások

12.3.5. ábra. alfa - béta vágások