Жасанды интеллект және Го ойынының зерттелуі

Кіріспе

Жасанды интеллектте Го (ойын) зерттеуі, Го компьютерлік бағдарламаларының айналасындағы жасанды интеллект саласы. Компьютерлік Го – бұл дәстүрлі Го ойынын ойнайтын компьютерлік бағдарлама жасауға арналған жасанды интеллект (ЖИ) саласы. Бұл сала екі кезеңге бөлінеді. 2015 жылға дейін бұл кезеңдегі бағдарламалар нашар болды. 1980 және 1990 жылдардағы ең жақсы әрекеттердің нәтижесінде тек бастаушылардың жеңілуіне болатын ЖИ пайда болды, ал 2000 жылдардың басындағы ЖИ ең жақсы жағдайда орташа деңгейде болды. Кәсіби ойыншылар бұл бағдарламаларды тіпті ЖИ пайдасына 10 және одан да көп тас артық берген жағдайда жеңіп шығуға мүмкін болды. Шахмат пен шашкада ЖИ ретінде жақсы жұмыс істеген альфа-бета минимакс сияқты көптеген алгоритмдер Го-ның 19x19 тақтасында тиімсіз болды, себебі қарастыруға тым көп мүмкіндіктер болды. Сол кездегі техникалық және аппараттық мүмкіндіктермен кәсіби деңгейдегі бағдарлама жасау мүмкін емес еді. Кейбір ЖИ зерттеушілері бұл мәселені адам сияқты ЖИ құрылмаса шешуге болмайды деп болжады. 2000 жылдардың соңында Монте-Карло ағаштарын іздеу алгоритмін Го алгоритмдеріне қолдану айтарлықтай жақсартуға мүмкіндік берді, нәтижесінде бағдарламалар төменгі дан деңгейіне жетті: озық әуесқой деңгейі. Жоғары дан деңгейлі әуесқойлар мен кәсіби ойыншылар осы бағдарламалардың кемшіліктерін пайдаланып, үнемі жеңіске жете берді, бірақ компьютердің өнімділігі орташа (бір таңбалы кю) деңгейден асып түсті. Ұзақ уақыт бойы қол жетпес деп саналған, ең үздік ойыншыларды хендикапсыз жеңудің мақсаты жаңа қызығушылықты тудырды. Шешуші түсінік – машиналық және терең оқытуты қолдану болды. Google компаниясының ЖИ зерттеулеріне арналған DeepMind 2015 жылы AlphaGo-ны жасады және 2016 жылы оны әлемге таныстырды. AlphaGo 2016 жылы хендикапсыз матчта 9 дандық кәсіби Ли Седолды жеңіп, 2017 жылы Ке Цзеді жеңді, ол сол кезде екі жыл бойы әлемдегі бірінші орынды сақтап тұрған. 1995 жылы шахмат пен шашка машиналардың жеңісімен аяқталғандай, компьютерлік бағдарламалар 2016-2017 жылдары адамзат тарихындағы ең үздік Го чемпиондарын жеңді. DeepMind AlphaGo-ны жалпы қолдануға шығармады, бірақ DeepMind AlphaGo және оның нұсқаларын сипаттаған ғылыми мақалалар негізінде әртүрлі бағдарламалар жасалды.

the study of Go (game) in artificial intelligence

Field of artificial intelligence around Go computer programs

Computer Go is the field of artificial intelligence (AI) dedicated to creating a computer program that plays the traditional board game Go. The field is sharply divided into two eras. Before 2015, the programs of the era were weak. The best efforts of the 1980s and 1990s produced only AIs that could be defeated by beginners, and AIs of the early 2000s were intermediate level at best. Professionals could defeat these programs even given handicaps of 10+ stones in favor of the AI. Many of the algorithms such as alpha beta minimax that performed well as AIs for checkers and chess fell apart on Go's 19x19 board, as there were too many branching possibilities to consider. Creation of a human professional quality program with the techniques and hardware of the time was out of reach. Some AI researchers speculated that the problem was unsolvable without creation of human like AI. The application of Monte Carlo tree search to Go algorithms provided a notable improvement in the late 2000s decade, with programs finally able to achieve a low dan level: that of an advanced amateur. High dan amateurs and professionals could still exploit these programs' weaknesses and win consistently, but computer performance had advanced past the intermediate (single digit kyu) level. The tantalizing unmet goal of defeating the best human players without a handicap, long thought unreachable, brought a burst of renewed interest. The key insight proved to be an application of machine learning and deep learning. DeepMind, a Google acquisition dedicated to AI research, produced AlphaGo in 2015 and announced it to the world in 2016. AlphaGo defeated Lee Sedol, a 9 dan professional, in a no handicap match in 2016, then defeated Ke Jie in 2017, who at the time continuously held the world No. 1 ranking for two years. Just as checkers had fallen to machines in 1995 and chess in 1997, computer programs finally conquered humanity's greatest Go champions in 2016–2017. DeepMind did not release AlphaGo for public use, but various programs have been built since based on the journal articles DeepMind released describing AlphaGo and its variants.

