Computer Go - Computer Go

Denne artikel handler om studiet af Go (spil) i kunstig intelligens. For computerprogrammeringssprog kaldet Go, se Go (programmeringssprog) .
For ikke at forveksle med Go -software .
Del af en serie om
Gå
Gå ombord del.jpg
Spilspecifikationer
Historie og kultur
Spillere og organisationer
Computere og matematik

Computer Go er feltet kunstig intelligens (AI) dedikeret til at oprette et computerprogram, der spiller det traditionelle brætspil Go . Go -spillet har været et frugtbart emne for forskning i kunstig intelligens i årtier, der kulminerede i 2017 med AlphaGo Master, der vandt tre af tre kampe mod Ke Jie , der på det tidspunkt kontinuerligt havde verdens nummer 1 -placering i to år.

Ydeevne

Go er et komplekst brætspil, der kræver intuition, kreativ og strategisk tænkning. Det har længe været betragtet som en vanskelig udfordring inden for kunstig intelligens (AI) og er betydeligt vanskeligere at løse end skak . Mange inden for kunstig intelligens anser Go for at kræve flere elementer, der efterligner menneskelig tanke end skak . Matematiker IJ Good skrev i 1965:

Gå på en computer? - For at programmere en computer til at spille et rimeligt spil Go, snarere end blot et lovligt spil - er det nødvendigt at formalisere principperne for god strategi eller at designe et læringsprogram. Principperne er mere kvalitative og mystiske end i skak, og afhænger mere af dømmekraft. Så jeg tror, ​​det vil være endnu vanskeligere at programmere en computer til at spille et rimeligt spil Go end skak.

Inden 2015 nåede de bedste Go -programmer kun at nå amatør- og niveau. På det lille 9 × 9 -bord gik computeren bedre, og nogle programmer formåede at vinde en brøkdel af deres 9 × 9 -kampe mod professionelle spillere. Før AlphaGo havde nogle forskere hævdet, at computere aldrig ville besejre topmennesker på Go.

Tidlige årtier

Det første Go -program blev skrevet af Albert Lindsey Zobrist i 1968 som en del af hans speciale om mønstergenkendelse . Det introducerede en indflydelsesfunktion til at estimere territorium og Zobrist hashing for at opdage ko .

I april 1981 offentliggjorde Jonathan K Millen en artikel i Byte, hvor han diskuterede Wally, et Go-program med et 15x15-kort, der passer ind i KIM-1- mikrocomputerens 1K RAM. Bruce F. Webster offentliggjorde en artikel i bladet i november 1984 om et Go -program, han havde skrevet til Apple Macintosh , herunder MacFORTH -kilden .

I 1998 var meget stærke spillere i stand til at slå computerprogrammer, mens de gav handicap på 25-30 sten, et enormt handicap, som få menneskelige spillere nogensinde ville tage. Der var en sag i World Computer Go Championship 1994, hvor det vindende program, Go Intellect, tabte alle tre kampe mod ungdomsspillerne, mens han modtog et handicap på 15 sten. Generelt kunne spillere, der forstod og udnyttede et programs svagheder, vinde med meget større handicap end typiske spillere.

21. århundrede

Udviklingen inden for Monte Carlo træsøgning og maskinlæring bragte de bedste programmer til højt dan -niveau på det lille 9x9 bord. I 2009 dukkede de første sådanne programmer op, som også kunne nå og holde lave rækker på dan-niveau på KGS Go-serveren på 19x19-tavlen.

I 2010, på European Go Congress 2010 i Finland, spillede MogoTW 19x19 Go mod Catalin Taranu (5p). MogoTW modtog et handicap på syv sten og vandt.

I 2011 nåede Zen 5 dan på serveren KGS og spillede spil på 15 sekunder pr. Træk. Kontoen, der nåede denne rang, bruger en klyngeversion af Zen, der kører på en 26-kerne maskine.

I 2012 slog Zen Takemiya Masaki (9p) med 11 point med fem sten handicap, efterfulgt af en 20-point sejr på fire sten handicap.

I 2013 slog Crazy Stone Yoshio Ishida (9p) i et 19 × 19 spil med fire sten handicap.

