Перейти к содержанию

3.7 Го - новая цель

Материал из Охота на электроовец: Большая Книга Искусственного Интеллекта

Заниматься игрой в го является намного лучшим делом, чем предаваться целый день праздности и угощению рисом.

Конфуций. Суждения и беседы

Го — игра, которая на протяжении многих лет исполняла роль своеобразного философского камня в области искусственного интеллекта. Число возможных позиций в го (при размере доски 19 × 19) составляет[1] порядка 2 × 10170, а число различных партий оценивается[2] и вовсе в циклопическое число 10360. Если в среднестатистической шахматной позиции возможно 35 потенциальных ходов, то в го это число — 250, то есть больше почти на порядок. Таким образом, кремниевый блок для хранения сильного решения игры го, созданный по технологии, рассмотренной в прошлой главе, был бы примерно в 3 × 1091 раза тяжелее, чем всё обычное вещество нашей Вселенной, так что от затеи по строительству подобного устройства, по всей видимости, придётся отказаться.

Совершенно очевидно, что переборные алгоритмы для игры в го должны обладать чрезвычайной селективностью, то есть рассматривать лишь очень малое подмножество возможных альтернатив. Попытка создания моделей, обладающих подобной разборчивостью, долгое время оборачивалась неизменным фиаско. Если в шахматах оценка позиции на основе формализованных людьми правил позволила худо-бедно оценивать позиции с достаточным качеством, чтобы быстрый перебор компенсировал недостатки подобной оценки, то в го оценка была куда хуже формализуемой, а перебор куда более беспомощным в силу быстрого ветвления игрового дерева. Действительно, для оценки позиции в го довольно трудно придумать точные правила, задача оценки позиции в го похожа на задачу распознавания образов, а для этой задачи на протяжении многих лет также не было удовлетворительного решения.

В 1965 г. британский математик, коллега Тьюринга по Блетчли-парку Ай Джей Гуд писал: «Го на компьютере? — Чтобы запрограммировать компьютер для разумной игры в го, а не просто для игры в соответствии с правилами, необходимо формализовать стратегические принципы игры или разработать самообучающуюся программу. [Стратегические] принципы [го] более качественны и загадочны, чем в шахматах, и более субъективны. Поэтому я думаю, что будет гораздо сложнее запрограммировать компьютер для игры в го, чем в шахматы»[3].

До 2015 г. программы играли в го в лучшем случае на любительском уровне. В варианте игры на доске 9 × 9 машины демонстрировали более впечатляющие результаты, некоторым программам удалось выиграть на маленькой доске некоторое количество игр против профессиональных игроков[4]. Находились исследователи, которые утверждали, что компьютеры никогда не смогут победить сильнейших игроков в го[5].

Первая программа для игры в го была написана Альбертом Зобристом в 1968 г. как часть диссертации, посвящённой распознаванию образов. Зобрист ввёл функцию влияния для оценки территории и использовал хеш-функцию, названную позже его именем, для обнаружения «ко» (правило ко — одно из правил игры го, согласно которому запрещено делать ход, если он приводит к повторению позиции, существовавшей на доске за один ход до этого; в различных вариантах правил го точная формулировка и интерпретация правила ко может различаться). Кстати говоря, хеш-функция Зобриста и по сей день используется в шахматных программах для создания хеш-таблиц перестановок/опровержений, быстрого поиска повторения позиции, поиска позиции в дебютной библиотеке и многих других задач.

В апреле 1981 г. Джонатан Миллен опубликовал[6] в журнале Byte статью, посвящённую Wally, программе для игры в го на доске 15 × 15, которая помещалась в один килобайт оперативной памяти микрокомпьютера KIM-1. В ноябре 1984 г. Брюс Уэбстер опубликовал[7] листинг собственной программы для игры в го на языке MacFORTH для компьютера Apple Macintosh.

Первым оставившим след в истории турниром по компьютерному го стал Acornsoft Computer Go Tournament, прошедший в Лондоне в марте 1984 г. при участии Британской ассоциации го (British Go Association). Все программы-участники использовали популярные микрокомпьютеры BBC Micro и вариант игры с доской 13 × 13. Победителем стала программа, созданная Брониславом Пшибылой[8], [9]. Сегодня она известна под названием Acornsoft Go и доступна для игры в онлайн-эмуляторе BBC Micro[10].

