Как работают шахматные компьютеры

Обновлено: 06.07.2024

Возникновение первых компьютерных шахматных машин
Первое исследование на тему шахматного программирования сделал американский математик Клод Шеннон в 1950 году, он успешно предусмотрел два основных возможных метода поиска которые можно использовать при игре и назвал их «Тип А» и «Тип B». С появлением компьютеров в середине XIX века начинается история создания первых компьютерных шахматных машин. Мотивом для создания компьютерных шахмат было желание развлечься, создавая программы для компьютерных турниров, но главной целью создания шахматных программ послужило научное исследование, которое позволило бы глубже понять человеческий разум. В 1951 году английский математик Алан Тьюринг написал алгоритм, при помощи которого машина могла бы играть в шахматы, но алгоритм был весьма условный и программа ни разу не проверялась в работе. В том же году Клод Шеннон написал первую статью о шахматном программировании. Шеннон отметил невозможность нахождения лучшего хода на практике, хотя теоретически он существовал.

Первую успешную шахматную программу создали в 1952 году в лаборатории Лос-Аламоса на компьютере MANIAC I с тактовой частотой 11 кГц,

MANIAC I
компьютер играл на доске размером 6x6 и без участия слонов, всего сыграно было две партии – против сильного шахматиста и новичка. Первую партию компьютер проиграл, а вторую смог выиграть на 23-м ходу. В 1957 году американским математиком Алексом Бернштейном была создана первая шахматная программа для игры на стандартной доске при участии всех фигур.

Важнейшим годом для шахматного программирования стал 1958, в этот год Аллен Ньюэлл, Клифф Шоу и Герберт Саймон разработали алгоритм уменьшения дерева поиска, названный «альфа-бета-отсечение».

Альфа-бета-отсечение Преимущество этого алгоритма заключалось в значительном уменьшении ветвей подуровней дерева поиска. На основе этого алгоритма и по сей день работают многие сильные шахматные программы.

Эволюция шахматных программ

Начиная со второй половины XIX века развитие искусственного интеллекта и компьютерных шахматных машин стало идти большими шагами. Так, например, уже в 1967 году был проведён матч между двумя шахматными программами. В этом году программа, созданная в Институте теоретической и экспериментальной физики (ИТЭФ), обыграла шахматную программу Стэнфордского университета со счётом 3-1 по партиям, по различным оценкам гроссмейстеров программа имела уровень игры, сравнимый с третьим шахматным разрядом (рейтинг Эло 1000-1100). Развитие и появление различных шахматных программ шло полным ходом и вскоре между ними стали проводиться масштабные соревнования. В августе 1974 года в Стокгольме был проведен первый за всю историю Чемпионат мира по шахматам среди компьютерных программ, в котором программа «Каисса», созданная в 1971 году на основе разработок Института теоретической и экспериментальной физики (ИТЭФ), выиграла все четыре партии и стала первым чемпионом мира среди шахматных программ, на чемпионате она обогнала программы «Chess 4», «Chaos» и «Ribbit», набравшие по три очка. Всего в соревновании участвовали 13 различных компьютерных шахматных машин из 8 стран мира. К 1983 году была создана первая шахматная программа, которая могла сравниться по уровню игры с шахматным мастером, называлась она Belle. Джо Кондон и Кен Томпсон разработали первый компьютер, сделанный исключительно для игры в шахматы. Рейтинг Эло у данного компьютера был 2250, что делало эту шахматную машину сильнейшей для своего времени.

В 1994 году в Мюнхене шахматная программа Fritz 3 смогла обыграть тринадцатого чемпиона мира по шахматам Гарри Каспарова в рамках турнирной блиц-партии. Каспаров сыграл второй матч с этой программой, тринадцатый чемпион мира по шахматам завершил игру с четырьмя победами и двумя ничьими.

В 1996 году для шахмат произошло знаменательное событие, шахматный компьютер Deep Blue впервые за всю историю смог выиграть партию у чемпиона мира по шахматам (Гарри Каспарова) в турнирных условиях, хотя матч всё равно был выигран Гарри Каспаровым со счётом 4-2. В 1997 году произошёл матч-реванш, в котором суперкомпьютер Deep Blue выиграл у тринадцатого чемпиона мира по шахматам Гарри Каспарова со следующим результатом: 2 победы, 3 ничьи, 1 поражение. Этот год стал поворотным в истории шахмат, искусственный интеллект превзошёл человека в игре в шахматы, в будущем разрыв в уровне игры стал только увеличиваться.

