Anar al contingut

Go per computadora

De L'Enciclopèdia, la wikipedia en valencià
Est artícul tracta sobre l'inteligència artificial aplicada al go. Per a el llenguage de programació vore Go (llenguage de programació).


 Esta pàgina de desambiguació enumera artículs que tenen títuls similars.
Archiu:Pachi leela go.jpg
Pachi contra Leela Zero, jugant en l'interfaç del programa Sabaki.

El go per computadora és el camp de l'inteligència artificial dedicat a crear programes informàtics que juguen al go. El go ha segut un tema fèrtil d'investigació en inteligència artificial durant décades, que va culminar en 2017 en AlphaGo Master guanyant tres de tres partides contra Ke Jie, qui en eixe moment liderava l'escalafó mundial durant dos anys.[1][2]

Rendiment

[editar | editar còdic]

Go és un joc de taula complex que requerix intuïció, pensament creatiu i estratègic.[3][4] Durant molt temps s'ha considerat un desafiu difícil en el camp de l'inteligència artificial i és considerablement més difícil[5] de resoldre que l'escacs. Molts en el camp de l'inteligència artificial consideren que el go requerix més elements que imiten el pensament humà que l'escacs.[6] matemàtic I.J. Good va escriure en 1965:[7]

¿Go en una computadora? - Per a programar una computadora per a que jugue una bona partida de go, en lloc de simplement un joc llegal, és necessari formalisar els principis d'una bona estratègia o dissenyar un programa d'aprenentage. Els principis són més qualitatius i misteriosos que en l'escacs i depenen més del juí. Aixina que crec que serà encara més difícil programar una computadora per a jugar una partida raonable de go que d'escacs.


Abans de 2015,[8] els millors programes de go solament conseguien alcançar el nivell de donen amateur.[9] En el tauler chicotet de 9 × 9, a la computadora li va anar millor, i alguns programes varen conseguir guanyar una fracció dels seus jocs de 9 × 9 contra jugadors professionals. Abans de AlphaGo, alguns investigadors havien afirmat que les computadores mai vencerien als millors humans en go.[10]

Primeres décades

[editar | editar còdic]

El primer programa de Go va ser escrit per Albert Lindsey Zobrist en 1968 com a part de la seua tesis sobre el reconeiximent de patrones.[11] Va introduir una funció d'influència per a estimar el territori i el hash de Zobrist per a detectar un ko.

En abril de 1981, Jonathan K Millen va publicar un artícul en Byte sobre Wally, un programa Go per a tauler de 15x15 que encaixava en la memòria RAM de 1K del microordenador KIM-1.[12] Bruce F. Webster va publicar un artícul en la revista en novembre de 1984 discutint un programa de go que havia escrit para Apple Macintosh, inclós el còdic font de MacFORTH.[13]


En 1998, els jugadors molt forts eren capaços de véncer als programes de computadora mentres donaven hándicaps de 25 a 30 pedres, un hándicap enorme que pocs jugadors humans prendrien. Va haver un cas en el World Computer Go Championship de 1994 en el que el programa guanyador, Go Intellect, va perdre els tres jocs contra els jugadors jovenils mentres rebia una hándicap de 15 pedres.[14] En general, els jugadors que varen entendre i varen explotar les debilitats d'un programa podien guanyar en desventages molt majors que els jugadors típics.[15]

XXI

[editar | editar còdic]

Els desenrolls en els arbres de busca de Mont Carlo i l'aprenentage automàtic varen dur els millors programes a un alt nivell de donen en el chicotet tauler de 9x9. En 2009, varen aparéixer els primers programes d'este tipo que també podien alcançar i mantindre rancs baixos de nivell donen en el servidor KGS Go en tauler de 19x19.

En 2010, en el European Go Congress de 2010 en Finlàndia, MogoTW va jugar 19x19 Go contra Cătălin Țăranu (5p). MogoTW va rebre un handicap de sèt pedres i va guanyar.[16]

En 2011, Zen va alcançar 5 donen en el servidor KGS, jugant partides de 15 segons per moviment. El conte que va alcançar eixe ranc usa una versió en clúster de Zen que s'eixecuta en una màquina de 26 núcleus.[17]

En 2012, Zen va véncer a Takemiya Masaki (9p) per 11 punts en el handicap de cinc pedres, seguit d'una victòria per 20 punts en el handicap de quatre pedres.[18]

En 2013, Crazy Stone va véncer a Yoshio Ishida (9p) en un joc de 19 × 19 en quatre pedres de handicap.[19]

El Codecentric Go Challenge 2014, una trobada al millor de cinc en un joc parell de 19x19, es va jugar entre Crazy Stone i Franz-Jozef Dickhut (6d). Cap jugador més fort havia acceptat jugar una competició séria contra un programa de go en igualtat de condicions. Franz-Jozef Dickhut va guanyar, encara que Crazy Stone va guanyar la primera partida per 1,5 punts.[20]

