Игра в шашки. Фото с сайта mnscu.edu.

Компьютер покончил с шашками

Работа над доказательством была завершена 29 апреля 2007 года. Оно относится к классу так называемых "слабых": существование стратегии доказано для обеих сторон, но только для начальной позиции. Шашки — самая сложная из всех игр, для которых найдено подобное доказательство.

Группа Шеффера, работающая в университете Альберты, занимается стратегией игры в шашки с 1989 года. Количество возможных позиций в шестидесятичетырехклеточных шашках примерно равняется 5x10²⁰. Для перебора позиций в течение 18 лет постоянно работало несколько десятков компьютеров, порой их число доходило до двух сотен.

В ходе работы исследователи создали программу "Чинук" ("Chinook"), которая на данный момент является сильнейшим шашистом в мире. Как для совершенствования "Чинука", так и для проведения доказательства Шеффер использовал не только слепой перебор, но и усовершенствованные алгоритмы, позволяющие отсечь заведомо проигрышные варианты. Многие методы были позаимствованы у сильных игроков, в частности, у покойного чемпиона мира Мариона Тинсли (Marion Tinsley).

Ссылки по теме
- Checkers Is Solved – Science, 19.07.07
- Checkers 'solved' after years of number crunching – NewScientist, 19.07.07
- Азербайджанский гроссмейстер проиграл чемпиону мира среди компьютеров - Lenta.ru, 04.12.2006
- Владимир Крамник не сумел выиграть матч у компьютера - Lenta.ru, 03.12.2006
- Менеджер Топалова обвинил Крамника в использовании компьютера - Lenta.ru, 04.10.2006
- Россиянка Тамара Тансыккужина стала чемпионкой мира по шашкам - Lenta.ru, 24.08.2001
- Сильнейшим шашистом мира снова стал россиянин Чижов - Lenta.ru, 13.03.2001

Сайты по теме
- Chinook – World Man-Machine Checkers Champion