Kompjuterski Go

S Vikipedije, slobodne enciklopedije

Računarski Go je oblast veštačke inteligencije (VI) zadužena za pisanje računarskog programa koji igra tradicionalnu igru na tabli Go. Igra Go bila je plodonosna tema istraživanja u oblasti veštačke inteligencije proteklih decenija, koja je kulminirala 2016. godine, kada je tada najbolji program AlphaGo uspeo da pobedi jednog od najboljih ljudi koji se profesionalno bave igranjem Go-a.

Performanse[uredi | uredi izvor]

Go je kompleksna igra na tabli koja zahteva intuiciju, kreativnost i strateško razmišljanje.[1][2] Dugo se smatrala za težak izazov u okviru veštačke inteligencije i znatno je teža za rešavanje od šaha. Mnogi stručnjaci u oblasti veštačke inteligencije smatraju da Go zahteva više elemenata koji imitiraju ljudsko ponašanje nego šah.[3]

Pre 2015, najbolji Go programi su uspeli da dostignu samo amaterski dan nivo.[4] Na maloj 9h9 tabli su se bolje pokazivali, čak su i ponekada uspevali da pobede profesionalne igrače. Pre uspeha AlphaGo-a, neki istraživači su tvrdili da računarski programi nikada neće uspeti da pobede najbolje Go igrače.[5]

Rane decenije[uredi | uredi izvor]

Prvi Go program napisao je Alber Lindzi Zobrist 1968. godine kao deo svoje teze o prepoznavanju obrazaca. Tu je uvedena funkcija uticaja za procenu teritorije i zobristovo heširanje da detektuje ko.

U aprilu 1981. Godine Džonatan K. Milen je objavio članak u magazinu Byte gde je diskusovao o Go programu Wally, sa 15h15 tablom koji može da stane na KIM-1 mikroprocesorovih 1KV RAM-a. Brus F. Vebster je objavio članak u istom magazinu u novembru 1984. u kojem je pričao o Go programu koji je napisao.

Godine 1998. neki veoma jaki igrači su uspeli da pobede Go programe uz hendikep od 25-30 kamenova, što je ogroman hendikep. Bilo je slučajeva na Svetskom prvenstvu u Go-u 1994. godine gde je program koji je pobedio, Go Intellect, izgubio sve tri partije od mladih igrača Go-a koji su igrali uz hendikep od 15 kamenova.[6] U suštini, igrači koji su razumeli i iskorišćavali slabosti programa su mogli da pobede uz mnogo veći hendikep nego tipični igrači.

21. vek[uredi | uredi izvor]

Skorija napredovanja u monte karlo stablu pretraživanja i mašinskom učenju su doveli najbolje programe do viskog dan nivoa na maloj 9h9 tabli. 2009. Godine se pojavio prvi program koji je mogao da dostigne i zadrži nizak dan nivo na KGS Go serveru na 19h19 tabli.

Godine 2010. na evropskom Go kongresu u Finskoj, MogoTV je igrao na 19h19 tabli protiv Kejtlin Taranu(5p). MogoTB uspeo da pobedi uz hendikep od 7 kamenova.[7]

Godine 2011. Zen je dostigao 5 dan na KGS serveru, igrajući partije u kojima je dozvoljeno 15 sekunde po potezu. Nalog na kojem je dostignut taj nivo koristi klaster verziju Zen-a koja je bila pokrenuta na računaru sa 26 jezgara.[8]

U 2012. godini Zen je pobedio Takemiju Masakija (9p) sa 11 poena uz hendikep od 5 kamenova, a kasnije ga je pobedio sa 20 poena uz hendikep od 4 kamenova.[9]

Godine 2013. Crazy Stone je pobedio Jošio Išidu (9p) na 19h19 tabli sa 4 kamenova hendikepa.[10]

Godine 2014. na kodcentričnom Go izazovu, Crazy stone i Franc Jozef Dikhat (6d) su odigrali meč koji se sastojao od 5 partija bez hendikepa na 19h19 tabli. Ovo je najbolji igrač Go-a koji je do tada prihvatio da igra ozbiljan meč protiv Go programa na 19h19 tabli sa jednakim uslovima. Dikhat je pobedio, ali je Ludi kamen uspeo da osvoji prvu partiju sa 1.5 poena više.[11]

