Létezik-e "legjobb lépés"?

A Go Wiki wikiből
A következő eszmefuttatást a HunGo levelezőlista tagjai produkálták:

Gondoljunk csak bele, hogy egy go-táblán egy öszzetettebb helyzetben szinte mindenki más helyre tenné a kövét, és mindegyik ötlet mögött összetett meglátások vannak.

Szóval, a fenti állításra mit mondanak a profik: létezik adott állásban a "legjobb lépés" fogalma? (Nyilván nem megnyitásról beszélünk.)

Emléxem, 1* a Bodajki Go-táborban volt egy (igazából kettõ) japán profi gamer, akitõl megkérdeztük, hogy volt-e már olyan játszmája, amiben minden lépése hibátlan volt? Elmosolyodott, és büszkén kijelentette, hogy egyszer már volt...

Tauber László


A legjobb lépést nyilván egy (ma még nem létező;) szuperszámítógép tenné, akit nevezhetünk akár Istennek is. Egyszer megkérdezték a profikat, hogy szerintük Isten mennyivel erősebb mint ők. Takagawa Kaku beérte volna 4 kővel is, ha csúcsformában van. (Mármint, ha ő kapja:-))

Kis Kós László


Attol fugg mit ertunk legjobb lepes alatt. Az emberi nyelv ugye nem egyertelmu.

Ha pl. azt, hogy a leheto legnagyobb kulonbseggel nyerunk, ha az ellenfel mindig a szamara legkedvezobbet lepi, akkor nyilvan van. Hiszen a go egy veges jatek. Csak altalaban nem tudjuk, hogy melyik az, meg persze lehet tobb legjobb lepes.

Ez a definicio eleg jol egybeesik az "intuitiv" legjobb lepes fogalmaval, ha az adott allasban nyeresre allunk. (Es ez, marmint az egybeeses, igaz a fusekiben sot az ures tablan is.)

Ha viszont vesztesre allunk, akkor intuivivan mar mast erzunk legjobbnak. hiszen nem az a celunk, hogy minimalizaljuk a vereseget, hanem hogy nyerjunk. Ilyenkor jobbnak erezzuk az olyan lepeset, amely az ellenfel tokeletes jateka eseten ugyan nagyobb vereseghez vezet, azonban megadja neki a hibazas lehetoseget. Meg pontosabban, maximalizalja a hibazas valoszinuseget.Ez viszont mar kevesse egzakt, mert fugg az ellenfel tudasatol, veralkohol szintjetol, a rendelkezesre allo gondolkodasi idotol stb.

Téby Attila


"A legjobb lépést nyilván egy (ma még nem létező) szuperszámítógép tenné," http://321.hu/sas

ilyen számítógép sosem lesz

"akit nevezhetünk akár Istennek is."

ezért. (gyakorlatiag végtelen számítási kapacitás)

azt viszont 100% tökéletességgel meg tudom mondani, melyik a legjobb lépés: amelyik a számunkra legjobb álláshoz vezet:-))

Szervác Attila http://321.hu/sas


"ilyen számítógép sosem lesz"
never say never... 8-)

Bohus Géza


"never say never... 8-)" http://321.hu/sas

én azért tartom még 100 évig de legkésõbb halálomig. Ha meg valamire fatálisan nem gondoltunk volna a számítási kapacitással kapcsolatban, akkor terjesszük ki a gótábla méretét még n-nel (például n dimenzióval) vagy bármilyen más módon növeljük meg ezt a gráfot a felépítését megtartva és arra vagyük a megoldást. Hoszen tulképp teljesen mindegy, hogy hányszor*hányszor*hányszor*...*hányas a gótábla a feladat pontosan ugyanaz. Ez _is_ a szép benne :-))

Szervác Attila http://321.hu/sas


Hmmm. Vajon tényleg csak a számítási kapacitás a korlátja a számítógép általi legjobb lépés megtalálásának? Vajon a számítási kapacitás növekedése megoldhatja a problémát? Hmmm. És mi lenne ennek a szuperszámítógépnek a mûkodési elve?

Miki


