Компјутерски Го — разлика између измена

С Википедије, слободне енциклопедије
Интерактиван преглед историје
← Старија изменаНовија измена →
Садржај обрисан Садржај додат
ВизуелноВикитекст
Ред 34: Ред 34:
Дуго времена је било општеприхваћено мишљење да Го програм има представља проблем који се у основи разликује од шаховског програма. Веровало се да се методе које се ослањају на брзе глобалне претраге са релативно мало знања у домену нису могле да буду ефективне против мајстора Го-а. Због тога, велики део развијања Го програма током овог времена био је усмерен на начине уз које се могло представити човеколико знање и његово комбиновање са локалним претраживањима да би се одговорила питања тактичке природе. Резултат овога били су програми који су се добро носили са много ситуација, али су имали изражену слабост у општем руковању партије. Такође ови програми нису много побољшани уз повећање процесорске моћи, и напредак у области је био спор.
Дуго времена је било општеприхваћено мишљење да Го програм има представља проблем који се у основи разликује од шаховског програма. Веровало се да се методе које се ослањају на брзе глобалне претраге са релативно мало знања у домену нису могле да буду ефективне против мајстора Го-а. Због тога, велики део развијања Го програма током овог времена био је усмерен на начине уз које се могло представити човеколико знање и његово комбиновање са локалним претраживањима да би се одговорила питања тактичке природе. Резултат овога били су програми који су се добро носили са много ситуација, али су имали изражену слабост у општем руковању партије. Такође ови програми нису много побољшани уз повећање процесорске моћи, и напредак у области је био спор.