U oktobru 2015. godine AlphaGo program kompanije Google DeepMind pobedio je Fan Huija, evropskog Go šampiona, 5 od 5 mečeva u turnirskim uslovima.[12]

Marta 2016. godine, AlphaGo je uspeo da pobedi Li Sedola u prve tri od ukupno 5 partija.[13] Ovo je bio prvi put da 9-dan majstor igra profesionalan meč protiv programa bez hendikepa.[14] Li je pobedio u 4. meču, dok je AlphaGo uspeo da pobedi u finalnom meču.

Prepreke ka visokom nivou igranja[uredi | uredi izvor]

Dugo vremena je bilo opšteprihvaćeno mišljenje da Go program ima predstavlja problem koji se u osnovi razlikuje od šahovskog programa. Verovalo se da se metode koje se oslanjaju na brze globalne pretrage sa relativno malo znanja u domenu nisu mogle da budu efektivne protiv majstora Go-a. Zbog toga, veliki deo razvijanja Go programa tokom ovog vremena bio je usmeren na načine uz koje se moglo predstaviti čovekoliko znanje i njegovo kombinovanje sa lokalnim pretraživanjima da bi se odgovorila pitanja taktičke prirode. Rezultat ovoga bili su programi koji su se dobro nosili sa mnogo situacija, ali su imali izraženu slabost u opštem rukovanju partije. Takođe ovi programi nisu mnogo poboljšani uz povećanje procesorske moći, i napredak u oblasti je bio spor.

Neki istraživači su uvideli potencijal probabilističke metode i predvideli da će one dominirati u računarskim programima[15], ali su mnogi drugi smatrali da je jak Go program nešto što će biti moguće u dalekoj budućnosti kao rezultat velikih napretka u oblasti veštačke inteligencije. Čak je i pisanje programa za utvrđivanje pobednika završene partije bilo gledano kao netrivijalna stvar.

Dolazak programa zasnovanih na monte karlo pretrazi 2006. godine je promenio pogled na ovu situaciju u mnogim pogledima, uz prvog 9-dan majstora koji je 2013. godine doživeo poraz uz hendikep od 4 kamena.

Veličina table[uredi | uredi izvor]

Velika tabla (19h19, 361 preseka) je često bila postavljana kao jedan od glavnih razloga zašto je teško napraviti jak Go program. Velika tabla je sprečavala alfa-beta pretraživač da postigne dubok pogled bez značajne ekstenzije pretrage ili heuristike odstranjivanja.

Godine 2002, računarski program MIGOS (MIni GO Solver) kompletno je rešio igru Go na 5h5 tabli. Igrač sa crnim kamenovima pobeđuje, pritom zauzimajući celu tablu.[16]

Broj mogućih poteza[uredi | uredi izvor]

Nastavljajući upoređivanje sa šahom, potezi u Go-u nisu toliko ograničeni pravilima igre. Na prvom potezu u šahu igrač ima 20 legalnih poteza. Igrači go-a imaju 55 različitih legalnih poteza uzimajući u obzir simetriju. Ovaj broj se brzo uvećava uz razbijanje simetrije, i uskoro skoro svaki od 361 različitih poteza se moraju proceniti. Neki potezi su mnogo popularniji tokom otvaranja, ali ih je sve moguće odigrati.

Tehnike iz šaha koje se ne mogu primeniti na Go[uredi | uredi izvor]

Osnovne slabosti Go programa u poređenju sa šahovskim programima su služile da pokrenu istraživanja u mnogo novih računarskih tehnika. Tehnike koje su se pokazale kao izuzetno efektivne u šahovskim programima su se pokazale kao poprilično slabe u igranju Go-a.

Funkcija procene[uredi | uredi izvor]

Iako jednostavna procena na osnovu materijala nije dovoljna za šahovske programe, funkcije procene se često zasnivaju na tome, uz kombinaciju sa suptilnijim razmatranjima kao što su izolovani i dvostruki pijuni, topovi na otvorenim redovima, pijuni na centru table itd. Ova pravila mogu biti lako formalizovana, i takva pružaju poprilično dobro funkciju procene koja se može izvršavati brzo.

Ovakvi tipovi pravila procene na osnovu pozicije se ne mogu efikasno primeniti na Go. Vrednost Go pozicije zavisi od kompleksnog analiziranja da li je grupa živa, koji kamenovi se mogu povezati, i heuristika na to u kojoj meri dobra pozicija ima uticaja, ili u kojoj meri se loša pozicija može napasti.

