Computer Go -
Computer Go

Denna artikel handlar om studiet av Go (spel) i artificiell intelligens. För datorprogrammeringsspråket Go, se Go (programmeringsspråk) .
Inte att förväxla med Go -programvara .
Del av en serie om
Gå
Gå ombord del.jpg
Spelspecifika
Historia och kultur
Spelare och organisationer
Datorer och matematik

Computer Go är fältet för artificiell intelligens (AI) dedikerat till att skapa ett datorprogram som spelar det traditionella brädspelet Go . Go -spelet har varit ett bördigt ämne för artificiell intelligensforskning i årtionden, som kulminerade 2017 med AlphaGo Master som vann tre av tre matcher mot Ke Jie , som vid den tiden kontinuerligt höll världens nr 1 -ranking i två år.

Prestanda

Go är ett komplext brädspel som kräver intuition, kreativt och strategiskt tänkande. Det har länge ansetts vara en svår utmaning inom artificiell intelligens (AI) och är betydligt svårare att lösa än schack . Många inom artificiell intelligens anser att Go kräver fler element som efterliknar mänskligt tänkande än schack . Matematiker IJ Good skrev 1965:

Gå på en dator? - För att programmera en dator för att spela ett rimligt spel Go, snarare än bara ett juridiskt spel - är det nödvändigt att formalisera principerna för en bra strategi, eller att utforma ett inlärningsprogram. Principerna är mer kvalitativa och mystiska än i schack, och beror mer på omdöme. Så jag tror att det blir ännu svårare att programmera en dator för att spela ett rimligt spel Go än schack.

Före 2015 lyckades de bästa Go -programmen bara nå amatörnivå . På det lilla 9 × 9 -kortet gick datorn bättre, och vissa program lyckades vinna en bråkdel av sina 9 × 9 -spel mot professionella spelare. Innan AlphaGo hade vissa forskare hävdat att datorer aldrig skulle besegra toppmänniskor på Go.

Tidiga decennier

Det första Go -programmet skrevs av Albert Lindsey Zobrist 1968 som en del av hans avhandling om mönsterigenkänning . Det introducerade en inflytande funktion för att uppskatta territorium och Zobrist hashing för att upptäcka ko .

I april 1981 publicerade Jonathan K Millen en artikel i Byte om Wally, ett Go-program med ett 15x15-kort som passar in i KIM-1 mikrodatorn 1K RAM. Bruce F. Webster publicerade en artikel i tidningen i november 1984 om ett Go -program som han hade skrivit för Apple Macintosh , inklusive MacFORTH -källan .

1998 kunde mycket starka spelare slå datorprogram medan de gav handikapp på 25–30 stenar, ett enormt handikapp som få mänskliga spelare någonsin skulle ta. Det fanns ett fall i World Computer Go Championship 1994 där det vinnande programmet, Go Intellect, förlorade alla tre matcherna mot ungdomsspelarna samtidigt som de fick ett 15-stenars handikapp. I allmänhet kan spelare som förstod och utnyttjade ett programs svagheter vinna med mycket större handikapp än vanliga spelare.

2000 -talet

Utvecklingen inom Monte Carlo trädsökning och maskininlärning tog de bästa programmen till hög dan -nivå på den lilla 9x9 -tavlan. Under 2009 dök de första sådana program upp som kunde nå och hålla låga dan-nivåer på KGS Go Server på 19x19-kortet också.

2010, vid European Go Congress 2010 i Finland, spelade MogoTW 19x19 Go mot Catalin Taranu (5p). MogoTW fick ett handikapp med sju stenar och vann.

2011 nådde Zen 5 dan på servern KGS och spelade spel på 15 sekunder per drag. Kontot som nådde den rankningen använder en klusterversion av Zen som körs på en 26-kärnmaskin.

2012 slog Zen Takemiya Masaki (9p) med 11 poäng på fem stenars handikapp, följt av en 20-poängs vinst på fyra stenars handikapp.