2015 en avant: l'era de l'aprenentage profunt

[editar | editar còdic]
Archiu:KataGoanalisis.png
KataGo, mòdul basat en les polítiques d'anàlisis d'AlphaZero, analisant una posició.

En octubre de 2015, el programa AlphaGo de DeepMind va véncer a Fan Hui, el campeó europeu de go, en cinc partides en condicions de torneig.[21]

En març de 2016, AlphaGo va véncer a Lee Sedol en les primeres tres de cinc partides.[22] Esta va ser la primera volta que un mestre de 9 donen va jugar una trobada professional contra una computadora sense handicap.[23] Lee va guanyar la quarta partida, descrivint la seua victòria com "inevaluable".[24] AlphaGo va guanyar la partida final dos dies despuix.[25][26]

En maig de 2017, AlphaGo va véncer a Ke Jie, qui en eixe moment ocupava el primer lloc en el món,[2][27] en una trobada a tres partides durant la Cim del Futur de Go.[28]

En octubre de 2017, DeepMind va revelar una nova versió de AlphaGo, entrenada solament a través del joc personal, que havia superat totes les versions anteriors, superant a la versió que va derrotar a Ke Jie en 89 de 100 jocs.[29]

Ya que els principis bàsics de AlphaGo s'havien publicat en la revista Nature, atres equips varen poder produir programes d'alt nivell. En 2017, tant Zen com el proyecte Fine Art de Tencent varen ser capaços de derrotar a professionals de molt alt nivell en algunes ocasions i es va llançar el motor Leela Zero de còdic obert.

Obstàculs per al rendiment d'alt nivell

[editar | editar còdic]

Durant molt temps, va ser una opinió generalisada que el go informàtic plantejava un problema fonamentalment diferent del escacs informàtic. Es creïa que els métodos que es basaven en una busca global ràpida en relativament poc coneiximent del domini no serien efectius contra els experts humans. Per lo tant, una gran part de l'esforç de desenroll del go informàtic es va centrar durant estos temps en formes de representar el coneiximent expert similar a l'humà i combinar-ho en la busca local per a respondre preguntes de naturalea tàctica. El resultat d'açò varen ser programes que varen manejar ben moltes situacions pero que tenien debilitats molt pronunciades en comparació al seu maneig general del joc. Ademés, estos programes clàssics no varen obtindre casi res dels auments en la potència informàtica disponible per es, i el progrés en el camp va ser en general llent.

Alguns investigadors varen captar el potencial dels métodos provabilístics i varen predir que aplegarien a dominar els jocs de computadora,[30] pero molts uns atres varen considerar que un programa fort de go és alguna cosa que solament podria conseguir-se en un futur lluntà, com a resultat d'alvanços fonamentals en la tecnologia d'inteligència artificial general. Inclús escriure un programa capaç de determinar automàticament el guanyador d'un joc terminat no es considerava un assunt trivial.

El advenimiento dels programes basats en la busca de Montecarlo (que va començar en 2006) va canviar esta situació de moltes maneres, ya que els primers jugadors professionals de go de 9 donen varen ser derrotats en 2013 per computadores multinúcleo, encara que en hándicap de quatre pedres.

Tamany del tauler

[editar | editar còdic]

El tauler gran (19 × 19, 361 interseccions) es considera a sovint com una de les principals raons per les que és difícil crear un programa sòlit. El gran tamany del tauler evita que un buscador alfa-beta conseguixca una busca profunda sense extensions de busca significatives o heurístiques de poda.

En 2002, un programa informàtic cridat MIGOS (MIni GO Solver) va resoldre per complet el joc de go per al tauler de 5 × 5. Les negres guanyen, duent-se tot el tauler.[31]

Número d'opcions de moviment

[editar | editar còdic]

Continuant en la comparació en l'escacs, els moviments de Go no estan tan llimitats per les regles del joc. Per al primer moviment en l'escacs, el jugador té vint opcions. Els jugadors de Go comencen en una selecció de 55 moviments llegals distints, tenint en conte la simetria. Este número aumenta ràpidament a mida que es trenca la simetria, i pronte deuen evaluar-se casi tots els 361 punts del tauler. Alguns moviments són molt més populars que uns atres i alguns casi mai es juguen, pero tots són possibles.

Funció d'evaluació

[editar | editar còdic]

Si be una evaluació de conteo de material no és suficient per a un joc decent en escacs, el balanç de material i varis factors posicionals com l'estructura de peons són fàcils de quantificar.

