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

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

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

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

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

Наука и техника00:0116 февраля
Луис Глазман «Битва при Ситке»

Обойдемся

Эти индейцы воевали с русскими до 2004 года. Они вынудили Россию продать Аляску
Звери с Чумного озера
Щелковская ОПГ не знала пощады и отправляла жертв на корм рыбам
Земля и доля
Подмосковные крестьяне бьются с Грудининым за свои гектары
Огонь, вода и бандитские трупы
На работе он стреляет в боевиков, а по выходным людей спасает
Темные времена
Лихие 90-е: спецпроект «Ленты.ру»
Знаток «Что? Где? Когда?» Андрей КозловБольно умные
В России делают лучшие интеллектуальные шоу. Даже когда воруют идеи у Запада
Чувство мема
Американцев и европейцев оскорбляет буквально все. Россиян это смешит
Круче Tor
Богачи вложили миллионы в магазин наркотиков нового поколения
Abandoned Howey MansionИ тишина
Прекрасные заброшенные уголки мира
В комнате пыток
Сколько стоит самое дешевое и страшное жилье в Москве
Он же памятник
Угадай полководца: хитрый военный тест «Ленты.ру»
Соседи из ада
Интеллигентные жильцы превратили жизнь москвички в кошмар