År 2013 Crazy Sten slå Yoshio Ishida (9p) i ett 19 x 19 spel på fyra stenar handikapp.

2014 Codecentric Go Challenge, en bäst-av-fem-match i ett jämnt 19x19-spel, spelades mellan Crazy Stone och Franz-Jozef Dickhut (6d). Ingen starkare spelare hade någonsin tidigare gått med på att spela en seriös tävling mot ett go -program på jämna villkor. Franz-Jozef Dickhut vann, även om Crazy Stone vann den första matchen med 1,5 poäng.

2015 och framåt: Deep learning -eran

Ytterligare information: AlphaGo kontra Fan Hui , AlphaGo kontra Lee Sedol och AlphaGo kontra Ke Jie

I oktober 2015 Google DeepMind program AlphaGo slå Fan Hui , mästare Europeiska Go, fem gånger av fem i turnerings förhållanden.

I mars 2016 slog AlphaGo Lee Sedol i de tre första av fem matcherna. Detta var första gången som en 9-danig mästare hade spelat ett professionellt spel mot en dator utan handikapp. Lee vann den fjärde matchen och beskrev hans vinst som "ovärderlig". AlphaGo vann den sista matchen två dagar senare.

I maj 2017 slog AlphaGo Ke Jie , som vid den tiden rankades högst i världen, i en match med tre spel under Future of Go Summit .

I oktober 2017 avslöjade DeepMind en ny version av AlphaGo, endast utbildad genom självspel, som hade överträffat alla tidigare versioner och slog Ke Jie -versionen i 89 av 100 spel.

Eftersom de grundläggande principerna för AlphaGo hade publicerats i tidskriften Nature kunde andra team ta fram program på hög nivå. År 2017 kunde både Zen och Tencents projekt Fine Art besegra mycket högnivåproffs en del av tiden och Leela Zero- motorn med öppen källkod släpptes.

Hinder för prestanda på hög nivå

Länge var det en utbredd uppfattning att dator Go utgjorde ett problem som skiljer sig väsentligt från datorschack . Man trodde att metoder som förlitar sig på snabb global sökning med relativt liten domänkunskap inte skulle vara effektiva mot mänskliga experter. Därför fokuserade en stor del av utvecklingen av dator Go under dessa tider på sätt att representera människoliknande expertkunskaper och kombinera detta med lokal sökning för att besvara frågor av taktisk karaktär. Resultatet av detta var program som hanterade många situationer bra men som hade mycket uttalade svagheter jämfört med deras övergripande hantering av spelet. Dessa klassiska program fick också nästan ingenting från ökningar i tillgänglig datorkraft i sig och framstegen på området var i allmänhet långsamma.

Några forskare insåg potentialen i probabilistiska metoder och förutspådde att de skulle komma att dominera datorspel, men många andra ansåg att ett starkt Go-playing-program var något som bara kunde uppnås inom en avlägsen framtid, till följd av grundläggande framsteg inom allmän artificiell intelligens teknik. Tillkomsten av program baserade på Monte Carlo- sökning (startade 2006) förändrade denna situation på många sätt med att de första 9-danska professionella Go-spelarna besegrades 2013 av flerkärniga datorer, om än med fyra-stenars handikapp.

Brädans storlek

Den stora brädan (19 × 19, 361 korsningar) noteras ofta som en av de främsta anledningarna till att ett starkt program är svårt att skapa. Den stora brädstorleken förhindrar att en alfa-beta-sökare uppnår djup blick framåt utan betydande söktillägg eller beskärningsheuristik .

2002 löste ett datorprogram som heter MIGOS (MIni GO Solver) spelet Go för 5 × 5 -kortet helt. Svart vinner och tar hela brädet.

Antal flyttalternativ

Fortsätter jämförelsen med schack, Go -drag är inte lika begränsade av spelreglerna. För det första steget i schack har spelaren tjugo val. Go -spelare börjar med ett urval av 55 olika rättsliga drag, som står för symmetri. Detta nummer stiger snabbt när symmetri bryts, och snart måste nästan alla 361 punkter på tavlan utvärderas. Vissa drag är mycket mer populära än andra och vissa spelas nästan aldrig, men alla är möjliga.