На сегодняшний день существует множество программ с открытыми кодами, в частности, Crafty, Fruit и GNU Chess, которые можно свободно загрузить из интернета и которые могут победить большинство профессиональных шахматистов. Программы Fritz, Komodo, Stockfish уже намного превысили уровень действующего чемпиона мира по шахматам, разница составляет по разным подсчётам 400-700 рейтинга Эло.

В 2017 году в шахматном искусственном интеллекте произошла очередная революция, компьютерная нейросеть AlphaZero,

Принцип действия AlphaZero

разработанная компанией Google, обыграла программу Stockfish, из 100 партий AlphaZero выиграла 28, а остальные были сыграны в ничью. Особенность заключалась в том, что AlphaZero основывалась совсем на других алгоритмах, это была нейросеть, которая самообучалась, играя сама с собой миллионы партий, в отличии от Stockfish, работа которой была основана на больших вычислительных мощностях, загруженной базы дебютов, миттельшпилей, эндшпилей и на основе алгоритма «альфа-бета-отсечения».

Сравнительный график

За довольно короткое время искусственный интеллект в решении шахматных задач добился определённого успеха, для наглядности было решено сопоставить прогресс развития человека и искусственного интеллекта в шахматах, наибольшую наглядность дает приблизительный сравнительный график рейтинга Эло.
Из графика можно извлечь следующие выводы: рост рейтинга искусственного интеллекта не прекращается до сих пор; рейтинг человека либо растёт на несколько десятков, либо наблюдается стагнация; наивысшим рейтингом сейчас обладает нейросеть AlphaZero, которая использует в своей основе алгоритмы схожие с интуицией человека, но при этом имеет безошибочность искусственного интеллекта. Таким образом, исходя из сравнения, искусственный интеллект обогнал человека в решении основных шахматных задач и, следовательно, в уровне игры, начиная с 1997 года, когда машина впервые смогла одолеть действующего чемпиона мира, компьютер занял определяющую роль в современных шахматах, если рассматривать их с точки зрения классического варианта. В 2017 году сильнейшим игроком в шахматы стала нейросеть, которая имеет интуицию схожую с человеком и безошибочность искусственного интеллекта.

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

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

Несмотря на ранние механические машины, игравшие в шахматы – и, по меньшей мере, один розыгрыш – механическая игра оставалась гипотетическим вопросом до появления цифровых компьютеров. Работая над своей докторской диссертацией в начале 1940-х, немецкий пионер компьютеростроения Конрад Цузе использовал компьютерные шахматы в качестве примера при разработке языка программирования высокого уровня, названного им "планкалкюль". Но из-за Второй мировой войны его работа не публиковалась вплоть до 1972 года. Поскольку работа Цузе оставалась неизвестной британским и американским инженерам, Норберт Винер, Алан Тьюринг и особенно Клод Шеннон (с его работой 1950 года "Программирование компьютера для игры в шахматы") проложили путь к размышлениям по поводу компьютерных шахмат.

Начав работу в начале 1970-х, исследователи из телефонных лабораторий Белла Кен Томпсон и Джо Кондон разработали Belle, компьютер, игравший в шахматы. Томпсон стал одним из создателей операционной системы Unix, но ещё он очень любил шахматы. Он вырос в эпоху Бобби Фишера, и в молодости участвовал в шахматных турнирах. В лаборатории Белла он устроился в 1966 году, получив диплом магистра по электротехнике и информатике в Калифорнийском университете в Беркли.

Джо Кондон был физиком по образованию, работавшим в металлургическом подразделении лабораторий Белла. Его исследования помогли раскрыть электронную зонную структуру металлов, а интересы развивались по мере появления цифровых компьютеров. Томпсон познакомился с Кондоном, когда они с его партнёром по разработке Unix, Деннисом Ритчи, начали работу над игрой «Космическое путешествие» [Space Travel], используя микрокомпьютер PDP-7, относившийся к компетенции Кондона. Томпсон и Кондон впоследствии вместе работали над множеством проектов, включая продвижение языка С как основного языка для использования в системе коммутаторов AT&T.

