Охота на электроовец. Большая книга искусственного интеллекта

Марков Сергей Николаевич

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

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

886

Wedd N. (2016). Human-Computer Go Challenges / computer-go.info // http://www.computer-go.info/h-c/index.html

887

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

В

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

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

888

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

889

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

890

Macfadyen M. (1984). Computer Go / British Go Journal No. 61. March 1984 // https://www.britgo.org/bgj/06123.html

891

History of Go-playing Programs / Go British Association // https://www.britgo.org/computergo/history

892

Bronislaw Przybyla (1984). Acornsoft Go / Sensei's Library // https://senseis.xmp.net/?AcornsoftGo

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

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

893

History of Go-playing Programs / Go British Association // https://www.britgo.org/computergo/history

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

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

894

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

895

History of Go-playing Programs / Go British Association // https://www.britgo.org/computergo/history

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

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

896

Strickland J. (2010). Top 5 Computer vs. Human Game Matchups / howstuffworks // https://electronics.howstuffworks.com/5-computer-vs-human-game-matchups5.htm

897

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

Теоретически

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

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

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

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

898

Cosmic Style V.S. Zen (Computer Go) / The Nihon Ki-in[Японская ассоциация го] // https://www.nihonkiin.or.jp/english/topics/12/topics2012_03.htm#120326f

899

Shotwell P. (2011). Go! More Than a Game. Tuttle Publishing // https://books.google.ru/books?id=qf_QAgAAQBAJ

900

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

901

Althofer 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

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

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

3.8 Итоги и перспективы

Так как всякое настоящее состояние простой субстанции, естественно, есть следствие её предыдущего состояния, то настоящее её чревато будущим.

Готфрид фон Лейбниц. Монадология

Как описано в предыдущих главах, к началу 2010-х компьютерные программы доминировали практически во всех настольных играх: некоторые из них вообще оказались решены (например, шашки), для других решения были получены для некоторого, порой весьма внушительного, подмножества позиций, и даже в шахматах, которые часто назывались самой интеллектуальной игрой, достижения компьютерных программ не вызывали сомнений. Однако в то же время существовали игры, успех машин в которых был весьма скромным, — к ним, помимо го, относились, например, покер, бридж, игра аримаа (arimaa), созданная американским программистом индийского происхождения Амаром Саедом в качестве сложной для компьютеров игры [902] .

902

Syed O. The Creation of Arimaa // http://arimaa.com/arimaa/

Традиционные настольные и карточные игры по размеру поискового пространства в большинстве случаев существенно уступают стратегическим компьютерным играм, таким, например, как Civilization, Heroes of Might and Magic, не говоря уже о StarCraft или Dota. И в то же время стратегические компьютерные игры по этому показателю во много раз проще, чем ряд задач, возникающих перед интеллектуальным агентом в реальном мире. Если в арсенале методов искусственного интеллекта не было методов, позволяющих создавать ботов, способных обыгрывать человека в стратегические игры, значит, об успехах в решении стратегических задач в реальном мире можно было только мечтать. Чтобы сделать противостояние компьютерным противникам в играх более сложным, программисты нередко допускали некоторое жульничество — на сверхсложных уровнях в карточных играх компьютерные игроки могли заглядывать в карты противника (например, партнёр «Рентген» в программе «Марьяж» для игры в преферанс [903] ), выполнять действия быстрее или с меньшей ценой (например, в Civilization компьютерные противники на высоких уровнях быстрее совершают открытия и выполняют улучшения [904] ) и, наконец, просто управлять всеми персонажами (юнитами) одновременно и «видеть» всю игровую карту целиком. В реальном мире, однако, большая часть из подобных трюков невозможна, поэтому нужно искать другие решения.

903

Натансон Л., Серов А., Лесной Д. МАРЬЯЖ для Windows: академическое издание // https://dr-vamp-r.ucoz.ru/load/1-1-0-5

904

The Computer Is A Cheating Bastard: Civilization / TV Tropes // https://tvtropes.org/pmwiki/pmwiki.php/TheComputerIsACheatingBastard/Civilization