Više od jednog poteza se mogu smatrati kao najbolji u zavisnosti od toga koja se strategija koristi pri proceni. Da bi izabrao potez, program mora da proceni različite ishode i da odredi koji je najbolji. Ovo je teško zbog delikatnih kompromisa koji se nalaze u Go-u. Na primer, moguće je zarobiti nekoliko protivnikovih kamenova a pritom ojačati protivnikovu poziciju na nekom drugom mestu. Pitanje da li je ovo dobar potez predstavlja tešku odluku, čak i za majstore Go-a.

Kompleksnost izračunavanja se može videti i ovde, pošto neki potez možda neće biti odmah važan, ali posle mnogo poteza kada se druge oblasti table popune, može se ispostaviti da je ovaj potez bio ključan.

Završna igra[uredi | uredi izvor]

Pošto u završnoj igri ima manje mogućih poteza nego na početku ili u srednjem periodu igre, neko će možda pretostaviti da ju je lakše igrati, i da će je stoga računarski program lakše igrati. U šahu, programi imaju lošije performanse u završetku igre pošto se ideje prožimaju kroz mnogo poteza unapred. Izuzetak su situacije kada se mogu koristiti baze podataka završnih igara u pojedinim slučajevima.

Primena nadrealnih brojeva na završnice u Go-u, opšte analize igre čiji je pionir Džon H. Konvej, dodatno je razvijena od strane Elvin R. Berlekampa i David Volfea što je navedeno u njihovoj knjizi, Matematički Go. Iako nije opšte korisno u većini pozicija, u velikoj meri pomaže pri analizi određenih klasa pozicija.

Ipak, iako su izvršene detaljne studije, dokazano je da su završne igre u Go-u PSPACE-teške. Postoje mnogi razlozi zašto su toliko teške:

  • Čak i ako kompjuter može da igra na svim lokalnim oblastima u zavržnici perfektno, ne možemo zaključiti da će njegova igra biti savršena u odnosu na celu tablu. Dodatne oblasti razmatranja u završnicama uključuju Sente i Gote odnose, dodeljivanje prioriteta različitim lokalnim završnicama, prebrojavanje teritorija i procena, i tako dalje.
  • U završnici se može sadržati mnogo drugih aspekta Go-a, uključujući "život i smrt", za koje se zna da su NP-teški.[17][18]
  • Svaka od lokalnih oblasti završnice može uticati na ostale. Drugim rečima, one su dinamične u prirodi, iako su vizuelno izolovane. Zbog toga je mnogo teže računarima da se bave sa tim. Ova priroda dovodi do nekih veoma složenih situacija.

Stoga, malo je verovatno da će biti moguće da se napiše razumno brz algoritam koji bi igrao završnicu besprekorno.

Redosled igre[uredi | uredi izvor]

Trenutni go programi bazirani na Monte-Karlo pretrazi mogu imati poteškoća pri rešavanju problema kada je redosled poteza važan.[19]

Taktička pretraga[uredi | uredi izvor]

Jedan od glavnih problema za GO igrača je koje grupe kamenova može držati u životu a koje mogu biti zarobljene. Ova opšta klasa problema je poznata kao život i smrt. Najdirektnija strategija za izračunavanje života i smrti je da se izvrši obilazak stabla o potezima koje potencijalno utiču na kamenove u pitanju, a zatim da se sačuva status kamenja na kraju glavne linije igre.

Međutim, unutar vremenskih i memorijskih ograničenja, u opštem slučaju nije moguće utvrditi sa potpunom preciznošću koji potezi bi mogli da utiču na "život" jedne grupe kamenja. Ovo znači da mora da se primeni neka heuristika za odabir poteza koje treba uzeti u obzir. Krajnji efekat je da za bilo koji program, postoji kompromis između brzine igre i procene život i smrt pozicija.

Sa Bensonovim algoritmom, moguće je odrediti lance koji su bezuslovno živi i stoga ih ne bi trebalo u budućnosti proveravati za sigurnost.

Predstavljanje stanja[uredi | uredi izvor]

Problem koji svi Go programi moraju rešiti je kako da predstave trenutno stanje igre. Za programe koji koriste opsežne pretraživačke tehnike, stanje treba da se kopira i / ili menja za svaki nov hipotetički potez koji se posmatra. Ova potreba postavlja dodatno ograničenje da bi trenutno stanje trebalo da bude ili dovoljno malo da bi moglo da se kopira brzo ili dovoljno fleksibilno da bi se potez mogao odigrati i poništiti lako.