Utvärderingsfunktion

Även om en materialräknande utvärdering inte är tillräcklig för anständigt spel i schack, är materialbalans och olika positionsfaktorer som pantstruktur lätt att kvantifiera.

Dessa typer av positionsbedömningsregler kan inte effektivt tillämpas på Go. Värdet av en Go -position beror på en komplex analys för att avgöra om gruppen lever eller inte, vilka stenar kan kopplas till varandra och heuristik kring i vilken utsträckning en stark position har inflytande eller i vilken utsträckning en svag position kan attackeras.

Mer än ett drag kan ses som det bästa beroende på vilken strategi som används. För att kunna välja ett drag måste datorn utvärdera olika möjliga resultat och avgöra vilket som är bäst. Detta är svårt på grund av de känsliga avvägningarna som finns i Go. Till exempel kan det vara möjligt att fånga några fiendens stenar på bekostnad av att förstärka motståndarens stenar någon annanstans. Om detta är en bra affär eller inte kan vara ett svårt beslut, även för mänskliga spelare. Beräkningskomplexiteten visar också här eftersom ett drag kanske inte är omedelbart viktigt, men efter många drag kan det bli mycket viktigt när andra delar av tavlan tar form.

Kombinerande problem

Ibland nämns det i detta sammanhang att olika svåra kombinatoriska problem (i själva verket alla NP-hårda problem) kan konverteras till Go-liknande problem på en tillräckligt stor bräda; Detsamma gäller dock för andra abstrakta brädspel, inklusive schack och gruvsvepare , när de är lämpliga generaliserade till ett bräde av godtycklig storlek. NP-kompletta problem tenderar i deras allmänna fall inte att vara lättare för ohjälpade människor än för lämpligt programmerade datorer: det är tveksamt att ohjälpade människor skulle kunna konkurrera framgångsrikt mot datorer för att lösa exempelvis fall av delmängdsproblemet .

Slutspel

Med tanke på att slutspelet innehåller färre möjliga drag än öppningen ( fuseki ) eller mittspel, kan man anta att det är lättare att spela, och därmed att en dator enkelt ska kunna hantera det. I schack fungerar datorprogram i allmänhet bra i schackslutspel , särskilt när antalet bitar har reducerats i den utsträckning det gör det möjligt att dra nytta av lösta slutspel bordbaser .

). Även om det inte är allmänt användbart under de flesta spelomständigheter, hjälper det starkt analysen av vissa klasser av positioner.

Trots att detaljerade studier har genomförts har Go-slutspel visat sig vara PSPACE-hårda . Det finns många anledningar till att de är så svåra:

  • Slutspelet kan innebära många andra aspekter av Go, inklusive "liv och död", som också är kända för att vara NP-hårda .
  • Var och en av de lokala slutspelsområdena kan påverka varandra. Med andra ord, de är dynamiska till sin natur även om de är visuellt isolerade. Detta gör det svårt att resonera för både datorer och människor. Denna natur leder till vissa komplexa situationer som Triple Ko, Quadruple Ko, Molasses Ko och Moonshine Life.

Således kan traditionella Go -algoritmer inte spela Go -slutspelet felfritt i bemärkelsen att beräkna ett bästa drag direkt. Starka Monte Carlo-algoritmer kan fortfarande hantera normala Go-slutspelsituationer tillräckligt bra, och i allmänhet är det osannolikt att de mest komplicerade klasserna av liv-och-död-slutspelsproblem kommer upp i ett spel på hög nivå.

Spelordning