Estos tipos de regles d'evaluació posicional no es poden aplicar de manera eficient al go. El valor d'una posició de go depén d'un anàlisis complex per a determinar si un grup està viu o no, quines pedres es poden conectar entre sí i heurístiques sobre el grau en que una posició forta té influència, o el grau en que un dèbil posició pot ser atacada.


Més d'un moviment pot considerar-se el millor segons l'estratègia que s'utilise. Per a elegir un moviment, la computadora deu evaluar diferents resultats possibles i decidir quin és el millor. Açò és difícil per les delicades compensació presents en go. Per eixemple, pot ser possible capturar algunes pedres enemigues a costa d'enfortir les pedres de l'oponent en una atra part. Si es tracta d'un bon intercanvi o no, pot ser una decisió difícil, inclús per als jugadors humans. La complexitat computacional també es mostra ací, ya que un moviment podria no ser immediatament important, pero despuix de molts moviments podria tornar-se molt important a mida que atres àrees del tauler prenen forma.

Problemes combinatoris

[editar | editar còdic]

A voltes es menciona en este context que varis problemes combinatoris difícils (de fet, qualsevol problema NP-hard) poden convertir-se en problemes tipo go en un tauler suficientment gran; no obstant, lo mateix és cert per a uns atres jocs abstractes, incloent l'escacs i el buscaminas, quan es generalisen adequadament a un tauler de tamany arbitrari. Els problemes NP-complets no tendixen, en el seu cas general, a ser més fàcils per a humans sense ajuda que per a computadores adequadament programades: és dubtós que els humans sense ajuda puguen competir exitosamente contra computadores per a resoldre, per eixemple, casos del problema de suma de subconjunts.

Finals

[editar | editar còdic]

Ya que el final conté menys moviments possibles que l'obertura (fuseki) o el mig joc, un podria supondre que és més fàcil de jugar i, per lo tant, una computadora deuria poder abordar-ho fàcilment. En l'escacs, els programes de computadora generalment funcionen be en els finals d'escacs, especialment una volta que el número de peces es reduïx en la mida en que permet aprofitar les bases de taules de finals resoltes.

L'aplicació de números surreales al final del joc en go, un anàlisis general del joc iniciat per John H. Conway, ha segut desenrollat per Elwyn R. Berlekamp i David Wolfe i descrit en el seu llibre Mathematical Go (ISBN  978-1-56881- 032-4). Si ben no és d'utilitat general en la majoria de les circumstàncies de joc, és de gran ajuda per a l'anàlisis de certes classes de posicions.

No obstant, encara que s'ha realisat un estudi elaborat, s'ha demostrat que els finals de go són PSPACE-difícils. Hi ha moltes raons per les que són tan difícils:

  • Inclús si una computadora pot jugar cada àrea de joc local sense problemes, no podem concloure que les seues jugades siguen impecables sobre tot el tauler. Les àrees adicionals de consideració en els finals inclouen les relacions sente i gote, la priorisació de diferents finals locals, el conteo i l'estimació de territoris, etc.
  • Cada una de les àrees de finals locals poden afectar-se entre sí. En atres paraules, són de naturalea dinàmica encara que visualment aïllades. Açò fa que siga difícil raonar tant per a les computadores com per als humans. Esta naturalea conduïx a situacions complexes com a Triple Ko,[34] Cuádruple Ko,[35] Molasses Ko,[36] i Vida de Moonshine.[37]

Per lo tant, els algoritmes tradicionals de go no poden jugar el final de go sense problemes en el sentit de calcular el millor moviment directament. Els sòlits algoritmes de Mont Carlo encara poden manejar situacions normals de finals de go prou be i, en general, és poc provable que les classes més complicades de problemes de final de joc de vida o mort sorgixquen en un joc d'alt nivell.[38]

Orde de joc

[editar | editar còdic]

Els motors de go basats en Montecarlo tenen la reputació d'estar molt més disposts a jugar tenuki, es mou a una atra part del tauler, en lloc de continuar una baralla local que els jugadors humans. Calcular directament quàn es requerix una mudança local específica pot ser difícil.[39] Açò a sovint es percebia com una debilitat al principi de l'existència d'estos programes.[40] Dit açò, esta tendència ha persistit en l'estil de joc de AlphaGo en resultats dominants, per lo que açò pot ser més una "peculiaritat" que una "debilitat".[41]

Vore també

[editar | editar còdic]

Referències

