💻 - Компьютеры, которые играют в игры

Кто победит, если две одинаковые программы устроят между собой шахматный турнир? Будут ли партии всегда заканчиваться вничью или у белых будет преимущество первого хода? *старая добрая шутка про расизм* И есть ли какая-то выигрышная стратегия, которая позволила бы полному чайнику одолеть чемпиона?

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

Итак, по сравнению с великими и ужасными шахматами, шашки покажутся развлечением для малышей. Помните, что для английских шашек количество различных вариантов партий равняется 5х10^20, и полностью просчитать их смогли только спустя 18 лет после начала работы программы?

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

Напрашивается очевидный вопрос: раз шашки рассчитали, то и шахматы сможем, разве нет? Ждали же 18 лет, подождем и еще. Всё равно простым смертным нет дела до этих математических извращений, и в каком-нибудь 2040 году, листая ленту девятым кибер-пальцем, мы смахнем новость про найденное решение для шахмат.

К сожалению, пока что это утопия. И дело не в том, что математики поняли, что страдают какой-то фигней, проблема заключается в сложности самой игры: одних только позиций фигур на доске существует около 10^46, а уникальных партий – не меньше 10^120.

Десять в сто двадцатой степени. Это много. Так много, что у нас даже нет аналогии, чтобы показать весь ужас этого гигантского числа, его попросту не существует в физическом мире. Чтобы вы понимали, количество атомов в известной нам части Вселенной примерно равно 10^80, а количество оригинальных партий в шахматах больше этой цифры в 10^40 раз. Причем в начале игры все выглядит довольно безобидно: у белых есть всего двадцать ходов пешками и четыре конями - но с каждым сделанным шагом количество возможных комбинаций на доске очень быстро растет. Так, например, после первого хода каждого из соперников, на поле существует 400 различных позиций для следующего шага, после второго – 72084, после третьего – больше 9 миллионов, после четвертого – более 288 миллиардов. Такое число соразмерно с количеством звезд в нашей галактике, а ведь это всего лишь самое начало партии.

Однако не просто так было сказано, что теория игр без шахмат – как самолёт без двигателя. После окончания Второй мировой еще на заре эпохи машинных вычислений шахматы стали своеобразным эталоном для проверки различных идей в этой области. Клод Шеннон *кстати, именно в честь него число 10^120 называется числом Шеннона*, один из основателей раздела об искусственном интеллекте, говорил, что не видит практической ценности в вычислении всех возможных шахматных партий, но сама эта мысль побуждает исследователей двигаться вперед и развивать технологии до тех пор, пока они не найдут решение.

Первую программу для игры в шахматы написал еще в 1952 году Дитрих Принц (коллега Алана Тьюринга) на компьютере Ferranti Mark. Правда, тут не стоит обольщаться, этот компьютер, лишь отдалённо напоминающий наши современные устройства, был таким слабеньким, что объем его оперативной памяти мог содержать программу только по типу «мат в два хода». Она была рассчитана лишь для последних двух ходов, но начало шахматной эпопеи было положено.

В 1956 году компьютер MANIAC-1 *милое название* сыграл три партии в облегченные шахматы (на поле 6х6 и без слонов) – сам с собой, против сильного игрока и против новичка. Несмотря на то, что опытный шахматист в начале игры решил отказаться от ферзя, программа все равно ему проиграла *какой неумелый маньяк*, но вот последнего – слабого соперника компьютер смог победить. Это была первая победа машины над человеком.