2014 Codecentric Go Challenge, en best-of-five-kamp i et lige 19x19 spil, blev spillet mellem Crazy Stone og Franz-Jozef Dickhut (6d). Ingen stærkere spiller havde nogensinde tidligere accepteret at spille en seriøs konkurrence mod et go -program på lige vilkår. Franz-Jozef Dickhut vandt, selvom Crazy Stone vandt den første kamp med 1,5 point.

2015 og fremefter: Den dybe læringstid

Yderligere information: AlphaGo versus Fan Hui , AlphaGo versus Lee Sedol og AlphaGo versus Ke Jie

I oktober 2015 slog Google DeepMind -programmet AlphaGo Fan Hui , European Go -mesteren , fem gange ud af fem under turneringsforhold.

I marts 2016 slog AlphaGo Lee Sedol i de første tre af fem kampe. Dette var første gang, at en 9-danig mester havde spillet et professionelt spil mod en computer uden handicap. Lee vandt den fjerde kamp og beskrev sin sejr som "uvurderlig". AlphaGo vandt den sidste kamp to dage senere.

I maj 2017 slog AlphaGo Ke Jie , der på det tidspunkt var placeret øverst i verden, i en tre-spil kamp under Future of Go Summit .

I oktober 2017 afslørede DeepMind en ny version af AlphaGo, kun uddannet gennem selvspil, der havde overgået alle tidligere versioner og slog Ke Jie -versionen i 89 ud af 100 spil.

Da de grundlæggende principper for AlphaGo var blevet offentliggjort i tidsskriftet Nature , kunne andre teams producere programmer på højt niveau. I 2017 var både Zen og Tencents projekt Fine Art i stand til at besejre fagfolk på meget højt niveau noget af tiden, og open source Leela Zero- motoren blev frigivet.

Hindringer for ydeevne på højt niveau

I lang tid var det en udbredt opfattelse, at computer Go udgjorde et problem, der var fundamentalt anderledes end computerskak . Det blev antaget, at metoder, der er afhængige af hurtig global søgning med relativt lidt domænekendskab, ikke ville være effektive mod menneskelige eksperter. Derfor var en stor del af computer Go udviklingsindsatsen i disse tider fokuseret på måder at repræsentere menneskelignende ekspertviden på og kombinere dette med lokal søgning for at besvare spørgsmål af taktisk karakter. Resultatet af dette var programmer, der håndterede mange situationer godt, men som havde meget markante svagheder i forhold til deres samlede håndtering af spillet. Disse klassiske programmer opnåede også næsten ingenting ved stigninger i tilgængelig computerkraft i sig selv, og fremskridtene på området var generelt langsomme.

Nogle få forskere forstod potentialet i sandsynlige metoder og forudsagde, at de ville komme til at dominere computerspil, men mange andre betragtede et stærkt Go-play-program som noget, der kun kunne opnås i den fjerne fremtid som et resultat af grundlæggende fremskridt inden for generel kunstig intelligens teknologi. Fremkomsten af ​​programmer baseret på Monte Carlo- søgning (startet i 2006) ændrede denne situation på mange måder, da de første 9-danse professionelle Go-spillere blev besejret i 2013 af multicore- computere, omend med fire-sten-handicap.

Pladestørrelse

Det store bord (19 × 19, 361 kryds) er ofte noteret som en af ​​de primære årsager til, at et stærkt program er svært at oprette. Den store tavlestørrelse forhindrer en alfa-beta-søger i at opnå et dybt blik fremad uden væsentlige søgeudvidelser eller beskæring af heuristik.

I 2002 løste et computerprogram ved navn MIGOS (MIni GO Solver) spillet Go fuldstændigt for 5 × 5 -brættet. Sort vinder og tager hele brættet.

Antal flytningsmuligheder

Fortsætter sammenligningen med skak, er Go -træk ikke så begrænset af spillereglerne. Ved det første træk i skak har spilleren tyve valgmuligheder. Go -spillere begynder med et valg af 55 forskellige juridiske træk, der tegner sig for symmetri. Dette tal stiger hurtigt, da symmetrien brydes, og snart skal næsten alle de 361 punkter på tavlen evalueres. Nogle træk er meget mere populære end andre, og nogle bliver næsten aldrig spillet, men alle er mulige.

Evalueringsfunktion