Najlakši način je da se tabla predstavi kao jedno- ili dvodimenzionalan niz, gde elementi u nizu predstavljaju tačke na tabli, i mogu da se imaju vrednost koja odgovara belom kamenu, crnom kamenu, ili prazanoj raskrsnici. Dodatan prostor je potreban za čuvanje informacije koliko kamenova je zarobljeno, čiji je red, i koje raskrsnice su ilegalni zbog Ko pravila.

Većina programa, međutim, koristi više od informacija gde se koji kamen nalazi za procenu pozicije. Podaci kao što su koji su kamenovi povezani u žicu, koje žice su povezane jedne sa drugima, koje grupe kamenova su u opasnosti od zarobljavanja i koje grupe kamenova su efektivno mrtve, su neophodne da bi se napravila tačna procena određene pozicije. Iako se ove informacije mogu izdvojiti samo od položaja kamenova, mnogo toga se može mnogo brže izračunati ako se ažuriraju pri svakom odigranom potezu. Ovaj ažuriranje zahteva da se čuva više informacija kao predstavljanje pozicije table, što zauzvrat može učiniti da kopiranja table traju duže. Ova vrsta kompromisa ukazuje na probleme koji su uključeni u izradu brzih kompjuterskih Go programa.

Alternativni metod je da postoji samo jedna tabla na kojoj se potezi igraju i vraćaju kako bi se smanjilo korišćenje memorije a pritom da se rezultati evaluacije table sačuvaju. Ovim se izbegava da se informacije kopiraju iznova i iznova.

Dizajn sistema[uredi | uredi izvor]

Novi pristupi problemima[uredi | uredi izvor]

Istorijski gledano, DSBI (Dobra Staromodna Veštačka Inteligencija) tehnike se koriste za pristupe problemu Go VI. Odnedavno, neuronske mreže se koriste kao alternativni pristup. Jedan primer programa koji koristi neuronske mreže je WinHonte.[traži se izvor]

Ovi pristupi pokušavaju da ublaže probleme igre Go, kao što su veliki faktor grananja.

Rezultati istraživanja kompjuterskog Go-a se primenjuju u drugim sličnim oblastima kao što su kognitivne nauke, prepoznavanje oblika i mašinsko učenje.[20] Kombinatorna teorija igara, grana primenjene matematike, je tema od značaja za kompjuterski Go.[20]

Filozofije dizajna[uredi | uredi izvor]

Jedini izbor koji program treba da napravi je mesto gde da stavi svoj sledeći kamen. Međutim, ova odluka je otežana širokim spektrom uticaja koji jedan kamen može imati na celu tablu i kompleksnim interakcijama koje grupe kamenja mogu imati između sebe. Nastale su razne arhitekture za rukovanje ovim problemom. Najpopularnije koriste:

Nekoliko programo koriste isključivo jednu od ovih tehnika, dok većina kombinuje date tehnike.

Minimaks pretraga stabla[uredi | uredi izvor]

Tehnika tradicionalne VI za kreiranje softvera za igranje igara koja je korišćena je pretraga minimaks stabla. Ovo uključuje igranje svih hipotetičkih poteza do određene tačke, a zatim korišćenje funkciju evaluacije za procenu vrednosti te pozicije za tog igrača. Određuje se potez koji ima najbolju "vrednost table" i zatim se proces ponavlja za svaki potez. Dok su pretrage stabla bile veoma efikasne u kompjuterskom šahu, one su imale manje uspeha u kompjuterskim programima za igranje Go-a. To je delimično zato što je bilo teško da se napravi efikasnu funkciju evaluacije vrednosti pozicije, a i delimično zato što je veliki broj mogućih poteza koji svaka strana može da napravi dovodi do visokog faktora grananja. Zbog toga je ova tehnika veoma resursno zahtevna. Zbog toga, mnogi programi koji koriste pretrage stabala mogu intenzivno igrati samo na manjim 9 × 9 tablama.

