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