Vita:Go programozás

Innen: Go Wiki
Ugrás a navigációhozUgrás a kereséshez

Ami eddig itt szerepel, az mind gyakorlatilag taktika és harc. Valami startégiai dolog is kellene.

(Redulált elágazási tényezőjű) alfa-beta keresés, eseleg egy kis neuronhálóval megsegítve. --Stone 2007. február 1., 20:22 (CET)


Vitatkoznék azon, hogy "Az élő alakzatok 2"-ben hozott ellenpélda jó.

Az említett alakzat éppen azért nem tekinthető még élőnek, mert sötét el tudja pusztítani, ha világos csak passzol.


Tehát ez az alakzat még gyengébb,


mint ez.


Hogy még egyértelműbb legyen, nézzük az alábbi példát.


Ebben a helyzetben már világosnak mindenképpen védenie kell.


És hogy egyáltalán ne legyen egyértelmű, világosnak nem kell védekeznie - rögtön, vagyis bevárhatja fekete támadását - ugyanis a és b miai. Fekete csak sekit, vagy kölcsönös két szemet érhet csak el. Üdv phoward


Élő alakzatok 1.[szerkesztés]

Sokat nem értek a go programozáshoz, így a saját meglátásaimat közlöm az "Élő alakzatok (1.)" szakasszal kapcoslatban. Az alapötlet jó, de véleményem szerint hiányzik belőle a rekurzió. Így önmagában élő alakzatnak tekint egy olyan alakzatot is, aminek két szeme van, de az egyik szemet egy nem élő alakzat határol (hamis szem).

A másik hiba, hogy esetleg nem élőként kezel olyan alakzatot, ami a fenti kritériumoknak nem felel meg, viszont gyakorlatilag leüthetetlen.

Itt kérdés, hogy a második, harmadik, negyedik szabály egyetlen alakzatról szó-e, vagy többről?

  • Ha egyről, akkor a c-vel jelölt szemekkel szomszédos alakzatokat nem fogja élőnek tekinteni, ami hibás döntés, mert egy előnyösebb lépés, vagy passz helyet össze akarja őket kötni (ráadásul ezzel területet is veszít).
  • Ha többről, akkor viszont élőnek tekinti a jobb alsó sarokban látható köveket, ami megint csak hibás döntés, hiszen hagyni fogja körbekeríteni, és - egyéb algoritmustól függően - akár egyenként kiszúrni a szemeket.


Az én elképzelésem inkább közelebb áll a tényleges leüthetetlenség megfogalmazásához. (Azt nem tudom mennyivel több számítási kapacitást igényel.) Íme:

Keressük meg a kváziszemeket


Nézzük meg, melyik alakzattal határos legalább két szem, és melyikkel egy, vagy egy sem. (Piros négyzet legalább két szemre lát rá, a piros körrel jelzettek kettőnél kevesebbre.)


Vegyük el azokat az alakzatokat, amik kettőnél kevesebb szemmel szomszédosak.


Ismételjük meg az egészet egészen addig, amíg már nem történik változás.


Végeredményként megkapjuk az ténylegesen leüthetetlen köveket


Ez természetesen nem veszi figyelembe a nagyobb szemek problémáját, azaz azt, hogy egy nagyobb szemben létrehozhatók olyan alakzatok, amiknek van élete, de az adott szem kerületén található összes életet megszüntetik.

Szintén nem veszi figyelembe, hogy egy ilyen módon nem élőnek vett alakzat több, élő alakzattal közös ponttal rendelkezhet. (Például a kiinduló ábra fehér kövei közül is van egy ilyen kő.) Bár az is igaz, hogy elvileg fekete rákényszerítheti fehéret, hogy olyan - nagyobb haszonnal, kisebb veszteséggel járó - lépéseket tegyen, ami végülis a kő, vele együtt a szem elvesztését is eredményezi. Fekete jobb alsó részén a két nem élőnek vett kő kicsit más helyzetet mutat. Első nekifutásra azt gondolom, elsősorban azér tekinthetőek a kövek - nevezzük így - élőbbnek, és a szem valódibbnak, mert az élő alakzattal közös életeiből kettő a szemen belül helyezkedik el. Ilyen esetben is lehetséges, hogy logikus lépések során el lehet veszíteni a köveket, ha a szembe behelyezett kőre nem ad választ a program, azért, hogy ezáltal lépéselőnyhöz jusson. Ilyenkor megint csak elképzelhető olyan eset, hogy ezt a két követ feláldozza egy nagyobb alakzat megmentéséért.