К 1980-м гг. также относится первое появление программ для игры в го в турнирах людей. По всей видимости, первым таким случаем стало участие программы Nemesis в турнирах Массачусетского клуба по го.

В 1987 г. тайваньский фонд Ing Foundation спонсировал первый из серии ежегодных турниров по компьютерному го. Победитель каждого из турниров играл партии с форой против «инсэев» (стремящихся стать профессионалами игроков в го, чей уровень игры в среднем соответствует шестому любительскому дану) и, в зависимости от результатов, мог претендовать на дополнительные призы. Размер приза зависел от размера форы, необходимой программе для победы над инсэем. Максимальный приз соответствовал победе без форы и составлял 40 млн тайваньских долларов (более миллиона долларов США). Он так никому и не достался, и спонсорство со стороны Ing Foundation прекратилось после турнира 2001 г., когда были выиграны призы за фору в 11 камней и более[11].

В 1998 г. сильнейшие игроки побеждали компьютерные программы, предоставляя им огромные форы в 25–30 камней. В ходе чемпионата мира по компьютерному го в 1994 г. программа-победитель Go Intellect проиграла все три игры против игроков-юниоров, имея фору в 15 камней[12]. Игроки, понимавшие и использовавшие специфические слабые места программ, могли выигрывать с гораздо большими форами, чем их менее искушённые коллеги.

Развитие методов Монте-Карло для перебора вариантов в игровых деревьях в комбинации с прогрессом в области машинного обучения привело к тому, что лучшие программы достигли высокого уровня на маленькой доске, а в конце нулевых годов появились первые программы, способные достигать и удерживать ранги низкого уровня на сервере KGS Go (популярный онлайн-сервис для игры в го) для доски 19 × 19[13].

В 2010 г. на Европейском конгрессе по го в Финляндии программа MogoTW смогла, имея фору в семь камней, обыграть (c разницей всего в полтора очка) Каталина Цэрану, игрока пятого профессионального дана (высший дан — девятый, существует также понятие «десятый дан» (дзюдан), но это уже не ранг, указывающий на мастерство игрока, а один из титулов), первого европейца, получившего в го профессиональный дан[14].

В 2011 г. программа Zen, игравшая на 26-ядерном компьютере, достигла уровня пятого, а немногим позже и шестого любительского дана на сервере KGS Go, играя при временно́м ограничении 15 секунд за ход[15].

Теоретически первый профессиональный дан означает, что его обладатель играет сильнее любого любителя, в том числе обладателя седьмого любительского дана (восьмой любительский дан является скорее почётным званием, выдаваемым за особые заслуги перед федерацией го). На деле же бывают и исключения, поскольку для получения профессионального дана необходимо соблюсти немало требований, в том числе сдать специальный экзамен, поэтому обладатель седьмого любительского дана иногда может играть в го на профессиональном уровне, но шестой любительский дан всё-таки далёк от этого.

В 2012 г. Zen победила обладателя необычного (так называемого космического) стиля игры в го Масаки Такемию (девятый дан) на 11 очков при форе в пять камней и на 20 очков при форе в четыре камня[16].

В 2013 г. программа Crazy Stone, имея фору в четыре камня, одержала победу над Йосио Исиду по прозвищу Компьютер[17] (девятый дан)[18].

В 2014 г. состоялся матч без форы Codecentric Go Challenge между Францем-Йозефом Дикхутом (6-й любительский дан) и Crazy Stone. Игра велась на доске 19 × 19 до трёх побед. Дикхут одержал победу, хотя и уступил в первой партии на полтора очка[19]. Ни один из более сильных игроков в го не соглашался до этого играть матч на равных условиях.

В общем и целом успехи программ по игре в го несколько лет назад были весьма невелики. Спустя почти два десятилетия с момента победы над чемпионом мира по шахматам машины, казалось, были всё ещё безнадёжно далеки от чемпионского титула в го. Это заставляло критиканов, вечно принижающих прогресс в области искусственного интеллекта, злорадно потирать руки и отпускать едкие комментарии.