Selvom en materialetællingsevaluering ikke er tilstrækkelig til anstændigt spil i skak, er materialebalance og forskellige positionelle faktorer som bondestruktur let at kvantificere.

Disse typer af positionelle evalueringsregler kan ikke effektivt anvendes på Go. Værdien af ​​en Go -position afhænger af en kompleks analyse for at afgøre, om gruppen er i live, hvilke sten der kan forbindes med hinanden, og heuristik omkring, i hvilken grad en stærk position har indflydelse, eller i hvilken grad en svag position kan angribes.

Mere end ét træk kan betragtes som det bedste afhængigt af hvilken strategi der bruges. For at vælge et træk skal computeren evaluere forskellige mulige resultater og beslutte, hvilket der er bedst. Dette er vanskeligt på grund af de sarte afvejninger, der findes i Go. For eksempel kan det være muligt at fange nogle fjendtlige sten på bekostning af at styrke modstanderens sten andre steder. Om dette er en god handel eller ej kan være en vanskelig beslutning, selv for menneskelige spillere. Den beregningsmæssige kompleksitet viser også her, da et træk måske ikke umiddelbart er vigtigt, men efter mange træk kan blive meget vigtigt, efterhånden som andre områder af tavlen tager form.

Kombinerende problemer

Nogle gange nævnes det i denne sammenhæng, at forskellige vanskelige kombinatoriske problemer (faktisk ethvert NP-hårdt problem) kan konverteres til Go-lignende problemer på et tilstrækkeligt stort bord; det samme gælder imidlertid for andre abstrakte brætspil, herunder skak og minestryger , når de er passende generaliseret til et bræt af vilkårlig størrelse. NP-komplette problemer har i deres generelle tilfælde ikke en tendens til at være lettere for uhjælpede mennesker end for passende programmerede computere: det er tvivlsomt, at uhjælpede mennesker ville være i stand til at konkurrere med succes med computere om f.eks. At løse eksempler på delmængdesummen .

Slutspil

I betragtning af at slutspillet indeholder færre mulige træk end åbningen ( fuseki ) eller mellemspillet , kan man formode, at det er lettere at spille, og dermed at en computer let skal kunne tackle det. I skak klarer computerprogrammer sig generelt godt i skak -endspil , især når antallet af brikker er reduceret i det omfang, det gør det muligt at drage fordel af løste slutspilsbordbaser .

Anvendelsen af surrealistiske tal på slutspillet i Go, en generel spilanalyse, som John H. Conway var banebrydende for , er blevet videreudviklet af Elwyn R. Berlekamp og David Wolfe og skitseret i deres bog, Mathematical Go ( ISBN  978-1-56881- 032-4 ). Selvom det ikke er generelt nyttigt i de fleste spilleforhold, hjælper det i høj grad med analysen af ​​bestemte positionsklasser.

Ikke desto mindre, selvom der er gennemført omfattende undersøgelser, har Go endgames vist sig at være PSPACE-hårde . Der er mange grunde til, at de er så hårde:

  • Selvom en computer kan spille hvert lokale slutspilsområde fejlfrit, kan vi ikke konkludere, at dens spil ville være fejlfrie i forhold til hele brættet. Yderligere betragtningsområder i slutspil omfatter sente- og gote -relationer, prioritering af forskellige lokale slutspil, territorialtælling og estimering og så videre.
  • Slutspillet kan involvere mange andre aspekter af Go, herunder 'liv og død', som også er kendt for at være NP-hårde .
  • Hvert af de lokale slutspilsområder kan påvirke hinanden. Med andre ord er de dynamiske i naturen, selvom de er visuelt isolerede. Dette gør det svært at ræsonnere for både computere og mennesker. Denne natur fører til nogle komplekse situationer som Triple Ko, Quadruple Ko, Molasses Ko og Moonshine Life.

Således kan traditionelle Go -algoritmer ikke spille Go -slutspillet fejlfrit i den forstand at beregne det bedste træk direkte. Stærke Monte Carlo-algoritmer kan stadig klare normale Go-slutspilsituationer godt nok, og generelt er det usandsynligt, at de mest komplicerede klasser af liv-og-død-slutspilsproblemer vil dukke op i et spil på højt niveau.

Spillerækkefølge