Жалпы түсінік және тарих

Кәсіби го ойыншылары бұл ойынға интуиция, шығармашылық және стратегиялық ойлау қажет екенін айтады. Бұл жасанды интеллект (ЖИ) саласында ұзақ жылдар бойы қиын міндет болып саналады және шахматтан гөрі әлдеқайда күрделі. Көптеген мамандар го шахматқа қарағанда адам ойлауын жақсырақ бейнелейтін элементтерді қажет етеді деп санайды. Математик И. Дж. Гуд 1965 жылы былай жазған:

2015 жылға дейін ең жақсы го бағдарламалары тек әуесқой дан деңгейіне ғана жете алды. Кішкентай 9x9 тақтасында компьютер жақсы нәтиже көрсетті, ал кейбір бағдарламалар кәсіби ойыншыларға қарсы 9x9 ойындарының бір бөлігін жеңіп алды. АльфаГо пайда болғанға дейін кейбір зерттеушілер компьютерлердің годан ең мықты ойыншыны жеңе алмайтынын айтқан.

Алғашқы онжылдықтар

Go бағдарламасын алғаш рет 1968 жылы Альберт Линдси Зобрист үлгілерді тану туралы диссертациясының бір бөлігі ретінде жазды. Ол аумақты бағалау үшін ықпал ету функциясын және ко-ны анықтау үшін Зобрист хэшін енгізді. 1981 жылдың сәуірінде Джонатан К. Миллен Byte журналында Wally туралы мақала жариялады, бұл 15x15 тақтасы бар Go бағдарламасы, ол KIM 1 микрокомпьютерінің 1К RAM-іне сыйып отырды. Брюс Ф. Вебстер 1984 жылдың қарашасында MacFORTH кодымен қоса Apple Macintosh үшін жазған Go бағдарламасын талқылай отырып, журналға мақала жариялады. Go бағдарламалары әлсіз болды; 1983 жылғы мақалада олар ең жақсы жағдайда 20 кю деңгейіне тең деп бағаланды, бұл жаңа бастаған ойыншының рейтингі, және көбінесе олар кішігірім тақталарда ғана қолданылды. 19x19 өлшемді тақталарда Интернет Go Серверінде (IGS) ойнаған ЖЗ 2003 жылы аппараттық жағынан елеулі жақсарудан кейін 20–15 кю күшіне ие болды. 1998 жылы өте күшті ойыншылар 25–30 тас кемшілікпен компьютерлік бағдарламаларды жеңе алды, бұл адам ойыншыларының көбінесе қабылдамайтын өте үлкен кемшілік еді. 1994 жылғы Әлемдік Компьютерлік Go Чемпионатында жеңімпаз бағдарлама Go Intellect, 15 тас кемшілікпен жасөспірім ойыншыларға қарсы барлық үш ойында жеңіліп қалды. Жалпы, бағдарламаның әлсіз жақтарын түсініп, пайдаланған ойыншылар үлкен кемшіліктерге қарамастан жеңіске жете алатын еді.

2007-2014 жылдар: Монте-Карлодағы ағаш іздеу

