Kombinatorika - sakk (? )

Elsőnek tisztázni kellene, hogy mit értesz lépés alatt. A sakkban 4 lépés az 4 lépéspárt jelent, azaz 4*(világos lép-sötét lép). Tehát 8 fél lépésről van szó ebben az esetben.

Másodszor konkrét számítás csak egy adott állásból számolható. A nyitáskor – mondjuk az első 5 lépés(pár) esetén – minden játékosnak átlagosan 20 különböző lépési lehetősége van. A középjátékban átlagosan 30 különböző lépést tud megtenni egy játékos. De lehet, hogy többet, lehet, hogy kevesebbet.

De ha vesszük ezt az átlagot – középjáték esetén –, és feltételezzük, hogy senki nem ad sakkot – ami erősen lecsökkentheti az ellenfél lehetséges lépéseinek számát –, akkor:

1.1. Világos 30 különböző lépést tud lépni.

1.2. Sötét a világos bármelyik lépésére 30 különböző módon tud válaszolni.

Egy lépés esetén tehát 30² = 900 esetről beszélünk.

2.1. Világos mind a 900 esetben 30-30 különböző lépést tud tenni,

2.2. Amelyek mindegyikére sötét 30-30 különböző lépést tud tenni.

Két lépés esetén tehát 30⁴ = 810 000 esetről beszélünk.

Négy lépés után 30⁸ = 656 100 000 000 esetről van szó. Persze ezek között lehet egy csomó azonos állás is, hogy mennyi, azt nehéz lenne megbecsülni.

Ne írjunk már címeres ökörségeket, főleg, ha életünkben nem tetszettünk sakkozni.

Először is, nem nyitás, hanem megnyitás, másodszor, világos 20-féleképpen kezdheti a játszmát, erre sötét 20-féleképpen válaszolhat. Ugye gyaloggal 8x2=16 lehetséges lépés van megnyitáskor, huszárral pedig 2x2=4 megnyitás lehetséges első lépésben.

Innentől kezdve viszont elképzelhetetlenül bonyolult a variációk száma.

Ember nincs, aki ezt kiszámolná, de szerintem gép se nagyon.

Mezei kombinatorikával ez a kérdés nem megválaszolható.

(Tegeződjünk! Az internet őskorában az un. netikett is ezt ajánlja, mivel soha nem lehet tudni, hogy egy anonim beszélgetésben ki van a másik oldalon.)

Tehát az elv az, hogy ahány féllépés van, annyival szorzódik a játékvariációk száma.

Induljunk ki abból, hogy nem sakkot játszunk, hanem tic-tac-toe-t. (Ez a 3*3-as amőba, lásd: [link] )

Tegyük fel, hogy mindkét játékos úgy játszik, hogy a triviális veszteséget elkerüli.

Mondjuk O kezd. Neki 9 lehetséges lépése van.

Erre X-nek. 8 lehetséges lépése marad, tehát 9*8=72 különböző állapot alakulhat ki.

O következik, neki 7 lehetséges lépése van. Így már 9*8*7=504 játékmenet van.

Innen viszont nem triviális, hogy X-nek hány lépési lehetősége van. Ha O mindkét lépése egy egyenesre esett, és X nem erre az egyenesre tett (Pl.: A1, B2, A3), akkor X-nek csak egy lehetősége van, A2-re lépni, ha el akarja kerülni a biztos veszteséget. Viszont ha O két lépése nem egy egyenesre esett (A1, B2, B3), akkor X-nek 6 lehetősége van. Ugyanez a helyzet, ha O ugyan mindkét lépését egy egyenesre tette, de közben X is erre az egyenesre tett (A1, A2, A3).

Ráadásul innen már két különböző játékmenet ugyanazt az állást tudja előállítani. Pl. (A1, B2, A3) = (A3, B2, A1)

Tehát ez még tic-tac-toe esetén sem triviális már a második lépéspárnál sem.

~ ~ ~ ~ ~ ~ ~

Sakkban még kevésbé triviális, nagyban függ attól, hogy milyen figurák vannak a táblán, azok hol állnak. Még a kezdőpozícióból sem annyira egyszerű.

1. Pl. az oda-vissza lépések két teljesen más játékmenetet jelentenek, de ugyanazt az állást fogják produkálni.

Pl.: Ha3-Hc6, Hb1-Hb8 → kiinduló állapot

De lehet úgy is, hogy Ha3-Ha6, Hb1-Hb8 → kiinduló állapot

Vagy úgy is, hogy Ha3-Hh6, Hb1-Hg8 → kiinduló állapot

De úgy is, hogy Hc3-Hh6, Hb1-Hg8 → kiinduló állapot

2. A kölcsönösen felcserélhető lépések is elő tudják állítani ugyanazt az állást:

d4-d5, c3-c6 = c3-d5, d4-c6 = d4-c6, c3-d5 = c3-c6, d4-d5

1+2. A kettő ráadásul kombinálódik is

Ha3-d5, Hb1-c6 = Ha3-c6, Hb1-d5 = Hc3-d5, Hb1-c6 = Hc3-c6, Hb1-d5

~ ~ ~ ~ ~ ~ ~

