Turochamp

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

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

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

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

С 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].

Несмотря на то, что алгоритм так и не был формализован в виде программы, 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].

• История компьютерных игр

• Hodges, Andrew. Alan Turing: The Enigma. — Princeton University Press, 2014. — ISBN 978-1-4008-6512-3.
• Beavers, Anthony. Alan Turing: His Work and Impact. — Elsevier, 2013. — ISBN 978-0-12-386980-7.
• Oppy, Graham. The Antipodean Philosopher / Graham Oppy, Nick Trakakis. — Lexington Books^[англ.]*, 2011. — ISBN 978-0-7391-6655-0.
• Atkinson, George W. Chess and Machine Intuition. — Intellect Books, 1998. — ISBN 978-1-871516-44-09.
• Copeland, B. Jack. The Essential Turing. — Oxford University Press, 2004. — ISBN 978-0-19-825079-1.
• Levy, David. How Computers Play Chess / David Levy, Monty Newborn. — Ishi Press^[англ.], 2009. — ISBN 978-4-87187-801-2.
• Sipser, Michael. Introduction to the Theory of Computation. — PWS Publishing, 2006. — ISBN 978-0-534-95097-2.
• Dasgupta, Subrata. It Began with Babbage: The Genesis of Computer Science. — Oxford University Press, 2014. — ISBN 978-0-19-930941-2.
• Turing, Dermot. Prof: Alan Turing Decoded^[англ.]. — The History Press^[англ.], 2015. — ISBN 978-0-7509-6524-8.

• Партия Turochamp против Алика Гленни (1952) на сайте Chessgames.com^[англ.]
• Партия Turochamp против Гарри Каспарова (2012) на сайте Chessgames.com^[англ.]