Проект Belle начался как программный – Томпсон написал пробную шахматную программу в ранней инструкции для Unix. После присоединения Кондона к команде, программа превратилась в гибридный шахматный компьютер, в котором Томпсон отвечал за программирование, а Кондон разрабатывал железо.

Кен Томпсон (сидит) отвечал за программирование, а Кондон разрабатывал железо.

У Belle были три основные части: генератор ходов, оценщик позиции и таблица перестановок. Генератор ходов определял самую ценную из фигур, находящихся под угрозой, и наименее ценную атакующую фигуру, и сортировал потенциальные ходы на основе этой информации. Оценщик позиции отмечал местоположение короля и его относительную сохранность на разных этапах игры. Таблица перестановок содержала кэш памяти с потенциальными ходами, что делало оценку более эффективной.

Belle использовал метод грубой силы. Он перебирал все возможные ходы, которые может сделать игрок в текущей позиции, и рассматривал все ходы, которые мог сделать противник. Изначально Belle мог просчитывать партию на четыре хода вперёд. Когда Belle дебютировал на Северо-Американском чемпионате по шахматам среди компьютерных программ под эгидой Ассоциации вычислительной техники в 1978, где завоевал первое место, он умел просчитывать партию уже на восемь ходов вперёд. После этого Belle победил в чемпионате ещё четыре раза. В 1983 он также стал первым компьютером, завоевавшим звание «гроссмейстера».

Программисты компьютерных шахмат часто сталкивались с враждебным отношением к ним при попытке выставить свою программу против людей – некоторые из них подозревали программу в шулерства, а другие просто боялись. Захотев испытать Belle в местном шахматном клубе, Томпсон потратил много сил на установление личных связей. Он предлагал соперникам распечатку компьютерного анализа матча. Если Bell выигрывал в смешанных турнирах, где компьютеры играли с людьми, он отказывался брать приз, предлагая его следующему по порядку человеку. В итоге Belle еженедельно играл в Вестфилдском шахматном клубе в городе Вестфилд (Нью-Джерси) почти десять лет.

По контрасту с человеческими шахматными соревнованиями, где соблюдали тишину, чтобы не отвлекать игроков, компьютерные шахматные турниры были довольно шумным местом, где люди обсуждали и спорили по поводу различных алгоритмов и игровых стратегий. В 2005 году Томпсон вспоминал их с удовольствием. После турнира он чувствовал прилив сил, и возвращался в лабораторию, чтобы сразиться с очередной задачей.

Для компьютера у Belle была яркая жизнь – однажды он даже стал центром корпоративного розыгрыша. В 1978 году специалист по информатике из лабораторий Белла Майк Леск, ещё один член команды Unix, позаимствовал фирменные бланки AT&T у председателя совета директоров Джона Дибатса, и написал подложную докладную записку, где объявил о прекращении проекта T. Belle Computer.

Центром шуточной докладной записки стал философский вопрос: является ли игра человека и компьютера разновидностью коммуникаций или обработкой данных? В записке объявлялось, что верен второй вариант, из-за чего Belle нарушал антимонопольное постановление 1956 года, запрещавшее компании заниматься бизнесом, связанным с вычислительными машинами. На самом же деле директора AT&T никогда не заставляли создателей Belle прекращать играть или изобретать игры на работе, вероятно оттого, что эти их отвлечения приводили к экономически выгодным исследованиям. Розыгрыш получил известность после того, как Деннис Ритчи написал о нём в статье 2001 года для специального выпуска журнала международной ассоциации компьютерных игр, посвящённого вкладу Томпсона в компьютерные шахматы.

В своих воспоминаниях Томпсон описывает, как Belle стал также объектом международных интриг. В начале 1980 советский инженер-электрик, специалист по информатике и гроссмейстер Михаил Моисеевич Ботвинник предложил Томпсону привести Belle в Москву для проведения демонстраций. Тот вылетел из нью-йоркского аэропорта им. Джона Кеннеди, и вдруг обнаружил, что Belle не было на его самолёте.