Monte-Carlo-baserade Go-motorer har rykte om sig att vara mycket mer villiga att spela tenuki , flyttar någon annanstans på brädet, snarare än att fortsätta en lokal kamp än mänskliga spelare. Det kan vara svårt att direkt beräkna när en specifik lokal flytt krävs. Detta uppfattades ofta som en svaghet tidigt i programmets existens. Som sagt, denna tendens har kvarstått i AlphaGos spelstil med dominerande resultat, så det här kan vara mer "en egendom" än en "svaghet".

En av de viktigaste problemen för en Go -spelare är vilka grupper av stenar som kan hållas vid liv och vilka som kan fångas. Denna allmänna klass av problem är känd som liv och död . Den mest direkta strategin för att beräkna liv och död är att utföra en trädsökning på rörelserna som potentiellt kan påverka stenarna i fråga och sedan registrera status för stenarna i slutet av huvudlinjen.

Men inom tids- och minnesbegränsningar är det i allmänhet inte möjligt att med fullständig noggrannhet avgöra vilka rörelser som kan påverka 'en livsstil' för en grupp stenar. Detta innebär att en del heuristik måste tillämpas för att välja vilka steg som ska övervägas. Nettoeffekten är att det för varje givet program finns en avvägning mellan spelhastighet och livs- och dödsförmåga.

Med Bensons algoritm är det möjligt att bestämma kedjorna som villkorslöst lever och därför inte behöver kontrolleras i framtiden för säkerhet.

Statens representation

En fråga som alla Go -program måste ta itu med är hur man representerar spelets nuvarande tillstånd. För program som använder omfattande sökteknik måste denna representation kopieras och/eller modifieras för varje nytt hypotetiskt drag som övervägs. Detta behov ställer den ytterligare begränsningen att representationen antingen ska vara tillräckligt liten för att kunna kopieras snabbt eller tillräckligt flexibelt för att ett drag kan göras och enkelt ångras.

Det mest direkta sättet att representera en bräda är som en en- eller tvådimensionell matris, där element i matrisen representerar punkter på tavlan, och kan anta ett värde som motsvarar en vit sten, en svart sten eller en tom skärningspunkt . Ytterligare data behövs för att lagra hur många stenar som fångats, vems tur det är och vilka korsningar som är olagliga på grund av Ko -regeln .

De flesta program använder dock mer än bara den råa informationen för att utvärdera positioner. Data som vilka stenar som är anslutna i strängar, vilka strängar som är associerade med varandra, vilka grupper av stenar som riskerar att fånga och vilka grupper av stenar som faktiskt är döda är nödvändiga för att göra en noggrann utvärdering av positionen. Även om denna information kan extraheras från bara stenpositionerna, kan mycket av den beräknas snabbare om den uppdateras stegvis per steg. Denna inkrementella uppdatering kräver att mer information lagras som tillståndet på kortet, vilket i sin tur kan göra att det tar längre tid att kopiera kortet. Denna typ av avvägningar är ett tecken på problemen med att göra snabba datorprogram.

En alternativ metod är att ha ett enda kort och göra och ta tillbaka drag för att minimera kraven på datorminne och få resultaten av utvärderingen av kortet lagrade. Detta undviker att behöva kopiera informationen om och om igen.

Systemdesign

Nya tillvägagångssätt för problem

Historiskt sett har GOFAI (Good Old Fashioned AI) tekniker använts för att närma sig problemet med Go AI. På senare tid har neurala nätverk använts som ett alternativt tillvägagångssätt. Ett exempel på ett program som använder neurala nätverk är WinHonte.

Dessa tillvägagångssätt försöker mildra problemen med Go -spelet med en hög förgreningsfaktor och många andra svårigheter.

Computer Go -forskningsresultat tillämpas på andra liknande områden som kognitiv vetenskap , mönsterigenkänning och maskininlärning . Combinatorial Game Theory , en gren av tillämpad matematik , är ett ämne som är relevant för dator Go.

Designfilosofier

Det enda valet ett program behöver göra är var nästa sten ska placeras. Detta beslut försvåras emellertid av de stora effekter som en sten kan ha över hela linjen, och de komplexa interaktioner som olika stengrupper kan ha med varandra. Olika arkitekturer har uppstått för att hantera detta problem. Den mest populära användningen:

