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

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

Для игры в шашки доказано существование стратегии, не допускающей поражений. Если ее используют оба партнера, игра всегда заканчивается вничью, сообщается в статье исследовательского коллектива под руководством Джонатана Шеффера (Jonathan Schaeffer), опубликованной в журнале Science.

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

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

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

Обсудить
Наука и техника00:0311 декабря
Проект наземной мобильной версии электромагнитной пушки

И так сойдет

Америка прекратила разработку сдерживающего Россию оружия
Они ушли
Русские покидают Сирию. Там остаются тысячи террористов, а войне не видно конца
«Этим проклятым американцам мы еще покажем!»
Афганцы полюбили русских и возненавидели США
Кровавый конвейер
На Гаити круглый год режут и свежуют скот
Реджеп Тайип ЭрдоганВ спину не больно
Россия забыла обиды и взахлеб дружит с Турцией
Дональд ТрампСвоих не бросаем
План Трампа: спасти богатых и сэкономить на бедных
Домашние заготовки
Почему российской строительной сфере не обойтись без отечественных алюминиевых панелей
Выплюнь бяку
Личинки, тараканы и ДНК человека — на что можно нарваться в батоне колбасы
Тест-драйв лучшей BMW M5
Знакомимся с первой полноприводной «эмкой» на серпантинах Португалии
Самые редкие версии BMW M5
Эксклюзивные M5 для пуристов, арабских шейхов и просто прогулок с ветерком
Невероятные стартапы, которые изменят жизнь водителей
Автомат по продаже машин, встроенный алкотестер и так далее
Самые необычные фары в истории
Головная оптика, от которой можно офонареть
«Меня не убили, просто развели»
Россиянка влюбилась по уши и лишилась жилья
Что-то встало за окном
Строения, вызывающие самые пошлые ассоциации
С собой не увезешь
Как живут российские олигархи за границей
Его ворсейшество
Бессмертные ковры возвращаются на стены российских квартир