Судьбу Belle Томпсон узнал, пробыв в Москве несколько дней. Сотрудник службы безопасности лабораторий Белла, подрабатывавший в аэропорту, увидел коробку от лабораторий с надписью «компьютер», которую везли через таможню. Охранник предупредил своих друзей из лабораторий, эта история дошла до Кондона, и тот позвонил Томпсону.

Кондон предупредил Томпсона, чтобы тот выбросил запасные части для Belle, которые тот вёз с собой. «Тебя, скорее всего, арестуют по возвращению домой», — сказал он. «За что?» – спросил Томпсон. «За контрабанду компьютеров в Россию», — ответил Кондон.

В воспоминаниях Томпсон предполагает, что Belle пал жертвой мнения рейгановской администрации по поводу «утечки технологий» в СССР. Чрезмерно ретивые таможенники США заметили коробку Томпсона и конфисковали её, однако не сообщили об этом ни ему, ни в лаборатории. Его московская принимающая сторона согласилась, что винить в этом нужно Рейгана. Когда Томпсон встретился с ними, чтобы объяснить, что Belle задержали на таможне, глава советского шахматного клуба заметил, что аятолла Хомейни законодательно запретил шахматы в Иране на том основании, что они были противны богу. «Не думаете ли вы, что Рейган сделал это, чтобы запретить шахматы в США?» – спросил он Томпсона.

По возвращению в штаты Томпсон воспользовался советом Кондона, и оставил запасные части в Германии. По прибытию его никто не арестовал, ни за контрабанду, ни за что-либо иное. Однако попытавшись забрать Belle в аэропорту, он получил отказ на основании того, что он нарушает закон об экспорте – устаревший монитор Belle от компании Hewlett-Packard оказался в списках запрещённых к вывозу предметов. Лаборатории Белла заплатили штраф, и Belle в итоге вернули.

После того, как Belle несколько лет доминировала в мире компьютерных шахмат, её звезда начала закатываться, поскольку появились более мощные компьютеры с более хитрыми алгоритмами. Главным среди них был Deep Blue от IBM, привлекший внимание международной общественности в 1996 году, выиграв игру против чемпиона мира Гарри Каспарова. В итоге Каспаров выиграл матч, но это заложило основы реванша. В следующем году, претерпев существенное обновление, Deep Blue победил Каспарова, став первым компьютером, обыгравшим чемпиона мира среди людей в турнире, где регулируется время.

Моё внимание к Belle привлёк фотограф Питер Адамс, и его история демонстрирует, как важно дружить с архивариусами. Адамс фотографировал Томпсона и многих из его коллег по лабораториям Белла для серий портретов «Лица открытого кода». В процессе изысканий Адамса корпоративный архивариус лабораторий Белла Эд Экерт дал ему разрешение на фотографирование некоторых артефактов, связанных с исследовательской лабораторией Unix. Адамс записал Belle в свой список желаний, но предположил, что он сейчас находится в какой-нибудь музейной коллекции. К его изумлению он узнал, что машина всё ещё стоит в Nokia Bell Labs в Мюррей-Хилл (Нью-Джерси). Как писал мне Адамс, «до сих пор можно было разглядеть на нём износ от всех сыгранных им шахматных партий».

Когда создавались первые вычислительные машины, их воспринимали только как дополнение к человеческому разуму. И до недавнего времени так и было. Программисты учили компьютеры играть в шахматы с 1960-х годов. И тогда победа у игрока-новичка уже считалась большим прогрессом. О серьёзных матчах даже не задумывались.

В 1980-х программа Belle достигла рейтинга Эло в 2250 пунктов, что примерно соответствует рейтингу мастера спорта. И с того времени развитие компьютерных шахмат вышло на совершенно новый уровень.

Сначала честь человечества не смог защитить Гарри Каспаров в 1996 году, а сегодня уже создана нейросеть с рейтингом около 5000 Эло, что в разы превосходит даже сильнейших игроков.

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

Как работает шахматный движок: от механического перебора вариантов до «умного» выбора

У шахмат довольно простые правила. Две противоборствующие стороны, шесть разновидностей фигур и одна цель – дать мат сопернику.

Но при этом вариативность шахмат просто огромна. Существует 400 уникальных комбинаций первого хода – 20 вариантов первого полухода белых и 20 вариантов ответа чёрных. С каждым последующим ходом количество уникальных позиций увеличивается на степень.