Få program använder endast en av dessa tekniker uteslutande; de flesta kombinerar delar av varje till ett syntetiskt system.

En traditionell AI -teknik för att skapa spelprogram är att använda en minimax -trädsökning . Detta innefattar att spela ut alla hypotetiska drag på brädet upp till en viss punkt, sedan använda en utvärderingsfunktion för att uppskatta värdet av den positionen för den aktuella spelaren. Det drag som leder till den bästa hypotetiska tavlan väljs, och processen upprepas varje tur. Trädsökningar har varit mycket effektiva i datorchack , men de har sett mindre framgång i Computer Go -program. Detta beror dels på att det traditionellt har varit svårt att skapa en effektiv utvärderingsfunktion för ett Go -bräde, dels att det stora antalet möjliga drag varje sida kan göra att varje leder till en hög förgreningsfaktor . Detta gör denna teknik mycket beräkningsmässigt dyr. På grund av detta kan många program som använder sökträd i stor utsträckning bara spela på det mindre 9 × 9 brädet, snarare än hela 19 × 19.

Det finns flera tekniker som kan förbättra prestandan för sökträd både vad gäller hastighet och minne. Beskärningstekniker som alfa -beta beskärning , Principal Variation Search och MTD (f) kan minska den effektiva förgreningsfaktorn utan förlust av styrka. Inom taktiska områden som liv och död är Go särskilt mottagligt för cachningstekniker som transponeringstabeller . Dessa kan minska mängden upprepad ansträngning, särskilt i kombination med en iterativ fördjupning . För att snabbt kunna förvara en Go-bräda i full storlek i en transponeringstabell är en haschteknik för matematiskt sammanfattning i allmänhet nödvändig. Zobrist hashing är mycket populärt i Go -program eftersom det har låga kollisionshastigheter och kan iterativt uppdateras vid varje drag med bara två XOR , snarare än att beräknas från grunden. Även om man använder dessa prestandaförbättrande tekniker är sökningar på hela träd på ett bräde i full storlek fortfarande oöverkomligt långsamma. Sökningar kan påskyndas genom att använda stora mängder domänspecifika beskärningstekniker, till exempel att inte överväga drag där din motståndare redan är stark och selektiva tillägg som att alltid överväga drag bredvid grupper av stenar som är på väg att fångas . Båda dessa alternativ innebär dock en betydande risk för att inte överväga ett viktigt drag som skulle ha förändrat spelets gång.

Resultat från datortävlingar visar att mönstermatchningstekniker för att välja en handfull lämpliga drag kombinerat med snabba lokaliserade taktiska sökningar (förklarade ovan) en gång var tillräckliga för att skapa ett konkurrenskraftigt program. Till exempel var GNU Go konkurrenskraftigt fram till 2008.

Kunskapsbaserade system

Nybörjare lär sig ofta mycket av spelrekorden för gamla spel som spelas av mästare. Det finns en stark hypotes som tyder på att förvärva Go -kunskap är en nyckel för att få en stark dator Go. Till exempel hävdar Tim Kinger och David Mechner att "det är vår tro att med bättre verktyg för att representera och behålla Go -kunskap kommer det att vara möjligt att utveckla starkare Go -program." De föreslår två sätt: erkänna vanliga konfigurationer av stenar och deras positioner och koncentrera sig på lokala strider. "Go -program saknar fortfarande både kvalitet och kvantitet av kunskap."

Efter implementeringen har användningen av expertkunskap visat sig vara mycket effektiv för programmering av Go -programvara. Hundratals riktlinjer och tumregler för starkt spel har formulerats av både amatörer på hög nivå och proffs. Programmerarens uppgift är att ta dessa heuristik , formalisera dem till datorkod och använda mönstermatchning och mönsterigenkänningsalgoritmer för att känna igen när dessa regler gäller. Det är också viktigt att ha ett system för att bestämma vad man ska göra om två motstridiga riktlinjer är tillämpliga.

