Ész Ventura: Mekkora a kártya és a sakk univerzuma?

A paklikódos feladványnak több buktatója is volt. Az első az, hogy nem a pakli lehetséges állapotainak a számát kérdeztem, hanem a kódolható információ mennyiségét. A feladat szövegében elég részletesen el is volt magyarázva a kettő közti különbség, és a számítási módszer is. Utóbbi az első kettes alapú logaritmusa, ha bitben számoljuk az információt. Lényegében az a kérdés, hogy legfeljebb hány kétállapotú rendszert vehetünk, hogy a lehetséges állapotainak száma ne haladja meg a pakli lehetséges állapotainak számát. Nyilván az tévesztett meg sokakat, hogy MB-ban kérdeztem rá az eredményre, ezért nagy számokra számítottak, és elküldték nekem eredményül a lehetséges állapotok számára saccolt csillagászati méretű számaikat, pedig csak néhány száz bitről van szó, mint látni fogjuk.

Arra sokan rájöttek, hogy a lapok sorrendjének lehetéges száma nem más, mint az 52 lap úgynevezett permutációinak száma, ami 52 faktoriális (52!), ez pedig kb. 8*10^67, ami log2(8*10^67) = 225.6 bitnek felelne meg, de ezt lefele kell kerekítenünk, mert tört bitnyi információt nem szokás megadni. Itt jön azonban a második buktató, hogy nemcsak a lapok sorrendjével, de az állásukkal is lehet információt kódolni, mert minden lap kétféle helyzetben lehet a doboz tetejéhez képest, színével vagy hátlapjával felfelé. Ez minden lap esetében pont egy bit információnak felel meg, így nyertünk még 52 bitet.

Ha rájöttünk, hogy a lapok állhatnak képpel felfelé vagy lefelé is, akkor már valószínűleg az is eszünkbe jut, hogy a kártyalapok el is forgathatók a saját síkjukban, és kétféleképpen tehetők a pakliba attól függően, hogy melyik rövid élük néz a doboz nyílása felé. Ez a trükk azonban csak azoknál a kártyalapoknál használható, amiknek a képes oldala aszimmetrikus grafikájú. A harmadik buktató, hogy ezeket össze tudjuk-e jól számolni. 22 ilyen lap van: ászból, 3-as, 5-ös, 6-os, 7-es, 8-as és 9-es lapokból a treff, kőr, pikk lapok ilyenek, és még a káró hetes is!

A teljes kódolható információ mennyisége tehát 225+52+22 = 299 bit = 0,000037375 MB. Egyeseknek talán meglepő, hogy milyen kevés bit tartozik az állapotok számának csillagászati mennyiségéhez. Ez azért van, mert az állapotok száma exponenciális nő a bitek számával, hiszen N bit 2^N állapotot tud megvalósítani.

A sakk univerzuma

Hogy még jobban átérezzük a lehetőségek számának exponenciális felrobbanását, amiről már korábban is írtam a kombinatorika kapcsán. Vegyük a sakkjáték példáját, amit sokan ismernek. Hogy mennyi a szabályos játék során előállítható sakkállások lehetséges száma, annak kiszámítása túl nehéz probléma lenne, de nagyságrendileg egy jó becslés erre az ún. Shannon-féle szám, ami megadja, hogy az alap sakk-készlet bábuit hányféleképpen lehet a sakktáblára helyezni függetlenül attól, hogy az adott állás előállhat-e. Ez a szám durván 10^43, vagyis az 1-est 43 darab nulla követi. Ez azt jelenti, hogy 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.

A sakkállások csillagászati számával kontrasztban viszont nézzük meg, hogy egy sakkállás hány biten kódolható, tehát amikor mondjuk egy számítógépes program elmenti a félbehagyott partinkat, akkor az mekkora memóriaterületet foglal el a vincseszterünkön. Ehhez azt kell csak elmenteni, hogy melyik bábu melyik mezőn áll. Egy játékosnak 16 bábuja van, és 64 különböző mező van a sakktáblán. Egy bábu helyzetének rögzítéséhez log2(64) = 6 bit információra van szükség, tehát az egész parti állásának rögzítéséhez 2*16*6 = 192 bit elegendő. Valójában egy picit bonyolít a dolgon, hogy a gyalogokat be lehet cserélni a négyféle tiszt valamelyikére (vezér, bástya, huszár, futó), ha elérik az ellenfél alapvonalát, illetve az, hogy lehetnek leütött bábuk is, de ezt a Shannon-féle számításból is kihagytuk. Más oldalról viszont ez valójában egy felső becslés, mert ennél kevesebb bit is elegendő lehet a kódoláshoz, hiszen egy elfoglalt mezőre más bábu már nem rakható, tehát nem mindig a maximális 64 mező áll rendelkezésre.

A lényeg: megint csak pár száz bitről beszélünk, és ez érzékelteti a lényeget, nevezetesen azt, hogy ilyen kevés információval, azaz a tárhelyünk bár bitnyi kis területét használva a csillagászati számú lehetséges konfiguráció közül tudunk egy konkrétat, de tetszőlegeset kódolni.

Két pakli megoldása

Ha a két doboz megkülönböztethető, ami ésszerű, hiszen egy kék és egy piros hátú pakliról van szó, amelyek doboza is kék illetve piros szokott lenni, akkor a 2*52 = 104 lap lehetséges permutációinak száma 104 faktoriális, ami log2(104!) bit információnak felel meg, lefele kerekítve 551 bit.

A képpel felfelé és lefelé fordítás lehetőségei ehhez még 104 bitet adnak hozzá, továbbá az asszimetrikus lapok forgatása 2*22 bitet, összesítve tehát az eredmény 551+104+44 = 699 bit. Ha pedig a két doboz egyforma lenne, akkor az 1 bittel csökkentené a végeredményt.