nem, programot is kell írni rá 8-). ha lenne "végtelen" kapacitású (értsd, nagyon nagy és nagyon gyors) gép, akkor például egy tanulni képes program eljátszogatna rajta és jól megtanulná a tutit. ilyen pl. az ostábla (backgammon) világbajnok programja, de a sakké nem. erre vannak standard technikák, meg biztos kitalálnak még újabbakat.

ha a kvantumszámíógép bejön és jól értem az elvet, akkor az sok dolgot fog tudni párhuzamosan megtalálni. az is egy hasznos dolog ugye 8-).

csak két őtlet.

Bohus Géza


"Hmmm. Vajon tényleg csak a számítási kapacitás a korlátja a számítógép általi legjobb lépés megtalálásának? Vajon a számítási kapacitás növekedése megoldhatja a problémát? Hmmm. És mi lenne ennek a szuperszámítógépnek a mûkodési elve"

Elmeleti szinten tulajdonkeppen nagyon egyszeru a dolog, hiszen a go veges jatek. Veges szamu pont van a tablan (361), es egy jatszma mindig veget er veges szamu lepesben ( a vegtelen ciklusokat - triplako, orok elet stb - a szabalyok kizarjak, ill. ilyenkor dontetlen az eredmeny ). Tehat nincsen elmeleti akadalya annak hogy az osszes lehetseges gojatszmat eloallitsuk.

Felirjuk fekete osszes szabalyos kezdolepeset - a tabla barmely pontja -, mindegyikhez feher osszes lehetseges szabalyos valaszlepeset, - ezek minden lepesben az ures pontjai a tablanak, kiveve ahova nem szabalyos lepni ongyilkossag miatt mindegyikhez fekete osszes lehetseges szabalyos valaszlepeset, mindegyikhez feher osszes lehetseges szabalyos valaszlepeset, .. es igy tovabb... minden variacio veget er egyszer, olyankor feljegyezzuk az eredmenyt

Igy kialakul egy nagy "adatbazis", egy fastruktura, amiben benne van a letezo osszes gojatszma, mindegyik amit barki barmikor lejatszott, vagy amit soha senki sem jatszott le ... ( Persze benne van egy csomo "ertelmetlen" jatszma is, ahol minden lepes szabalyos ugyan, csak ertelmetlen. )

Ha egy "szuperszamitogep" rendelkezne ezzel az adatbazissal, akkor mindent tudna a gorol, tokeletes jatekos lenne. Barmilyen allasnal tisztaban lenne az osszes tovabbi lepes osszes lehetseges kovetkezmenyevel, egeszen a vegsokig, igy mindig optimalis dontest tudna hozni. Az igazan erdekes persze az lenne, ha ez a szuperszamitogep jatszana sajat magaval. Ebbol valoszinuleg kiderulne a komi idealis erteke, vagy az hogy (komi nelkul) van e egyaltalan feketenek nyero strategiaja, azaz van-e jo valasza feher barmely lepesere barmely helyzetben, es a kezdes elonye miatt nyerni tud, vagy esetleg van fehernek valami olyan strategiaja amivel ki tud kenyszeriteni valahogy dontetlent, pl tripla ko val. ( persze a nyero strategia letezeset lehet hogy egyszerubben is be lehet bizonyitani )

Csupan egy "apro" gond van ezzel a "teljes elemzessel", ami ugyan gyakorlati jellegu de eleg alapveto, ez a jatek meretebol es komplexitasabol adodik, miszerint rettenetesen sok variacio van. A tabla merete alapvetoen meghatarozza a lehetosegek szamat: Ha jol tudom 5x5 os tablara mar sikerult eloallitani az osszes lehetseges jatszmat (de mar 9x9 es nel is irrealis lenne jelenleg) De 19x19 es tablanal a lehetseges jatszmak szama az univerzum osszes atomjainak a szamaval van kb egy nagysagrenden! Ezert ez a teljes elemzes eleg eselytelennek tunik. ( Istennek kellene lenni hozza, teremteni gyorsan egy nagy univerzumot, ami csak ezzel foglalkozik es megoldja a got.) ( Ezt egyebkent a sakkra ( es sok mas sokkal egyszerubb jatekra) sem sikerult meg megcsinalni )

