Turochamp[a] — шахматная программа, разработанная Аланом Тьюрингом и Дэвидом Чемперноуном[en] в 1948 году в рамках исследования по информатике и машинному обучению. Перед тем, как сделать ход, Turochamp рассматривает все возможные ходы и просчитывает каждый возможный ответ оппонента, после чего дополнительно анализирует удачные ходы. Всем полученным в результате анализа позициям присваивается метрика, по которой программа выбирает наиболее удачный ход. Следуя этому алгоритму, программа способна разыграть полноценную партию от начала до конца против живого соперника на уровне начинающего игрока в шахматы[⇨].
Тьюринг и Чемперноун так и не закончили Turochamp, поскольку алгоритм был слишком сложным для работы на компьютерах того времени — таких как Automatic Computing Engine. Тьюринг попытался реализовать алгоритм на манчестерском компьютере Ferranti Mark 1[en] 1951 года выпуска, однако успеха не добился. В 1952 году Тьюринг сыграл матч против учёного Алика Гленни[en], пошагово исполнив алгоритм самостоятельно. В 1954 году Тьюринг умер, так и не добившись работы Turochamp на реальном компьютере; Чемперноун не стал продолжать проект, и код был утерян[⇨].
Несмотря на то, что алгоритм так и не был формализован в виде программы, Turochamp считается первой игрой для персонального компьютера и претендует на звание первой шахматной программы в истории (одновременно с Turochamp разрабатывалось несколько других шахматных программ, однако ни одна из них не была завершена). Первая работающая программа, написанная в 1951 году Дитрихом Принцем[en] для компьютера Ferranti Mark 1, основывалась на Turochamp и ограничивалась решением задач на мат в два хода. К конференции к столетию Алана Тьюринга[en] 2012 года Turochamp была воссоздана и против программы сыграл гроссмейстер Гарри Каспаров[⇨].
Turochamp — компьютерная программа, осуществляющая игру в шахматы, которой на вход подаются ходы игрока, а в ответ она выводит свой ход. Алгоритм программы использует эвристический метод для определения лучшего возможного хода. Программа рассматривает все разрешённые правилами ходы, просчитывает каждый возможный ответ соперника, а также дальнейшие «значимые» ходы — взятия незащищённых фигур, завершение размена, а также взятие сильной фигуры оппонента более слабой фигурой. Каждой полученной позиции присваивается метрика, после чего программа выбирает лучший возможный ход, используя алгоритм минимакса[3][4][5]. Метрика рассчитывается исходя из нескольких критериев — мобильности и безопасности каждой фигуры, угрозы постановки мата, стоимости взятой фигуры, а также ряда других факторов[6]. По словам Чемперноуна, алгоритм фактически сводится к принятию решений о том, стоит ли брать ту или иную фигуру; по словам Тьюринга, Turochamp способна играть в шахматы на уровне начинающего игрока, что он посчитал соразмерным собственному уровню игры в шахматы[3][6].
Партия Turochamp (белые) против Алика Гленни[en] (чёрные), разыгранная в 1952 году. На 30-м ходу игры белые имеют преимущество в одну пешку, однако не могут спасти связанного ферзя, а потому сдаются
С 1941 года, во время работы над военной криптографией[en] в Блетчли-парк, Тьюринг начал обсуждать с коллегами возможность создания машины, способной играть в шахматы и решать иные «интеллектуальные» задачи, а также идею решения задач путём перебора всех возможных ответов с использованием эвристического алгоритма[7][8]. Ряд работ Тьюринга в сфере криптоанализа, в том числе Bombe, использовали модель вычислительной машины, перебирающей все возможные решения[8]. В 1944 году Тьюринг обсудил свои идеи с экономическим статистиком Дэвидом Чемперноуном[en], и к 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[en] 1951 года выпуска, однако в силу сложности кода не добился успеха[2]. Джек Коупленд[en], автор монографий о Тьюринге, писал, что неудачные попытки написать программу для реального компьютера не беспокоили Тьюринга, так как он был убеждён, что скорость и сложность компьютеров вскоре вырастут, и написать подобную программу станет возможно[11]. Летом 1952 года Тьюринг разыграл партию против Алика Гленни[en] с помощью программы, пошагово исполнив алгоритм самостоятельно. Матч, запись которого сохранилась, длился 29 ходов и закончился поражением Turochamp, а каждый ход программы занимал вплоть до 30 минут расчётов. Этот матч продемонстрировал, что программа, способная сыграть полноценный матч против человека, возможна. В 1954 году Тьюринг умер, так и не добившись работы Turochamp на реальном компьютере[2].
Исходный код и алгоритм, написанный Тьюрингом и Чемперноуном, не сохранился. В 1980 году Чемперноун описал, как работал алгоритм, однако он не смог вспомнить все подробности рассчёта метрики[3][11]. По этому описанию в 2012 году Turochamp была воссоздана[12]. Реконструкция алгоритма, однако, не смогла воспроизвести записанный матч Тьюринга против Гленни. В попытках правильно интерпретировать сохранившиеся описания программы авторы решили проконсультироваться с рядом шахматных экспертов и современников Тьюринга, в том числе с Кеном Томпсоном, создателем шахматного автомата Belle[en] и операционной системы Unix, однако никто из них не мог найти причину расхождений. Наконец, Дональд Михи предположил, что Тьюринг во время игры не следовал алгоритму дотошно; в дальнейшем исследователям удалось доказать, что Тьюринг начиная с самого первого хода ошибочно исключал из рассмотрения ходы, которые казались ему неоптимальными, чтобы сэкономить время на их анализе[b]. Полученная реконструкция была представлена в рамках конференции к столетию Алана Тьюринга[en], проведённой 22—25 июля 2012 года, в матче против гроссмейстера и экс-чемпиона мира Гарри Каспарова[13]. Каспаров обыграл программу за 16 ходов[14].
Несмотря на то, что алгоритм так и не был формализован в виде программы, Turochamp претендует на звание первой шахматной программы в истории. Одновременно с Turochamp разрабатывались и обсуждались и другие шахматные программы: в 1950 году Клод Шеннон опубликовал статью «Programming a Computer for Playing Chess» (с англ. — «программирование компьютера для игры в шахматы»), Конрад Цузе в 1941—1945 годах решал шахматные задачи на разрабатываемом им языке планкалкюль, а Дональд Михи[en] и Шон Уайли[en] разрабатывали шахматный алгоритм Machiavelli, которую Тьюринг безуспешно пытался реализовать на Ferranti Mark I одновременно с Turochamp[1][15][16][17]. В ноябре 1951 года Дитрих Принц[en], сотрудник Ferranti, вдохновился работой Тьюринга над Turochamp и на её основе разработал первую успешную шахматную программу для Ferranti Mark I, которая ограничивалась решением задач на мат в два хода[3]
Turochamp была воссоздана в 2012 году и представлена в рамках конференции к столетию Алана Тьюринга[en][13]. Гарри Каспаров, принявший участие на конференции, произнёс речь, в которой назвал «выдающимся достижением» создание шахматной программы в условиях, когда результат своей работы невозможно выполнить на компьютере, и заявил, что Turochamp нашла своё место в истории[14].
↑«Тьюрочемп» — названа по фамилиям создателей, Тьюринга (англ.Turing) и Чемперноуна (англ.Champernowne)[1]. Иногда ошибочно называется Turbochamp[2].
↑В частности, Тьюринг открылся ходом королевской пешки на два поля, поскольку посчитал, что ход на E4 очевидно лучше хода на E3. Однако алгоритм считает ход на E4 менее удачным, так как он в теории оставляет сопернику больше пространства для атаки на короля — несмотря на то, что ни одна вражеская фигура не могла добраться до поля E3 в тот момент[13].