Monte-Carlo-baserede Go-motorer har et ry for at være meget mere villige til at spille tenuki , bevæger sig andre steder på brættet frem for at fortsætte en lokal kamp end menneskelige spillere. Det kan være svært at beregne, hvornår et specifikt lokalt træk er påkrævet. Dette blev ofte opfattet som en svaghed tidligt i programmets eksistens. Når det er sagt, har denne tendens vedvaret i AlphaGos spillestil med dominerende resultater, så dette kan mere være en "finurlighed" end en "svaghed".

Taktisk søgning

En af de største bekymringer for en Go -spiller er, hvilke grupper af sten der kan holdes i live, og hvilke der kan fanges. Denne generelle klasse af problemer er kendt som liv og død . Den mest direkte strategi til beregning af liv og død er at udføre en træsøgning på de træk, der potentielt kan påvirke de pågældende sten, og derefter registrere status for stenene i slutningen af ​​hovedlinjen.

Men inden for tids- og hukommelsesbegrænsninger er det generelt ikke muligt med fuldstændig nøjagtighed at bestemme, hvilke bevægelser der kan påvirke 'livet' for en gruppe sten. Dette indebærer, at der skal anvendes noget heuristisk for at vælge, hvilke træk der skal overvejes. Nettoeffekten er, at der for et givet program er en afvejning mellem afspilningshastighed og livs- og dødslæseevner.

Med Bensons algoritme er det muligt at bestemme de kæder, der ubetinget er i live og derfor ikke skal kontrolleres i fremtiden af ​​hensyn til sikkerheden.

Statens repræsentation

Et problem, som alle Go -programmer skal tackle, er, hvordan man repræsenterer den aktuelle tilstand i spillet. For programmer, der bruger omfattende søgeteknikker, skal denne repræsentation kopieres og/eller ændres for hvert nyt hypotetisk træk, der overvejes. Dette behov sætter den yderligere begrænsning, at repræsentationen enten skal være lille nok til at blive kopieret hurtigt eller fleksibel nok til, at et træk kan foretages og let kan fortrydes.

Den mest direkte måde at repræsentere et bræt på er som et en- eller todimensionalt array, hvor elementer i arrayet repræsenterer punkter på tavlen og kan indtage en værdi, der svarer til en hvid sten, en sort sten eller et tomt skæringspunkt . Yderligere data er nødvendige for at gemme, hvor mange sten der er blevet fanget, hvis tur det er, og hvilke kryds der er ulovlige på grund af Ko -reglen .

De fleste programmer bruger imidlertid mere end bare rå bordinformation til at evaluere positioner. Data såsom hvilke sten der er forbundet i strenge, hvilke strenge der er forbundet med hinanden, hvilke grupper af sten der er i fare for at blive fanget, og hvilke grupper af sten der reelt er døde, er nødvendige for at foretage en nøjagtig vurdering af positionen. Selvom disse oplysninger kun kan udtrækkes fra stenpositionerne, kan meget af dem beregnes hurtigere, hvis de opdateres trinvist pr. Træk. Denne trinvise opdatering kræver, at flere oplysninger gemmes som tilstanden på tavlen, hvilket igen kan få kopiering af tavlen til at tage længere tid. Denne form for afvejning er et tegn på de problemer, der er forbundet med at lave hurtige computer Go-programmer.

En alternativ metode er at have et enkelt kort og foretage og tage bevægelser tilbage for at minimere kravene til computerhukommelse og have resultaterne af evalueringen af ​​tavlen gemt. Dette undgår at skulle kopiere oplysningerne igen og igen.

Systemdesign

Nye tilgange til problemer

Historisk set er GOFAI (Good Old Fashioned AI) teknikker blevet brugt til at nærme sig problemet med Go AI. For nylig er neurale netværk blevet brugt som en alternativ tilgang. Et eksempel på et program, der bruger neurale netværk, er WinHonte.

Disse tilgange forsøger at afbøde problemerne ved spillet Go med en høj forgreningsfaktor og mange andre vanskeligheder.

Computer Go -forskningsresultater anvendes på andre lignende områder såsom kognitiv videnskab , mønstergenkendelse og maskinlæring . Combinatorial Game Theory , en gren af anvendt matematik , er et emne, der er relevant for computer Go.