Tehat a "Kami no itte", a tokeletes lepes ( ~azaz a barmilyen helyzetben tokeletes lepes kepessege? ) elerhetetlennek tunik. (de azert senki se adja fel 8) )

De ez nem jelenti feltetlenul azt, hogy lehetetlen olyan szamitogepet epiteni amelyik jobban jatszik barmelyik embernel!

Hiszen nem kell az osszes lehetoseget ismerni, ha nem torekszunk az abszolut tokeletessegre. A fenti oriasadatbazist peldaul radikalisan le lehetne csokkenteni az ertelmetlen lepesek kizarasaval es egyeb trukkokkel, de sajnos ez sem segit igazan. Vannak erre szamitgatasok, a reszletekre nem emlekszem, de a becslesek szerint meg ehhez is tobb galaxisnyi anyagra lenne szukseg, csak a szamitogep memoriajahoz - de ebben a becslesben benne van hogy ez a memoria hagyomanyos ( ma ismert ) technologiaval keszulne (~ atomokbol epulne fel), es nem valamifele jovobeli nano- vagy kvantumtechnologiaval.

Elkepzelheto hogy a jovoben lesz olyan technologia amely az informacio tarolasat es feldolgozasat az atomoknal sokkal kisebb meretekben valositja meg? Ki tudja .. Valoszinuleg meg elkepzelni sem tudjuk mi lesz 50 vagy 100 ev mulva ... (100 evvel ezelott is korberohogtek volna azt aki Internetrol meg marsszondakrol beszelt volna) Mire lesz eleg vajon ez az akarhany nagysagrenddel nagyobb szamitasi kapacitas? Nem tudhatjuk.

A sakk es a go kozott a kulonbseg a komplexitasban van. A go sok-sok nagysagrenddel komplexebb. Nagyobb a tabla, tobb a lehetoseg, sokkal melyebben kene eloreolvasni ( gondoljunk csak egy letrara, vagy egy hatalmas semeai-ra ).. az egesz jatek sokkal komplexebb es nyitottabb.

A "valodi" (sakk es go) programok nem a fent leirt modon mukodnek. Peldaul a vilagbajnok sakkprogramok, akik esetenkent megverik a legjobb embereket is, tulajdonkeppen nagyon butak. Ugyesen kizarjak mindig amit lehet ( pl vezerrel nem lepunk onkent atariba, ilyenkor felesleges is tovabb vizsgalodni) eloreszamolnak valahany lepes melyen ( nem tudom de ugy tippelem kb max tizenvalahany lepes melysegrol beszelhetunk praktikusan) es kiertekelik az allast, hozzarendelnek valami szamszeru erteket, hogy mennyire jo, majd azt valasztjak amelyik a legjobbnak tunik. ( Ez tulajdonkeppen egyfajta nyers-ero (brute-force) megkozelites. )

A szamitogepek mai sebessege mellett ez a sakknal egesz jo eredmenyt ad. A go-nal nem.

Valoszinuleg valami egesz masfajta megkozelites fog inkabb segiteni ( a szamitasi kapacitas novekedesevel egyutt persze ). A mesterseges-intelligencia kutatasban sok igeretes, otletes irany van, komoly fejlodes varhato. (neuralis halok, genetikus algoritmusok stb).

Hogy valaha is kepes lesz e az ember olyan gepet epiteni ami jobban gozik nala? Es ha igen mikor? Nem tudhatjuk, de nem zarhato ki hogy ez egyszer bekovetkezik.

En mindenesetre kivancsian varom mit hoz a jovo. 8)

Pampalini


Hát igen, értem amit írtál, de én nem ebben látom a fõ problémát.

Az elsõ kérdés, hogy ha minden egyes lehetséges játszmát ismerne a szuperszámítógép memóriája, mi alapján döntené el, hogy mit lépjen egy adott helyzetben? Mi garantálja azt, hogy nincs olyan nem egyensúlyi helyzet, amelyben a gép bármely lépésére létezik olyan további lefolyás, amelybõl az ellenfél gyõzelme következik?

Miki