Postoji nekoliko tehnika koje u velikoj meri mogu da poboljšaju performanse pretraživača stabala u smislu brzine i memorije. Tehnike odsecanja kao što su alfa-beta pretraga, pretraga glavne varijacije, i MTD-f mogu da smanje faktor grananja bez gubitka snage. U taktičkim oblastima kao što su "život i smrt", Go je naročito pogodan za tehnike keširanja kao što su transpozicione tabele. One mogu smanjiti količinu ponovljenog napora, naročito u kombinaciji sa pristupom pretrage u dubinu iterativnim produbljavanjem. Da bi se brzo skladištile Go table pune veličine u transpozicione tabele, potrebne su tehnike heširanja za matematičko sumiranje. Zobristovo heširanje je veoma popularno u Go programima jer ima nisku stopu sudara i može se iterativno ažurirati u svakom potezu pomoću samo dve ekskluzivne disjunkcije, umesto da se računa svaki put ispočetka. Čak i korišćenjem ovih tehnika optimizacija performansi, pretrage stabala tablepune veličine su i dalje veoma spore. Pretrage mogu biti ubrzane pomoću velikog broja tehnika odsecanja za specifičan domen, kao što je ne uzimanje u obzir poteza gde je protivnik već jak i selektivnih proširenja da uvek razmatra poteze blizu grupa kamenja koje će biti uhvaćene. Međutim, obe ove opcije donose rizik da se ne razmatra ključni potez koji bi promenio tok cele igre.

Rezultati računarskih takmičenja pokazuju da prepoznavanje oblika za biranje poteza u kombinaciji sa prethodno objašnjenim tehnikama je dovonjno da se napravi program kompetentan za takmičenje. Na primer, GNU Go je bio konkurentan do 2008. godine.

Sistemi zasnovani na prethodnom znanju[uredi | uredi izvor]

Početnici često nauče mnogo iz igara igranih od strane profesinalaca. Postoji snažna pretpostavka koja sugeriše da je sticanje znanja o Go-u ključ za stvaranje snažnog kompjuterskog Go-a. Na primer, Tim Kinger i David Mehner tvrde da "sa će boljim alatima za predstavljanje i održavanje znanja biti moguće napraviti bolje programe za igranje Go-a." Oni predlažu dva načina: prepoznavanje čestih konfiguracije kamenja i njihovih pozicija i koncentrisanje na borbe u pojedinim delovima table. "... Go programima još uvek nedostaje kvalitetu i kvantitet znanja."[21]

Nakon realizacije, korišćenje stručnog znanja se pokazalo veoma efikasno u programiranju Go softvera. Profesionalci su predstavili stotine načina i saveta za jake igre. Zadatak programera je da ove heuristike formalizuje, u implementira ih pomoću programskog koda, koristeći prepoznavanje oblika kako bi znao kada da primeni određena pravila. Takođe je važno imati sistem za određivanje šta treba uraditi kada se pojavi konflikt u igranju sledećeg poteza.

Većina relativno uspešnih rezultata dolaze iz individualnih sposobnosti programere u igranju Go-a; oni pokušavaju da naprave program tako da računar oponaša način na koji oni igraju Go. "Većini programa je potrebno 5-15 ljudskih godina truda i sadrže 50-100 modula koji se bave različitim aspektima igre."[22]

Ova metoda je donedavno bila najuspešnija tehnika u stvaranju takmičarskih Go programa koji igraju na tablama pune veličine. Neki primer programa koji su se oslanjali na ekspertsko znanje su Handtalk (kasnije poznat kao Goemate), The Many Faces of Go, Go Intellect, and Go++, od kojih je svaki u nekom trenutku smatran za najbolji Go program.

Ipak, dodavanje znanja je nekad oslabljibalo Go programe jer je površno znanje dovodilo do grešaka: "Najbolji programi obično igraju poteze majstorkog nivoa. Međutim, kao što svaki igrač zna, jedan loš potez može da uništi dobru igru. Uzimajući u obzir celu igru, preformanse programa obično mogu biti mnogo lošije od majstorskog nivoa.""[22]

Monte Karlo metode[uredi | uredi izvor]