Designfilosofier

Det eneste valg, et program skal træffe, er, hvor den næste sten skal placeres. Denne beslutning vanskeliggøres imidlertid af den brede vifte af påvirkninger, en enkelt sten kan have på tværs af hele brættet, og de komplekse interaktioner, som forskellige stens grupper kan have med hinanden. Forskellige arkitekturer er opstået til håndtering af dette problem. Den mest populære anvendelse:

Få programmer bruger udelukkende en af ​​disse teknikker; de fleste kombinerer dele af hver i et syntetisk system.

Minimax træ søgning

En traditionel AI teknik til at skabe spil at spille software er at bruge en minimax træ søgning . Dette indebærer at udspille alle hypotetiske træk på brættet op til et bestemt punkt og derefter bruge en evalueringsfunktion til at estimere værdien af ​​den position for den aktuelle spiller. Det træk, der fører til det bedste hypotetiske bord, vælges, og processen gentages hver tur. Selvom træsøgninger har været meget effektive inden for computerskak , har de oplevet mindre succes i Computer Go -programmer. Dette skyldes dels, at det traditionelt har været svært at skabe en effektiv evalueringsfunktion til et Go -bord, og dels fordi det store antal mulige træk, hver side kan få hver til at føre til en høj forgreningsfaktor . Dette gør denne teknik meget beregningsmæssigt dyr. På grund af dette kan mange programmer, der bruger søgetræer i vid udstrækning, kun spille på det mindre 9 × 9 bord, frem for hele 19 × 19.

Der er flere teknikker, som i høj grad kan forbedre søgetræernes ydeevne med hensyn til både hastighed og hukommelse. Beskæringsteknikker såsom alfa -beta beskæring , Principal Variation Search og MTD (f) kan reducere den effektive forgreningsfaktor uden tab af styrke. På taktiske områder som liv og død er Go særligt egnet til cacheteknikker såsom transponeringstabeller . Disse kan reducere mængden af ​​gentagen indsats, især når de kombineres med en iterativ uddybende tilgang. For hurtigt at kunne gemme et Go-bræt i fuld størrelse i en transponeringstabel er en hashingteknik til matematisk opsummering generelt nødvendig. Zobrist -hashing er meget populær i Go -programmer, fordi den har lave kollisionshastigheder og kan iterativt opdateres ved hvert træk med kun to XOR'er , frem for at blive beregnet fra bunden. Selv ved hjælp af disse præstationsfremmende teknikker er fulde træsøgninger på et bord i fuld størrelse stadig uoverkommeligt langsomme. Søgninger kan fremskyndes ved hjælp af store mængder domænespecifik beskæringsteknik, f.eks. Ikke at overveje træk, hvor din modstander allerede er stærk, og selektive udvidelser som altid at overveje træk ved siden af ​​grupper af sten, der er ved at blive fanget . Begge disse muligheder medfører imidlertid en betydelig risiko for ikke at overveje et vigtigt træk, som ville have ændret spillets gang.

Resultater af computerkonkurrencer viser, at mønstermatchningsteknikker til at vælge en håndfuld passende træk kombineret med hurtige lokaliserede taktiske søgninger (forklaret ovenfor) engang var tilstrækkelige til at producere et konkurrencedygtigt program. For eksempel var GNU Go konkurrencedygtig indtil 2008.

Videnbaserede systemer

Nybegyndere lærer ofte meget af spilrekorden for gamle spil, der spilles af mesterspillere. Der er en stærk hypotese, der tyder på, at erhvervelse af Go -viden er en nøgle til at få en stærk computer til at gå. For eksempel hævder Tim Kinger og David Mechner, at "det er vores overbevisning, at med bedre værktøjer til at repræsentere og vedligeholde Go -viden vil det være muligt at udvikle stærkere Go -programmer." De foreslår to måder: genkende fælles konfigurationer af sten og deres positioner og koncentrere sig om lokale kampe. "Go -programmer mangler stadig både kvalitet og kvantitet af viden."