Szintén nem veszi figyelembe, hogy egy nagy kiterjedésű jelen pillanatban ezen az módon nem élőnek tekinthető alakzat könnyedén élővé tehető, minimum ko harc eredményeként, de akár anélkül is.

--Süsü 2007. február 6., 14:35 (CET)

Szép, korrekt algoritmust adtál, nekem tetszik. A rekurzió ilyen szintű alkalmazása nem dobja meg nagyon a számítási időt szerintem, és tényleg jobb mint az enyém.

--Stone 2007. február 6., 15:08 (CET)

Ötletek[szerkesztés]

Inkább a vitalapon írom meg. Van egy-két ötletem go programozás terén. Mint már említettem, nem ismerem az go programozást, így nem tudom nyitott kapukat döntögetek-e, mennyire megvalósítható, amit gondolok. Ezek csak ötletek, mélyebb belegondolás nélkül.

Általános ötletek[szerkesztés]


Hogyan lehet megfogalmazni a táblán található kövek jellemzőit:

Önnálló jellemzők:

  • Egyrészt ugye számít az egy alakzat életeinek száma.
  • Másrészt számít, hogy az alakzat hány kőből áll.
  • Egész jól jellemez egy alakzatot ezek aránya. (Juteszembe, a területszámító szakasz pont ezzel nem számol.) (Ez nem alakzatfelismerés ugyan, de egy alakzat formájáról sokat elárul.)
  • A szomszédos valódi és nem valódi szemek száma.


Ellenséges szomszédokkal való viszony:

  • Számíthat, hogy egy adott alakzat milyen másik ellenséges alakzatokkal határos, azok milyen fenti jellemzőkkel bírnak. (Nem kezdek el több élettel rendelkező alakzatot körbekeríteni. Inkább egy nagyobb, tömörebb alakzatokat támadok, mint egy kisebb, de "lyukacsosabb" alakzatot.)
  • Számíthat - főleg egyenlő életszám, és lépéselőny esetén -, hogy milyen közös életei vannak a szomszéddal.


Azonos alakzatok közötti viszony:

  • Számít, hogy két alakzatnak hol vannak közös életeik, és ebből mennyi van.
  • Ugyanígy számít az ellenfelek köveinél is ez az adat.


Mindez több szinten, több lépésen keresztül vizsgálható, és többféle szempontból elemezhető. Az összes alakzatra megvizsgálva meg lehet állapítani az adott alakzat szempontjából a legjobb lépéseket.

Elemzés szempontjai lehetnek:

  • Területsaccolás eredménye (csalóka)
  • Saját és ellenséges élő alakzatok, és az általuk szerzett területek.
  • Több lépés elemzése után a leütött kövek száma.
  • Alakzatok száma (ha nekünk kevesebb alakzatunk lett (kötés), és az ellenfélnek több, és ráadásul azok között sincs, vagy csak egy-egy közös élet, az jó)
  • Egy-egy alakzat jellemzőinek, és szomszédaival való viszonyának változása. (Több élete van-e, nagyobb lett-e, tömörebb lett-e, az ellenségekhez mérten több élete van-e.)


Szintek növelése:

  • Az egyik lehetséges megoldás, hogy egy alakzat adott sugarú körében vizsgálódunk. (a második szinten azokkal foglalkozunk, amik két lépésre vannak az alakzatunktól)
  • A másik lehetséges megoldás, hogy inkább a szomszédosság szerint mélyítjük az elemzést (a szomszéd szomszédja a második szint, még akkor is, ha a tábla másik végén van) (előnye, hogy messzebbre lát, viszont viszonylag telítetlen pályán gyakorlatilag a teljes pályát kellene elemezni)
  • Mindkét szempont egyszerre érvényesül.


Lehet több szintet is vizsgálni egyszerre, és ezeket is különálló szempontként kezelni. (Pl. 3-as rádiuszu kőrben ez előnyös, 5-ös rádiusznál már inkább ez. Két lehetséges lépés, ami közül majd a többi szempont és többi alakzat jó lépései alapján lehet választani.)

Lépések számának növelése:

  • Célszerű alfa-béta algoritmust használni. Ha egy adott lépés jelentős előnyt jelent, és elenyésző veszteséggel, akkor nem érdemes sokkal tovább elemezni a helyzetet, bár 1-2 lépés itt sem árt.