Jedna od glavnih alternativa korišćenju ručno kodiranog znanja i pretraga je upotreba Monte Karlo metode. To se radi generisanjem liste potencijalnih poteza, a za svaki potez igranje na hiljade igara nasumice. Potez koji vodi do najboljeg skupa slučajnih igara za trenutnog igrača se bira kao najbolji potez. Prednost ove tehnike je da je potreban vrlo mali domen znanja, a kompromis je povećanje memorije i zahtevnosti procesora. Međutim, pošto su potezi koji se koriste za procenu nastaju nasumice moguće je da će potez koji bi bio odličan, osim za jedan specifičan odgovor protivnika, biti pogrešno ocenjen kao dobar potez. Rezultat toga su programi koji su jaki u celokupnom strateškom smislu, ali nisu savršeni taktički. Ovaj problem se može ublažiti dodavanjem domena znanja u generisanje poteza i veći stepen dubine pretraživanja. Neki programi koji koriste Monte Karlo metode su Fuego,[23] The Many Faces of Go v12,[24] Leela,[25] MoGo,[26] Crazy Stone, MyGoFriend[27] i Zen.

U 2006. godini je razvijena nova tehnika pretrage, gornje granice poverenja primenjena na stabla[28] i primenjena je na mnoge 9x9 Monte-Karlo Go programe sa odličnim rezultatima. Ova tehnika koristi rezultate prikupljene do sada kako bi navodila pretragu duž linije uspešnijeg igranja, dok i dalje omogućava alternativne tokove da budu istraženi. Pored mnogih optimizacija ova tehnika je omogućila da za igranje na velikim tablama 19x19 MoGo postane jedan od najjačih programa istraživanja. Uspešne prvobitne primene ove tehnike na table dimenzija 19x19 su MoGo, Crazy Stone i Mango.[29] MoGo je osvojio kopjutersku olipijadu 2007. i pobedio je jednu (od tri) blic igara protiv Guo Juan-a, profesionalnog igrača 5. dan, u mnogo manje kompleksnom 9x9 Go-u. The Many Faces of Go[30] je osvojio kopjutersku olipijadu 2008.

Mašinsko učenje[uredi | uredi izvor]

Dok su sistemi zasnovani na prethodnom znanju su bili veoma efikasni u Go-y, njihov nivo veština je usko povezan sa znanjem programera koji ih je implementirao. Jedan od načina da se ukine ovo ograničenje je da koriste tehnike mašinskog učenja kako bi se omogućilo da softver automatski generiše pravila i obrasce i vlada strategijama rešavanja kolizija.

Ovo se obično radi tako što se neuronskim mrežama ili genetskom algoritmu da velika baza podataka profesionalnih igara ili se pusti da igra protiv samog sebe ili drugih programa ili ljudi. Ovi algoritmi su tada u stanju da iskoriste ove podatke kao sredstvo za poboljšanje svojih preformansi. AlphaGo intenzivno koristi ovu tehniku. Ostali programi koji su ranije koristili neuronske mreže su NeuroGo i WinHonte.

Tehnike mašinskog učenja se takođe mogu koristiti u manje ambicioznom kontekstu, na primer za nameštanje specifičnih parametara programa koji se oslanjaju na druge tehnikama. Na primer, Crazy Stone uči generisanje poteza iz nekoliko stotina primera igara, koristeći generalizaciju Elo sistema rangiranja.[31]

AlfaGo[uredi | uredi izvor]

AlfaGo, razvijen od strane Google DeepMind, napravio je značajan napredak pobedivši ljudskog profesionalca u oktobru 2015. korišćenjem tehnike učenja sa razumevanjem i Monte Karlo pretrage stabla.[32] AlfaGo je značajno moćniji od prethodnih Go programa i prvi koji je pobedio čoveka 9. dan u igri bez hendikepa na tabli dimenzije 19x19.

Lista najpoznatijih Go programa[uredi | uredi izvor]

Takmičenja između Go programa[uredi | uredi izvor]

U toku godine se održava nekoliko takmičenja između Go programa od kojih je najistaknutije takmičenje u Go-u na kompjuterskoj olimpijadi. Manje formalna su KGS Go Server[42] koje se održava mesečno, Kompjuter Go Server[43] itd.

Istaknuti programi koji se takmiče su Crazy Stone, Zen, Aya, Mogo, The Many Faces of Go, pachi and Fuego, Steenvreter, DolBaram, coldmilk i svi gorenavedeni.

Istorija[uredi | uredi izvor]

Prvo takmičenje programa u Go-a je bilo pod pokroviteljstvom Acornsoft-a,[44] a prva redovna su bila sponzorisana od strane USENIX. Na ovim takmičenjima se pojavio Nemesis, prvi takmičarski Go program koji je napisao Brus Vilkoks, i G2.5 napisan od strane Davida Fotlanda, koji će kasnije postati Cosmos i The Many Faces of Go.

