Go programozás

A Go Wiki wikiből

Területszámítás[szerkesztés]

Ezen az ötleten már egy ideje gondolkodom, és most megosztom veletek. Az algoritmust, ha kiegészítenénk valami utólagos halott alakzat levevéssel, akkor már elég jó kiértékelőfüggvényt kapnánk.

A halott alakzat detektálásra a szerintem legjobb eljárás az lenne amit a Many Faces of Go is használ, azaz negyed-, fél-, háromnegyed-, egészszemeket számolunk, és abból vonunk le következtetést, hogy az alakzat él-e. Ez irányban is gondolkodtam (gondolkodtunk) már egy ideje, de még nem sikerült a kidolgozni a megfelelő eljárást.

Az algoritmus[szerkesztés]

  1. Színezzük be a tábla üres mezőit olyan színnel mint amiből körülötte a legtöbb van, mindezt párhuzamosan az összes mezőre (azért, hogy az éppen beszínezett mező ne befolyásolja a mellette lévőt).
  2. Ismételjük az 1. lépést addig amíg van szabad mező a táblán.

Egy példa[szerkesztés]

Legyen ez az alapállás.


Az első lépés után ezt kapjuk. A pirossal jelzett mezők félig a fehérhez félig a feketéhez tartoznak.


Az második lépés után ezt kapjuk.


Az harmadik lépés után ezt kapjuk. És láthatjuk, hogy a fekete vezet 14 - 11-re.


--Stone 2005. március 10., 10:13 (CET)

Egy másik példa[szerkesztés]

Ez Shusaku partijának a Fülpirító lépés pillanatában történt elemzése. Az eredmény: 170 - 106 fekete javára.


Az élő alakzatok[szerkesztés]

Az itt leírtak az alapjai a Many Faces of Gonak is. Az egész a következőn alapul:

Az a-val jelzett pontok negyed szemek, a b-vel jelzettek fél szemek, a c-vel jelzettek háromnegyed szemek, a d-vel jelzettek egesz szemek. A pirossal jelzett pont a baloldali alakzatnak háromnegyed, a jobboldalinak negyed szeme. (A tábla széle negyed, míg a sarka fél szemnek minősül.)

Egy alakzat akkor él ha:

  • Van két szeme.
  • Ha van egy szeme és van egy másik egyszemű alakzattal közösen egy olyan pontja amin ha összeadjuk a szemeik értékét, akkor kiad egy egész szemet.
  • Ha van egy másik alakzattal két olyan pontja, amelyek közösen kiadnak egy-egy egész szemet.
  • Ha körben van n darab alakzat amelyekre minden szomszédos kettőnek közösen van egy-egy szeme.


Az élő alakzatok 2[szerkesztés]

A következő érdekes algoritmus a Migos Rules című doksiból való.

Ott azt írja, hogy azok az alakzatok élnek feltétel nélkül, amik akkor sem üthetők le, ha csak az egyik játékos lép a másik meg közben végig passzol. Ez első ránézésre jó ötletnek tűnt a számomra, de elég hamar tudtam ellenpéldát szerválni:

ez az alakzat élő, mivel bármikor tud mégegy szemet csinálni, de ha a fehér mindig passzol, akkor simán meglehet ölni.


Különvélemény


Egy új megközelítés[szerkesztés]

Mostanában, ahogy egyre nő a számítási teljesítmény, a programozók egy régi algoritmushoz nyúltak vissza, ez a Monte Carlo algoritmus. A lényege, hogy véletlenszerű lépésekkel annyi partit játszanak végig az adott állásból amennyit csak lehet, majd az lehetséges következő lépések szerint kiszámolják, hogy abból hány százalékban nyert és vesztett a program. Ezek után a legnagyobb nyerési százalékkal kecsegtető lépést választják.

Több program is van ami ezen az úton indult el, az egyik ezek közül a MoGo.

Bajnok go programok[szerkesztés]

Egyéb[szerkesztés]

A KGSen mostanában rendszeresen vannak go-programoknak versenyek, bővebb infóért lásd: http://www.intelligentgo.org/en/index.html

Külső hivatkozások[szerkesztés]