Efter implementering har brugen af ​​ekspertviden vist sig at være meget effektiv til programmering af Go -software. Hundredvis af retningslinjer og tommelfingerregler for stærkt spil er blevet formuleret af både højtstående amatører og professionelle. Programmørens opgave er at tage disse heuristikker , formalisere dem til computerkode og bruge mønstermatchning og mønstergenkendelsesalgoritmer til at genkende, når disse regler gælder. Det er også vigtigt at have et system til at bestemme, hvad der skal gøres, hvis to modstridende retningslinjer er gældende.

De fleste af de relativt vellykkede resultater stammer fra programmørers individuelle færdigheder på Go og deres personlige formodninger om Go, men ikke fra formelle matematiske påstande; de forsøger at få computeren til at efterligne den måde, de spiller Go. "De fleste konkurrencedygtige programmer har krævet 5-15 års års indsats og indeholder 50-100 moduler, der omhandler forskellige aspekter af spillet."

Denne metode har indtil for nylig været den mest succesrige teknik til at generere konkurrencedygtige Go-programmer på et bord i fuld størrelse. Nogle eksempler på programmer, der har været stærkt afhængige af ekspertviden, er Handtalk (senere kendt som Goemate), The Many Faces of Go, Go Intellect og Go ++, der hver især på et tidspunkt er blevet betragtet som verdens bedste Go -program.

Ikke desto mindre svækker tilføjelse af kendskab til Go nogle gange programmet, fordi en vis overfladisk viden kan medføre fejl: "de bedste programmer spiller normalt gode træk på masterniveau. Men som alle spilspillere ved, kan bare et dårligt træk ødelægge et godt spil. Programmets præstation over et helt spil kan være meget lavere end masterniveau. "

Monte-Carlo metoder

Hovedartikel: Monte-Carlo træsøgning

Et stort alternativ til at bruge håndkodet viden og søgninger er brugen af Monte Carlo-metoder . Dette gøres ved at generere en liste over potentielle træk, og for hvert træk udspille tusindvis af spil tilfældigt på det resulterende bræt. Det træk, der fører til det bedste sæt tilfældige spil for den aktuelle spiller, vælges som det bedste træk. Fordelen ved denne teknik er, at den kræver meget lidt domænekendskab eller ekspertinput, idet afvejningen er øgede hukommelses- og processorbehov. Fordi de træk, der bruges til evaluering, genereres tilfældigt, er det imidlertid muligt, at et træk, der ville være fremragende bortset fra et specifikt modstanders svar, fejlagtigt ville blive vurderet som et godt træk. Resultatet af dette er programmer, der er stærke i en overordnet strategisk forstand, men som er ufuldkomne taktisk. Dette problem kan afhjælpes ved at tilføje noget domænekendskab i trækgenerationen og et større søgedybde oven på den tilfældige udvikling. Nogle programmer, der bruger Monte-Carlo-teknikker, er Fuego, The Many Faces of Go v12, Leela, MoGo, Crazy Stone , MyGoFriend og Zen.

I 2006 blev en ny søgeteknik, øvre tillidsgrænser for træer (UCT), udviklet og anvendt på mange 9x9 Monte-Carlo Go-programmer med fremragende resultater. UCT bruger resultaterne af de hidtil indsamlede play -outs til at guide søgningen langs de mere vellykkede spillelinjer, samtidig med at alternative linjer kan udforskes. UCT -teknikken sammen med mange andre optimeringer til at spille på det større 19x19 -bræt har fået MoGo til at blive et af de stærkeste forskningsprogrammer. Vellykkede tidlige applikationer af UCT -metoder til 19x19 Go inkluderer MoGo, Crazy Stone og Mango. MoGo vandt computerolympiaden i 2007 og vandt et (ud af tre) blitz -spil mod Guo Juan, 5. Dan Pro, i den langt mindre komplekse 9x9 Go. The Many Faces of Go vandt computerolympiaden 2008 efter at have tilføjet UCT-søgning til sin traditionelle videnbaserede motor.

Maskinelæring

Selvom vidensbaserede systemer har været meget effektive på Go, er deres færdighedsniveau tæt forbundet med deres programmører og tilhørende domæneksperters viden. En måde at bryde denne begrænsning på er at bruge maskinindlæringsteknikker for at give softwaren mulighed for automatisk at generere regler, mønstre og/eller styre konfliktløsningsstrategier.

