Dezvoltarea de programe de calculator capabile să joace Go este o problemă a inteligenței artificiale . Această problemă este considerată una dintre cele mai complexe de rezolvat, algoritmii clasici ( minimax și alfa-beta ) oferind rezultate slabe.
Primul program a fost scris în 1968 de Albert Zobrist (în) ca parte a tezei sale despre recunoașterea tiparelor . Abia în 2015 un program AlphaGo a învins mai întâi un jucător profesionist de go , Fan Hui , campion european de go, înainte de a-l învinge pe Lee Sedol , unul dintre cei mai buni jucători din lume, înmartie 2016și Ke Jie , cel mai bun jucător din lume, înmartie 2017.
La fel ca în toate jocurile, trebuie să jucați o lovitură care vă îmbunătățește situația și o înrăutățește pe cea a adversarului. Pentru a estima o situație în șah, o estimare bună este să numărați numărul de piese de pe tabla de șah, ponderându-le (1 punct pe pion, 5 pe tura ...) și ajustând valoarea găsită de libertăți, părțile protectie ...
Aceasta implică calculul unei funcții de evaluare, asocierea scorurilor fiecăruia dintre adversari cu fiecare nod.
Este dificil de realizat cu go: nu există o funcție de evaluare (estimarea valorilor antagonice ale unei poziții) care să nu necesite - printre altele - capacități „umane” de „recunoaștere a tiparelor”, „experiența” jocurilor. „deja jucat și o„ adâncime de calcul ”foarte mare.
Tehnica de explorare a diferitelor posibilități (pentru fiecare mișcare, determinarea celui mai bun răspuns posibil, apoi cel mai bun răspuns la asta și așa mai departe ...), mai tehnic așa-numita metodă minimax , eșuează din mers din cauza cantității uriașe de mișcări plauzibile, lungimea jocurilor și complexitatea crescândă (în șah, complexitatea este - ea - scade prin scăderea numărului de piese rămase).
Numărul de poziții juridice este estimat la 10.170 - pe un goban de 19 × 19 (împotriva a aproximativ 10 40 în șah - pe o tablă de șah 8 × 8), în timp ce arborele de joc acoperă 10.600 de jocuri plauzibile (împotriva a aproximativ 10.120 în șah).
Creșterea puterii computerelor are o influență foarte mică asupra nivelului programelor Go, iar problema go este adesea privită ca una dintre marile provocări ale inteligenței artificiale .
Primul turneu mașină la mașină a fost organizat în 1984 de compania Acorn Computers și a fost câștigat de programatorul polonez Bronislaw Przybyla. Toate cele opt programe se joacă conform regulilor (cu excepția unei dificultăți în timpul unei lupte ko ), dar se joacă „teribil de sărac” .
Spre deosebire de programele de șah care au concurat împotriva unor profesioniști de top din anii 1990, programele Go au început să atingă nivelul jucătorilor profesioniști Go doar în 2013. Anterior, pe tablele de dimensiuni mici 9 × 9, cele mai bune programe atinseseră în 2005 nivelul jucătorilor amatori. în dan , dar tehnicile care au permis această progresie au dat doar rezultate mixte pe dimensiunea normală a plăcii de 19 × 19, iar nivelul în dan a rămas neatins până la apariția programelor bazate pe algoritmul Monte-Carlo în 2006.
Înainte de acea dată, un jucător mediu era capabil să învingă cele mai bune programe și câțiva jucători buni, instruiți în mod specific, îi bătuseră cu handicapuri de până la 30 de pietre, ceea ce ar fi imposibil pentru un jucător uman, chiar și pentru un jucător foarte neexperimentat. Astfel , în 1997 , Janice Kim, Shodan profesionale ( 1 st dan pro.), Beat programul Handtalk în ciuda 25 de pietre handicap , apoi în 1998 , Martin Müller, 6 - lea Dan amatori pisate se confruntă cu multe Go , în ciuda un handicap de 29 de pietre.
Pe gobanii mici, calculele sunt mai ușor de efectuat. În 2002 , clearance-ul pe un goban 5 × 5 a fost rezolvat de programul MIGOS (MIni GO Solver) al lui Erik van der Werf, rod al examinării a 4.472.000.000 de poziții (aproximativ 4 ore pe un P4 2.0 GHz ). Teza sa dezvoltă în continuare rezoluția 5 × 5 go.
Una dintre principalele alternative la utilizarea cunoștințelor și a cercetării este utilizarea metodelor Monte-Carlo . Pentru aceasta este suficient să enumerați mișcările posibile și ca fiecare mișcare să joace mii de părți la întâmplare. Miscarea care duce la cel mai bun rezultat pentru jucătorul actual se presupune că este cea mai bună mișcare. Avantajul acestei metode este că necesită puține cunoștințe specifice, dar dezavantajul este că este scump în ceea ce privește memoria și timpul procesorului. În plus, deoarece mișcările utilizate pentru evaluare sunt alese la întâmplare, este posibil ca o mișcare care ar fi excelentă, cu excepția unui răspuns specific, să fie aleasă din greșeală ca o mișcare bună. Rezultatul este un program puternic din punct de vedere strategic, dar tactic slab. Această problemă poate fi compensată prin adăugarea de cunoștințe pentru generarea de hituri și o profunzime mai mare a cercetării înainte de evaluarea Monte Carlo. Printre programele care folosesc tehnici Monte Carlo se numără MoGo, Crazy Stone , Olga și Gobble.
În 2006, o nouă tehnică, limitele superioare de încredere aplicate copacilor (UCT), a fost dezvoltată și utilizată de multe programe 9 × 9 cu rezultate excelente. UCT folosește rezultatele play out-urilor jucate până acum pentru a ghida explorarea, permițând în același timp explorarea secvențelor alternative. UCT și multe alte optimizări au făcut din MoGo unul dintre cele mai puternice programe produse de un cercetător. Printre primele aplicații de succes ale metodei UCT pe 19 × 19 putem găsi MoGo, CrazyStone și Mango. Mogo a câștigat 2007 de calculator Olimpiada si a castigat unul din cele trei blitzes împotriva Guo Juan , profesionale 5 - lea dan, pe 9 × 9 Goban . The Many Faces of Go a câștigat Olimpiada de computer din 2008 după ce a adăugat UCT la metodele lor clasice de cercetare.
În 2008, datorită paralelizării eficiente, MoGo a câștigat un joc (din trei) împotriva lui Cătălin Taranu, al 5- lea profesionist, pe 9 × 9 cu timpi clasici (30 de minute pentru fiecare jucător). MoGo rulează pe un cluster furnizat de Bull (32 de noduri cu 8 nuclee pe nod, fiecare rulând la 3 GHz ). Aparatul nu a fost disponibil în timpul unuia dintre meciurile pierdute. MoGo a jucat, de asemenea, un joc de 19 × 19 împotriva lui Cătălin Taranu și a pierdut în ciuda unui avantaj cu handicap de 9 pietre. Cu toate acestea, MoGo a fost într-o poziție bună în timpul acestui joc și a pierdut din cauza unei alegeri slabe într-un knockout . Mașina folosită pentru acest eveniment (provocarea IAGO, organizată de compania „Recitsproque”) a fost o mașină bună, dar departe de cele mai bune standarde din industrie.
7 august 2008MoGo a câștigat un joc de 19 × 19 împotriva lui Kim MyungWan , pro-al 8- lea dan, MoGo având un avantaj cu handicap de 9 pietre. MoGo a câștigat (cu 0,5 puncte, dar această victorie nu este atât de apropiată pe cât pare, programul îl joacă în siguranță și pierde puncte de îndată ce este sigur că va câștiga). Kim MyungWan a folosit aproximativ 13 minute, în timp ce MoGo a folosit aproximativ 55 de minute, însă nu crede că folosind mai mult timp l-ar fi salvat. MoGo rulează din Olanda pe un supercomputer cu 800 de noduri, fiecare conținând 4 nuclee care rulează la 4,7 GHz pentru a produce 15 Teraflops . MyungWan și MoGo au jucat în total 4 jocuri cu handicap variabil și limită de timp, fiecare câștigând două. Înregistrările jocurilor sunt accesibile pe serverul KGS go unde Mogo a jucat sub pseudonimul MogoTitan.
În 2009, au avut loc alte victorii împotriva profesioniștilor cu handicapuri mai mici (prin programe precum Crazy Stone ); în plus, Zen (programul pentru medalia de aur a Jocurilor Olimpice din 2009) s-a clasat constant între 1 și 2 dan pe KGS .
Zen, în special, apoi a cunoscut o progresie mai lent , dar constant, aducându - l la începutul anului 2012 la un nivel de 4 - lea dan pe KGS , și chiar 6 - lea dan în jocurile rapide; în timpul unui meci de expoziție împotriva lui Takemiya Masaki , el a câștigat succesiv un joc cu 5 pietre handicap, apoi un joc cu 4 pietre.
În octombrie 2015, programul AlphaGo dezvoltat de Google DeepMind , care combină mai multe tehnici, inclusiv învățarea profundă , a făcut un nou pas la care experții au crezut că nu poate fi atins de mulți ani: îl învinge pe Fan Hui , cel mai bun jucător european, profesionist 2 fără handicap. e dan, cu scorul de cinci victorii la zero în jocurile lente și trei-două în jocurile rapide.
În martie 2016, îl învinge pe Lee Sedol , jucătorul al 9- lea dan, considerat apoi unul dintre cei mai buni jucători din lume, câștigând succesiv primele trei jocuri, apoi al cincilea dintr-un meci de cinci jocuri . Acest meci este urmărit în direct pe internet și calificat drept un moment istoric.
Performanța AlphaGo îi determină pe mulți programatori să încerce să dezvolte sisteme similare; astfel, înnoiembrie 2016, o versiune îmbunătățită a Zen, Deep Zen, reușește să câștige un joc în trei la egalitate împotriva Cho Chikun .
În timp ce o versiune îmbunătățită a AlphaGo bate, în jocurile rapide neoficiale jucate devreme ianuarie 2017pe serverele chinezești, unii dintre cei mai buni jucători din lume ( Ke Jie , Iyama Yuta , Gu Li etc.) cu un scor uluitor de 60 de victorii la zero, JueYi, un program chinez care folosește aceiași algoritmi reușește, cu rezultate similare puțin mai slab, de atins înmartie 2017al 10- lea nivel de pe serverul FoxGo. În 2019, cele mai bune programe ( Arte plastice (ro) , Golaxy etc.) au returnat în mod constant două pietre de handicap celor mai buni profesioniști, care ar corespunde unui nivel de al 11- lea dan (amator).