Шахматы — удобный объект исследований в области искусственного интеллекта. Игра проста по структуре, подчинена основной задаче (поставить мат противнику) и не допускает вольной трактовки правил – следовательно, классифицируется как «логическая». Именно на шахматах испытывались многие направления искусственного интеллекта. Например, методики оптимизации перебора (уход от «комбинаторного взрыва» при просчёте вариантов вперёд на несколько ходов), логическое программирование, распознавание образов и экспертные системы.
В этой игре воплотился, известный нам по фантастическим фильмам и книгам, сюжет: человек против машины, плоть и кровь против микросхемы, эмоция против алгоритма. Разумеется, в противостоянии гроссмейстеров и компьютерных программ не наблюдалось голливудского размаха, да и ни о какой угрозе речи не шло, напротив, развитие искусственного интеллекта в наших реалиях одна из составляющих прогресса. И всё же нужно признать, что сражения на доске происходили в лучших традициях драматургии. Об этом сегодня и поговорим, доставайте блокноты и записывайте ходы.
❯ Истоки
Шахматы зародились в Индии полторы тысячи лет назад. Была там такая игра – чатуранга, её принято считать первым предком шахмат. В дальнейшем чатуранга попала в соседние с Индией страны, преобразилась там и сменила название. На Арабском Востоке — шатрандж, в Азии: сянци, макрук и сёги. От арабов шатрандж попал в Европу и Африку. Там (в Европе, не в Африке) игра продолжала меняться вплоть до XV века — тогда-то и сложились классические правила шахмат. А в XIX веке, когда стали проводиться международные турниры, свод правил был официально стандартизирован.
Влияние технологий шахматный мир впервые ощутил во второй половине 18-го века, когда венгерский барон Вольфганг фон Кемпелен изобрёл своего «Механического Турка». Влияние, надо признать, оказалось декоративным. Автаматон Кемплена представлял собой не столько шахматного робота, сколько искусный фокус. Пыль в глаза, конечно, бросили эффектно. Только представьте: «Механический Турок» — машина со сложной системой рычагов и маятников, детище прогресса и, одновременно с тем, настоящее чудо для своего времени. Механизм, который обыгрывает опытных игроков, благодаря каким-то неизведанным граням инженерного гения Вольфгана фон Кемпелена. Это потрясало, завораживало, и это, естественно, был чистой воды трюк. Да, машина действительно была хитро устроена, но не для того, чтобы анализировать и осуществлять ходы, а для того, чтобы прятать внутри живого шахматиста. Вот и вся технологичность. Красивое и хитрое устройство, но, разумеется, о противостоянии человека и машины в данном случае говорить бессмысленно.
Мастерство «Механического Турка» зависело лишь от мастерства спрятанного в нём игрока. Иными словами – посади внутрь сильнейшего шахматиста эпохи и можно смело говорить, что Турок способен победить любого, посади зелёного новичка, и партия против опытного соперника закончится очень быстро. К слову, в 1868 году Чарльз Хупер представил автомат Ajeeb — в котором тоже был спрятан человек.
❯ «Бумажная машина Тьюринга»
Хитрые «шахматные шкатулки» уступили цифровым технологиям в середине XX века. Так в 1951 году Алан Тьюринг подарил миру алгоритм Turochamp. В теории он позволял машине играть в шахматы, однако всё не так просто. Связующим звеном между механизмом и игральной доской вновь выступал человек. А именовался этот нонсенс — «бумажная машина Тьюринга». В чём же суть? Ведущая роль отводится человеку, при этом он не обязан уметь играть в шахматы, даже правил может не знать. Ему нужно просто следовать алгоритму, основанном на информации о ходе соперника. Например, «при ходе противника N передвиньте ферзя на B7». До наших дней даже дошла запись партии, где «бумажная машина Тьюринга» уступила компаньону самого математика. Можно назвать — Turochamp вариацией «китайской комнаты» с шахматным уклоном. В работе же программе не посчастливилось принять участие.
Примерно в то же время математик, инженер, создатель «теории информации» Клод Шеннон опубликовал статью «Программирование компьютера для игры в шахматы». В ней говорилось следующее:
«Шахматная машина идеальна, чтобы с нее начать, поскольку (1) задача четко определяется допустимыми операциями (ходы) и конечной целью (мат); (2) она не слишком проста, чтобы быть тривиальной, и не слишком сложна для получения удовлетворительного решения; (3) считают, что шахматы требуют «мышления» для искусной игры, решение этой задачи приведет нас либо к тому, что мы будем восхищаться способностями механизированного , либо к ограничению нашей концепции «мышления»; (4) дискретная структура шахмат хорошо укладывается в цифровую природу современных компьютеров».
Помимо этого Шеннон отметил существование в шахматах лучшего хода и практическую невозможность его нахождения.
❯ Дальнейшее развитие
1952 год ознаменовал появление программы для игры без участия слонов — шесть клеток вместо восьми. К разработке подошли со всей серьёзностью — она была создана в ядерной лаборатории Лос-Аламоса на компьютере MANIAC I c тактовой частотой 11 кГц. С этой программой, к слову, связан одни любопытней эксперимент. Произвели две партии: в одной компьютеру противостоял умелый шахматист, в другой женщина, которая недавно освоила правила и не имела игрового опыта. Первая партия длилась целых 10 часов, в результате напряжённой борьбы сильнее оказался шахматист. Во второй машина одолела соперницу всего на 23-м ходу. Сейчас нам может показаться, что результат эксперимента не представляет ничего выдающегося, однако в то время – это был настоящий прорыв для мира программирования.
Вскоре на смену программе для игры 6х6 пришла программа, использующая все фигуры. Она была разработана в 1957 году Алексом Бернштейном. А уже в 1958 году Аллен Ньюэлл, Клифф Шоу и Герберт Саймон создали алгоритм, влияющий на дерево поиска. Назвали его «альфа-бета-отсечение». Позже рассмотрим и само «дерево» и алгоритм подробнее, чтобы понимать принцип функционирования.
В 1974 году стартовал Чемпионат мира по шахматам среди компьютерных программ. Победа в нём досталась «Каисса», созданной в Институте проблем управления АН СССР. Всего Чемпионат посетило тринадцать машин из восьми стран.
Уровня элитных игроков компьютеры достигли только в 1983 году. Речь идёт о Belle, созданном Джо Кондоном и Кеном Томпсоном. Его проектировали специально для игры в шахматы, не отвлекаясь на другие возможные сферы применения. Компьютер имел официальный рейтинг – 2250, что делало его настоящим флагманом среди шахматных машин того времени.
❯ Первые столкновения
В этом разделе стоит вспомнить международного гроссмейстера Дэвид Леви и его пари. На каких условиях оно заключалось? Всё просто — ни один компьютер не должен был обыграть Леви в течение следующих десяти лет. Что в результате? С 1968 года вплоть до 1978 – его действительно не смогли превзойти. Леви победил программу Chess 4.7 (сильнейшую на тот момент), но шахматные машины не стояли на месте. В 1989 году программа Deep Thought обыграла Леви. Открытым оставался лишь один вопрос: когда искусственный интеллект достигнет самой вершины шахматного мира — титула чемпиона?
❯ На сцене Deep Blue
В феврале 1996 года случилось знаковое противостояние — Гарри Каспаров сразился с суперкомпьютером Deep Blue. Первую партию взяла машина. У бывалых профессионалов и зелёных новичков перехватило дыхание от этого факта. Дело в том, что подобного ещё ни разу не случалось в турнирных условиях. Deep Blue вычислял 50 миллиардов позиций каждые три минуты, в нём находилось 200 процессоров – против чемпиона выступил настоящий шахматный терминатор. Однако в полном матче победа всё же досталось Каспарову. Он изменил стиль игры, что позволило ему выиграть три следующие партии, а ещё две перевести вничью.
Но его абсолютное чемпионство продлилось не долго. В мае 1997 года Deep Blue вернулся в своей новой, усовершенствованной форме. Со счётом 3,5-2,5 Каспарову было нанесено поражение. А отыграться ему уже не позволили. Создатели разобрали Deep Blue сразу по окончанию игры.
Существует документальный фильм «Матч окончен: Каспаров и машина», в котором не только подробно рассматриваются игры, но и фигурируют упрёки Каспарова в сторону IBM (разработчики Deep Blue) после поражения. А именно механическое вычисление закономерностей и намеренная адаптация компьютера под его стиль игры.
❯ Программа выходит на недосягаемый уровень
Преимущество человечества на шахматной доске постепенно таяло, новые программы появлялись одна за другой и мгновенно навязывали конкуренцию. Так, например, специальный шахматный программно-аппаратный комплекс с 64 процессорами Hydra в 2005 году – не просто победил Майкла Адамса (седьмое место в мире). Нет, Hydra разгромил его. В матче из шести партий преимущество машины оказалось несравненным — 5,5 против 0,5. После этой игры пошли разговоры о том, что компьютер наконец вышел на недосягаемый для человека уровень.
Однако подобная тенденция проявлялась ещё раньше. В 2000 году коммерческие шахматные программы Junior и Fritz перевели в ничью матчи против Гарри Каспарова и Владимира Крамника – предыдущего и действующего чемпионов мира. Каспарова так вообще собрал целую серию подобных сценариев. Против программы Junior в Нью-Йорке результат оказался 3-3, против X3D Fritz – 2-2.
❯ Внутренняя кухня
Поговорим немного о том, что творится в «голове» у машины. Шахматные программы рассматривают игру в виде условного «ветвистого» или вариативного дерева. Все позиции, которые возникнут после множества допустимых ходов, оцениваются, следом оцениваются сами ходы. Анализ продолжается до нахождения конечной позиции (пат, мат), либо достижения максимальной глубины поиска. После оценки выбирается лучшая стратегия. Вычислительные способности компьютера кажутся недосягаемыми для человека. Так среднее количество возможных ходов в каждой позиции равняется примерно тридцати пяти. Для полного анализа четырёх полуходов (это два хода от каждого игрока) исследуется около полутора миллиона возможностей, для шести — два миллиарда.
А сейчас, как заявлялось ранее, коснёмся альфа-бета-отсечения. Древо поиска необходимо «обрезать», то есть ограничивать количество лишних ходов. Вот для этого обычно и применяется «альфа-бета». В нём позиции, получившие меньшую оценку в сравнении с уже оцененными — просто не допускаются.
Приблизительная программная реализация выглядит так:
<i>
private int AlphaBeta(int color, int Depth, int alpha, int beta) {
if (Depth == 0) return Evaluate(color);
int bestmove;
Vector moves = GenerateMoves();
for(int i = 0; i < moves.size(); i++) {
makeMove(moves.get(i));
eval = -AlphaBeta(-color, Depth-1, -beta, -alpha);
unmakeMove(moves.get(i));
if(eval >= beta)
return beta;
if(eval > alpha) {
alpha = eval;
if (Depth == defaultDepth) {
bestmove = moves.get(i);
}
}
}
return alpha;</i>❯ Фора
Машинам приходится жертвовать преимущество человеку, чтобы у того появился шанс на победу. Например, гроссмейстер может превзойти программу, если предоставить ему фору в две пешки. Вот она – разница мастерства. Человека и машину разделяют не просто вычислительные способности, их разрыв измеряется лишними фигурами на доске.
Но и эта фора в скором времени увеличится. Последние 5 лет рейтинг компьютера продолжает расти, а вот у человека изменений не наблюдается. Это, разумеется, не значит, что компьютеры серьёзно угрожают шахматному спорту. Да, есть проблема читинга и заучивания чуть ли не целых партий наизусть благодаря программным решениям, но это всё же что-то из разряда допинга, запретного приёма. Шахматы в своём чистом проявлении никуда не денутся, техническое изучение напротив способно помочь в наработке навыка, открыть новые пути и решения. Шахматы останутся теми же, просто люди и машины начнут (или уже начинают) играть в разных измерениях.
❯ Как дела обстоят сейчас?
В данный момент в шахматном мире царствует эпоха нейронных сетей. Лидирующую позицию занимает движок Stockfish, за ним следуют: Komodo Dragon 2.6, Fat Fritz 2 и LeelaChessZero (LC0).
В чём их преимущество? Нейронные сети намного гибче старых программ, они могут распознавать позиции на доске под разными углами, а это выливается в лучший захват пространства и контроль игры. Дело в том, что преимущество человека над машиной заключается как раз в ставке на долгоиграющие манёвры (такой сюрприз может просто быть не распознан программой), подобную стратегию, к слову, использовал Каспаров в том самом легендарном матче против Deep Blue. Но нейронные сети видят куда больше, они адаптируются и совершенствуются в процессе игры. LC0, например, изначально знала только основные правила передвижения фигур, но самообучилась, после того как провела бесчисленные тысячи и десятки тысяч партий против самой себя же. Стоит признать, что человеку вряд ли удастся когда-нибудь вновь сравняться с машинами. LC0, если хотите, настоящий терминатор новейшего поколения, готовый подстроиться к любому игроку, а после уничтожить его на доске. И это не финальная глава, темпы развития шахматных программ потрясают. Сама игра с её упором на логику, простором для математических решений – стала идеальным полем для искусственного интеллекта с его точностью и прагматичностью. Можно сказать, что в этих шестидесяти четырёх клетках – машина способна видеть будущее.
Автор:
god_from_the_machine