Общее количество уникальных партий в шахматы составляет примерно 10 120 , что на 10 40 превышает количество атомов во Вселенной.

Шахматам не грозит быть посчитанными полностью. Поэтому в бой вступают алгоритмы оценки позиции и дерево возможных ходов.

В шахматной теории у каждой фигуры есть своя ценность, которая измеряется в пешках:

Король – бесценен, потому что его потеря означает проигрыш партии.

Анализ современных машин подтверждает истинность такой оценки. Так, в зависимости от позиции на доске компьютер оценивает ферзя в 9–12 пешек, ладью – в 5–6, коня и слона – в 3–5. Короля же машина оценивает в 300 пешек. Это задаёт максимальную границу оценки.

Чтобы было более понятно, преимущество в 0,5 пешки – это уже неплохо для шахматиста. В целую пешку – серьёзный перевес. В 3 пешки – подавляющее преимущество, которое можно практически без проблем довести до победы.
Но счётные возможности машины ограниченны. Иногда она показывает оценку в +51 или что-то вроде. Это означает, что алгоритм видит колоссальное преимущество белых в позиции и материале, но не может найти конкретный путь к мату.

Минимакс, или прямой перебор вариантов, в таком случае не работает. Даже КМС без проблем найдёт на доске мат в 3 хода в миттельшпиле, когда на доске ещё много фигур. А программе для этого нужно будет перебрать свыше 750 млн. полуходов.

Даже если программа перебирает 1 млн вариантов в секунду, чтобы найти мат в 3 хода, ей понадобится до 750 секунд, или 12,5 минут.

И это глубина в 3 хода. В стратегических позициях, где развитие игры идёт с учетом на пять или десять ходов вперёд, такие программы и вовсе будут бесполезными.

Поэтому для анализа позиции используется алгоритм под названием «альфа-бета-отсечение».

Система анализирует начальные варианты ходов и сразу отсекает те из них, которые ведут к мгновенному ухудшению оценки.

Программа отметает те варианты, в которых она сразу проигрывает материал или которые включают комбинации со стороны соперника, в ходе которых она выигрывает материал или партию.

Это позволяет сократить количество рабочих линий на порядки, сосредотачивая вычислительные ресурсы только на тех ветвях дерева, которые в перспективе ведут к улучшению позиции.

Псевдокод для минимакса с ограниченной глубиной с отсечением альфа-бета выглядит следующим образом:

За код особо не ругайте.

Рассмотрим на примере. Движок Stockfish считается сегодня одной из самых сильных компьютерных шахматных программ. Обратите внимание на первые пять линий.

Из всего множества вариантов развития событий программа выбирает ряд линий, которые в перспективе ведут к улучшению позиции. Их она анализирует более глубоко – на 15–20 ходов вперёд, чтобы отсечь возможные проигрышные варианты. В результате она выбирает лучшую из возможных линий и делает ход.

После ответа соперника ситуация снова анализируется по тому же алгоритму. Сначала отсекаются заведомо проигрышные линии (таких порядка 95 %), а затем путём более глубокого анализа перспективных вариантов выбирается лучший из них.

Новая эра в шахматных движках: нейросеть Alpha Zero

В 2017 году компания Deep Mind объявила о создании нейросети Alpha Zero. Тестировать её решили на трёх самых популярных стратегических настольных играх: шахматы, го и сёги.

Обучение и подготовка нейросети отличаются от классических компьютерных движков.

Stockfish и другие движки используют для своей работы существующие дебютные базы и анализ позиций огромного количества сыгранных партий.

Alpha Zero не использует ничего, кроме правил. Ей просто дали стартовую позицию, объяснили, как ходят фигуры, и цель игры – поставить мат сопернику. И всё.

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

В декабре 2018 года Alpha Zero во второй раз сразилась с самой последней версией движка Stockfish.

Исследователи провели 1000 партий с контролем 3 часа на партию плюс 15 секунд на ход. Alpha Zero одержала уверенную победу, выиграв в 155 партиях, сыграв вничью 839 партий и проиграв только 6.
Более того, Alpha Zero одерживала победу даже в партиях с форой по времени на обдумывание. Имея в 10 раз меньше времени, чем у противника, нейросеть всё равно победила в суммарном итоге. Только 30-кратная фора во времени смогла уравнять шансы и дать Stockfish примерно равную игру – 3 часа у движка и всего лишь 6 минут у нейросети.