Jedan od ranih pokretača istraživanja kompjuterskog Go-a bila je Ing nagrada, relativno velika novčana nagrada pod pokroviteljstvom tajvanskog bankara Ing Chang-ki, koja se dodeljivala godišnje između 1985. i 2000. na Svetskom Kompjuterskom Go kongresu (ili Ing Kup). Pobednik ovog turnira je mogao da izazove mlade igrače u hendikep kratkom meču. Ako bi računar je pobedio, nagrada bi bila dodeljena i nova nagrada koja je bila veća ali zahtevala manji hendikep, bi bila najavljena. Rok za istek Ing nagrade je postavljen ili do 2000. godine ili dok program ne pobedi profesionalnog igrača bez hendikepa a fond je bio 40.000.000 novih tajvanskih dolara. Poslednji dobitnik je Handtalk 1997. godine, u iznosu od 250.000 novih tajvanskih dolara, pobedivši u meču sa hendikepom od 11 kamenčića protiv tri 11-13 godina stara amaterska ikrača koji su bili od 2. do 6. dana. Rok za dodeljivanje nagrade je istekao 2000. godine, ostavivši 400,000 novih tajvanskih dolara nagrade nedodeljeno.[45]

Japan je započeo sponzorisanje takmičenja programa u Go-u 1995. godine FOST Kup se održavao svake godine od 1995. do 1999. u Tokiju. Ovaj turnir je potisnut od strane Gifu Čelindža, koji se održavao svake godine od 2003. do 2006. u Ogaki, Gifu. Kompjuter Go UEC Kup se održava godišnje od 2007. godine.

Testiranje[uredi | uredi izvor]

Mnogi programi koji omogućavaju kompjuter Go mašinama da igraju jedni protiv drugih i oni skoro uvek komuniciraju preko Go Tekst Protokola (GTP).

GoGUI i njegov dodatak gogui-twogtp se može koristiti za igranje meča između dva programa na jednom sistemu.[46] SmartGo and Many Faces of Go takođe pružaju ovu mogućnost.

Da bi odigrao mečeve sa što širim spektrom protivnika, KGS Go Server dozvoljava program protiv programa kao i program protiv čoveka režim igre u mečevima koji se mogu rangirati ili ne.

