Интересное
Life-HackНемного поведаю об искусственном интеллекте в шахматах.
Первая часть поста будет содержать немного алгоритмов и касаться вопросов брутфорса, а вторая часть будет чисто исторической: о том, как Михаил Моисеевич Ботвинник пытался создать отличный от всех алгоритм игры в шахматы и что он в итоге получил...
Содержание:
1. Введение
2. Минимакс
3. Альфа-Бета отсечение
4. Эвристики
5. Ботвинник - история его шахматного программирования
6. Почему же провалились попытки Ботвинника? Моё мнение.
7. Список литературы.
1. Введение
Вообще, человечество давно пыталось создать разумные машины. Первое, что мне на ум приходит - "Турка" творение Вольфганга фон Кемпелена, созданное им в 1769 году. На мой взгляд, это было неплохое творение инженерной мысли. Понятное дело, что никакого искусственного интеллекта там не было, внутри автомата сидел шахматист, который при помощи специальных устройств наблюдал за доской и делал ходы. Имхо, это довольно круто.
По-настоящему искусственным интеллектом для игры в шахматы заинтересовались лишь в середине 20 века. Как написал кто-то из великих:" Шахматы - дрозофила для искусственного интеллекта". И вот в 1951 вышла работа Шеннона, посвящённая вопросам шахматного программирования. В ней он затрагивал вопросы поиска лучшего хода и им было выдвинуто два тезиса, полностью противоположные друг другу:
1. Чтобы найти лучший ход надо полностью перебирать всевозможные варианты, используя некоторые эвристики для облегчения перебора. (читай: брутфорс)
2. Существует «умный» перебор, который целенаправленно согласно некоторому алгоритму искал бы лучший ход.
Говоря вкратце, второй подход подразумевает знание некоторого супер-алгоритма, которому не надо всё перебирать. Сам Шеннон верил только в первый подход. А вот наш главный программист в шахматах верил исключительно во второй вариант и именно он загубил наше шахматное программирование.
2. Минимакс
Вообще, первый шахматный алгоритм был придуман фон Нейманом в 1928 году. И это не случайно. фон Нейман является отцом-основателем такого раздела математики как "Теория игр". Он там предложил такой алгоритм как минимакс. Сам минимакс для игры в шахматы был рассмотрен Виннером. Что же это за зверь?
Дано:
- Предположим, что у нас есть два игрока. Кружочек и квадратик.
- У нас есть функция оценивания позиций. Для простоты будем считать, что положительное число означает нашу выгоду, а отрицательное наш убыток и профит для соперника.
Допустим, что необходимо нам оценить некоторую позицию и найти план выигрыша в ней. Для это представим всевозможные варианты продолжения игры из заданной позиции. Затем при помощи нашей функции оценим самые последние позиции в наших расчётах (на рисунке это позиции на 4 уровне). А теперь немного порассуждаем. Очевидно, что мы с соперником на каждом своём ходе будем стремиться выбрать наилучшее развитие событий для себя и чем лучше позиция для меня, то тем хуже она для соперника и наоборот. Тогда, при своём ходе мы будем выбирать позицию с наибольшим значением функции, а соперник с наименьшим.
А теперь, после оценки узловых (самых нижних позиций) начнём восходить по дереву и приписывать оценки узлам по правилу: на уровне, когда ход мой- выбираем наибольшую оценку у потомков, а когда ход противника то с наименьшим. Когда будут оценены все вершины, то легко можно будет точно сказать, какое решение стоит нам принять. В чём же профит у алгоритма?
Profit. Он только один. Алгоритм корректен - он всегда вернёт наилучшее решение, если мы можем построить дерево для всей партии.
Недостатки:
1. Сколько там всего шахматных позиций - 10^120? Ну-ну, успехов.
2. Функция оценки. Как нам запрограммировать функцию оценки позиции?
3. Допустим, мы строим дерево не для всей игры. А хотя бы ходов на 10. Сколько нам надо будет перебрать позиций? Всё равно как-то многовато.
И тут нам на помощь приходит Альфа-Бета отсечение и эвристики.
3. Альфа-Бета отсечение
Основная его идея в том, что ряд позиций можно не рассматривать. Ну а смысл рассматривать альтернативы, если мы гарантированно побеждаем в одном варианте? Зачем нам дальше осуществлять перебор? Рассмотрим чуть подробнее...
Здесь тёмным цветом обозначены не просматриваемые варианты. По-прежнему действуем так же, как и при минимаксном обходе дерева. Только теперь будем динамически обновлять минимаксные оценки, как только это становится возможным. Когда узлу на третьем уровне слева будет выставлена оценка 4, нам не имеет смысла просматривать оставшуюся вершину в последнем уровне т.к. текущая минимаксная оценка на третьем уровне ниже, чем её альтернатива. Поэтому, всё равно соперник выберет её. Поэтому, мы пока продолжаем выставлять минимаксные оценки и обходим дальнейшие узлы дерева. Процедура, по которой мы не стали даже рассматривать узел на нижнем уровне в левом поддереве и имеющим оценку 5, называется бета-отсечением. Аналогичное отсечение происходит в центральном поддереве с узлом, который имел бы оценку 9.
Рассмотрим теперь правое поддерево. Предположим, что мы уже получили минимаксную оценку 5 для узла в первом уровне. Не имеет смысла идти дальше по оставшемуся поддереву потому, что минимаксная оценка не сможет уже возрасти, а текущее её значение не превышает максимальной минимаксной оценки по уровню.
Доказывается, что альфа-бета отсечение позволяет сократить количество вариантов в самом удачном случае до 2n^(m/2)-1, где n-количество уровней в дереве, а m количество узлов на каждом уровне.
Данный алгоритм Аллен Ньюэлл и Герберт Саймон, использовавшие то, что Джо Маккарти назвал «аппроксимацией» в 1958 году, написали, что альфа-бета отсечение «кажется, изобреталось неоднократно». Артур Самуэль, Ричардс, Харт, Левин, Эдвардс независимо предлагали ранние версии этого алгоритма. Маккарти также выдвигал подобные идеи на Дартмутском семинаре в 1956 году, а затем, в 1961 году, предложил для исследования группе своих студентов в MIT, включая Алана Котока.
Александр Брудно, наш советский математик, независимо открыл алгоритм и, что самое важное, доказал его, опубликовав работу в 1963 году. В 1975 году Дональд Кнут и Рональд У. Мур усовершенствовали алгоритм добавив «бета» отсечения.
В списке литературы дам ссылку на псевдокод алгоритма и список эвристик.
4. Эвристики.
Смысл эвристик - подсказать компьютеру на основе жизненных наблюдений, что это позиция хороша/плоха, пора прекратить расчёт, оптимизировать перебор. Для этой цели были созданы следующие эвристики:
Эвристика нулевого хода. Основная идея заключается в том, что расчёт и построение дерева можно прервать на том моменте, когда позиция уже настолько хороша, что если не по правилам позволить противнику сделать два хода подряд, оценка позиции всё равно останется приемлемо высокой. Известно, что эту эвристику одной из первых шахматных программ использовала отечественная «Каисса».
Эвристика убийцы. Идея состоит в том, что хороший ход в одной части дерева является также хорошим и в другой его части на той же самой глубине. для этой цели на каждом уровне мы храним один или два хода-убийцы, которые рассматриваются прежде, чем другие ходы. Успешное отсечение ходом не-убийцы записывает этот ход поверх одного из шагов убийцы для этого уровня. Как пример: почти всегда убить вражеского ферзя хорошо и мы должны рассмотреть его взятие в первую очередь.
Эвристика выборочных продлений. В полной части дерева, глубина поиска может быть увеличена в форсированных вариантах . Различные критерии могут использоваться для того, чтобы принять решение о том, является ли вариант форсированным; примеры - уклонения от шаха, взятие фигуры, которая только что взяла другую фигуру, угроза превращения. Основная опасность заключается в том, что при небрежном использовании выборочные продления могут привести к взрывному росту дерева перебора. Специальный случай выборочных продлений - сингулярная эвристика продления, примененная в программе Deep Thought. Идея состоит в том, чтобы обнаружить форсированные варианты за счет того, что одна из позиций-потомков имеет более значимую оценку, чем другие. Очень схоже с эвристикой убийцы.
Эвристика истории - другой метод усовершенствования для упорядочения ходов. В таблице, индексированной по статистике полей с которых совершаются ходы и полей, на которые совершаются ходы, хранится статистика хороших ходов отсечения. Эта таблица используется при упорядочивании ходов (вместе с другой информацией типа выигрыша/потерь при взятии).
Таблица хэшей/перестановок. Основная идея в том, чтобы запоминать просмотренные позиции т.к. довольно часто многие позиции могут встречаться по нескольку раз в рамках одного и того же построения дерева. На этой идее строятся эндшпильные таблицы Налимова.
5. Трагедия отечественных шахматных программ
Михаил Моисеевич Ботвинник. Патриарх отечественных шахмат. Благодаря ему наши шахматисты АБСОЛЮТНО ДОМИНИРОВАЛИ с 1937 до конца века. Весьма неплохой учёный в области технических наук. Трёхкратный чемпион мира и неплохой программист. Однако, по иронии судьбы именно он и загубил отечественные шахматные программы.
Я не буду расписывать все его шахматные заслуги - это прекрасно сделал Гарри Каспаров в своём монументальном труде "Мои великие предшественники".
Проиграв Петросяну в 1963 году, Михаил Моисеевич решил заняться своей идеей фикс: создать робота-шахматиста. Сначала основная работа велась над тем, как формализовать шахматную задачу и алгоритм поиска принятия решения. Когда первые шаги были сделаны в 1964 году, Михаил Моисеевич решил приступать к разработке алгоритма. Однако, здесь разработка программы существенно застопорилась:
Во-первых, математики (Д. Юдин, М. Шура-Бура, М.Келдыш) отнеслись с существенным скептицизмом к его формализации алгоритма.
Во-вторых, учёные из ИТЭФа разрабатывали свою шахматную программу «КАИССА» и у них не было времени, чтобы работать вместе с Михаилом Моисеевичем над его проектом.
В 1965 году Ботвинник рассказывает о своих шахматных идеях Шеннону и Заде, на торжественном приёме в Москве. Его идеи явно заинтересовали последних, и они даже предложили своё название некоторым терминам. После этого Ботвинник несколько доработал рукопись и снова попробовал её опубликовать. Несмотря на отрицательный отзыв доцента математики Арамоновича, Владимир Симагин, гроссмейстер и редактор бюллетеня ЦШК, решил опубликовать статью Ботвинника в порядке обсуждения. Публикация вышла в свет в 1966 году 13 мая и вызвала серьёзный диспут среди учёных-математиков. Причём, большинство осуждало публикацию.
Причиной осуждения была техническая сложность вычисления основной идеи Ботвинника- вычисление «траекторий» (термин Ботвинника) фигур. Однако, Михаилу Моисеевичу удалось решить и эту проблему, причём всего за две недели. Поэтому, он написал уже новую статью, где рассказывал о поиске траекторий. Эту статью он показал академику Криницкому. Последний после многочасового разговора, корректировки статьи с математической точки зрения, дал положительный отзыв. Воодушевлённые последними событиями, Ботвинник решил не выпускать статью, а напечатать книгу. Академик Островитянов без задержек и проволочек опубликовал книгу «Алгоритм игры в шахматы» в редакции научно-популярной литературы в 1968. Более того, данной работой заинтересовались и в США. Данная работа была переведена на английский язык и опубликована в 1971 году. В этом же году Ботвинник выступает с семинаром в Доме Учёных. Академик Е.Геллер, выступавший инициатором приглашения Ботвинника на семинар, предлагает напечать блок-схему алгоритма игры. Этот препринт увидел свет в 1972 году.
Как результат всех публикаций и трудов, всё-таки было принято решение на государственном уровне (приказы Госплана, Госэнерго, комитет по науке и технике) начать работу над шахматной программой по трудам Ботвинника. В августе 1972 года началась непосредственная разработка программы. В помощь Ботвиннику были выделены два программиста. Первый программист, разбиравшийся в шахматах начал разработку дебютной и эндшпильной баз, а второй программировал понятие траектории. В 1974 году и появились первые трудности - оказалось, что понятие «зоны», одно из ключевых в работе Ботвинника, плохо программируется и с прикладной точки зрения оказалось сомнительным. Пока Ботвинник занимался электротехникой и уделял не всё время шахматной программе, разработка застопорилась окончательно. Поэтому, Ботвинник решил все время посвятить себя шахматной программе. К тому же, в декабре 1974 года Ботвинник получает ещё двух программистов, являющихся ещё и неплохими шахматистами. Дальнейшие два года проходят в разработке баз для миттельшпиля и в 1976 году альфа-версия программы наконец была завершена. Программа была завершена и названа «Пионер».
В декабре 1976 года начался эксперимент, целью которого было проверить, сумеет ли решить «Пионер» знаменитый этюд Рети. И первое испытание закончилось неудачно. Дерево вариантов расползалось без позиционной оценки и баз эндшпиля. Тогда было принято решение: запрограммировать правило квадрата и добавить базы эндшпиля. В январе 1976 года за 74 минуты «Пионер» всё ж справился с задачей. Затем «Пионеру» при дополнительно запрограммированных правилах всё же удалось решить и один этюд Ботвинника, составленный в 1926 году. Затем последовала попытка решить этюд Надареишвили, решение которого в основном варианте требовало 20 полуходов. Путём проб и ошибок в отключении различных модулей, библиотек, перепрограммировании старых и разработке новых правил, «Пионер» всё же сумел решить и его.
Как вы видите, Ботвинник нарушал одно из правил. Он не разрабатывал алгоритм, а подгонял под свои идеи, плодя всевозможные костыли. Я уверен, что Ботвинник понимал, что его путь сомнителен, но гордость... Ладно, я малость отвлёкся.
Затем в этом же году Ботвинник продемонстрировал свою программу (а именно принципы её работы. Сам «Пионер» не участвовал в чемпионате мира) миру на чемпионате по компьютерным шахматам в Канаде. Большим удовольствием для него служил тот факт, что победитель чемпионата «Чесс 4.6» не смог решить этюд Надареишвили. Ботвинник же был окрылён успехом и по возвращению в СССР решил, что корень всех проблем «Пионера» в слабом компьютере и более быстродействующий компьютер сумеет существенно усилить его работу.
Для это цели Ботвинник решил заручиться поддержкой академиков, созвав симпозиум. Однако, на симпозиуме не было практически ни одного голоса за, чтобы усилить компьютер, на котором работал «Пионер» и вообще, было достаточно много упрёков в адрес создателя. Впрочем, сам Ботвинник, несмотря на первое шоковое состояние от услышанного, оценил отклонение своего прошения исключительно как положительное - ведь «Пионер» был всё-таки алгоритмически не до конца готов, а провал испытаний на хорошей машине мог существенно навредить «Пионеру».
Дальнейшая доработка программы привела к удивительному результату - оказалось, что можно использовать «Пионера» и для проведения расчёта затрат ремонтных работ. Версия «Пионер 2.1» была посвящена как раз этому применению. На этой версии программы как раз защитились аспиранты-программисты, работавшие с Ботвинником в 1984 году. Более того, некоторые идеи, положенные в реализацию «Пионера» были успешно внедрены в программы для разработки госплана в 1986 году («Пионер 4.6»). Но в шахматном отношении дела у программы обстояли плохо: программа никуда не прогрессировала, несмотря на работу Ботвинника, который придумал новый вид абстракции цепочки, заменившие зону.
Уже сильно начал давать о себе знать и возраст(сильно за 80) - Михаил Моисеевич стал значительно хуже видеть и общее самочувствие его ухудшалось. В скором времени произошёл развал СССР и идеи Ботвинника оказались совсем невостребованным: экономика перестала быть плановой, а шахматные программы из-за резкого усиления компьютеров стали вполне успешно играть по более простому алгоритмическому методу альфа-бета отсечения. Ботвинник скончался 5 мая 1995 года в Москве...
6. Почему же провалился "Пионер"
Несмотря на то, что «Пионер» в целом показал себя неплохо в экономических задачах, но на шахматном поприще, к сожалению, это был абсолютный провал. Причём, интересен следующий вопрос: почему столь талантливый учёный и величайший гроссмейстер не мог понять, что его идеи в шахматах, выражаясь шахматным языком, заслуживают оценки «?!» (сомнительное решение). Тем более, поводов, чтобы насторожиться, было предостаточно:
-Явная подгонка программы под результат. В машинном обучении такая ситуация называется переобучением. То есть, алгоритм может решить конкретные тестовые задачи, но в целом не обладает хорошей обобщающей способностью. Группа Ботвинника явно подгоняла работу программы под результат.
- В процессе подгонки всё равно приходилось использовать методы, которые чрезвычайно похожи на брутфорсные методы. Например, создание эндшпильных и миттельшпильных баз. А ведь именно этого Ботвинник и хотел избежать...
- Успешное развитие брутфорсных программ и явное отсутствие программ, которые хотя бы частично повторяли идеи Ботвинника. Действительно, немного сомнительно, что кругом одни студенты и профаны, а лишь ты д'Артаньян
- Сильное сопротивление математического сообщества. Понятное дело, что всегда и везде верхушка организаций - серпентарий. Но не до такой же степени, чтобы гнобить только тебя одного...
- Отсутствие шахматного прогресса «Пионера». Ну да. Разрабатываем шахматную программу, которая не играет в шахматы, зато решает экономические задачи. Обыденное дело.
Ответом, как мне кажется, может служить то, что Ботвинника сначала просто коробила сама идея, что простой перебор всех вариантов, дополненный некоторыми эвристиками, может являться оптимальной стратегией. В дальнейшим, видя свою неправоту, ему просто не хотелось признавать того факта, что он был не прав и идея последней четверти его жизни была в корне ошибочной. Более того, экономические успехи его программы давали надежду, что это ошибки программистов, и что стоит найти кого-нить ещё и всё будет хорошо.
Доказательством последнего может служить, что Ботвинник в своих работах «Аналитических и критических работах» в 4 томе, вышедшем где-то за 7-8 лет до его смерти, пишет, что половина программистов не оправдала надежд. Это очень важный момент - люди, которых он мог уволить (и обязательно уволил бы, если бы дело было в них), когда с ними работал, его устраивали.
Как вывод, Ботвинник фактически загубил отечественные шахматные программы: ведь шла разработка «Каиссы» и Ботвинник мог вполне настроить ей позиционные оценки, как это сделал американский гроссмейстер Бенджамин с группой коллег для Deep Blue, а эти оценки могли бы помочь ей сделать неплохой качественный рывок вперёд и это могло бы сделать многое для развития советских шахматных программ. Более того, учитывая, что Ботвинник был величайшим шахматистом и прекрасно разбирался в программировании, если бы он взялся за стандартные методы программирования, то аналог сильнейшей программы Rybka мог бы появиться если не в Советском Союзе, то точно в России и намного раньше Rybka.
Список литературы:
Про идеи Ботвинника я писал, исходя из его работ:
1. М.М.Ботвинник. Аналитические и критические работы. Статьи, воспоминания»// Физкультура и спорт.1987г. 528 стр.
2. М.М.Ботвинник. О кибернетической цели игры.// Физкультура и спорт. 1955г. 120 стр.
3. М.М.Ботвинник. О решении неточных переборных задач.// Советское радио. 1979г. 145 стр.
Про алгоритмы:
4. Н. Нильсон. Искусственный интеллект//М.:Мир.1973г.273 стр. -
Классика. Для общего развития рекомендую. Идеи для Риверси/Шашек/Шахмат в принципе работают.
5. Про эвристики( в виде бонуса псевдокод альфа бета отсечения)
Кто интересуется противостоянием компьютеров и человека в 90ых и начале нулевых, очень рекомендую книжку:
Д.Бронштейн, С.Воронков. Давид против Голиафа// Москва, «Риппол классик», 2002 г. 560 стр.
В ней описывается опыт игры с компьютером в весьма необычном стиле, который, пожалуй, сейчас форменное самоубийство, но тогда смотрелось очень и очень здорово! К тому же, иногда даются интервью с разработчиками шахматных программ - в общем, рекомендую к прочтению.