Alpha Zero анализирует лишь 60 000 позиций в секунду, а тестируемая версия Stockfish – 60 млн. позиций. Для достижения аналогичных результатов анализа нейросети нужно в 1000 раз меньше ресурсов, чем движку.

Секрет успеха – в качественно другом уровне анализа. Нейросеть использует метод Монте-Карло, который высчитывает математическое ожидание комплекса ходов.

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

И, что гораздо более важно, при оценке ситуации Alpha Zero учитывает стратегическую позицию.

Давайте рассмотрим на примере одной из партий.

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

Позиционная игра – это то, что отличает нейросеть от классического шахматного движка. Ведь она подразумевает длительные игровые планы, которые часто превышают вычислительные возможности машин.

Тем не менее нейросеть умеет играть позиционно не хуже человека и при этом идеально играет тактические позиции, где преимущество достигается в течение 5 или меньше ходов.

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

Многие теоретики считают, что благодаря шахматным компьютерам повысился и средний рейтинг топовых шахматистов. Ведь современные тренировки включают глубокую проработку компьютерных вариантов и разбора партий движками. Средний рейтинг ведущих топ-100 шахматистов в 2000 году составлял 2644 пункта Эло, а в январе 2021 года – 2715. За 20 лет среднее значение увеличилось на 71 пункт.

Сегодня человек уже не способен соревноваться с компьютером в шахматах. Нейросеть вобрала в себя все преимущества человеческого шахматного мышления, но при этом лишена его недостатков.

Она умеет мыслить позиционно и при этом не допускает зевков и ошибок. И самое интересное в этом – шахматы для Alpha Zero являются только тестовым полигоном, где система оттачивает навыки работы. Реальные же её цели Google не раскрывает. Поэтому здесь может быть всё что угодно: от анализа изменений климатической ситуации до создания системы идеально персонифицированной рекламы. А как вы считаете, для чего создают настолько мощную нейросеть?

Создать своего гениального цифрового шахматиста или получить Level Up по навыкам и зарплате можно пройдя онлайн-курсы SkillFactory со скидкой 40% и промокодом HABR, который даст еще +10% скидки на обучение. Узнайте подробности.

Как работает шахматный движок: от механического перебора вариантов до «умного» выбора

Общее количество уникальных партий в шахматы составляет примерно 10120, что на 1040 превышает количество атомов во Вселенной.

В шахматной теории у каждой фигуры есть своя ценность, которая измеряется в пешках:

Король – бесценен, потому что его потеря означает проигрыш партии.

Чтобы было более понятно, преимущество в 0,5 пешки – это уже неплохо для шахматиста. В целую пешку – серьёзный перевес. В 3 пешки – подавляющее преимущество, которое можно практически без проблем довести до победы.
Но счётные возможности машины ограниченны. Иногда она показывает оценку в +51 или что-то вроде. Это означает, что алгоритм видит колоссальное преимущество белых в позиции и материале, но не может найти конкретный путь к мату.

Поэтому для анализа позиции используется алгоритм под названием «альфа-бета-отсечение».

В варианте кода это может быть реализовано примерно следующим образом:

За код особо не ругайте.

Новая эра в шахматных движках: нейросеть Alpha Zero

Обучение и подготовка нейросети отличаются от классических компьютерных движков.

В декабре 2018 года Alpha Zero во второй раз сразилась с самой последней версией движка Stockfish.

Исследователи провели 1000 партий с контролем 3 часа на партию плюс 15 секунд на ход. Alpha Zero одержала уверенную победу, выиграв в 155 партиях, сыграв вничью 839 партий и проиграв только 6.
Более того, Alpha Zero одерживала победу даже в партиях с форой по времени на обдумывание. Имея в 10 раз меньше времени, чем у противника, нейросеть всё равно победила в суммарном итоге. Только 30-кратная фора во времени смогла уравнять шансы и дать Stockfish примерно равную игру – 3 часа у движка и всего лишь 6 минут у нейросети.

И, что гораздо более важно, при оценке ситуации Alpha Zero учитывает стратегическую позицию.

Давайте рассмотрим на примере одной из партий.