Mérlegelés:

  • Keressük meg a legjobb lépéseket a különböző szempontok alapján. Minden szempontnak lehet bizonyos prioritása. (Azaz fontosabb lehet két egyszemű alakzat összekapcsolása, mint egy kő megmentése.) Az a jobb lépés, ami különböző szempontok szerint - prioritással összegezve - nagyobb haszont jelent. (Ha egy alakzat növeli az életeimet, miközben a másiktól elvesz életeket, valamint még saját alakzataimat is összeköti, és az ellenfelet is szétválasztja, az bizonyára jó lépésnek tekinthető egy olyan lépéssel szemben, ami ebből csak kettő feltétel szerint hasznos.)
  • Ha egy alakzat szempontjából megvannak a legjobb lépések, akkor egyrészt azok hasznossága szerint lehet dönteni. A több alakzat szempontjából is előnyös lépéseket lehet valamilyen módon összegezni. (Nem feltétlenül összeget jelent.)


Bele lehet venni egy fordított gondolkodást, hiszen sokszor előnyös az a lépés is ami az ellenfél előnyös lépés lenne ha máshova tennénk, viszont lehet a fenti vizsgálat szerint nem tűnik annyira előnyösnek.

Finomítás:

  • Egyrészt lehet játszani azzal, hogy melyik szempontnak mennyi a súlya.
  • Lehet azt is variálni, hogy inkább "jobban körbenézünk-e", azaz a szinteket növeljük, vagy inkább a lépések számát gondoljuk-e tovább. Akár lehet paraméterezni is, hogy milyen esetben melyik célszerűbb.
  • Ezen kívül is rengeteg olyan paramétert van, ami állítható, és aminek helyes meghatározásával jobbá tehető a program.


Tanuló algoritmus[szerkesztés]


Itt arról van szó, hogy van egy adatbázis, amit meg lehet vizsgálni, és ami a lejátszott játszmák során növekszik.

Vizsgáljuk meg egy adott kő, vagy alakzat körüli területet. (Szintén lehet akár fix rádiusszal, akár adott szomszédsági szintnek megfelelően.) Keressünk olyan mintát az adatbázisban, ami 100%-ban, illetve kis eltéréssel megfelel a jelenlegi lokális helyzettel. (Nem elfeledkezve a helyzet forgatásáról, tükrözéséről, színcseréről.) Nézzük meg, melyik lépések voltak akár a játék végeredménye, akár az eredmény javítása szempontjából a legsikeresebb lépések.

Ha például egy lépésnek eléggé kétes kimenetele van, akkor lehetséges, hogy érdemesebb nagyobb sugarú körben vizsgálódni, vagy több lépést elemezni. Ennek szükségessége is tanulható, ha a program által játszott játékok egyes lépéseit külön információval látjuk el. (Például. Ebben az esetben mikor több lépés mélységben vizsgálódtam, jobb ereményt értem el, mint a sugár növelésével.)

Ötvözés[szerkesztés]


Természetesen az elemzéses, és a tanulós módszer ötvözhető, mind a potenciális lépések kiválasztásánál, mind a helyzet elemzésénél, de a tényleges lépés kiválasztásánál is.

Tanulható, hogy melyiket milyen mértékben kell figyelembe venni, mikor melyik módszer melyik szempontját kell jobban megvizsgálni.

Véleményem[szerkesztés]


Egyelőre tényleg nem körvonalazott ötletek. Valószínű a jelenlegi számítási kapacitások mellett nem is valósíhatóak meg egy programon belül, illetve túl bonyolult program lenne belőle. Sok olyan nyitott kérdés van benne, amire nincs kielégítő válaszom. Például egy - akár jó, akár rontott - lépcső sikerességét egy nagyon távoli kő, alakzat határozza meg, ami ráadásul csak nagyon sok lépés után válik kézzelfogható, valóságnak megfelelő eredménnyé. Szintén nyitott kérdés számomra a fuseki problémája, ami szerintem más algoritmust kell, hogy kövessen, bár ebből a szempontból a tanuló algoritmus jó lehet. Nagyon nehéz azt is körvonalazni, hogy egy 1 kő eltérés az adatbázisban fellelt helyzethez képest lényeges-e, vagy lényegtelen.

Ha van valakinek ötlete, (egyetértő, egyet nem értő) véleménye, esetleg tapasztalata, az egészítse, korrigálja mindezt.

--Süsü 2007. február 6., 17:00 (CET)

A játszmában az állások három szempont szerint elemzendőek: erő, pozició és idő (ez utóbbi alatt lépésszámot kell érteni). Az első kettő eléggé jól algoritmizálható, de a harmadik nem olyan egyszerű. Főleg a fuseki során fontos, hogy hatékony lépésekkel minnél jobb bázist hozzunk létre. Tempóelőnyt, illetve tempóhátrányt hogyan lehet számitógéppel kiértékelni?

--gabaux 2008. április 17., 14:40 (CET)