Создатели программы "Чинук", компьютерного чемпиона мира по шашкам, доказали, что для каждого из партнеров существует оптимальная стратегия. Если ее используют оба партнера, игра всегда заканчивается вничью. Над доказательством ученые работали с 1989 года, использовав для него десятки компьютеров.
Для игры в шашки доказано существование стратегии, не допускающей поражений. Если ее используют оба партнера, игра всегда заканчивается вничью, сообщается в статье исследовательского коллектива под руководством Джонатана Шеффера (Jonathan Schaeffer), опубликованной в журнале Science.
Работа над доказательством была завершена 29 апреля 2007 года. Оно относится к классу так называемых "слабых": существование стратегии доказано для обеих сторон, но только для начальной позиции. Шашки — самая сложная из всех игр, для которых найдено подобное доказательство.
Группа Шеффера, работающая в университете Альберты, занимается стратегией игры в шашки с 1989 года. Количество возможных позиций в шестидесятичетырехклеточных шашках примерно равняется 5x1020. Для перебора позиций в течение 18 лет постоянно работало несколько десятков компьютеров, порой их число доходило до двух сотен.
В ходе работы исследователи создали программу "Чинук" ("Chinook"), которая на данный момент является сильнейшим шашистом в мире. Как для совершенствования "Чинука", так и для проведения доказательства Шеффер использовал не только слепой перебор, но и усовершенствованные алгоритмы, позволяющие отсечь заведомо проигрышные варианты. Многие методы были позаимствованы у сильных игроков, в частности, у покойного чемпиона мира Мариона Тинсли (Marion Tinsley).
Компьютер покончил с шашками
Создатели программы "Чинук", компьютерного чемпиона мира по шашкам, доказали, что для каждого из партнеров существует оптимальная стратегия. Если ее используют оба партнера, игра всегда заканчивается вничью. Над доказательством ученые работали с 1989 года, использовав для него десятки компьютеров.
Для игры в шашки доказано существование стратегии, не допускающей поражений. Если ее используют оба партнера, игра всегда заканчивается вничью, сообщается в статье исследовательского коллектива под руководством Джонатана Шеффера (Jonathan Schaeffer), опубликованной в журнале Science.
Работа над доказательством была завершена 29 апреля 2007 года. Оно относится к классу так называемых "слабых": существование стратегии доказано для обеих сторон, но только для начальной позиции. Шашки — самая сложная из всех игр, для которых найдено подобное доказательство.
Группа Шеффера, работающая в университете Альберты, занимается стратегией игры в шашки с 1989 года. Количество возможных позиций в шестидесятичетырехклеточных шашках примерно равняется 5x1020. Для перебора позиций в течение 18 лет постоянно работало несколько десятков компьютеров, порой их число доходило до двух сотен.
В ходе работы исследователи создали программу "Чинук" ("Chinook"), которая на данный момент является сильнейшим шашистом в мире. Как для совершенствования "Чинука", так и для проведения доказательства Шеффер использовал не только слепой перебор, но и усовершенствованные алгоритмы, позволяющие отсечь заведомо проигрышные варианты. Многие методы были позаимствованы у сильных игроков, в частности, у покойного чемпиона мира Мариона Тинсли (Marion Tinsley).