De flesta av de relativt framgångsrika resultaten kommer från programmerares individuella färdigheter på Go och deras personliga gissningar om Go, men inte från formella matematiska påståenden; de försöker få datorn att efterlikna hur de spelar Go. "De flesta konkurrenskraftiga program har krävt 5–15 personårs insats och innehåller 50–100 moduler som behandlar olika aspekter av spelet."

Denna metod har tills nyligen varit den mest framgångsrika tekniken för att generera konkurrenskraftiga Go-program på en fullstor styrelse. Några exempel på program som har förlitat sig mycket på expertkunskaper är Handtalk (senare känt som Goemate), The Many Faces of Go, Go Intellect och Go ++, som alla någon gång har ansetts vara världens bästa Go -program.

Att lägga till kunskap om Go försvagar emellertid ibland programmet eftersom viss ytlig kunskap kan ge misstag: "de bästa programmen spelar vanligtvis bra, masternivåer. Men som alla spelare vet kan bara ett dåligt drag förstöra ett bra spel. Programprestanda över ett helt spel kan vara mycket lägre än masternivå. "

Monte-Carlo metoder

Huvudartikel: Monte-Carlo trädsökning

Ett stort alternativ till att använda handkodad kunskap och sökningar är användningen av Monte Carlo-metoder . Detta görs genom att generera en lista över potentiella drag, och för varje drag spelar tusentals spel slumpmässigt på det resulterande brädet. Det drag som leder till den bästa uppsättningen slumpmässiga spel för den aktuella spelaren väljs som det bästa draget. Fördelen med denna teknik är att den kräver mycket lite domänkunskap eller expertinmatning, avvägningen är ökade minne och processorbehov. Eftersom de drag som används för utvärdering genereras slumpmässigt är det dock möjligt att ett drag som skulle vara utmärkt utom ett specifikt motståndarsvar felaktigt skulle utvärderas som ett bra drag. Resultatet av detta är program som är starka i en övergripande strategisk mening, men som är ofullkomliga taktiskt. Detta problem kan lindras genom att lägga till viss domänkunskap i flyttgenerationen och ett större sökdjup ovanpå den slumpmässiga utvecklingen. Några program som använder Monte-Carlo-tekniker är Fuego, The Many Faces of Go v12, Leela, MoGo, Crazy Stone , MyGoFriend och Zen.

År 2006 utvecklades en ny sökteknik, övre konfidensgränser för träd (UCT), som tillämpades på många 9x9 Monte-Carlo Go-program med utmärkta resultat. UCT använder resultaten av spel outs samlats hittills för att styra sökningen längs de mer framgångsrika linjer spel samtidigt tillåta alternativa linjer på att utforskas. UCT -tekniken tillsammans med många andra optimeringar för att spela på det större 19x19 -brädet har lett till att MoGo har blivit ett av de starkaste forskningsprogrammen. Framgångsrika tidiga tillämpningar av UCT -metoder till 19x19 Go inkluderar MoGo, Crazy Stone och Mango. MoGo vann 2007 Computer Olympiad och vann en (av tre) blitz match mot Guo Juan, 5th Dan Pro, i mycket mindre komplexa 9x9 Go. Många ansikten Go vann 2008 Computer Olympiad efter att ha lagt UCT sökning på sin traditionella kunskapsbaserad motor.

Maskininlärning

Medan kunskapsbaserade system har varit mycket effektiva på Go, är deras färdighetsnivå nära kopplad till kunskapen hos sina programmerare och tillhörande domänexperter. Ett sätt att bryta denna begränsning är att använda maskininlärningstekniker för att låta mjukvaran automatiskt generera regler, mönster och/eller regelstrategier för konfliktlösning.

Detta görs i allmänhet genom att låta ett neuralt nätverk eller en genetisk algoritm antingen granska en stor databas med professionella spel eller spela många spel mot sig själv eller andra människor eller program. Dessa algoritmer kan sedan använda dessa data som ett sätt att förbättra deras prestanda. AlphaGo använde detta med stor effekt. Andra program som tidigare använt neurala nät har varit NeuroGo och WinHonte.

