Go programozás
A Go Wiki wikiből
Tartalomjegyzék |
[szerkesztés] Területszámítá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.
[szerkesztés] Az algoritmus
- 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).
- Ismételjük az 1. lépést addig amíg van szabad mező a táblán.
[szerkesztés] Egy példa
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)
[szerkesztés] Egy másik példa
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.
[szerkesztés] Az élő alakzatok
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.
[szerkesztés] Az élő alakzatok 2
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.
[szerkesztés] Egy új megközelíté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.
[szerkesztés] Egyéb
A KGSen mostanában rendszeresen vannak go-programoknak versenyek, bővebb infóért lásd: http://www.intelligentgo.org/en/index.html
