Turochamp (Turochamp)

Перейти к навигации Перейти к поиску
Turochamp
Разработчики Алан Тьюринг и Дэвид Чемперноун[вд]
Дата выпуска
  • 1948
Жанр компьютерные шахматы
Технические данные
Режим игры одиночная игра

Turochamp[a] — шахматная программа, разработанная Аланом Тьюрингом и Дэвидом Чемперноуном[англ.] в 1948 году в рамках исследования по информатике и машинному обучению. Перед тем, как сделать ход, Turochamp рассматривает все возможные ходы и просчитывает каждый возможный ответ оппонента, после чего дополнительно анализирует удачные ходы. Всем полученным в результате анализа позициям присваивается метрика, по которой программа выбирает наиболее удачный ход. Следуя этому алгоритму, программа способна разыграть полноценную партию от начала до конца против живого соперника на уровне начинающего игрока в шахматы➤.

Тьюринг и Чемперноун так и не закончили Turochamp, поскольку алгоритм был слишком сложным для работы на компьютерах того времени — таких как Automatic Computing Engine. Тьюринг попытался реализовать алгоритм на манчестерском компьютере Ferranti Mark 1[англ.] 1951 года выпуска, однако успеха не добился. В 1952 году Тьюринг сыграл матч против учёного Алика Гленни[англ.], пошагово исполнив алгоритм самостоятельно. В 1954 году Тьюринг умер, так и не добившись работы Turochamp на реальном компьютере; Чемперноун не стал продолжать проект, и код был утерян➤.

Несмотря на то, что алгоритм так и не был формализован в виде программы, Turochamp считается первой игрой для персонального компьютера[источник не указан 323 дня] и претендует на звание первой шахматной программы в истории (одновременно с Turochamp разрабатывалось несколько других шахматных программ, однако ни одна из них не была завершена). Первая работающая программа, написанная в 1951 году Дитрихом Принцем[англ.] для компьютера Ferranti Mark 1, основывалась на Turochamp и ограничивалась решением задач на мат в два хода. К конференции к столетию Алана Тьюринга[англ.] 2012 года Turochamp была воссоздана и против программы сыграл гроссмейстер Гарри Каспаров➤.

Игровой процесс

[править | править код]

Turochamp — компьютерная программа, осуществляющая игру в шахматы, которой на вход подаются ходы игрока, а в ответ она выводит свой ход. Алгоритм программы использует эвристический метод для определения лучшего возможного хода. Программа рассматривает все разрешённые правилами ходы, просчитывает каждый возможный ответ соперника, а также дальнейшие «значимые» ходы — взятия незащищённых фигур, завершение размена, а также взятие сильной фигуры оппонента более слабой фигурой. Каждой полученной позиции присваивается метрика, после чего программа выбирает лучший возможный ход, используя алгоритм минимакса[3][4][5]. Метрика рассчитывается исходя из нескольких критериев — мобильности и безопасности каждой фигуры, угрозы постановки мата, стоимости взятой фигуры, а также ряда других факторов[6]. По словам Чемперноуна, алгоритм фактически сводится к принятию решений о том, стоит ли брать ту или иную фигуру; по словам Тьюринга, Turochamp способна играть в шахматы на уровне начинающего игрока, что он посчитал соразмерным собственному уровню игры в шахматы[3][6].

История

[править | править код]
Партия Turochamp (белые) против Алика Гленни[англ.] (чёрные), разыгранная в 1952 году. На 30-м ходу игры белые имеют преимущество в одну пешку, однако не могут спасти связанного ферзя, а потому сдаются

С 1941 года, во время работы над военной криптографией[англ.] в Блетчли-парк, Тьюринг начал обсуждать с коллегами возможность создания машины, способной играть в шахматы и решать иные «интеллектуальные» задачи, а также идею решения задач путём перебора всех возможных ответов с использованием эвристического алгоритма[7][8]. Ряд работ Тьюринга в сфере криптоанализа, в том числе Bombe, использовали модель вычислительной машины, перебирающей все возможные решения[8]. В 1944 году Тьюринг обсудил свои идеи с экономическим статистиком Дэвидом Чемперноуном[англ.], и к 1945 году они пришли к выводу, что машина, способная проводить произвольные вычисления, теоретически способна повторить всё, на что способен человеческий мозг, в том числе игру в шахматы[7][9].

