Shannon száma

Claude Elwood Shannon (1916-2001) amerikai elektromérnök, híradástechnikus, matematikus és kriptográfus, az információelmélet alapító atyja. Ismertségét leginkább ez utóbbinak köszönheti, hiszen a róla elnevezett Shannon-féle entrópia az információelmélet központi fogalma, az információ mérésére bevezetett mennyiség, amely számos tudományterületet forradalmasított, az információelmélet eredményeit pedig megannyi műszaki megoldás felhasználja. Kevésbé ismert azonban az, hogy lényegében Shannon az atyja a számítógépes sakkozásnak is. 1949-ben írta meg úttörő cikkét arról, hogy mi az elméleti alapja egy számítógépes sakkprogram működésének. De műszaki ember lévén ő maga is épített kezdetleges sakkgépet, amint az az alábbi ábrán is látható Emanuel Lasker matematikus, filozófus és sakkvilágbajnok társaságában, aki egyébként rekord hosszúságú 27 éven keresztül tudta 1894 és 1921 között megvédeni világbajnoki címét.

Az kezdetek óta készült sakkprogramoknak lényegében mindegyike a Shannon által vázolt megoldásra épít, a mai sakkprogramok pedig már képesek túlszárnyalni a világbajnoki szintet is. Minden ilyen algoritmus őse az ún. minimax keresés, ami lényegében nagyon egyszerű. A sakkjáték leírható egy fa jellegű gráffal, aminek a csúcsai sakkállások, az irányított élek pedig a lehetséges lépések, amik egyik állapotból a másikba vezetik a játék fonalát. Egy állapothoz hozzá tartozik az is, hogy a sötét vagy a világos játékos következik. Ez az irányított fa a játék kezdő állapotából kiindulva leírja, hogy mik a lehetséges lépés sorozatok. Nyilvánvalóan minden játékosnak azt a lépést érdemes választania, ami az ellenfél legjobb válaszlépése esetén is a legkedvezőbb számára. Ha mindkét játékos ismerné ezt a hatalmas gráfot, és át tudnák tekinteni az összes lehetséges bejárást, akkor mindegyikük eldönthetné minden egyes állásról, hogy az nyerő, vesztő, vagy esetleg döntetlenre jönne ki az ellenfél optimális lépéseit figyelembe véve. Tulajdonképpen elvileg lehetséges, hogy a sakk esetében létezik nem vesztő stratégia, vagyis a kezdő állapot tulajdonképpen döntetlent ér.

A gyakorlatban azonban az említett fa gráfot nem lehet áttekinteni csak néhány lépés mélységig, akár emberről, akár gépről legyen szó, mert a gráf lényegében csillagászati méretű. Ebből kifolyólag az állásokat sem lehet értékelni egyértelműen, csak valamilyen heurisztika alapján, például figyelembe véve a bábuk pontértékét, a gyalogállást, és egyéb tényezőket, amiket tipikusan nagymesterek segítenek megállapítani, vagy játszmák alapján tanulják a programok. Ha azonban valamilyen közelítő értékelést tudunk adni a sakkállásokra, akkor a minimax keresés lesz az, amely valamilyen mélységig a legjobb lépéskombinációt megtalálja valamely játékos számára. Az elnevezés onnan jön, hogy az egyik játékos szempontjából az állásokra adott értékelést felváltva akarják maximalizálni illetve minimalizálni a játékosok, tekintettel arra, hogy felváltva lépnek. Az algoritmus roppant egyszerű, azonban a futási ideje a fa mélységével, azaz a lépések számával exponenciálisan növekszik. A Kaszparovot legyőző Deep Blue például átlagosan hat lépéspárt tekintett előre, míg a mai legjobb Hydra nevezetű gépi sakkozó kilenc lépéspárig tekint előre átlagosan. Sannonról egyébként egy trófeát is elneveztek, amit a sakkprogramok világbajnokságán a nyertes program tervezői kapnak. Ez látszik az alábbi képen, amint azt a Deep Blue elődjének a Deep Tought-nak a tervezője vesz át Shannontól 1989-ben.