2006 жылы (2007 жылы жарияланған мақаласы) Реми Кулом Монте-Карло ағаштарын іздеу деп аталатын жаңа алгоритм ойлап тапты. Онда, әр қимылмен тармақталатын болашақ мүмкіндіктердің ойын ағашы жасалады. Бірақ компьютерлер ағаштың соңғы жапырағын қайталама кездейсоқ ойындар арқылы "бағалайды" (басқа мәселелер үшін Монте-Карло стратегиясына ұқсас). Бұл әдіс кездейсоқ ойындарды өте жылдам жасауға мүмкіндік береді. Кездейсоқ ойындар позицияның нақты құнын көрсете бермейді деген интуитивті пікір күткендей қауіпті емес екені анықталды; алгоритмнің "ағаш іздеу" бөлігі болашақ ойын ағаштарын іздеу үшін жеткілікті деңгейде түзетілді. Осы әдіске негізделген MoGo және Fuego сияқты бағдарламалар бұрынғы классикалық жасанды интеллекттен жақсы нәтижелер көрсетті. Ең жақсы бағдарламалар әсіресе 9x9 тақтасында жақсы өнер көрсетті, себебі онда зерттеуге мүмкіндіктер шектеулі болды. 2009 жылы KGS Go Server-де 19x19 тақтасында төменгі дан деңгейіне жете алатын және сақтай алатын алғашқы бағдарламалар пайда болды. 2010 жылы Финляндияда өткен Еуропалық Го конгресінде MogoTW 19x19 Го ойынында Каталина Таранумен (5п) ойнады. MogoTW жеті таспен берілген мүмкіндікпен жеңіске жетті. 2011 жылы Zen KGS серверінде 5 данға жетті, әр қимылға 15 секундтан ойын ойнады. Бұл деңгейге жеткен тіркелгі 26 ядролы машинада жұмыс істейтін Zen-нің кластерлік нұсқасын пайдаланды. 2012 жылы Zen Takemiya Masaki (9п) командасын бес таспен берілген мүмкіндікпен 11 ұпаймен жеңіп, содан кейін төрт таспен берілген мүмкіндікпен 20 ұпаймен жеңді. 2013 жылы Crazy Stone 19×19 ойынында төрт таспен берілген мүмкіндікпен Йосио Ишиданы (9п) жеңді. 2014 жылғы Codecentric Go Challenge, 19x19 ойынындағы бес матчтың ең жақсысы, Crazy Stone мен Franz Jozef Dickhut (6d) арасында өтті. Бұрын ешқандай күшті ойыншы Go бағдарламасына қарсы тең мүмкіндіктермен бәсекелесуге келіспеген. Франц Йозеф Дикхут жеңіске жетті, бірақ Crazy Stone бірінші матчты 1,5 ұпай айырмасымен жеңді.

2015 жылдан бастап: терең білім беру дәуірі

Google DeepMind компаниясы жасаған AlphaGo компьютерлік бағдарламасының күші бұрынғы Go бағдарламаларымен салыстырғанда айтарлықтай жоғары болды. Ол терең оқыту және Монте-Карло ағаштарын іздеу әдістерін біріктірді. 2015 жылдың қазан айында турнир жағдайында Еуропаның Go чемпионы Фан Хуэйді бес ойында бес рет жеңді. 2016 жылдың наурызында AlphaGo Ли Седолды бес матчтың алғашқы үшеуінде жеңіске жеткізді. Бұл 9 дан шеберінің компьютермен кәсіби деңгейдегі ойын ойнаған алғашқы реті еді. Ли төртінші матчта жеңіске жетті және бұл жеңісін "бағалы" деп атады. AlphaGo екі күннен кейін финалдық матчта жеңіске жетті. Осы жеңіспен AlphaGo толық өлшемді тақтада ешқандай жеңілдіксіз 9 дан кәсіби ойыншыны жеңген алғашқы бағдарлама атанды. 2017 жылдың мамыр айында AlphaGo Go-ның болашағы саммитінде әлемдегі бірінші орында тұрған Ке Цзеге үш ойындық матчта жеңді. 2017 жылдың қазан айында DeepMind AlphaGo-ның жаңа нұсқасын ұсынды, ол тек өзін-өзі ойнау арқылы жаттықтырылды және Ke Jie нұсқасын 100 ойынның 89-ында жеңіп, барлық алдыңғы нұсқаларын басып өтті. AlphaGo-ның негізгі принциптері Nature журналында жарияланғаннан кейін, басқа командалар да жоғары деңгейдегі бағдарламаларды жасауға қол жеткізді. Go AI саласындағы жұмыс негізінен AlphaGo құру үшін қолданылған әдістерді қайталаудан тұрады, ол басқа барлық бағдарламалардан әлдеқайда күшті болды. 2017 жылға қарай Zen және Tencent-тің Fine Art жобалары да кейде өте жоғары деңгейдегі кәсіби ойыншыларды жеңе алды. Сондай-ақ, ашық кодты Leela Zero ойын қозғалтқышы құрылды.

Мемлекеттік өкілдік