После Второй мировой войны Тьюринг работал в Национальной физической лаборатории, где разрабатывал Automatic Computing Engine (ACE) — один из первых прототипов компьютера с хранимой в памяти программой. В 1946 году Тьюринг написал отчёт, озаглавленный «Proposed Electronic Calculator» (с англ. — «предлагаемый электронный вычислитель»), где перечислил проекты, для которых он собирался использовать ACE — одним из них была игра в шахматы. Годом спустя он выступил с докладом перед Лондонским математическим обществом, в котором представил идею машины, запрограммированной играть в шахматы и обучаться на собственном игровом опыте. В 1948 году он отправил новый отчёт «Intelligent Machinery» (с англ. — «интеллектуальное оборудование»), в котором предложил способ имитировать шахматную игру[1].

В конце лета 1948 года Тьюринг и Чамперноун, работавшие в Королевском колледже в Кембридже, разработали систему теоретических правил для определения оптимального следующего хода в шахматной игре. Они реализовали этот алгоритм в виде компьютерной программы, однако она оказалась слишком сложной для ACE или любого другого компьютера того времени[3]. Программа была названа Turochamp — в честь фамилий создателей (Turing и Champernowne)[1]. В прессе её иногда ошибочно называют Turbochamp[2]. По словам Чамперноуна, его жена разыграла шахматную партию против программы, названной «бумажным компьютером», и проиграла[1][10]. Тьюринг попытался реализовать алгоритм на манчестерском компьютере Ferranti Mark 1[англ.] 1951 года выпуска, однако в силу сложности кода не добился успеха[2]. Джек Коупленд[англ.], автор монографий о Тьюринге, писал, что неудачные попытки написать программу для реального компьютера не беспокоили Тьюринга, так как он был убеждён, что скорость и сложность компьютеров вскоре вырастут, и написать подобную программу станет возможно[11]. Летом 1952 года Тьюринг разыграл партию против Алика Гленни[англ.] с помощью программы, пошагово исполнив алгоритм самостоятельно. Матч, запись которого сохранилась, длился 29 ходов и закончился поражением Turochamp, а каждый ход программы занимал вплоть до 30 минут расчётов. Этот матч продемонстрировал, что программа, способная сыграть полноценный матч против человека, возможна. В 1954 году Тьюринг умер, так и не добившись работы Turochamp на реальном компьютере[2].

Исходный код и алгоритм, написанный Тьюрингом и Чемперноуном, не сохранился. В 1980 году Чемперноун описал, как работал алгоритм, однако он не смог вспомнить все подробности рассчёта метрики[3][11]. По этому описанию в 2012 году Turochamp была воссоздана[12]. Реконструкция алгоритма, однако, не смогла воспроизвести записанный матч Тьюринга против Гленни. В попытках правильно интерпретировать сохранившиеся описания программы авторы решили проконсультироваться с рядом шахматных экспертов и современников Тьюринга, в том числе с Кеном Томпсоном, создателем шахматного автомата Belle[англ.] и операционной системы Unix, однако никто из них не мог найти причину расхождений. Наконец, Дональд Михи предположил, что Тьюринг во время игры не следовал алгоритму дотошно; в дальнейшем исследователям удалось доказать, что Тьюринг начиная с самого первого хода ошибочно исключал из рассмотрения ходы, которые казались ему неоптимальными, чтобы сэкономить время на их анализе[b]. Полученная реконструкция была представлена в рамках конференции к столетию Алана Тьюринга[англ.], проведённой 22—25 июля 2012 года, в матче против гроссмейстера и экс-чемпиона мира Гарри Каспарова[13]. Каспаров обыграл программу за 16 ходов[14].

Наследие

[править | править код]
Гарри Каспаров произносит речь на конференции к столетию Алана Тьюринга[англ.] 25 июня 2012 года