Dette gøres generelt ved at lade et neuralt netværk eller en genetisk algoritme enten gennemgå en stor database med professionelle spil eller spille mange spil mod sig selv eller andre mennesker eller programmer. Disse algoritmer er derefter i stand til at udnytte disse data som et middel til at forbedre deres ydeevne. AlphaGo brugte dette med stor effekt. Andre programmer, der tidligere har brugt neurale net, har været NeuroGo og WinHonte.

Maskinindlæringsteknikker kan også bruges i en mindre ambitiøs kontekst til at indstille specifikke parametre for programmer, der hovedsageligt er afhængige af andre teknikker. For eksempel lærer Crazy Stone at flytte generationsmønstre fra flere hundrede eksempelspil ved hjælp af en generalisering af Elo -vurderingssystemet .

AlphaGo

Hovedartikel: AlphaGo

AlphaGo , udviklet af Google DeepMind , gjorde et betydeligt fremskridt ved at slå en professionel menneskelig spiller i oktober 2015 ved hjælp af teknikker, der kombinerede dyb læring og Monte Carlo træsøgning . AlphaGo er betydeligt mere kraftfuld end andre tidligere Go-programmer, og den første til at slå en 9 dan menneskelig professionel i et spil uden handicap på et bræt i fuld størrelse.

Liste over computerprogrammer til spil

Se også: Go -software
  • AlphaGo , det første computerprogram til at vinde i lige kampe mod en professionel human Go -spiller
  • AYA af Hiroshi Yamashita
  • BaduGI af Jooyoung Lee
  • Crazy Stone af Rémi Coulom (sælges som Saikyo no Igo i Japan)
  • Darkforest fra Facebook
  • Fine Art af Tencent
  • Fuego, et open source Monte Carlo -program
  • Goban, Macintosh OS X Go -program af Sen: te (kræver gratis Goban -udvidelser)
  • GNU Go , et open source klassisk Go -program
  • Go ++ af Michael Reiss (sælges som Strongest Go eller Tuyoi Igo i Japan)
  • Leela , det første Monte Carlo -program til salg til offentligheden
  • Leela Zero , en reimplementering af det beskrevne system i AlphaGo Zero papir
  • The Many Faces of Go af David Fotland (sælges som AI Igo i Japan)
  • MyGoFriend af Frank Karger
  • MoGo af Sylvain Gelly; parallel version af mange mennesker.
  • Pachi open source Monte Carlo -program af Petr Baudiš, onlineversion Peepo af Jonathan Chetwynd, med kort og kommentarer, mens du spiller
  • Smart Go af Anders Kierulf, opfinder af Smart Game Format
  • Steenvreter af Erik van der Werf
  • Zen af Yoji Ojima aka Yamato (sælges som Tencho no Igo i Japan); parallel version af Hideki Kato.

Konkurrencer mellem computer Go -programmer

Flere årlige konkurrencer finder sted mellem Go -computerprogrammer, hvor de mest fremtrædende er Go -begivenhederne ved computerolympiaden . Regelmæssige, mindre formelle konkurrencer mellem programmer, der plejede at forekomme på KGS Go Server (månedligt) og Computer Go Server (kontinuerlig).

Fremtrædende go-playing-programmer omfatter Crazy Stone, Zen, Aya, Mogo, The Many Faces of Go, pachi og Fuego, som alle er anført ovenfor; og taiwansk-forfattet koldmælk, hollandsk-forfattet Steenvreter og koreansk-forfattet DolBaram.

Historie

Den første computer Go -konkurrence blev sponsoreret af Acornsoft , og de første almindelige af USENIX . De løb fra 1984 til 1988. Disse konkurrencer introducerede Nemesis, det første konkurrencedygtige Go -program fra Bruce Wilcox og G2.5 af David Fotland , som senere ville udvikle sig til Cosmos og The Many Faces of Go.