Неки истраживачи су увидели потенцијал probabilistic methods е и предвидели да ће они доминирати у рачунарским програмима, али су многи други сматрали да је јак Го програм нешто што ће бити могуће у далекој будућности као резултат великих напретка у области вештачке интелигенције. Чак је и писање програма за утврђивање победника завршене партије било гледано као нетривијална ствар.
Неки истраживачи су увидели потенцијал пробабилистичке методе и предвидели да ће оне доминирати у рачунарским програмима<ref>[http://www.robinupton.com/research/phd/Game_Tree_Searching_with_DSC_%28Upton,1998%29.pdf Game Tree Searching with Dynamic Stochastic Control] pp. 194–195</ref>, али су многи други сматрали да је јак Го програм нешто што ће бити могуће у далекој будућности као резултат великих напретка у области вештачке интелигенције. Чак је и писање програма за утврђивање победника завршене партије било гледано као нетривијална ствар.

Долазак програма заснованих на Монте Карло претрази 2006. године је променио поглед на ову ситуацију у многим погледима, уз првог 9-дан мајстора који је 2013. године доживео пораз уз хендикеп од 4 камена.
Долазак програма заснованих на [[Монте Карло метода|монте карло]] претрази 2006. године је променио поглед на ову ситуацију у многим погледима, уз првог 9-дан мајстора који је 2013. године доживео пораз уз хендикеп од 4 камена.


=== Величина табле ===
=== Величина табле ===
Велика табла (19х19, 361 пресека) је често била постављана као један од главних разлога зашто је тешко направити јак Го програм. Велика табла је спречавала алфа-бета претраживач да постигне дубок поглед без значајне екстензије претраге или хеуристике одстрањивања.
Велика табла (19х19, 361 пресека) је често била постављана као један од главних разлога зашто је тешко направити јак Го програм. Велика табла је спречавала [[алфа-бета претраживач|алфа-бета претраживач]] да постигне дубок поглед без значајне екстензије претраге или хеуристике одстрањивања.
2002. године, рачунарски програм МИГОС (MIni GO Solver) комплетно је решио игру Го на 5х5 табли. Играч са црним каменовима побеђује, притом заузимајући целу таблу.
2002. године, рачунарски програм МИГОС (MIni GO Solver) комплетно је решио игру Го на 5х5 табли. Играч са црним каменовима побеђује, притом заузимајући целу таблу.<ref>{{cite web|url=http://erikvanderwerf.tengen.nl/5x5/5x5solved.html|title=5x5 Go is solved|publisher=|accessdate=28 January 2016}}</ref>


=== Број могућих потеза ===
=== Број могућих потеза ===
Ред 60: Ред 61:
Примена надреалних бројева на завршнице у Го-у, опште анализе игре чији је пионир Џон Х. Конвеј, додатно је развијена од стране Елвин Р. Берлекампа и Давид Волфеа што је наведено у њиховој књизи, Математички Го. Иако није опште корисно у већини позиција, у великој мери помаже при анализи одређених класа позиција.
Примена надреалних бројева на завршнице у Го-у, опште анализе игре чији је пионир Џон Х. Конвеј, додатно је развијена од стране Елвин Р. Берлекампа и Давид Волфеа што је наведено у њиховој књизи, Математички Го. Иако није опште корисно у већини позиција, у великој мери помаже при анализи одређених класа позиција.


Ипак, иако су извршене детаљне студије, доказано је да су завршне игре у Го-у PSPACE-тешке. Постоје многи разлози зашто су толико тешке:
Ипак, иако су извршене детаљне студије, доказано је да су завршне игре у Го-у [[PSPACE|PSPACE-тешке]]. Постоје многи разлози зашто су толико тешке:
* Чак и ако компјутер може да игра сваке локалне области уа завржници перфектно, не можемо закључити да ће његова игра бити савршена у односу на целу таблу. Додатне области разматрања у завршницама укључују Сенте и Готе односе, додељивање приоритета различитим локалним завршницама, пребројавање територија и процена, и тако даље.
* Чак и ако компјутер може да игра на свим локалним областима у завржници перфектно, не можемо закључити да ће његова игра бити савршена у односу на целу таблу. Додатне области разматрања у завршницама укључују Сенте и Готе односе, додељивање приоритета различитим локалним завршницама, пребројавање територија и процена, и тако даље.
* У завршници се може садржати много других аспекта Го-а, укључујући "живот и смрт", за које се зна да су НП-тешки.
* У завршници се може садржати много других аспекта Го-а, укључујући "живот и смрт", за које се зна да су [[НП-тешки проблеми|НП-тешки]].<ref name="Go-Demaine-Hearn">On page 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.) {{cite journal |author=Erik D. Demaine, Robert A. Hearn |title=Playing Games with Algorithms: Algorithmic Combinatorial Game Theory |date=2008-04-22 |arxiv=cs/0106019}}</ref><ref name="Go-Crasmaru">{{cite journal |author=Marcel Crasmaru |title=On the complexity of Tsume-Go |volume=1558 |doi=10.1007/3-540-48957-6_15 |pages= 222–231 | location=London, UK |journal=Lecture Notes in Computer Science |publisher=[[Springer-Verlag]] |year=1999 |series=Lecture Notes in Computer Science |isbn=978-3-540-65766-8}}</ref>
* Свака од локалних области завршнице може утицати на остале. Другим речима, оне су динамичне у природи, иако су визуелно изоловане. Због тога је много теже рачунарима да се баве са тим. Ова природа доводи до неких веома сложених ситуација.
* Свака од локалних области завршнице може утицати на остале. Другим речима, оне су динамичне у природи, иако су визуелно изоловане. Због тога је много теже рачунарима да се баве са тим. Ова природа доводи до неких веома сложених ситуација.
Стога, мало је вероватно да ће бити могуће да се напише разумно брз алгоритам који би играо завршницу беспрекорно.
Стога, мало је вероватно да ће бити могуће да се напише разумно брз алгоритам који би играо завршницу беспрекорно.


=== Редослед игре ===
=== Редослед игре ===
Тренутни го програми базирани на Монте-Карло претрази могу имати потешкоћа при решавању проблема када је редослед потеза важно.
Тренутни го програми базирани на Монте-Карло претрази могу имати потешкоћа при решавању проблема када је редослед потеза важан.<ref>[http://dvandva.org/pipermail/computer-go/2010-August/000827.html example of weak play of a computer program]</ref>


== Тактичка претрага ==
== Тактичка претрага ==

Верзија на датум 19. мај 2016. у 17:37

Рачунарски Го је област вештачке интелигенције (ВИ) задужена за писање рачунарског програма који игра традиционалну игру на табли Го. Игра Го била је плодоносна тема истраживања у области вештачке интелигенције протеклих деценија, која је кулминирала 2016. године, када је тада најбољи програм АлфаГо успео да победи једног од најбољих људи који се професионално баве играњем Го-а.

Перформансе

Го је комплексна игра на табли која захтева интуицију, креативност и стратешко размишљање.[1][2] Дуго се сматрала за тежак изазов у оквиру вештачке интелигенције и знатно је тежа за решавање од шаха. Многи стручњаци у области вештачке интелигенције сматрају да Го захтева више елемената који имитирају људско понашање него шах.[3]

Пре 2015, најбољи Го програми су успели да достигну само аматерски дан ниво.[4] На малој 9х9 табли су се боље показивали, чак су и понекада успевали да победе професионалне играче. Пре успеха АлфаГо-а, неки истраживачи су тврдили да рачунарски програми никада неће успети да победе најбоље Го играче.[5]

Ране деценије

Први Го програм написао је Албер Линдзи Зобрист 1968. године као део своје тезе о препознавању образаца. Ту је уведена функција утицаја за процену територије и зобристово хеширање да детектује ко.

У априлу 1981. Године Џонатан К. Милен је објавио чланак у магазину Бајт где је дискусовао о Волију, Го програму са 15х15 таблом који може да стане на КИМ-1 микропроцесорових 1КВ РАМ-а. Брус Ф. Вебстер је објавио чланак у истом магазину у новембру 1984. у којем је причао о Го програму који је написао.

1998. године неки веома јаки играчи су успели да победе Го програме уз хендикеп од 25-30 каменова, што је огроман хендикеп. Било је случајева на Светском првенству у Го-у 1994. године где је програм који је победио, Го интелект, изгубио све три партије од младих играча Го-а који су играли уз хендикеп од 15 каменова.[6] У суштини, играчи који су разумели и искоришћавали слабости програма су могли да победе уз много већи хендикеп него типични играчи.

21. век

Скорија напредовања у монте карло стаблу претраживања и машинском учењу су довели најбоље програме до виског дан нивоа на малој 9х9 табли. 2009. Године се појавио први програм који је могао да достигне и задржи низак дан ниво на КГС Го серверу на 19х19 табли.

2010. године на европском Го конгресу у Финској, МогоТВ је играо на 19х19 табли против Кејтлин Тарану(5п). МогоТБ успео да победи уз хендикеп од 7 каменова.[7]

2011. године Зен је достигао 5 дан на КГС серверу, играјући партије у којима је дозвољено 15 секунде по потезу. Налог на којем је достигнут тај ниво користи кластер верзију Зен-а која је била покренута на рачунару са 26 језгара.[8]

У 2012. години Зен је победио Такемију Масакија (9п) са 11 поена уз хендикеп од 5 каменова, а касније га је победио са 20 поена уз хендикеп од 4 каменова.[9]

2013. године Луди камен је победио Јошио Ишиду (9п) на 19х19 табли са 4 каменова хендикепа.[10]

2014. године на кодцентричном Го изазову, Луди камен и Франц Јозеф Дикхат (6д) су одиграли меч који се састојао од 5 партија без хендикепа на 19х19 табли. Ово је најбољи играч Го-а који је до тада прихватио да игра озбиљан меч против Го програма на 19х19 табли са једнаким условима. Дикхат је победио, али је Луди камен успео да освоји прву партију са 1.5 поена више.[11]

У октобру 2015. године АлфаГо програм компаније Google DeepMind победио је Фан Хуија, европског Го шампиона, 5 од 5 мечева у турнирским условима.[12]

Марта 2016. године, АлфаГо је успео да победи Ли Седола у прве три од укупно 5 партија.[13] Ово је био први пут да 9-дан мајстор игра професионалан меч против програма без хендикепа.[14] Ли је победио у 4. мечу, док је АлфаГо успео да победи у финалном мечу.

Препреке ка високом нивоу играња

Дуго времена је било општеприхваћено мишљење да Го програм има представља проблем који се у основи разликује од шаховског програма. Веровало се да се методе које се ослањају на брзе глобалне претраге са релативно мало знања у домену нису могле да буду ефективне против мајстора Го-а. Због тога, велики део развијања Го програма током овог времена био је усмерен на начине уз које се могло представити човеколико знање и његово комбиновање са локалним претраживањима да би се одговорила питања тактичке природе. Резултат овога били су програми који су се добро носили са много ситуација, али су имали изражену слабост у општем руковању партије. Такође ови програми нису много побољшани уз повећање процесорске моћи, и напредак у области је био спор.

Неки истраживачи су увидели потенцијал пробабилистичке методе и предвидели да ће оне доминирати у рачунарским програмима[15], али су многи други сматрали да је јак Го програм нешто што ће бити могуће у далекој будућности као резултат великих напретка у области вештачке интелигенције. Чак је и писање програма за утврђивање победника завршене партије било гледано као нетривијална ствар.

Долазак програма заснованих на монте карло претрази 2006. године је променио поглед на ову ситуацију у многим погледима, уз првог 9-дан мајстора који је 2013. године доживео пораз уз хендикеп од 4 камена.

Величина табле

Велика табла (19х19, 361 пресека) је често била постављана као један од главних разлога зашто је тешко направити јак Го програм. Велика табла је спречавала алфа-бета претраживач да постигне дубок поглед без значајне екстензије претраге или хеуристике одстрањивања. 2002. године, рачунарски програм МИГОС (MIni GO Solver) комплетно је решио игру Го на 5х5 табли. Играч са црним каменовима побеђује, притом заузимајући целу таблу.[16]

Број могућих потеза

Настављајући упоређивање са шахом, потези у Го-у нису толико ограничени правилима игре. На првом потезу у шаху играч има 20 легалних потеза. Играчи го-а имају 55 различитих легалних потеза узимајући у обзир симетрију. Овај број се брзо увећава уз разбијање симетрије, и ускоро скоро сваки од 361 различитих потеза се морају проценити. Неки потези су много популарнији током отварања, али их је све могуће одиграти.

Технике из шаха које се не могу применити на Го

Основне слабости Го програма у поређењу са шаховским програмима су служиле да покрену истраживања у много нових рачунарских техника. Технике које су се показале као изузетно ефективне у шаховским програмима су се показале као поприлично слабе у игрању Го-а.

Функција процене

Иако једноставна процена на основу материјала није довољна за шаховске програме, функције процене се често заснивају на томе, уз комбинацију са суптилнијим разматрањима као што су изоловани и двоструки пијуни, топови на отвореним редовима, пијуни на центру табле итд. Ова правила могу бити лако формализована, и таква пружају поприлично добро функцију процене која се може извршавати брзо.

Овакви типови правила процене на основу позиције се не могу ефикасно применити на Го. Вредност Го позиције зависи од комплексног анализирања да ли је група жива, који каменови се могу повезати, и хеуристика на то у којој мери добра позиција има утицаја, или у којој мери се лоша позиција може напасти.

Више од једног потеза се могу сматрати као најбољи у зависности од тога која се стратегија користи при процени. Да би изабрао потез, програм мора да процени различите исходе и да одреди који је најбољи. Ово је тешко због деликатних компромиса који се налазе у Го-у. На пример, могуће је заробити неколико противникових каменова а притом ојачати противникову позицију на неком другом месту. Питање да ли је ово добар потез претставља тешку одлуку, чак и за мајсторе Го-а. Комплексност израчунавања се може видети и овде, пошто неки потез можда неће бити одмах важан, али после много потеза када се друге области табле попуне, може се испоставити да је овај потез био кључан.

Завршна игра

Пошто у завршној игри има мање могућих потеза него на почетку или у средњем периоду игре, неко ће можда претоставити да ју је лакше играти, и да ће је стога рачунарски програм лакше играти. У шаху, програми имају лошије перформансе у завршетку игре пошто се идеје прожимају кроз много потеза унапред. Изузетак су ситуације када се могу користити базе података завршних игара у појединим случајевима.

Примена надреалних бројева на завршнице у Го-у, опште анализе игре чији је пионир Џон Х. Конвеј, додатно је развијена од стране Елвин Р. Берлекампа и Давид Волфеа што је наведено у њиховој књизи, Математички Го. Иако није опште корисно у већини позиција, у великој мери помаже при анализи одређених класа позиција.

Ипак, иако су извршене детаљне студије, доказано је да су завршне игре у Го-у PSPACE-тешке. Постоје многи разлози зашто су толико тешке:

  • Чак и ако компјутер може да игра на свим локалним областима у завржници перфектно, не можемо закључити да ће његова игра бити савршена у односу на целу таблу. Додатне области разматрања у завршницама укључују Сенте и Готе односе, додељивање приоритета различитим локалним завршницама, пребројавање територија и процена, и тако даље.
  • У завршници се може садржати много других аспекта Го-а, укључујући "живот и смрт", за које се зна да су НП-тешки.[17][18]
  • Свака од локалних области завршнице може утицати на остале. Другим речима, оне су динамичне у природи, иако су визуелно изоловане. Због тога је много теже рачунарима да се баве са тим. Ова природа доводи до неких веома сложених ситуација.

Стога, мало је вероватно да ће бити могуће да се напише разумно брз алгоритам који би играо завршницу беспрекорно.

Редослед игре

Тренутни го програми базирани на Монте-Карло претрази могу имати потешкоћа при решавању проблема када је редослед потеза важан.[19]

Тактичка претрага

Један од главних проблема за ГО играча је које групе каменова може држати у животу а које могу бити заробљене. Овај општа класа проблема је позната као живот и смрт. Најдиректнија стратегија за израчунавање живота и смрти је да се изврши претрага стабла о потезима које потенцијално утичу на каменове у питању, а затим да се сачува статус камења на крају главне линије игре.

Међутим, унутар временских и меморијских ограничења, у општем случају није могуће утврдити са потпуном прецизношћу који потези би могли да утичу на "живот" једне групе камења. Ово значи да мора да се примени нека хеуристика за одабир потеза које треба узети у обзир. Крајњи ефекат је да за било који програм, постоји компромис између брзине игре и процене живот и смрт позиција.

Са Бенсоновим алгоритмом, могуће је одредити ланце који су безусловно живи и стога их не би требало у будућности проверавати за сигурност.

Представљање стања

Проблем који сви Го програми морају решити је како да представе тренутно стање игре. За програме који користе опсежне претраживачке технике, стање треба да се копира и / или мења за сваки нов хипотетички потез који се посматра. Ова потреба поставља додатно ограничење да би тренутно стање требало да буде или довољно мало да би могло да се копира брзо или довољно флексибилно да би се потез могао одиграти и поништити лако.

Најлакши начин је да се табла представи као једно- или дво-димензионалан низ, где елементи у низу представљају тачке на табли, и могу да се имају вредност која одговара белом камену, црном камену, или празаној раскрсници . Додатан простор је потребан за чување информације колико каменова је заробљено, чији је ред, и које раскрснице су илегални због Ко правила.

Већина програма, међутим, користи више од информација где се који камен налази за процену позиције. Подаци као што су који су каменови повезани у жицу, које жице су повезане једне са другима, које групе каменова су у опасности од заробљавања и које групе каменова су ефективно мртве, су неопходне да би се направила тачна процена одређене позиције. Иако се ове информације могу издвојити само од положаја каменова, много тога се може много брже израчунати ако се ажурирају при сваком одиграном потезу. Овај ажурирање захтева да се чува више информација као представљање позиције табле, што заузврат може учинити да копирања табле трају дуже. Ова врста компромиса указује на проблеме који су укључени у израду брзих компјутерских Го програма.

Алтернативни метод је да постоји само једна табла на којој се потези играју и враћају како би се смањило коришћење меморије а притом да се резултати евалуације табле сачувају. Овим се избегава да се информације копирају изнова и изнова.


Референце

  1. ^ „Google’s AI Wins First Game in Historic Match With Go Champion”. WIRED. 9. 3. 2016. 
  2. ^ https://www.koreatimes.co.kr/www/news/tech/2016/03/325_200068.html
  3. ^ Bouzy, Bruno; Cazenave, Tristan (9. 8. 2001). „Computer Go: An AI oriented survey”. Artificial Intelligence. 132 (1): 39—103. doi:10.1016/S0004-3702(01)00127-8. Приступљено 14. 3. 2016. 
  4. ^ Wedd, Nick. „Human-Computer Go Challenges”. computer-go.info. Приступљено 2011-10-28. 
  5. ^ „‘Huge leap forward’: Computer that mimics human brain beats professional at game of Go”. 
  6. ^ „CS-TR-339 Computer Go Tech Report”. Приступљено 28. 1. 2016. 
  7. ^ „EGC 2010 Tampere News”. Приступљено 28. 1. 2016. 
  8. ^ „KGS Game Archives”. Приступљено 28. 1. 2016. 
  9. ^ „Zen computer Go program beats Takemiya Masaki with just 4 stones!”. Go Game Guru. Приступљено 28. 1. 2016. 
  10. ^ „「アマ六段の力。天才かも」囲碁棋士、コンピューターに敗れる　初の公式戦”. MSN Sankei News. Приступљено 27. 3. 2013. 
  11. ^ „codecentric go challenge – Just another WordPress site”. Приступљено 28. 1. 2016. 
  12. ^ „Google AI algorithm masters ancient game of Go”. Nature News & Comment. Приступљено 28. 1. 2016. 
  13. ^ „Artificial intelligence: Google's AlphaGo beats Go master Lee Se-dol”. BBC News Online. 12. 3. 2016. Приступљено 12. 3. 2016. 
  14. ^ „Google's DeepMind defeats legendary Go player Lee Se-dol in historic victory”. www.theverge.com. Приступљено 9. 3. 2016. 
  15. ^ Game Tree Searching with Dynamic Stochastic Control pp. 194–195
  16. ^ „5x5 Go is solved”. Приступљено 28. 1. 2016. 
  17. ^ On page 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.) Erik D. Demaine, Robert A. Hearn (2008-04-22). „Playing Games with Algorithms: Algorithmic Combinatorial Game Theory”. arXiv:cs/0106019 Слободан приступ. 
  18. ^ Marcel Crasmaru (1999). „On the complexity of Tsume-Go”. Lecture Notes in Computer Science. Lecture Notes in Computer Science. London, UK: Springer-Verlag. 1558: 222—231. ISBN 978-3-540-65766-8. doi:10.1007/3-540-48957-6_15. 
  19. ^ example of weak play of a computer program
Преузето из „https://sr.wikipedia.org/w/index.php?title=Компјутерски_Го&oldid=11864124”