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

[kaipa]

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

1. Каспаров – Deep Thought. Игра в одни ворота (1989)

2. Первые обидчики. Fritz и Genius (1994-1995)

3. Каспаров против Deep Blue. Часть I: черный ящик (1996)

4. Каспаров против Deep Blue. Часть II: Филадельфийский эксперимент (1996)

В следующем матче в 1997г с усовершенствованным Deep Blue Каспаров проиграл (статья об этом, видимо, еще будет), но примерно до середины 2000х лучшие гроссмейстеры все еще сражались с компьютерами примерно на равных. Есть "закон Мура для шахмат", по которому считается, что удвоение вычислительной мощности вдвое увеличивает силу шахматной программы на 30 пунктов рейтинга Эло. Если учесть, что каждые полтора-два года производительность удваивается, то за 10 лет компьютеры "умнеют" минимум на 300 пунктов, что ОЧЕНЬ много. А если добавить к этому постоянное совершенствование алгоритмов, то понятно, что в шахматах у человека уже шансов нет. Лучшие шахматные программы на довольно скромных четырехпроцессорных компьютерах играют в силу 3300+, тогда как лучшие гроссмейстеры "всего лишь" 2800-2900.

Гроссмейстеры все еще могут что-то противопоставить шахмтаным программам только в середине партии, так как дебюты машина "знает" лучше, а для эндшпилей (5 и 6, а недавно и 7 фигур) рассчитали полные эндшпильные таблицы. Компьютеры не допускают тактических ошибок, и могут быть обыграны только стратегически. Но это еще надо уметь.

Впрочем, интересно было бы сравнить силу компьютеров и человека при равном энергопотреблении. Есть ощущение, что человек тут будет все еще впереди. С другой стороны, я играл или играю примерно в силу второго взрослого разряда (1700-1800). Шахматная программа в моем макбуке меня уже стабильно обыгрывает. Даже если я не допускаю явных ошибок и зевков, так как играю между делом. По-моему, дважды мне удалось сделать ничью. Оба раза позиционную (с повторением ходов).

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

(продолжение)

Comments

[ushastyi.livejournal.com]

Ну не то, что сдвинулось, но есть пример использования Deep Learning для обучения нейронной сети игре в шахматы и более простые игры. Но до серьезных результатов еще далеко. Вот тут небольшой мой обзор на эту тему, вдохновленный записью Плахова: http://ushastyi.livejournal.com/247487.html

[olegch82.livejournal.com]

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

Может ли компьютер иметь доступ ко всем эндшпильным и дебютным базам? (Тогда получается вроде как человек играет против всех компьютеров, которые этот анадиз выполняли.)

Сколько времени у игроков есть "на подумать"? Какую мощность и память компьютер может задействовать?

Все эксперты отмечают, что сравнивать человеческий и компьютерный ELO бессмысленно, так как ELO - это относительный рейтинг внутри группы игроков. Поскольку матчей между компьютерами и людьми не проводится, эти две шкалы вообще нельзя привести в соответствие (грубо говоря, если бы в мире было 100000 компьютерных программ, то не было бы у них ELO за 3000)

[ushastyi.livejournal.com]

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

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

Вопрос со временем решается обычным образом -- часы. А вот мощность и память -- это как раз интересный вопрос. Поэтому я и предложил мерять по энергопотреблению :) Сколько калорий человек потребляет в час -- известно.

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