Nem is értem, miért problémázunk ezen, mikor van ennek egy egyszerű megoldása. enel utólagos engedélyével ide másolom a GoWikin lévő bemutatkozásából az utolsó mondatot: "Milyen erős go-játékos Isten? (Ha levélben megkérdezed, akkor megí­rom.)" Nosza, írjunk neki egy levelet, és ő majd megmondja a valót! :O)))))

Inimma



"Hát igen, értem amit írtál, de én nem ebben látom a fõ problémát.

Az elsõ kérdés, hogy ha minden egyes lehetséges játszmát ismerne a szuperszámítógép memóriája, mi alapján döntené el, hogy mit lépjen egy adott helyzetben? Mi garantálja azt, hogy nincs olyan nem egyensúlyi helyzet, amelyben a gép bármely lépésére létezik olyan további lefolyás, amelybõl az ellenfél gyõzelme következik?"

ezt valoban semmi nem garantalja. ezert (is) jobb a tanulos megoldas.

Bohus Géza


"ezt valoban semmi nem garantalja. ezert (is) jobb a tanulos megoldas."


Hmm. Elvesztettem a fonalat.

Ha minden játék ki van számolva miért is ne dönthetné el a gép mit köll neki lépni?

Ha látja, hogy az adott lépés után mindenképpen õ nyer (ha követi saját algoritmusát) akkor meglépi. Ha nem, akkor feladja.

Végülis a tökéletes játékos tökéletesen játszik és nem trükköz, a játék szellemében bizonyítva milyen rendkívül tökéletes is õ. :)

Következésképpen két istenszámítógép közt rövidek a menetek. ;-)

A sok programozónak addig is csatolnám az istenprogram forráskódját. Sajnos egyenlõre csak fehérrel tud játszani és komi nélkül, valamint a hibakezelés is gyengélkedik, de nem akarok minden dicsõséget egymagam learatni :)

#include <stdio.h>
int main() {
        char input[4];
        fgets(input,4,stdin);
        printf("I fear I have to resign. Makemashita.\n");
        return;
}

1 MonK


"Az elsõ kérdés, hogy ha minden egyes lehetséges játszmát ismerne a szuperszámítógép memóriája, mi alapján döntené el, hogy mit lépjen egy adott helyzetben? Mi garantálja azt, hogy nincs olyan nem egyensúlyi helyzet, amelyben a gép bármely lépésére létezik olyan további lefolyás, amelybõl az ellenfél gyõzelme következik?"

a jatekelmelet alapja, hogy minden ketszemelyes jatekban, ahol nincs dontetlen letezik az egyik jatekos szamara nyero strategia es ha a dontetlent megengedjuk, akkor letezik az egyiknek nem veszto strategia, es bizonyitani is pofon egyszeru, amit lentebb le is irtam ha valaki meg nem ismerne.

