десно|безоквира Рачунарски Го је област вештачке интелигенције (ВИ) задужена за писање рачунарског програма који игра традиционалну игру на табли Го. Игра Го била је плодоносна тема истраживања у области вештачке интелигенције протеклих деценија, која је кулминирала 2016. године, када је тада најбољи програм AlphaGo успео да победи једног од најбољих људи који се професионално баве играњем Го-а.
Перформансе Го је комплексна игра на табли која захтева интуицију, креативност и стратешко размишљање.AlphaGo victorious once again Дуго се сматрала за тежак изазов у оквиру вештачке интелигенције и знатно је тежа за решавање од шаха. Многи стручњаци у области вештачке интелигенције сматрају да Го захтева више елемената који имитирају људско понашање него шах.
Пре 2015, најбољи Го програми су успели да достигну само аматерски дан ниво. На малој 9х9 табли су се боље показивали, чак су и понекада успевали да победе професионалне играче. Пре успеха AlphaGo-а, неки истраживачи су тврдили да рачунарски програми никада неће успети да победе најбоље Го играче.
Ране деценије Први Го програм написао је Албер Линдзи Зобрист 1968. године као део своје тезе о препознавању образаца. Ту је уведена функција утицаја за процену територије и зобристово хеширање да детектује ко.
У априлу 1981. Године Џонатан К. Милен је објавио чланак у магазину Byte где је дискусовао о Го програму Wally, са 15х15 таблом који може да стане на КИМ-1 микропроцесорових 1КВ РАМ-а. Брус Ф. Вебстер је објавио чланак у истом магазину у новембру 1984. у којем је причао о Го програму који је написао.
Године 1998. неки веома јаки играчи су успели да победе Го програме уз хендикеп од 25-30 каменова, што је огроман хендикеп. Било је случајева на Светском првенству у Го-у 1994. године где је програм који је победио, Go Intellect, изгубио све три партије од младих играча Го-а који су играли уз хендикеп од 15 каменова. У суштини, играчи који су разумели и искоришћавали слабости програма су могли да победе уз много већи хендикеп него типични играчи.
21. век Скорија напредовања у монте карло стаблу претраживања и машинском учењу су довели најбоље програме до виског дан нивоа на малој 9х9 табли. 2009. Године се појавио први програм који је могао да достигне и задржи низак дан ниво на КГС Го серверу на 19х19 табли.
Године 2010. на европском Го конгресу у Финској, МогоТВ је играо на 19х19 табли против Кејтлин Тарану(5п). МогоТБ успео да победи уз хендикеп од 7 каменова.
Године 2011. Zen је достигао 5 дан на КГС серверу, играјући партије у којима је дозвољено 15 секунде по потезу. Налог на којем је достигнут тај ниво користи кластер верзију Зен-а која је била покренута на рачунару са 26 језгара.
У 2012. години Zen је победио Такемију Масакија (9п) са 11 поена уз хендикеп од 5 каменова, а касније га је победио са 20 поена уз хендикеп од 4 каменова.
Године 2013. Crazy Stone је победио Јошио Ишиду (9п) на 19х19 табли са 4 каменова хендикепа.
Године 2014. на кодцентричном Го изазову, Crazy stone и Франц Јозеф Дикхат (6д) су одиграли меч који се састојао од 5 партија без хендикепа на 19х19 табли. Ово је најбољи играч Го-а који је до тада прихватио да игра озбиљан меч против Го програма на 19х19 табли са једнаким условима. Дикхат је победио, али је Луди камен успео да освоји прву партију са 1.5 поена више.
У октобру 2015. године AlphaGo програм компаније Google DeepMind победио је Фан Хуија, европског Го шампиона, 5 од 5 мечева у турнирским условима.
Марта 2016. године, AlphaGo је успео да победи Ли Седола у прве три од укупно 5 партија. Ово је био први пут да 9-дан мајстор игра професионалан меч против програма без хендикепа. Ли је победио у 4. мечу, док је AlphaGo успео да победи у финалном мечу.
Препреке ка високом нивоу играња Дуго времена је било општеприхваћено мишљење да Го програм има представља проблем који се у основи разликује од шаховског програма. Веровало се да се методе које се ослањају на брзе глобалне претраге са релативно мало знања у домену нису могле да буду ефективне против мајстора Го-а. Због тога, велики део развијања Го програма током овог времена био је усмерен на начине уз које се могло представити човеколико знање и његово комбиновање са локалним претраживањима да би се одговорила питања тактичке природе. Резултат овога били су програми који су се добро носили са много ситуација, али су имали изражену слабост у општем руковању партије. Такође ови програми нису много побољшани уз повећање процесорске моћи, и напредак у области је био спор.
Неки истраживачи су увидели потенцијал пробабилистичке методе и предвидели да ће оне доминирати у рачунарским програмимаGame Tree Searching with Dynamic Stochastic Control pp. 194–195, али су многи други сматрали да је јак Го програм нешто што ће бити могуће у далекој будућности као резултат великих напретка у области вештачке интелигенције. Чак је и писање програма за утврђивање победника завршене партије било гледано као нетривијална ствар.
Долазак програма заснованих на монте карло претрази 2006. године је променио поглед на ову ситуацију у многим погледима, уз првог 9-дан мајстора који је 2013. године доживео пораз уз хендикеп од 4 камена.
Величина табле Велика табла (19х19, 361 пресека) је често била постављана као један од главних разлога зашто је тешко направити јак Го програм. Велика табла је спречавала алфа-бета претраживач да постигне дубок поглед без значајне екстензије претраге или хеуристике одстрањивања.
Године 2002, рачунарски програм МИГОС (MIni GO Solver) комплетно је решио игру Го на 5х5 табли. Играч са црним каменовима побеђује, притом заузимајући целу таблу.
Број могућих потеза Настављајући упоређивање са шахом, потези у Го-у нису толико ограничени правилима игре. На првом потезу у шаху играч има 20 легалних потеза. Играчи го-а имају 55 различитих легалних потеза узимајући у обзир симетрију. Овај број се брзо увећава уз разбијање симетрије, и ускоро скоро сваки од 361 различитих потеза се морају проценити. Неки потези су много популарнији током отварања, али их је све могуће одиграти.
Технике из шаха које се не могу применити на Го Основне слабости Го програма у поређењу са шаховским програмима су служиле да покрену истраживања у много нових рачунарских техника. Технике које су се показале као изузетно ефективне у шаховским програмима су се показале као поприлично слабе у игрању Го-а.
Функција процене Иако једноставна процена на основу материјала није довољна за шаховске програме, функције процене се често заснивају на томе, уз комбинацију са суптилнијим разматрањима као што су изоловани и двоструки пијуни, топови на отвореним редовима, пијуни на центру табле итд. Ова правила могу бити лако формализована, и таква пружају поприлично добро функцију процене која се може извршавати брзо.
Овакви типови правила процене на основу позиције се не могу ефикасно применити на Го. Вредност Го позиције зависи од комплексног анализирања да ли је група жива, који каменови се могу повезати, и хеуристика на то у којој мери добра позиција има утицаја, или у којој мери се лоша позиција може напасти.
Више од једног потеза се могу сматрати као најбољи у зависности од тога која се стратегија користи при процени. Да би изабрао потез, програм мора да процени различите исходе и да одреди који је најбољи. Ово је тешко због деликатних компромиса који се налазе у Го-у. На пример, могуће је заробити неколико противникових каменова а притом ојачати противникову позицију на неком другом месту. Питање да ли је ово добар потез представља тешку одлуку, чак и за мајсторе Го-а.
Комплексност израчунавања се може видети и овде, пошто неки потез можда неће бити одмах важан, али после много потеза када се друге области табле попуне, може се испоставити да је овај потез био кључан.
Завршна игра Пошто у завршној игри има мање могућих потеза него на почетку или у средњем периоду игре, неко ће можда претоставити да ју је лакше играти, и да ће је стога рачунарски програм лакше играти. У шаху, програми имају лошије перформансе у завршетку игре пошто се идеје прожимају кроз много потеза унапред. Изузетак су ситуације када се могу користити базе података завршних игара у појединим случајевима.
Примена надреалних бројева на завршнице у Го-у, опште анализе игре чији је пионир Џон Х. Конвеј, додатно је развијена од стране Елвин Р. Берлекампа и Давид Волфеа што је наведено у њиховој књизи, Математички Го. Иако није опште корисно у већини позиција, у великој мери помаже при анализи одређених класа позиција.
Ипак, иако су извршене детаљне студије, доказано је да су завршне игре у Го-у PSPACE-тешке. Постоје многи разлози зашто су толико тешке: Чак и ако компјутер може да игра на свим локалним областима у завржници перфектно, не можемо закључити да ће његова игра бити савршена у односу на целу таблу. Додатне области разматрања у завршницама укључују Сенте и Готе односе, додељивање приоритета различитим локалним завршницама, пребројавање територија и процена, и тако даље. У завршници се може садржати много других аспекта Го-а, укључујући "живот и смрт", за које се зна да су НП-тешки.On pp. 11: "Crasmaru shows that it is NP-complete to determine the status of certain restricted forms of life-and-death problems in Go." (See the following reference.) Свака од локалних области завршнице може утицати на остале. Другим речима, оне су динамичне у природи, иако су визуелно изоловане. Због тога је много теже рачунарима да се баве са тим. Ова природа доводи до неких веома сложених ситуација.
Стога, мало је вероватно да ће бити могуће да се напише разумно брз алгоритам који би играо завршницу беспрекорно.
Редослед игре Тренутни го програми базирани на Монте-Карло претрази могу имати потешкоћа при решавању проблема када је редослед потеза важан.
Тактичка претрага Један од главних проблема за ГО играча је које групе каменова може држати у животу а које могу бити заробљене. Ова општа класа проблема је позната као живот и смрт. Најдиректнија стратегија за израчунавање живота и смрти је да се изврши обилазак стабла о потезима које потенцијално утичу на каменове у питању, а затим да се сачува статус камења на крају главне линије игре.
Међутим, унутар временских и меморијских ограничења, у општем случају није могуће утврдити са потпуном прецизношћу који потези би могли да утичу на "живот" једне групе камења. Ово значи да мора да се примени нека хеуристика за одабир потеза које треба узети у обзир. Крајњи ефекат је да за било који програм, постоји компромис између брзине игре и процене живот и смрт позиција.
Са Бенсоновим алгоритмом, могуће је одредити ланце који су безусловно живи и стога их не би требало у будућности проверавати за сигурност.
Представљање стања Проблем који сви Го програми морају решити је како да представе тренутно стање игре. За програме који користе опсежне претраживачке технике, стање треба да се копира и / или мења за сваки нов хипотетички потез који се посматра. Ова потреба поставља додатно ограничење да би тренутно стање требало да буде или довољно мало да би могло да се копира брзо или довољно флексибилно да би се потез могао одиграти и поништити лако.
Најлакши начин је да се табла представи као једно- или дводимензионалан низ, где елементи у низу представљају тачке на табли, и могу да се имају вредност која одговара белом камену, црном камену, или празаној раскрсници. Додатан простор је потребан за чување информације колико каменова је заробљено, чији је ред, и које раскрснице су илегални због Ко правила.