Барлық Go бағдарламалары шешуге тиіс мәселе – ойынның қазіргі күйін қалай бейнелеу. Тақтаны бейнелеудің ең тікелей жолы – бір немесе екі өлшемді массив, онда массивтегі элементтер тақтадағы ұяшықтарды көрсетеді және ақ тасқа, қара тасқа немесе бос қиылысқа сәйкес келетін мәнге ие болуы мүмкін. Қанша тас түсірілгенін, кімнің кезегі екенін және Ко ережесіне сәйкес қандай қиылыстар рұқсат етілмейтінін сақтау үшін қосымша деректер қажет. Әдетте, машиналық оқыту бағдарламалары осы ең қарапайым түрінде тоқтап, жасанды интеллектінің (ЖА) тақтаның мағынасын өздігінен түсінуіне мүмкіндік береді, көбінесе Монте-Карло симуляцияларын қолданып, тақтаны ойыншы үшін жақсы немесе жаман деп бағалайды. Адамның стратегиясын тікелей модельдеуге тырысқан «классикалық» ЖА бағдарламалары одан әрі жүре алады, мысалы, өлі деп саналатын тастар, міндетті түрде тірі тастар, өзара өмір күйіндегі секи тастар және ойын күйін көрсету үшін басқа да деректерді қосады.

Минимальды ағаш іздеу

Ойын ойнау бағдарламалық жасақтамасын жасаудың дәстүрлі AI әдістерінің бірі – минимакс ағаштарын іздеу. Бұл белгілі бір нүктеге дейін тақтадағы барлық гипотетикалық қимылдарды ойнауды қамтиды, содан кейін бағалау функциясы арқылы сол позицияның қазіргі ойыншы үшін құндылығын бағалау. Ең жақсы гипотетикалық тақтаға әкелетін қимыл таңдалады және процесс әр кезеңде қайталанады. Ағаш іздеу компьютерлік шахматта өте тиімді болғанымен, Computer Go бағдарламаларында одан аз сәттілікке жетті. Бұл Go тақтасы үшін тиімді бағалау функциясын жасаудың қиындығынан және әр тараптың жасауы мүмкін көптеген қимылдардың жоғары тармақтану факторына әкелуінен туындайды. Бұл әдісті есептеу жағынан өте қымбатқа түседі. Осы себепті, іздеу ағаштарын кеңінен пайдаланатын көптеген бағдарламалар толық 19x19 емес, кішігірім 9x9 тақтада ойнай алады. Іздеу ағаштарының жылдамдығы мен жады жағынан өнімділігін жақсартуға қабілетті бірнеше техникалар бар. Альфа-бета кесу, негізгі вариацияларды іздеу және MTD(f) сияқты кесу техникалары күшін жоғалтпай тиімді тармақтану факторын азайта алады. Өмір мен өлім сияқты тактикалық жағдайларда Go әсіресе транспозиция кестелері сияқты кэштік техникаларға бейім. Бұл қайталанатын еңбек көлемін азайтады, әсіресе итеративті тереңдету тәсілімен біріктірілгенде. Толық өлшемді Go тақтасын транспозиция кестесінде жылдам сақтау үшін математикалық тұжырымдама жасауға арналған хэштеу техникасы қажет. Зобрист хэштеуі Go бағдарламаларында өте танымал, себебі оның соқтығысу деңгейі төмен және әр қимылда тек екі XOR операциясы арқылы жаңартуға болады, бастапқы есептеудің орнына. Мұндай өнімділікті арттыратын техникаларды қолданғанның өзінде, толық өлшемді тақтада толық ағаш іздеу әлі де тым баяу. Іздеуді үлкен көлемдегі доменге тән кесу техникаларын қолдану арқылы жылдамдатуға болады, мысалы, қарсыласыңыздың күшті болған жерлерін қарастырмау және әрқашан ұстауға жақын болатын тастар тобының жанындағы қимылдарды міндетті түрде қарастыру сияқты. Алайда, екі опцияның да ойын барысын өзгерте алатын маңызды қимылды қарастырмау қаупі бар. Компьютерлік жарыстардың нәтижелері көрсеткендей, бірнеше қолайлы қимылдарды таңдау үшін үлгілерді сәйкестендіру техникалары, жылдам локальді тактикалық іздеулермен (жоғарыда түсіндірілгендей) біріктірілгенде, бәсекеге қабілетті бағдарлама жасау үшін жеткілікті болды. Мысалы, GNU Go 2008 жылға дейін бәсекеге қабілетті болды.