De mégis mekkora az a csillagászati szám, amiről beszélünk? Shannon adott erre egy becslést az említett cikkben, amiben azt tekintette, hogy hányféle képpen lehet a táblára helyezni az alap sakkbábu készletet, vagyis azt, amivel a játék elején rendelkeznek az ellenfelek. Ezt nevezik Shannon-féle számnak. Ez természetesen lehet több is és kevesebb is, mint a játék során előforduló valódi sakkálások száma. Egyrészt nem minden állás állhat elő szabályos játék során. Például a gyalogok nem mehetnek hátrafele, vagy nem lehetnek a királyok egyszerre sakkban. Másrészt a gyalogokat más bábukra lehet cserélni, ha elérik a szemközti alapvonalat, ez pedig növeli a lehetőségek számát. Ha azonban nagyságrendi becslést szeretnénk, akkor a Shannon-féle szám egy jó kiindulópont. Hogyan lehet tehát kiszámolni?

Ehhez érdemes tudni, hogy egy n elemű halmazból hányféle képpen lehet kiválasztani k elemet úgy, hogy a sorrendjük nem számít. Matematikusok ezt úgy mondják, hogy "n alatt a k", és úgy is jelölik, hogy zárójelbe téve n alá írják a k számot. Érdemes még azt is tudni, hogy 1-től n-ig összeszorozva a számokat, a kapott számot úgy mondják, hogy n faktoriális, és n! a jelölése, a matematikusok így rövidítik ezt a szorzatot. Faktoriálisokkal n alatt a k könnyen kifejezhető. Ha n elemből k elemet akarunk kiválasztani úgy, hogy számít a sorrend, akkor az első elemet n féle képpen választhatjuk, a másodikat (n-1) féle képpen, és így tovább, míg a k. elemet (n-k-1) féle képpen. Az összes lehetőségek számát tehát megkapjuk, ha ezeket összeszorozzuk, ami n!/(n-k)! lesz. Ha viszont a sorrend nem számít, akkor ezt le kell osztani annyival, ahány féle képpen k elemet sorba rendezhetünk, hiszen mindent ennyiszer számoltunk, ebben az esetben k! darabszor. Végeredményben tehát az alábbi képletet kapjuk.

Ezt felhasználva Shannon számát mostmár ki tudjuk számolni. Először ki kell választani, hogy hova tesszük a 32 sakkfigurát a 64 mezőből álló sakktáblán, ami 64 alatt a 32 lehetőség. Aztán ki kell választani, hogy a 32 helyből melyik 16-ra tesszük mondjuk a világos bábukat, ami 32 alatt a 16 lehetőség. Aztán ki kell választani, hogy a sötét és a világos bábuk közül melyik a 8 gyalog, ami 16 alatt a 8 lehetőség mindkét játékosnál. Aztán ki kell választani a maradék 8 helyből mindkét játékos esetén, hogy hova kerülnek a bástyák, ami 8 alatt a 2 lehetőség mindkét esetben. Aztán ki kell választani mondjuk a huszárokat a maradék 6-6 helyből, ami 6 alatt a 2 mindkét játékosnál. Aztán a futókat, ami 4 alatt a 2 mindkét játékosnál. Vegyük észre, hogy a sakkban szokás a mezők színe szerint fehér és fekete futókról is beszélni, de mi itt most ezt a megkülönböztetést nem tesszük meg. Legvégül azt kell eldönteni mindkét játékos bábuinál, hogy a maradék 2 helyből melyiken van a király és melyiken a királynő, ami kétszer két lehetőség összesen. Mindent összetéve és az egyszerűsítéseket elvégezve az alábbi képlet adódik, ami durván 10^43, vagyis az 1-est 43 darab nulla követi. Ez azt jelenti, ha nanoszekundumonként vizsgálnánk meg egy állást, akkor is 10^34 másodpercig, azaz 10^26 évig tartana az összes lehetséges állás végignézése, ami az Univerzum életkorának is rengetegszerese!