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