One traditional AI technique for creating game playing software is to use a minimax tree search. This involves playing out all hypothetical moves on the board up to a certain point, then using an evaluation function to estimate the value of that position for the current player. The move which leads to the best hypothetical board is selected, and the process is repeated each turn. While tree searches have been very effective in computer chess, they have seen less success in Computer Go programs. This is partly because it has traditionally been difficult to create an effective evaluation function for a Go board, and partly because the large number of possible moves each side can make each leads to a high branching factor. This makes this technique very computationally expensive. Because of this, many programs which use search trees extensively can only play on the smaller 9×9 board, rather than full 19×19 ones. There are several techniques, which can greatly improve the performance of search trees in terms of both speed and memory. Pruning techniques such as alpha–beta pruning, Principal Variation Search, and MTD(f) can reduce the effective branching factor without loss of strength. In tactical areas such as life and death, Go is particularly amenable to caching techniques such as transposition tables. These can reduce the amount of repeated effort, especially when combined with an iterative deepening approach. In order to quickly store a full sized Go board in a transposition table, a hashing technique for mathematically summarizing is generally necessary. Zobrist hashing is very popular in Go programs because it has low collision rates, and can be iteratively updated at each move with just two XORs, rather than being calculated from scratch. Even using these performance enhancing techniques, full tree searches on a full sized board are still prohibitively slow. Searches can be sped up by using large amounts of domain specific pruning techniques, such as not considering moves where your opponent is already strong, and selective extensions like always considering moves next to groups of stones which are about to be captured. However, both of these options introduce a significant risk of not considering a vital move which would have changed the course of the game. Results of computer competitions show that pattern matching techniques for choosing a handful of appropriate moves combined with fast localized tactical searches (explained above) were once sufficient to produce a competitive program. For example, GNU Go was competitive until 2008.

Білімге негізделген жүйелер

Адамдар го ойынында жаңадан бастағанда, шебер ойыншылардың өткен ойындарының жазбаларынан үйренеді. 1990 жылдардағы ИИ жұмыстары көбінесе ИИ-ге го білімінің адам стиліндегі ережелерін «оқытуға» бағытталған. 1996 жылы Тим Клингер мен Дэвид Мехнер ең жақсы ИИ-дің жаңадан бастағандар деңгейіндегі күшін мойындап, «Go білімін көрсету және сақтау үшін жақсы құралдармен күшті го бағдарламаларын жасау мүмкін болады деп есептейміз» деді. Олар екі жол ұсынды: тастардың жиі кездесетін орналасуын және олардың позицияларын анықтау, сондай-ақ жергілікті шайқастарға назар аудару. 2001 жылы бір мақалада «Го бағдарламаларында әлі де білімнің сапасы мен саны жетіспейді» деген қорытынды жасалды және оны түзету го ИИ-нің өнімділігін жақсартады делінді. Go v12 ойынының көптеген түрлері, Leela, MoGo, Crazy Stone, MyGoFriend және Zen. 2006 жылы ағаштарға қолданылатын жоғарғы сенімділік шекарасы (UCT) деп аталатын жаңа іздеу техникасы жасалды және көптеген 9x9 Монте-Карло го бағдарламаларына қолданылып, тамаша нәтижелер көрсетті. UCT осы уақытқа дейін жиналған ойын нәтижелерін пайдаланып, табысты ойын жолдарын іздеуге бағытталды, сонымен бірге басқа мүмкіндіктерді де зерттеуге мүмкіндік берді. UCT техникасы және 19x19 тақтасында ойнауға арналған көптеген басқа да оңтайландырулар MoGo-ны ең күшті зерттеу бағдарламаларының біріне айналдырды. 19x19 го ойынына UCT әдістерін сәтті қолданған алғашқы бағдарламаларға MoGo, Crazy Stone және Mango кірді. MoGo 2007 жылғы Компьютерлік Олимпиадада жеңіске жетті және 5-дан про деңгейіндегі Гуо Хуанға қарсы бір блиц ойынын (үш ойынның біреуін) жеңді, бұл 9x9 го ойынындағыдан әлдеқайда қарапайым еді. The Many Faces of Go 2008 жылғы Компьютерлік Олимпиадада UCT іздеуін өзінің дәстүрлі білімге негізделген қозғалтқышына қосып, жеңіске жетті. Монте-Карло негізіндегі го қозғалтқыштары адам ойыншыларына қарағанда тақтаның басқа жерлеріне (тенуки) көшуге, жергілікті шайқасты жалғастырмауға көбірек бейім екендігін көрсетеді. Бұл бағдарламалардың алғашқы кезеңдерінде әлсіздік ретінде қарастырылды. Алайда, бұл тенденция AlphaGo ойын стилінде де сақталды, сондықтан бұл «әлсіздік» емес, «ерекшелік» болуы мүмкін.