Несмотря на то, что алгоритм так и не был формализован в виде программы, Turochamp претендует на звание первой шахматной программы в истории. Одновременно с Turochamp разрабатывались и обсуждались и другие шахматные программы: в 1950 году Клод Шеннон опубликовал статью «Programming a Computer for Playing Chess» (с англ. — «программирование компьютера для игры в шахматы»), Конрад Цузе в 1941—1945 годах решал шахматные задачи на разрабатываемом им языке планкалкюль, а Дональд Михи[англ.] и Шон Уайли[англ.] разрабатывали шахматный алгоритм Machiavelli, которую Тьюринг безуспешно пытался реализовать на Ferranti Mark I одновременно с Turochamp[1][15][16][17]. В ноябре 1951 года Дитрих Принц[англ.], сотрудник Ferranti, вдохновился работой Тьюринга над Turochamp и на её основе разработал первую успешную шахматную программу для Ferranti Mark I, которая ограничивалась решением задач на мат в два хода[3]

Turochamp была воссоздана в 2012 году и представлена в рамках конференции к столетию Алана Тьюринга[англ.][13]. Гарри Каспаров, принявший участие на конференции, произнёс речь, в которой назвал «выдающимся достижением» создание шахматной программы в условиях, когда результат своей работы невозможно выполнить на компьютере, и заявил, что Turochamp нашла своё место в истории[14].

См. также

[править | править код]

Комментарии

[править | править код]
  1. ↑ «Тьюрочемп» — названа по фамилиям создателей, Тьюринга (англ. Turing) и Чемперноуна (англ. Champernowne)[1]. Иногда ошибочно называется Turbochamp[2].
  2. ↑ В частности, Тьюринг открылся ходом королевской пешки на два поля, поскольку посчитал, что ход на E4 очевидно лучше хода на E3. Однако алгоритм считает ход на E4 менее удачным, так как он в теории оставляет сопернику больше пространства для атаки на короля — несмотря на то, что ни одна вражеская фигура не могла добраться до поля E3 в тот момент[13].

Примечания

[править | править код]
  1. ↑ 1 2 3 4 5 Alan Turing: His Work and Impact, pp. 644–650
  2. ↑ 1 2 3 4 Clark, Liat; Steadman, Ian Remembering Alan Turing: from codebreaking to AI, Turing made the world what it is today. Wired. Condé Nast (7 июня 2017). Дата обращения: 7 февраля 2019. Архивировано 14 октября 2017 года.
  3. ↑ 1 2 3 4 5 The Essential Turing, pp. 563-564
  4. ↑ "David Champernowne (1912-2000)". ICGA Journal. 23 (4): 262. December 2000. doi:10.3233/ICG-2000-23419.
  5. ↑ Cochlin, Daniel Kasparov versus Turing. University of Manchester (26 июня 2012). Дата обращения: 9 апреля 2019. Архивировано 1 августа 2018 года.
  6. ↑ 1 2 How Computers Play Chess, p. 35
  7. ↑ 1 2 Hodges, Andrew (2013-09-30). "Alan Turing". Stanford Encyclopedia of Philosophy. Stanford University. Архивировано 16 декабря 2021. Дата обращения: 22 мая 2019.
  8. ↑ 1 2 Copeland, Jack; Proudfoot, Diane (2012). "Alan Turing, Founder of the Modern Computer". The Rutherford Journal. 1 (4). ISSN 1177-1380. Архивировано 24 января 2022. Дата обращения: 1 сентября 2022.
  9. ↑ Alan Turing: The Enigma, p. 488
  10. ↑ "Reconstructing Turing's "Paper Machine"". ICGA Journal. 40 (2): 1—8. June 2018.
  11. ↑ 1 2 The Antipodean Philosopher, pp. 13–14
  12. ↑ "Player of the Century". New In Chess. Interchess. August 1999. pp. 6—7. ISSN 0168-8782.
  13. ↑ 1 2 3 Kasparov, Garry (June 2012). The Reconstruction of Turing's 'Paper Machine'. Alan Turing Centenary Conference. Manchester, England. Архивировано 26 января 2019. Дата обращения: 9 апреля 2019 — VideoLectures.net.
  14. ↑ 1 2 Parnell, Brid-Aine Chess algorithm written by Alan Turing goes up against Kasparov. The Register. Situation Publishing (26 июня 2012). Дата обращения: 9 апреля 2019. Архивировано 27 октября 2017 года.
  15. ↑ It Began with Babbage: The Genesis of Computer Science, p. 193
  16. ↑ Prof: Alan Turing Decoded[англ.], ch. 9
  17. ↑ Chess and Machine Intuition, p. 39

Литература

[править | править код]

Ссылки

[править | править код]
Источник — https://ru.wikipedia.org/w/index.php?title=Turochamp&oldid=140380441