Maskininlärningstekniker kan också användas i ett mindre ambitiöst sammanhang för att ställa in specifika parametrar för program som huvudsakligen förlitar sig på andra tekniker. Till exempel lär Crazy Stone flytta generationsmönster från flera hundra provspel, med hjälp av en generalisering av Elo -klassificeringssystemet .

AlphaGo

Huvudartikel: AlphaGo

AlphaGo , utvecklat av Google DeepMind , gjorde ett betydande framsteg genom att slå en professionell mänsklig spelare i oktober 2015, med hjälp av tekniker som kombinerade djupinlärning och Monte Carlo -trädsökning . AlphaGo är betydligt kraftfullare än andra tidigare Go-program, och den första som slog en 9 dan mänsklig proffs i ett spel utan handikapp på ett brett i full storlek.

Lista över Go-playing-datorprogram

Se även: Go -programvara
  • AlphaGo , det första datorprogrammet som vann i jämna matcher mot en professionell human Go -spelare
  • AYA av Hiroshi Yamashita
  • BaduGI av Jooyoung Lee
  • Crazy Stone av Rémi Coulom (säljs som Saikyo no Igo i Japan)
  • Darkforest från Facebook
  • Konst av Tencent
  • Goban, Macintosh OS X Go -program av Sen: te (kräver gratis Goban -tillägg)
  • GNU Go , ett klassiskt Go -program med öppen källkod
  • Go ++ av Michael Reiss (säljs som Strongest Go eller Tuyoi Igo i Japan)
  • Leela , det första Monte Carlo -programmet som säljs till allmänheten
  • Leela Zero , en omimplementering av systemet som beskrivs i AlphaGo Zero -papperet
  • The Many Faces of Go av David Fotland (säljs som AI Igo i Japan)
  • MyGoFriend av Frank Karger
  • MoGo av Sylvain Gelly; parallellversion av många människor.
  • Pachi open source Monte Carlo -program av Petr Baudiš, onlineversion Peepo av Jonathan Chetwynd, med kartor och kommentarer medan du spelar
  • Smart Go av Anders Kierulf, uppfinnare av Smart Game Format
  • Steenvreter av Erik van der Werf
  • Zen av Yoji Ojima aka Yamato (säljs som Tencho no Igo i Japan); parallellversion av Hideki Kato.

Tävlingar mellan dator Go -program

Flera årliga tävlingar äger rum mellan Go -datorprogram, de mest framträdande är Go -evenemangen vid datorolympiaden . Regelbundna, mindre formella, tävlingar mellan program som förekom på KGS Go -servern (månadsvis) och Computer Go -servern (kontinuerlig).

Framträdande go-playing-program inkluderar Crazy Stone, Zen, Aya, Mogo, The Many Faces of Go, pachi och Fuego, alla listade ovan; och taiwanesisk-författad kallmjölk, holländsk-författad Steenvreter och koreansk-författad DolBaram.

Historia

Den första dator Go -tävlingen sponsrades av Acornsoft , och de första vanliga av USENIX . De sprang från 1984 till 1988. Dessa tävlingar introducerade Nemesis, det första konkurrenskraftiga Go -programmet från Bruce Wilcox och G2.5 av David Fotland , som senare skulle utvecklas till Cosmos och The Many Faces of Go.