Она умеет мыслить позиционно и при этом не допускает зевков и ошибок. И самое интересное в этом ситуации – шахматы для Alpha Zero являются только тестировочным полигоном, где система оттачивает навыки работы. Реальные же её цели Google не раскрывает. Поэтому здесь может быть всё что угодно: от анализа изменений климатической ситуации до создания системы идеально персонифицированной рекламы. А как вы считаете, для чего создают настолько мощную нейросеть?

Будущее шахмат за компьютерами. Трудно найти человека, который не согласится с этим утверждением.

Однако эти слова не совсем точны. В общем и целом компьютеры стали для шахмат и настоящим.

За шахматной доской человек и машина противостоят друг другу, но самыми увлеченными учителями шахмат являются разработчики программ, а самыми лучшими учениками - компьютерные движки.

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

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

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

Подобно тому, как Магнус Карлсен, Фабиано Каруана, Виши Ананд, Веселин Топалов и Хикаро Накамура (и прочие) доминируют в шахматном мире людей, также и элитные движки царят в мире компьютерных шахмат.

Вашему вниманию предлагается пятерка сильнейших шахматных движков. Поделитесь, пожалуйста, с нами своими мыслями о компьютерных шахматах, оставив комментарий на нашей странице в Фейсбуке.

5. Gull 2.8b (англ. "чайка", произносится - "галл")

Рейтинг: 3214

"Галл" можно назвать дебютантом среди элиты компьютерных шахмат. Этот бесплатный движок на основе открытого кода создан Вадимом Демичевым по образу и подобию 2-х других более ранних шахматных программ: "Айвенго" и "Стрелки".

В новой версии рейтинга компьютерных шахматных программ CCRL 40/40 Pure (в котором для предотвращения размывания показателей от каждого семейства движков представлена только одна версия) "Галл" завоевал 11 баллов, расположившись на 5-м месте среди лучших шахматистов Вселенной.

4. Fire 4 (англ. "пламя", произносится - "фаер")

Рейтинг: 3229

Картинка с сайта Fire

"Фаер" - бесплатный движок, который ранее функционировал на основе открытого кода (но больше его не использует).

Его разработка началась в 2010-м году, и поэтому "Фаер" можно назвать еще одним быстро прогрессирующий представитель мира компьютерных шахмат. В рейтинге компьютерных шахматных программ CCRL pure он набрал на 16 баллов больше своей версии с обычной базой данных, превысив аналогичные показатели всех движков из топ15.

3. Houdini 4 (англ. "Гудини")

Рейтинг: 3277

картинка с сайта Гудини

Гудини - платный движок, который раньше был сильнейшим в мире, но и сегодня остается мощной шахматной программой.

По словам создателей: "Название "Гудини" было дано за стиль позиционной игры, демонстрируемый движком, его стойкость в сложных позициях и способность обороняться с упорством и находить спасительную ничью, иногда находясь на волосок от гибели".

2. Stockfish 6 (англ. "вяленая рыба", произносится - "стокфиш")

Рейтинг: 3318

Картинка с сайта Stockfish

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

Главные преимущества Стокфиш, заключаются в том, что он бесплатный, использует открытый код и поддерживает кросс-платформенность.

Также Стокфиш стал победителем в самом интересном показательном выступлении, из когда-либо проводившихся Chess.com, нанеся поржение "киборгу" Хикару Накамуре, который играл против Стокфиш, используя более раннюю и более слабую версию шахматного движка.

Посмотрите, пожалуйста, на комментарий Дэниэла Ренша по этому матчу, представленный на видеоролике размещенном внизу.

1. Komodo 9 (англ. "Комодо")

Рейтинг: 3340

Комодо - лучшая платная программа, ставшая безоговорочным чемпионом в 2014-м году, после чего ее в этом году ненадолго превзошла новая версия Стокфиш. Затем его разработчики выпустили 9-ю версию Комодо, которая приблизительно на 50 рейтинговых баллов превзошла свою предшественницу.

“Я поражен до глубины души игрой Комодо. Я наблюдал и анализировал все партии и стал свидетелем безупречной позиционной игры, равной которой никогда не показывали ни компьютеры, ни люди.”

Что вы думаете о компьютерных шахматах? Поделитесь с нами своим мнением в разделе "Комментарии".

Читайте также: