#1 20.07.07 21:47
[Наука] Компьютер "покончил" с шашками
Компьютер "покончил" с шашками
20.07.2007 http://lenta.ru/news/2007/07/20/checkers/
Для игры в шашки доказано существование стратегии, не допускающей поражений. Если ее используют оба партнера, игра всегда заканчивается вничью, сообщается в статье исследовательского коллектива под руководством Джонатана Шеффера (Jonathan Schaeffer), опубликованной в журнале Science.
Работа над доказательством была завершена 29 апреля 2007 года. Оно относится к классу так называемых "слабых": доказано, что способ не проиграть существует, но сама стратегия полностью пока не описана. Шашки — самая сложная из всех игр, для которых найдено подобное доказательство.
Группа Шеффера, работающая в университете Альберты, занимается стратегией игры в шашки с 1989 года. Количество возможных позиций в шестидесятичетырехклеточных шашках примерно равняется 5x1020. Для перебора позиций в течение 18 лет постоянно работало несколько десятков компьютеров, порой их число доходило до двух сотен.
В ходе работы исследователи создали программу "Чинук" ("Chinook"), которая на данный момент является сильнейшим шашистом в мире. Как для совершенствования "Чинука", так и для проведения доказательства Шеффер использовал не только слепой перебор, но и усовершенствованные алгоритмы, позволяющие отсечь заведомо проигрышные варианты. Многие методы были позаимствованы у сильных игроков, в частности, у покойного чемпиона мира Мариона Тинсли (Marion Tinsley).
Offline
#6 24.07.07 21:55
Re: [Наука] Компьютер "покончил" с шашками
krik написал(а):
с шахматами разберутся лет так через 200...
Создана программа, не проигрывающая в шашки
24 июля 2007 http://www.compulenta.ru/326433
Группа исследователей из Университета провинции Альберта (Канада) завершили работу над компьютерной программой Chinook, которая предназначена для игры в шашки на доске 8 на 8 клеток. Её созданием Джонатан Шеффер со своими коллегами занимался с 1989 года, для чего в обсчёте всех возможных вариантов игры было задействовано 200 компьютеров одновременно. В 1994 году Chinook выиграла чемпионат мира по шашкам, однако, иногда проигрывала своим оппонентам. Теперь даже идеально сыгранная партия против программы будет завершена в ничью.
В шашках существует 5х1020 вариантов ходов. Однако Chinook не просчитывает их и не анализирует все проигрышные позиции. Вместо этого она вычисляет только тот ход, который приведёт к победе. В результате к концу игры обсчитывается только одна пятимиллионная часть от всех возможных вариантов.
По мнению редактора International Computer Games Journal Яапа Ван Ден Херика, достижение канадских учёных является действительно важным достижением в области искусственного интеллекта. Он также выразил мнение, что аналогичная программа для игры в шахматы, где игроки имеют 1046 вариантов ходов, будет создана между 2060 и 2070 годом. Однако Шеффер отмечает, что для полного обсчёта шахмат в игре, где существует примерно 10100 вариантов ходов, нынешнего уровня технологий недостаточно и необходимо создание новых вычислительных средств.
В своей работе Шеффер также видит фундаментальное значение. Алгоритмы, аналогичные применённым им в Chinook, могут использоваться, например, для поиска сведений в крупных базах данных по биологической информации. В обоих случаях необходимо организовать быстрый доступ к большим объёмам сжатой информации, сообщает Nature со ссылкой на журнал Science.
Offline
#7 25.07.07 10:45
Re: [Наука] Компьютер "покончил" с шашками
Bream написал(а):
Он также выразил мнение, что аналогичная программа для игры в шахматы, где игроки имеют 1046 вариантов ходов, будет создана между 2060 и 2070 годом.
это будет создана только сама программа. А сколько она будет считать, если для шашек
Bream написал(а):
Для перебора позиций в течение 18 лет постоянно работало несколько десятков компьютеров,
Offline