Human novices often learn from the game records of old games played by master players. AI work in the 1990s often involved attempting to "teach" the AI human style heuristics of Go knowledge. In 1996, Tim Klinger and David Mechner acknowledged the beginner level strength of the best AIs and argued that "it is our belief that with better tools for representing and maintaining Go knowledge, it will be possible to develop stronger Go programs." They proposed two ways: recognizing common configurations of stones and their positions and concentrating on local battles. In 2001, one paper concluded that "Go programs are still lacking in both quality and quantity of knowledge," and that fixing this would improve Go AI performance. The Many Faces of Go v12, Leela, MoGo, Crazy Stone, MyGoFriend, and Zen. In 2006, a new search technique, upper confidence bounds applied to trees (UCT), was developed and applied to many 9x9 Monte Carlo Go programs with excellent results. UCT uses the results of the play outs collected so far to guide the search along the more successful lines of play, while still allowing alternative lines to be explored. The UCT technique along with many other optimizations for playing on the larger 19x19 board has led MoGo to become one of the strongest research programs. Successful early applications of UCT methods to 19x19 Go include MoGo, Crazy Stone, and Mango. MoGo won the 2007 Computer Olympiad and won one (out of three) blitz game against Guo Juan, 5th Dan Pro, in the much less complex 9x9 Go. The Many Faces of Go won the 2008 Computer Olympiad after adding UCT search to its traditional knowledge based engine. Monte Carlo based Go engines have a reputation of being much more willing to play tenuki, moves elsewhere on the board, rather than continue a local fight than human players. This was often perceived as a weakness early in these program's existence. That said, this tendency has persisted in AlphaGo's playstyle with dominant results, so this may be more of a "quirk" than a "weakness."

Машиналық оқыту

Білімге негізделген жүйелердің шеберлік деңгейі олардың бағдарламалаушыларының және тиісті саланың сарапшыларының білімімен тығыз байланысты. Бұл шектеу шынайы күшті жасанды интеллект құруды қиындатады. Басқа бір жол – машиналық оқыту әдістерін қолдану. Мұнда бағдарламалаушылар ережелерді және позицияның құндылығын қалай бағалау керектігін анықтайтын қарапайым алгоритмдерді ғана бағдарламалауы керек. Бағдарламалық құрал, теория бойынша, өзіндік үлгілерді, эвристикалық тәсілдерді және стратегияларды автоматты түрде жасайды. Бұл әдетте нейрондық желіге немесе генетикалық алгоритмге кәсіби ойындардың үлкен деректер базасын қарауға немесе өзіне, басқа адамдарға немесе бағдарламаларға қарсы көптеген ойындар ойнауға рұқсат беру арқылы іске асырылады. Бұл алгоритмдер осы деректерді өнімділігін жақсарту құралы ретінде пайдалана алады. Машиналық оқыту әдістерін басқа әдістерге сүйенетін бағдарламалардың нақты параметрлерін реттеу үшін де, азырақ мақсатты жағдайда қолдануға болады. Мысалы, Crazy Stone бірнеше жүз үлгі ойындарынан Elo рейтингтік жүйесінің жалпыланған түрін пайдаланып, қозғалыс жасау үлгілерін үйренеді. Бұл тәсілдің ең танымал мысалы – AlphaGo, ол бұрынғы жасанды интеллектке қарағанда әлдеқайда тиімді болды. Оның алғашқы нұсқасында миллиондаған қолданыстағы позицияларды талдау арқылы, әрі қарай талдауға лайық ықтимал қозғалыстарды анықтау үшін бір қабат болды, ал екінші қабат бірінші қабаттан ұсынылған ықтимал қозғалыстарды пайдаланып жеңіс мүмкіндігін оңтайландыруға тырысты. AlphaGo нәтижелі позицияларды бағалау үшін Monte Carlo ағаштарын іздеу әдісін қолданды. AlphaGo-ның кейінгі нұсқасы, AlphaGoZero, Go ойындарынан үйренуден бас тартып, тек өзімен қайта-қайта ойнау арқылы ғана білім алды. Нейрондық желілерді пайдаланатын басқа бағдарламаларға NeuroGo және WinHonte жатады.

Компьютер Go және басқа өрістер