Кто бы мог подумать, что ситуация изменится в одночасье? О дальнейших событиях в мире го мы поговорим в одной из следующих глав.

  1. ↑ John Tromp (2016). Number of legal Go positions // https://tromp.github.io/go/legal.html
  2. ↑ Allis V. (1994). Searching for Solutions in Games and Artificial Intelligence (Ph. D. thesis). University of Limburg, Maastricht, The Netherlands // https://project.dke.maastrichtuniversity.nl/games/files/phd/SearchingForSolutions.pdf
  3. ↑ Good I. J. (1965). The Mystery of Go / New Scientist, 21 January // http://www.chilton-computing.org.uk/acl/literature/reports/p019.htm
  4. ↑ Wedd N. (2016). Human-Computer Go Challenges / computer-go.info // http://www.computer-go.info/h-c/index.html
  5. ↑ Cho A. (2016). ‘Huge leap forward’: Computer that mimics human brain beats professional at game of Go / Science // https://www.sciencemag.org/news/2016/01/huge-leap-forward-computer-mimics-human-brain-beats-professional-game-go
  6. ↑ Millen J. K. (1981). Programming the Game of Go / Byte, April 1981 // https://archive.org/stream/byte-magazine-1981-04/1981_04_BYTE_06-04_Future_Computers#page/n101/mode/2up
  7. ↑ Webster B. (1984). A Go Board for the Macintosh / Byte, November 1981 // https://archive.org/stream/byte-magazine-1984-11/1984_11_BYTE_09-12_New_Chips#page/n125/mode/2up
  8. ↑ Macfadyen M. (1984). Computer Go / British Go Journal No. 61. March 1984 // https://www.britgo.org/bgj/06123.html
  9. ↑ History of Go-playing Programs / Go British Association // https://www.britgo.org/computergo/history
  10. ↑ Bronislaw Przybyla (1984). Acornsoft Go / Sensei's Library // https://senseis.xmp.net/?AcornsoftGo
  11. ↑ History of Go-playing Programs / Go British Association // https://www.britgo.org/computergo/history
  12. ↑ Burmeister J., Wiles J. CS-TR-339 Computer Go Tech Report // https://staff.itee.uq.edu.au/janetw/Computer%20Go/CS-TR-339.html#6.2
  13. ↑ History of Go-playing Programs / Go British Association // https://www.britgo.org/computergo/history
  14. ↑ Strickland J. (2010). Top 5 Computer vs. Human Game Matchups / howstuffworks // https://electronics.howstuffworks.com/5-computer-vs-human-game-matchups5.htm
  15. ↑ Aydinian H., Cicalese F., Deppe C. (2013). Information Theory, Combinatorics, and Search Theory: In Memory of Rudolf Ahlswede. Springer Berlin Heidelberg // https://books.google.ru/books?id=qVW5BQAAQBAJ
  16. ↑ Cosmic Style V.S. Zen (Computer Go) / The Nihon Ki-in[Японская ассоциация го] // https://www.nihonkiin.or.jp/english/topics/12/topics2012_03.htm#120326f
  17. ↑ Shotwell P. (2011). Go! More Than a Game. Tuttle Publishing // https://books.google.ru/books?id=qf_QAgAAQBAJ
  18. ↑ House P. (2014). The Electronic Holy War / The Ney Yorker, March 25, 2014 // https://www.newyorker.com/tech/annals-of-technology/the-electronic-holy-war
  19. ↑ Althöfer I., Snatzke R. G. (2016). The codecentric Go Challenge 2014: Franz-Josef Dickhut vs. CRAZY STONE / ICGA Journal, Vol. 37, Iss. 4, pp. 232—236 // https://www.researchgate.net/publication/293799776_The_codecentric_Go_Challenge_2014_Franz-Josef_Dickhut_vs_CRAZY_STONE

‎

Loading comments...
Источник — http://wiki.markoff.science/index.php?title=3.7_Го_-_новая_цель&oldid=1136