[editar | editar còdic]
  1. ↑ «柯洁迎19岁生日 雄踞人类世界排名第一已两年». sports.sina.com.cn. Consultat el 2021-02-15.
  2. ↑ 2,0 2,1 «Go Ratings». www.goratings.org. Consultat el 2021-02-15.
  3. ↑ «[1]». Consultat el 2021-02-15 (en en-us).
  4. ↑ «AlphaGo victorious onze again» (en en). koreatimes. Consultat el 2021-02-15.
  5. ↑ Artificial Intelligence.132(1)
    39–103.ISSN 0004-3702.doi:10.1016/S0004-3702(01)00127-8.Consultat el 2021-02-15.
  6. ↑ «[2]». Consultat el 2021-02-15 (en en-US).
  7. ↑ «Go, Jack Good». www.chilton-computing.org.uk. Consultat el 2021-02-15.
  8. ↑ Nature.529(7587)
    484–489.ISSN 1476-4687.doi:10.1038/nature16961.Consultat el 2021-02-15.
  9. ↑ «Human-Computer Go Challenges». www.computer-go.info. Consultat el 2021-02-15.
  10. ↑ «‘Huge leap forward’: Computer that mimics human brain beats professional at game of Go» (en en). Science | AAAS. Consultat el 2021-02-15.
  11. ↑ Albert Zobrist (1970), Feature Extraction and Representation for Pattern Recognition and the Game of Go. Ph.D. Thesis (152 pp.), University of Wisconsin. Also published as technical report
  12. ↑ (1981-04) Byte Magazine Volume 06 Number 04 - Future Computers (en en), p. 102.
  13. ↑ (1984-11) Byte Magazine Volume 09 Number 12 - New Chips (en en), p. 125.
  14. ↑ «CS-TR-339 Computer Go Tech Report». Archivat des d'el original, el 4 de febrer de 2014.
  15. ↑ «See for instance intgofed.org». Archivat des d'el original, el 28 de maig de 2008. Consultat el 22 de giner de 2021.
  16. ↑ «EGC 2010 Tampere News». web.archive.org. Archivat des d'el original, el 14 d'agost de 2009. Consultat el 2021-02-15.
  17. ↑ «Archive de partides de KGS». www.gokgs.com. Consultat el 2021-02-15.
  18. ↑ «Zen computer Go program beats Takemiya Masaki with just 4 stones!». web.archive.org. Archivat des d'el original, el 1 de febrer de 2016. Consultat el 2021-02-15.
  19. ↑ «「アマ六段の力。天才かも」囲碁棋士、コンピューターに敗れる　初の公式戦 - MSN産経ニュース». web.archive.org. Archivat des d'el original, el 24 de març de 2013. Consultat el 2021-02-15.
  20. ↑ «codecentric go challenge | Just another WordPress site» (en en-us). Consultat el 2021-02-15.
  21. ↑ Nature News.529(7587)
    445.doi:10.1038/529445a.Consultat el 2021-02-15.
  22. ↑ «[3]». Consultat el 2021-02-15 (en en-GB).
  23. ↑ «Google's DeepMind defeats legendary Go player Lee Es-dol» (en en). The Verge. Consultat el 2021-02-15.
  24. ↑ «[4]». Consultat el 2021-02-15 (en en-GB).
  25. ↑ «Google's AlphaGo AI beats Llig Es-dol again to win Go séries 4-1» (en en). The Verge. Consultat el 2021-02-15.
  26. ↑ «After Win in China, AlphaGo's Designers Explore New AI».
  27. ↑ «柯洁迎19岁生日 雄踞人类世界排名第一已两年» (en zh).
  28. ↑ «Google's AlphaGo Continues Dominance With Second Win in China» (2017-05-25).
  29. ↑ Nature.550(7676)
    354–359.ISSN 1476-4687.doi:10.1038/nature24270.Consultat el 2021-02-15.
  30. ↑ Game Tree Searching with Dynamic Stochastic Control pp. 194–195
  31. ↑ «5x5 Go is solved». erikvanderwerf.tengen.nl. Consultat el 2021-02-15.
  32. ↑ arXiv:cs/0106019.Consultat el 2021-02-15.
  33. ↑ Marcel Crasmaru (1999). «On the complexity of Tsume-Go», Computers and Games (vol. 1558), London, UK: Springer-Verlag, pp. 222–231. doi:10.1007/3-540-48957-6_15. ISBN 978-3-540-65766-8.
  34. ↑ «Triple Ko».
  35. ↑ «Quadruple Ko».
  36. ↑ «Molasses Ko».
  37. ↑ «Moonshine Life».
  38. ↑ «Computer Go Programming».
  39. ↑ «example of weak play of a computer program».
  40. ↑ «Facebook trains AI to beat humans at Go board game – BBC News» (en en-gb).
  41. ↑ Ormerod, David (2016-03-12). «AlphaGo shows its true strength in 3rd victory against Lee Sedol». Go Game Guru.


Referències

[editar | editar còdic]


Obtingut de «https://www.lenciclopedia.org/w/index.php?title=Go_per_computadora&oldid=829392»