Hogy egy-egy figura hányféle módon tud oda-vissza lépni, az erősen függ a játék állásától. Mondjuk egy a1-en álló bástya esetén nem mindegy, hogy a3-on áll-e előtte egy gyalog, vagy a7-en, mert csak függőlegesen 1, vagy 5 oda-vissza lépése van. Nagyon nem mindegy, hogy ugyanezen bástyával egy sorban a király hol áll, a c1-en, vagy a h1-en, mert az egyik esetben 1, a másik esetben 6 oda-vissza lépése van. Egy király esetén sem mindegy, hogy az a1-en áll, mert akkor 3 féle módon tud oda-vissza lépni, vagy b2-n áll, ahol 8 féle módon tud oda-vissza lépni. Illetve itt a másik játékos figuráis is bekavarnak. Ha sötétnek h3-on áll egy bástyája, akkor mindjárt nem 8, hanem csak 5 féle módon tud a világos b2-n álló király oda-vissza lépni.

Tehát ezt így nagyon nem triviális kiszámolni. Annyit lehet mondani, hogy egy adott játékállásban egy játékosnak kb. 30 különböző lépése van. Így a játékmenetek száma:

1. fél lépés: 30

2. fél lépés: 30² = 900

3. fél lépés: 30³ = 2 700

4. fél lépés: 30⁴ = 810 000

Ennyi játékmenet van. Hogy ezekből mennyi vezet ugyanahhoz az álláshoz? Nehéz megmondani. De ha csak a kölcsönösen felcserélhető lépéseket nézem, akkor nagyjából a negyede az a játékállás, ami elérhető négy fél lépés után.

Persze ha nem volt ütés, vagy egy figurával nem lépett egy játékos kétszer egymás után, mert ott a felcserélhetőség mindjárt bukhat. Például kezdőállásból nagyon sok oda-vissza lépést nem tartalmazó állás négyféleképpen állhat elő. Lásd fent a 2. esetet. De! A következő állás csak egyféleképpen tud kialakulni: d4-e5, dxe5-Hc6. Máshogy nem történhet, mert fehér ugyanazzal a figurával lépett kétszer, sötét meg ha előbb lépi Hc6-ot, akkor világos nem üthet e5-re.

~ ~ ~ ~ ~ ~ ~

> az első lépés befejeztével 400 lehetséges kimenetel van, jól gondolom?

Kezdőlépés esetén pontosan ennyi van. Itt az a gond, hogy nagyon szerteágazóvá válik a dolog. Ha világos Ha3-at lépte, akkor 7*2=14 különböző lépést tehet gyaloggal. További 2 lépést tehet a g1-en álló huszárral. Az a3-on álló huszár is 3 különböző helyre léphet. Ez összesen 19 különböző lépési lehetőség.

Ha a huszár nem a3-ra, hanem c3-ra lépett, akkor 7*2=14 különböző lépést tehet gyaloggal. 2 lépést tehet a g1-en álló huszárral, és 5 különböző helyre léphet az c3-on álló huszárral. Ez 21 különböző lépési lehetőség.

Ha világos első lépése d3 volt, akkor: 7*2+1 = 15 lépét tehet meg gyaloggal. További 4 lépést tehet meg a két huszárral, valamint 5 lépést tehet meg a c1-en álló futóval. Ez 24 különböző lépési lehetőség.

Ha világos első lépése e3 volt, akkor 7*2+1 = 15 lépést tehet meg gyaloggal. További 4 lépést tehet meg a két huszárral. 5 lépést tehet meg a f1-en álló futóval, és 4 lépést tehet meg a d1-en álló vezérrel. Ez 28 különböző lépési lehetőség.

Innentől tehát már nem annyira triviális számolgatni, kvázi külön meg kell vizsgálni minden lépést. Szerencsére ezt megtették már, így nem kell nekünk megtenni.

1. fél lépés: 20 különböző állás

1 lépéspár (2 fél lépés) után: 400 különböző állás

2 lépéspár (4 fél lépés) után: 5362 különböző állás (8902 különböző játékmenet)

4 lépéspár után: 71 852 különböző állás (197 742 különböző játékmenet)

5 lépéspár után: 809 896 különböző állás (4 897 256 különböző játékmenet)

Persze ez csak a kezdőállásra vonatkozik. Ha már középjátéknál tartunk, ezek a számok egészen máshogy alakulnak, és ott nincs mese, végig kell számolni az összes lehetséges lépést. (Valamennyire lehet optimalizálni, de nem sokat.)

~ ~ ~ ~ ~ ~ ~

> Ön sakkal foglalkozik?

Informatikus vagyok, programozó. De szeretek sakkozni, szoktam is, de úgy olyan autodidakta úton tanuló sakkozó vagyok. Soha nem tanultam a sakkot – leszámítva az alapszabályokat még 7-8 éves koromban –, egy sakkot komolyan tanuló ember bizonyosan köpni-nyelni nem hagyna, de az ismerőseim többsége szerencsére nem tanult direkt módon sakkot, az ő szintjükhöz képest jó vagyok.

De ez nem is számít itt. Egy ilyen problémakört különösebben mély sakktudás nélkül is lehet boncolgatni, pusztán a szabályok ismerete elegendő hozzá.

A matematika azon területét, amely ezzel foglalkozik kombinatorikus játékelméletnek nevezik. Arról a fogalomról, ami ehhez csatlakozik, tudom ajánlani ezt a wiki oldalt: [link]

Például a sakk esetén annak, hogy kiszámoljuk, hogy az 5. lépéspár után pontosan hányféle állás lehetséges nem sok értelme van, arról nem is beszélve, hogy sok lépés után már számítógéppel sem lehetséges emberi időn belül.

A wiki oldal alapján a lehetséges sakk állások száma kb. 10^47 (state-space complexity) és egy adott állásban lehetséges lépések száma 35 (branching factor).