En af de tidlige drivere til computer Go-forskning var Ing-prisen, en relativt stor pengepris, sponsoreret af den taiwanske bankmand Ing Chang-ki , der udbydes årligt mellem 1985 og 2000 på World Computer Go Congress (eller Ing Cup). Vinderen af ​​denne turnering fik lov til at udfordre unge spillere på et handicap i en kort kamp. Hvis computeren vandt kampen, blev præmien uddelt og en ny præmie annonceret: en større præmie for at slå spillerne med et mindre handicap. Serien af ​​Ing-præmier skulle enten udløbe 1) i år 2000 eller 2), da et program kunne slå en 1-dan-professionel uden handicap for 40.000.000 NT-dollars . Den sidste vinder var Handtalk i 1997 og krævede 250.000 NT-dollars for at vinde en 11-sten-handicapkamp mod tre 11–13-årige amatør 2–6 dans. På det tidspunkt, hvor prisen udløb i 2000, var den ukravede præmie 400.000 NT-dollars for at vinde en ni-sten-handicapkamp.

Mange andre store regionale Go -turneringer ("kongresser") havde en vedhæftet computer Go -begivenhed. European Go Congress har sponsoreret en computerturnering siden 1987, og USENIX -arrangementet udviklede sig til US/North American Computer Go Championship, der afholdes årligt fra 1988–2000 på US Go Congress.

Japan begyndte at sponsorere computer Go -konkurrencer i 1995. FOST Cup blev afholdt årligt fra 1995 til 1999 i Tokyo. Denne turnering blev erstattet af Gifu Challenge, der blev afholdt årligt fra 2003 til 2006 i Ogaki, Gifu. Den computer Go UEC Cup har været afholdt hvert år siden 2007.

Regelformaliseringsproblemer i computer-computerspil

Når to computere spiller et spil Go mod hinanden, er det ideelle at behandle spillet på en måde, der er identisk med to mennesker, der spiller, mens man undgår enhver indgriben fra egentlige mennesker. Dette kan dog være svært under scoringen af ​​slutspillet. Hovedproblemet er, at Go playing -software, som normalt kommunikerer ved hjælp af den standardiserede Go Text Protocol (GTP), ikke altid vil være enig med hensyn til stenens levende eller døde status.

Selvom der ikke er nogen generel måde for to forskellige programmer at "tale det ud" og løse konflikten, undgås dette problem for det meste ved at bruge kinesiske , Tromp-Taylor eller American Go Association (AGA) regler, hvor fortsat spil ( uden straf) er påkrævet, indtil der ikke er mere uenighed om status for sten på tavlen. I praksis, f.eks. På KGS Go -serveren, kan serveren formidle en tvist ved at sende en særlig GTP -kommando til de to klientprogrammer, hvilket angiver, at de skal fortsætte med at placere sten, indtil der ikke er tvivl om status for en bestemt gruppe (alle døde sten) er blevet fanget). CGOS Go-serveren ser normalt, at programmer fratræder, før et spil overhovedet har nået scoringsfasen, men understøtter ikke desto mindre en modificeret version af Tromp-Taylor-regler, der kræver en fuld afspilning.

Disse regelsæt betyder, at et program, der var i en vindende position i slutningen af ​​spillet under japanske regler (når begge spillere har bestået) kan tabe på grund af dårligt spil i opløsningsfasen, men dette er ikke en almindelig begivenhed og betragtes som en normal del af spillet under alle områdets regelsæt.

Den største ulempe ved ovenstående system er, at nogle regelsæt (f.eks. De traditionelle japanske regler) straffer spillerne for at foretage disse ekstra træk, hvilket forhindrer brug af ekstra playout til to computere. Ikke desto mindre understøtter de fleste moderne Go -programmer japanske regler mod mennesker og er kompetente i både spil og scoring (Fuego, Many Faces of Go, SmartGo osv.).

Historisk set var en anden metode til at løse dette problem at få en ekspert menneskelig dommer til det sidste bord. Dette introducerer imidlertid subjektivitet i resultaterne og risikoen for, at eksperten ville gå glip af noget, programmet så.

Test

Mange programmer er tilgængelige, der giver computer Go -motorer mulighed for at spille mod hinanden, og de kommunikerer næsten altid via Go Text Protocol (GTP).

GoGUI og dets addon gogui-twogtp kan bruges til at afspille to motorer mod hinanden på et enkelt computersystem. SmartGo og Many Faces of Go har også denne funktion.

For at spille så mange forskellige modstandere som muligt tillader KGS Go -serveren Go engine vs. Go engine -spil samt Go engine vs. human i både rangerede og urangerede kampe. CGOS er en dedikeret computer vs. computer Go -server.

Se også

Referencer

Yderligere læsning

eksterne links