Компьютерлік Го зерттеулерінің нәтижелері басқа да ұқсас салаларға, мысалы, танымдық ғылымға, үлгілерді тануға және машиналық оқытуға қолданылады. Комбинаторлық ойын теориясы – қолданбалы математиканың бір саласы. Джон Х. Конвей Го ойынының соңғы кезеңін талдау үшін сюрреалистік сандарды қолдануды ұсынды. Бұл идеяны Эльвин Р. Берлекамп пен Дэвид Вулф «Математикалық Го» атты кітабында одан әрі дамытты. Го ойынының соңғы кезеңі, егер толыққанды толтырылған тақтада ең жақсы қадам есептелуі керек болса, PSPACE қиын екені дәлелденді. Үштік Ко, Төрттік Ко, Моласс Ко және Айшаң өмір сияқты кейбір күрделі жағдайлар бұл мәселені қиындатады. (Практикада, күшті Монте-Карло алгоритмдері Го ойынының қалыпты соңғы кезеңін жақсы шеше алады, ал өмір мен өлімнің ең күрделі жағдайлары жоғары деңгейдегі ойында кездесуі аз ғана мүмкіндік бар.) Әр түрлі күрделі комбинаторлық проблемаларды (кәдімгі NP қиын проблемаларды) жеткілікті үлкен тақтада Го сияқты проблемаларға түрлендіруге болады; алайда, шахмат және мина іздеу сияқты басқа абстрактілі тақта ойындарына да, оларды кез келген өлшемдегі тақтаға бейімдеген кезде, осы қағида қолданылады. NP толық проблемалары, жалпы жағдайда, бағдарламаланған компьютерлерге қарағанда көмексіз адамдар үшін оңай болмайды: көмексіз адамдар, мысалы, жиынның қосындысы сияқты мәселелерді шешуде компьютерлерге қарағанда нашар.

Go бағдарламаларының арасындағы бәсекелестік

Go компьютерлік бағдарламалары арасында жыл сайын бірнеше жарыс өтеді, оның ішінде Компьютерлік Олимпиададағы Go іс-шаралары да бар. Бұрын бағдарламалар арасында KGS Go Серверінде (ай сайын) және Computer Go Server-де (үнемі) ресми емес, тұрақты жарыстар болып тұратын. Go компьютерлік ойын қозғалтқыштарының бір-бірімен ойнауына мүмкіндік беретін көптеген бағдарламалар бар; олар көбінесе Go Text Protocol (GTP) арқылы байланысады.

Тарих

Go ойынының алғашқы компьютерлік жарысын Acornsoft, ал тұрақты жарыстарды USENIX демеушілік етті. Олар 1984 жылдан 1988 жылға дейін өтті. Бұл жарыстар Брюс Уилкокс жасаған алғашқы бәсекеге қабілетті Go бағдарламасы – Nemesis және Дэвид Фотландтың G2.5 бағдарламасын таныстырды, ол кейіннен Cosmos және Go-ның көптеген жақтарына (The Many Faces of Go) айналды. Компьютерлік Go зерттеулерін дамытуға ықпал еткен факторлардың бірі – Инг жүлдесі болды. Бұл жүлде 1985 жылдан 2000 жылға дейін Дүниежүзілік Компьютерлік Go Конгресінде (немесе Инг кубогы) тайваньдық банкир Инг Чанкидің демеушілігімен ұсынылатын, салыстырмалы түрде ірі ақшалай сыйлық еді. Бұл турнирдің жеңімпазына жас ойыншылармен қысқа матчта кемшілікпен ойнауға мүмкіндік берілді. Егер компьютер жеңіске жетсе, жүлде табысталды және жаңа жүлде жарияланды: одан да үлкен сыйлық, егер ойыншыларды одан да аз кемшілікпен жеңсе. Инг жүлделерінің сериясы екі жағдайда аяқталуға тиіс болды: 1) 2000 жылы немесе 2) егер бағдарлама 1 дандық кәсіби ойыншыны ешқандай кемшіліксіз 40 000 000 NT долларына жеңіп алса. Соңғы жеңімпаз 1997 жылы Handtalk болды, ол 11 тастық кемшілікпен 3 (11-13 жастағы) 2-6 дандық әуесқой ойыншыны жеңіп, 250 000 NT долларын жеңіп алды. 2000 жылы жүлде мерзімі біткен кезде талап етілмеген жүлде 9 тастық кемшілікпен жеңіске жеткені үшін 400 000 NT долларын құрады. Көптеген басқа да ірі аймақтық Go турнирлерінде ("конгрестерде") компьютерлік Go іс-шаралары өткізілді. Еуропалық Go Конгресі 1987 жылдан бері компьютерлік турнирді демеушілік етеді, ал USENIX іс-шарасы 1988 жылдан 2000 жылға дейін АҚШ-тың Go Конгресінде жыл сайын өткізілетін АҚШ/Солтүстік Американың Компьютерлік Go Чемпионатына айналды. Жапония 1995 жылы компьютерлік Go жарыстарын демеушілік етуді бастады. FOST кубогы 1995 жылдан 1999 жылға дейін Токиода жыл сайын өткізілді. Бұл турнир 2003 жылдан 2006 жылға дейін жыл сайын Огакиде (Гифу) өткізілетін Гифу шақыруымен (Gifu Challenge) ауыстырылды. Computer Go UEC кубогы 2007 жылдан бері жыл сайын өткізілуде.