En av de tidiga drivkrafterna för dator Go-forskning var Ing-priset, en relativt stor pengepris som sponsras av den taiwanesiska bankiren Ing Chang-ki , som årligen erbjuds mellan 1985 och 2000 på World Computer Go Congress (eller Ing Cup). Vinnaren av denna turnering fick utmana unga spelare på ett handikapp i en kort match. Om datorn vann matchen delades priset ut och ett nytt pris tillkännagavs: ett större pris för att slå spelarna med ett mindre handikapp. Serien av Ing-priser skulle antingen löpa ut 1) år 2000 eller 2) när ett program kunde slå en 1-daners proffs utan handikapp för 40 000 000 NT-dollar . Den sista vinnaren var Handtalk 1997 och krävde 250 000 NT-dollar för att ha vunnit en 11-stenars handikappsmatch mot tre 11–13-åriga amatörer 2–6 dans. När priset gick ut år 2000 var det outtagna priset 400 000 NT-dollar för att vinna en niostenshandikappsmatch.

Många andra stora regionala Go -turneringar ("kongresser") hade en bifogad dator Go -händelse. European Go Congress har sponsrat en datorturnering sedan 1987 och USENIX -evenemanget utvecklades till USA/North American Computer Go Championship, som hålls årligen 1988–2000 på US Go Congress.

Japan började sponsra dator Go -tävlingar 1995. FOST Cup hölls årligen från 1995 till 1999 i Tokyo. Den turneringen ersattes av Gifu Challenge, som hölls årligen 2003-2006 i Ogaki, Gifu. Den Computer Go UEC Cup har hållits årligen sedan 2007.

Regelformaliseringsproblem i dator-dataspel

När två datorer spelar ett spel Go mot varandra, är idealet att behandla spelet på ett sätt som är identiskt med två människor som spelar samtidigt som man undviker ingrepp från verkliga människor. Detta kan dock vara svårt under slutspelet. Huvudproblemet är att Go playing -mjukvaran, som vanligtvis kommunicerar med det standardiserade Go Text Protocol (GTP), inte alltid kommer att hålla med om stenarnas levande eller döda status.

Även om det inte finns något generellt sätt för två olika program att "prata ut det" och lösa konflikten, undviks detta problem för det mesta genom att använda kinesiska , Tromp-Taylor eller American Go Association (AGA) regler där fortsatt spel ( utan straff) krävs tills det inte längre råder oenighet om statusen för några stenar på tavlan. I praktiken, till exempel på KGS Go -servern, kan servern förmedla en tvist genom att skicka ett speciellt GTP -kommando till de två klientprogrammen som indikerar att de ska fortsätta placera stenar tills det inte finns någon fråga om statusen för en viss grupp (alla döda stenar har fångats). CGOS Go-servern brukar se program avgå innan ett spel ens har nått poängfasen, men stöder ändå en modifierad version av Tromp-Taylor-regler som kräver en fullständig uppspelning.

Dessa regeluppsättningar innebär att ett program som var i en vinnande position i slutet av spelet enligt japanska regler (när båda spelarna har passerat) kan förlora på grund av dåligt spel i upplösningsfasen, men detta är inte vanligt förekommande och anses en normal del av spelet under alla områdesregeluppsättningar.

Den största nackdelen med ovanstående system är att vissa regeluppsättningar (som de traditionella japanska reglerna) straffar spelarna för att göra dessa extra drag, vilket förhindrar användning av ytterligare spel för två datorer. De flesta moderna Go -program stöder dock japanska regler mot människor och är kompetenta i både spel och poäng (Fuego, Many Faces of Go, SmartGo, etc.).

Historiskt sett var en annan metod för att lösa detta problem att ha en expert mänsklig domare den sista styrelsen. Detta introducerar emellertid subjektivitet i resultaten och risken för att experten skulle missa något programmet såg.

Testning

Många program är tillgängliga som gör att dator Go -motorer kan spela mot varandra och de kommunicerar nästan alltid via Go Text Protocol (GTP).

GoGUI och dess tillägg gogui-twogtp kan användas för att spela två motorer mot varandra på ett enda datasystem. SmartGo och Many Faces of Go har också denna funktion.

För att spela så många olika motståndare som möjligt, tillåter KGS Go Server både Go engine vs. Go engine -motor och Go engine vs. human i både rankade och orankade matcher. CGOS är en dedikerad dator mot dator Go -server.

Se även

Referenser

Vidare läsning