Reference[uredi | uredi izvor]

  1. ^ „Google’s AI Wins First Game in Historic Match With Go Champion”. WIRED. 9. 3. 2016. 
  2. ^ AlphaGo victorious once again
  3. ^ Bouzy, Bruno; Cazenave, Tristan (9. 8. 2001). „Computer Go: An AI oriented survey”. Artificial Intelligence. 132 (1): 39—103. doi:10.1016/S0004-3702(01)00127-8. Pristupljeno 14. 3. 2016. 
  4. ^ Wedd, Nick. „Human-Computer Go Challenges”. computer-go.info. Pristupljeno 28. 10. 2011. 
  5. ^ „‘Huge leap forward’: Computer that mimics human brain beats professional at game of Go”. 
  6. ^ „CS-TR-339 Computer Go Tech Report”. Arhivirano iz originala 04. 02. 2014. g. Pristupljeno 28. 1. 2016. 
  7. ^ „EGC 2010 Tampere News”. Arhivirano iz originala 14. 8. 2009. g. Pristupljeno 28. 1. 2016. 
  8. ^ „KGS Game Archives”. Pristupljeno 28. 1. 2016. 
  9. ^ „Zen computer Go program beats Takemiya Masaki with just 4 stones!”. Go Game Guru. Arhivirano iz originala 1. 2. 2016. g. Pristupljeno 28. 1. 2016. 
  10. ^ „「アマ六段の力。天才かも」囲碁棋士、コンピューターに敗れる　初の公式戦”. MSN Sankei News. Arhivirano iz originala 24. 3. 2013. g. Pristupljeno 27. 3. 2013. 
  11. ^ „codecentric go challenge – Just another WordPress site”. Pristupljeno 28. 1. 2016. 
  12. ^ „Google AI algorithm masters ancient game of Go”. Nature News & Comment. Pristupljeno 28. 1. 2016. 
  13. ^ „Artificial intelligence: Google's AlphaGo beats Go master Lee Se-dol”. BBC News Online. 12. 3. 2016. Pristupljeno 12. 3. 2016. 
  14. ^ „Google's DeepMind defeats legendary Go player Lee Se-dol in historic victory”. www.theverge.com. Pristupljeno 9. 3. 2016. 
  15. ^ Game Tree Searching with Dynamic Stochastic Control pp. 194–195
  16. ^ „5x5 Go is solved”. Pristupljeno 28. 1. 2016. 
  17. ^ On pp. 11: "Crasmaru shows that it is NP-complete to determine the status of certain restricted forms of life-and-death problems in Go." (See the following reference.) Demaine, Erik D., Robert A. Hearn (22. 4. 2008). „Playing Games with Algorithms: Algorithmic Combinatorial Game Theory”. arXiv:cs/0106019 Slobodan pristup. 
  18. ^ Crasmaru, Marcel (1999). „On the complexity of Tsume-Go”. Lecture Notes in Computer Science. Lecture Notes in Computer Science. London, UK: Springer-Verlag. 1558: 222—231. ISBN 978-3-540-65766-8. doi:10.1007/3-540-48957-6_15. 
  19. ^ „example of weak play of a computer program”. Arhivirano iz originala 10. 07. 2012. g. Pristupljeno 19. 05. 2016. 
  20. ^ a b Müller, Martin. Computer Go[mrtva veza], Artificial Intelligence 134 (2002): p150
  21. ^ Müller, Martin. Computer Go[mrtva veza], Artificial Intelligence 134 (2002): p151
  22. ^ a b Müller, Martin. Computer Go[mrtva veza], Artificial Intelligence 134 (2002): p148
  23. ^ a b „Fuego”. 
  24. ^ a b Fotland, David. „Dan Level Go Software – Many Faces of Go”. 
  25. ^ a b „Sjeng – chess, audio and misc. software”. 
  26. ^ „Arhivirana kopija”. Arhivirano iz originala 10. 8. 2008. g. Pristupljeno 20. 5. 2016. 
  27. ^ a b „MyGoFriend – Gold Medal Winner 15th Computer Olympiad, Go (9x9)”. Arhivirano iz originala 8. 12. 2010. g. Pristupljeno 20. 5. 2016. 
  28. ^ „UCT”. 
  29. ^ „Page not found (404)”. Arhivirano iz originala 3. 11. 2007. g. Pristupljeno 20. 5. 2016. 
  30. ^ Fotland, David. „Smart Games”. 
  31. ^ „Computing Elo Ratings of Move Patterns in the Game of Go”. Pristupljeno 28. 1. 2016. 
  32. ^ „Research Blog: AlphaGo: Mastering the ancient game of Go with Machine Learning”. Google Research Blog. 27. 1. 2016. 
  33. ^ „Page ON/サービス終了のお知らせ”. Arhivirano iz originala 11. 12. 2006. g. Pristupljeno 20. 5. 2016. 
  34. ^ „Goban. Play Go on Mac – Sen:te”. Arhivirano iz originala 19. 05. 2013. g. Pristupljeno 20. 05. 2016. 
  35. ^ „Goban Extensions – Sen:te”. Arhivirano iz originala 18. 05. 2016. g. Pristupljeno 20. 05. 2016. 
  36. ^ „Go++, Go playing program”. Arhivirano iz originala 25. 05. 2003. g. Pristupljeno 09. 06. 2020. 
  37. ^ „Arhivirana kopija”. Arhivirano iz originala 28. 11. 2006. g. Pristupljeno 20. 5. 2016. 
  38. ^ „Pachi – Board Game of Go / Weiqi / Baduk”. 
  39. ^ Kierulf, Anders. „SmartGo”. 
  40. ^ „STEENVRETER”. 
  41. ^ „Zen (go program)”. 
  42. ^ „Computer Go Tournaments on KGS”. 
  43. ^ „9x9 Go Server”. Arhivirano iz originala 19. 1. 2007. g. Pristupljeno 20. 5. 2016. 
  44. ^ „Acorn 1984 The First Computer Go Tournament”. computer-go.info. 
  45. ^ Fotland, David. „World Computer Go Championships”. Pristupljeno 28. 1. 2016. 
  46. ^ „Using GoGUI to play go computers against each other”. Arhivirano iz originala 9. 3. 2011. g. Pristupljeno 20. 5. 2016. 
Preuzeto iz „https://sr.wikipedia.org/w/index.php?title=Компјутерски_Го&oldid=27755505”