es ebbol kovetkezik, hogy ha mindketten tokeletesen jatszanak akkor az egyik a kezdesenel fel is adhatja. mint pl az amobaban, ahol mar ismert a nyero strategia, es az 5x5-os go-ban is (lasd: http://www.cs.unimaas.nl/~vanderwerf/5x5/5x5solved.html).

szoval akit erdekel az elmelet:

- generaljuk le a jatekfat (olyan fa (kormentes graf) aminek a csucsaiban a lehetseges allasok vannak es az elek a lehetseges lepesek, a fa csucsaban a kezdoallas van (itt az ures tabla) a levelekben a vegso allasok. a fat ugy generalod, hogy a kezdoallasban meglepsz minden lehtseges lepest, a kijott allasokban a masik jatekossal leped meg az osszes lehetseges lepest, stb...

- ha kesz a fa akkor a leveleket megcimkezed, hogy ki nyert (A,B), majd ezt felfuttadod az egyel fentebbi csucsra, ha ott A lepese kovetkezik es a levelek kozott van olyan, aminek A a cimkeje akkor annak is A lesz mivel akkor ugyis olyat fog lepeni amibol o jon ki jol, ha B szintjen vagyuk azaz o jon lepesre es van olyan gyerek csucs aminek a cimkeje B akkor az o cimkeje is az lesz kulonben az ellenkezo, igy egy ido utan eljutunk a kezdoallasik ami szinten kap egy cinket A vagy B es akkor nekki van ott nyero strategiaja mivel akkor mindig tud ugy valasztani, hogy a vegen az o altal nyert levelcsucsba jussunk.

pl: tegyuk fel hogy ez a jatekfa, az o-val jelolt csucsok belso csucsok ahol A vagy B van az vegso allas, es a megjelolt jatekos nyert, a baloldalt lathato betuk, azt jelentik hogy melyik jatekos kovetkezik lepesre az adott szinten.

A        o
        / \
B      o   o
     / | \ | \
A   o  B A B B
   / \
  A  B

az a cimkek felufttatasa utan a fa igy nez ki:

A        A
        / \
B      A   B
     / | \ | \
A   A  A A B  A
   / \
  A  B


ebbol kovetkezik, hogy ebben az esetben az A jatekosnak van nyero strategiaja, ami lathato, hogy ha az elso lepesben a baloldali aghoz vezeto lepest valasztja akkor a B jatekos mar csak hatraltatni tudja az elkerulhetetlent, es a legbaloldalibbat lepi, de az A ekkor is tud olyat valasztni amibol o nyer.

remelem ertheto volt.:)

Stone


Hmmm, vajon ez válasz a kérdésemre? Persze én is a játékelméletbõl indultam ki, de valami megzavart. Ugyanis nyerõ stratégia csakis teljes információs játékok esetén értelmezhetõ. Nade: "Ha a levélelemek mind nyerõállások, akkor a stratégia nyerõ." ... és akkor ebbõl adódik a második kérdés, hogy vajon hogyan értékelhetõ egy állás? Eddigi kevés tapasztalatom szerint a go problémája, illetve a programozásának a problémája, hogy az állások értékelése nem megoldható. Nagyon eklatáns példa erre a kgs vagy a many faces becslõ értékelõje.

Tehát a kérdés volume 2: Hogyan értékelhetõ egy állás?

Persze visszatérhetünk az elsõ kérdéshez, ha valahogy ki tudjuk iktatni, hogy a gráfon való végighaladáshoz értékelni kelljen a pozíciót.

Miki


"Tehát a kérdés volume 2: Hogyan értékelhetõ egy állás?" http://321.hu/sas

Sajna nem nagyon volt idõm követni, most sincs még, de: igen, erre gondoltam.


Szervác Attila http://321.hu/sas


"Tehát a kérdés volume 2: Hogyan értékelhetõ egy állás? Persze visszatérhetünk az elsõ kérdéshez, ha valahogy ki tudjuk iktatni, hogy a gráfon való végighaladáshoz értékelni kelljen a pozíciót."

A gráfon való végighaladáshoz nem kell értékelni a poziciót. Kizárólag a végállásokat kell értékelni. Azokat pedig lehet.

Kérdés, hogy milyen nehéz olyan algoritmust irni ami eldönti, hogy ez itten egy végállás vagy nem végállás :-)

Egyébként meg kínai szabályok szerint köll programozni, azok sokkal elegánsabbak, egyértelmûbbek és matematikailag jobban megfoghatók. Példának okáért minden végjáték nyugodtan kijátszható az utolsó pontig, (hogy csak kétszemûek és sekik legyenek a pályán) így teljesen egyértelmûen kiderül mi az ábra.

(A jápán szabály persze épp ezért emberibb. :)

1 MonK


végre valaki rajtam kívül, aki kínai szabályokat szereti. amikor taní­tok, mindig azt mondom el, mert a japánt nagyon nehéz megértetni egy kezdővel.

egy ideje egyébként a nagyon nagy, nagyon gyors (ez esetben több memóriát tartalmazó, mint a világegyetem ismert részében az atomok) számítógépünk van 8-). (nem baj, minden atom egy csomó állást tárol 8-).)

egy ilyennek igazűn nem gond kiértékelni az állásokat, levelektől visszafelé.

Bohus Géza


Azért vigyázni kell, nehogy az utolsó gós atomjait is beépítsük a számítógépbe, mert akkor mi értelme az eredménynek? :)

1 MonK