Lehetséges abszolút verhetetlen sakkozógépet készíteni?

Van egy csomó jó hozzászólás a Stackoverflow-on:

[link]

Elvileg a lehetséges lépések száma véges, tehát csak a számítási erő fejlettsége szab határt. És léteznek olyan heurisztikák, amikkel biztonságosan csökkenthető a szükséges erő.

(És lehetséges olyan játékot is tervezni, ahol szándékosan növeljük ezt a határt vagy úgy tervezzük meg, hogy az egyszerű heurisztikákat preferálja

[link] , lásd pl. az Arimaa nevű játékot, ahol az volt a szándék, hogy egyszerűen tanulható legyen emberek, de nehezen megoldható számítógépek számára.)

A dáma esetében azt is sikerült bizonyítani, hogy lehetséges mindig elérni döntetlent vagy győzelmet. Sakkelémlet nem tudom, be tudja-e látni ugyanezt.

Az már nehezebb, hogy a döntetlen ellen is játsszunk.

Nem tudom, bizonyítható-e, hogy mindig el lehet érni döntetlent, az én sejtésem az igen lenne...???

És azt is megkérdezném, a játék tervezésénél lehetséges-e nem véletlen alapú játéknál teljesen eliminálni a döntetlent mint lehetőséget.

A sakk elvileg véges játék. Ergo elvileg végig lehetne venni az összes lépéssorozatot, és szépen egy fa struktúrába rendezni. A fa tetején le kell vágni azokat a játékokat, ahol az ellenfél lépése győzelemhez vezet. A következő szinten le kell vágni azokat az gallyakat, amelyekkel nem nyerhetünk.

A végén kétféle állapot képzelhető el:

1. Vagy van egy olyan ág, amiben minden fél a leginkább nyerő stratégiával játszik, mégis az egyik fél nyer. Ekkor az dönti el azt, hogy ki nyer, hogy ki kezd.

2. Vagy van olyan biztos stratégia, ami győzelemhez visz.

~ ~ ~ ~ ~ ~ ~

Pl. játszunk amőbát – vagy ha úgy tetszik tic-tac-toe-t – 2x2-es pályán. Aki kezd, az nyer. (Más lehetőség nincs is, gyakorlatilag ha random lépkednének, akkor is az nyer, aki kezd.)

3x3-as pályán már nem ennyire egyszerű a dolog, de ott is van olyan stratégia, ami biztosítja a döntetlent, akármit is lép a másik. Lásd: [link]

Elvileg a sakknál sincs ez máshogy, én nem tudok olyan játékról, ami kiértékelhetetlen lenne, illetve nem lehet végtelen hosszú egy játék. (Ha egy állás háromszor ismétlődik, a következő játékos kérheti a döntetlent.)

Kezdjük előbb a kérdés értelmezésével.

Verhetetlen az, aki nem kap ki. A "verés" azonos a kikapással. Tehát a döntetlennél rosszabbat nem játszó gép verhetetlen.

A sakkot 64 lehetséges pozícióban 16 bábuval játsszák. Ez azt sugallja, hogy a kombinációk száma véges, azaz véges számú különböző játék lehetséges. Azonban ezt az akadályozza, hogy egyes bábukkal vissza lehet lépni, azaz - elvileg - mondjuk a bástyával A1-ről A7-re lépek, aztán A1-re, és így tovább. Ezért a sakkjátékok lehetséges száma feltehetően végtelen. Ennek viszont az mond ellent, hogy mindkét fél a győzelemre tör, tehát - ha teheti - üti a másik figuráját. Ezáltal viszont véges számú bábu fogy, véges lépésben kevés figura marad, ami már átlátható.

Ugyanakkor számos olyan eset van, amikor a játék elvileg döntetlen, mert olyan bábuk maradnak, hogy nem viheti győzelemre egyik fél se.

De fogjuk meg a problémát más oldalról. A sakkozógép készítése véges időpillanatban, ezért véges tudással készül. Ha abban a pillanatban be van bizonyítva, hogy felírható a sakk összes lehetséges lépése, akkor tudható, hogy létezik-e biztos győztes stratégia, vagy sem. És a kérdés ennek alapján megválaszolható (igen/nem). Ha nincs bebizonyítva, akkor biztosan nem lehet verhetetlen sakkozógépet készíteni, mert egy későbbi pillanatban valaki tudni fog egy olyan kombinációt, amit a gép még nem, így kikap.

Elvileg tehát nem lehet ilyen gépet készíteni, mert minden pillanatban véges tudással áll szemben egy tetszőlegesen fejlődhető tudás.

> „Azonban ezt az akadályozza, hogy egyes bábukkal vissza lehet lépni, azaz - elvileg - mondjuk a bástyával A1-ről A7-re lépek, aztán A1-re, és így tovább. Ezért a sakkjátékok lehetséges száma feltehetően végtelen.”

Vannak konvenciók, például ha egymást követő 25 vagy 50 lépésváltás során nem történt sem gyaloglépés, sem ütés, akkor automatikusan döntetlen. Az is egy korlát, hogyha háromszor előáll ugyanaz a helyzet, akkor döntetlen (ugye véges sok helyzet van, ha elég sokáig megy a játék, akkor a skatulya elv alapján egyszer vége lesz, konkrétan legfeljebb 2*'a lehetséges helyzetek száma' + 1 lépésben).

Kis szőrszálhasogatás/megjegyzés:

> „A sakkot 64 lehetséges pozícióban 16 bábuval játsszák. Ez azt sugallja, hogy a kombinációk száma véges, azaz véges számú különböző játék lehetséges.”

Egyrészt 32 bábuval játsszák, másrészt szerintem ez elég gyenge sugallat, mert már kétféle jelből is lehet végtelen hosszú jelsorozatot csinálni. (Később ugyanezt írod leírod te is, szóval ezt nem kötekedésből írom, csak talán így egyszerűbben látszik.) De az valóban igaz, hogy a 32 bábut csak véges sok féleképen lehet felpakolni a táblára, így 'a lehetséges helyzetek száma' az előző bekezdésben egy létező valami.