Компьютерлік компьютерлік ойындардағы балл белгілеу

Екі компьютер бір-біріне қарсы Го ойынын ойнағанда, идеалды жағдай – ойынды екі адам ойнаған сияқты өткізу, ал нақты адамдардың араласуына жол бермеу. Дегенмен, ойын соңында есептесу кезінде бұл қиындық тудыруы мүмкін. Басты мәселе – әдетте стандартталған Go Text Protocol (GTP) арқылы байланысатын Го ойнату бағдарламалық жасақтамасы, тастардың тірі немесе өлі екендігіне қатысты әрдайым келіспеуі мүмкін. Екі бағдарламаның арасында «келісіп» дауды шешуге жалпы жол болмаса да, бұл мәселені көбінесе Қытай, Тромп Тейлор немесе Американдық Го Ассоциациясының (AGA) ережелерін қолдану арқылы болдырмауға болады. Бұл ережелерде ойынды тастардың статусы бойынша келісімге келгенше (барлық өлі тастар алынғанша) қосымша жүргізу талап етіледі. Мысалы, KGS Go Server-де сервер екі клиенттік бағдарламаға арнайы GTP командасын жіберіп, дауды реттеуге болады, осы арқылы оларға белгілі бір топтың статусы туралы сұрақтар қалғанша тастарды орналастыруды жалғастыру керектігін көрсетеді. CGOS Go Server көбінесе бағдарламалардың есептесу кезеңіне жетпес бұрын бас тартуын көреді, бірақ десе де Tromp Taylor ережелерінің толыққанды ойнатылуды талап ететін өзгертілген нұсқасын қолдайды. Бұл ережелер жиынтығы бойынша, ойын соңында жапон ережелері бойынша (екі ойыншы да өтті деп жариялағанда) жеңіске жеткен бағдарлама, шешім кезеңінде нашар ойнағандықтан теориялық тұрғыда жеңіліске ұшырауы мүмкін, бірақ мұндай жағдай өте сирек кездеседі және барлық аймақтық ережелер бойынша ойынның қалыпты бөлігі саналады. Аталған жүйенің басты кемшілігі – кейбір ережелер (дәстүрлі жапон ережелері сияқты) ойыншыларды осы қосымша жүргізілген қозғалыстар үшін жазалайды, бұл екі компьютер үшін қосымша ойнатылу мүмкіндігін жоққа шығарады. Дегенмен, қазіргі заманғы Го бағдарламаларының көпшілігі адамдарға қарсы жапон ережелерін қолдайды. Тарихи тұрғыдан алғанда, бұл мәселені шешудің тағы бір тәсілі – соңғы позицияны сарапшы адамға бағалау үшін ұсыну болатын. Алайда, бұл нәтижелерге субъективтілік енгізеді және сарапшының бағдарламада көрген нәрсені жіберіп алу қаупін тудырады.

When two computers play a game of Go against each other, the ideal is to treat the game in a manner identical to two humans playing while avoiding any intervention from actual humans. However, this can be difficult during end game scoring. The main problem is that Go playing software, which usually communicates using the standardized Go Text Protocol (GTP), will not always agree with respect to the alive or dead status of stones. While there is no general way for two different programs to "talk it out" and resolve the conflict, this problem is avoided for the most part by using Chinese, Tromp Taylor, or American Go Association (AGA) rules in which continued play (without penalty) is required until there is no more disagreement on the status of any stones on the board. In practice, such as on the KGS Go Server, the server can mediate a dispute by sending a special GTP command to the two client programs indicating they should continue placing stones until there is no question about the status of any particular group (all dead stones have been captured). The CGOS Go Server usually sees programs resign before a game has even reached the scoring phase, but nevertheless supports a modified version of Tromp Taylor rules requiring a full play out. These rule sets mean that a program which was in a winning position at the end of the game under Japanese rules (when both players have passed) could theoretically lose because of poor play in the resolution phase, but this is very unlikely and considered a normal part of the game under all of the area rule sets. The main drawback to the above system is that some rule sets (such as the traditional Japanese rules) penalize the players for making these extra moves, precluding the use of additional playout for two computers. Nevertheless, most modern Go Programs support Japanese rules against humans. Historically, another method for resolving this problem was to have an expert human judge the final board. However, this introduces subjectivity into the results and the risk that the expert would miss something the program saw.