Turochamp
Turochamp{{efn|«Тьюрочемп» — названа по фамилиям создателей, Тьюринга (англ. Turing) и Чемперноуна (англ. Champernowne). Иногда ошибочно называется Turbochamp — шахматная программа, разработанная Аланом Тьюрингом и Шаблон:Нп5 в 1948 году в рамках исследования по информатике и машинному обучению. Перед тем, как сделать ход, Turochamp рассматривает все возможные ходы и просчитывает каждый возможный ответ оппонента, после чего дополнительно анализирует удачные ходы. Всем полученным в результате анализа позициям присваивается метрика, по которой программа выбирает наиболее удачный ход. Следуя этому алгоритму, программа способна разыграть полноценную партию от начала до конца против живого соперника на уровне начинающего игрока в шахматы.
Тьюринг и Чемперноун так и не закончили Turochamp, поскольку алгоритм был слишком сложным для работы на компьютерах того времени — таких как Automatic Computing Engine. Тьюринг попытался реализовать алгоритм на манчестерском компьютере Шаблон:Нп5 1951 года выпуска, однако успеха не добился. В 1952 году Тьюринг сыграл матч против учёного Шаблон:Нп5, пошагово исполнив алгоритм самостоятельно. В 1954 году Тьюринг умер, так и не добившись работы Turochamp на реальном компьютере; Чемперноун не стал продолжать проект, и код был утерян. Несмотря на то, что алгоритм так и не был формализован в виде программы, Turochamp считается первой игрой для персонального компьютера и претендует на звание первой шахматной программы в истории (одновременно с Turochamp разрабатывалось несколько других шахматных программ, однако ни одна из них не была завершена). Первая работающая программа, написанная в 1951 году Шаблон:Нп5 для компьютера Ferranti Mark 1, основывалась на Turochamp и ограничивалась решением задач на мат в два хода. К Шаблон:Нп5 2012 года Turochamp была воссоздана и против программы сыграл гроссмейстер Гарри Каспаров.
Содержание |
Игровой процесс 
Turochamp — компьютерная программа, осуществляющая игру в шахматы, которой на вход подаются ходы игрока, а в ответ она выводит свой ход. Алгоритм программы использует эвристический метод для определения лучшего возможного хода. Программа рассматривает все разрешённые правилами ходы, просчитывает каждый возможный ответ соперника, а также дальнейшие «значимые» ходы — взятия незащищённых фигур, завершение размена, а также взятие сильной фигуры оппонента более слабой фигурой. Каждой полученной позиции присваивается метрика, после чего программа выбирает лучший возможный ход, используя алгоритм минимакса. Метрика рассчитывается исходя из нескольких критериев — мобильности и безопасности каждой фигуры, угрозы постановки мата, стоимости взятой фигуры, а также ряда других факторов. По словам Чемперноуна, алгоритм фактически сводится к принятию решений о том, стоит ли брать ту или иную фигуру; по словам Тьюринга, Turochamp способна играть в шахматы на уровне начинающего игрока, что он посчитал соразмерным собственному уровню игры в шахматы.
История
[[Файл:TUROCHAMP vs Glennie, 1952.gif|thumb|Партия Turochamp (белые) против Шаблон:Нп5 (чёрные), разыгранная в 1952 году. На 30-м ходу игры белые имеют преимущество в одну пешку, однако не могут спасти связанного ферзя, а потому сдаются]] С 1941 года, во время работы над Шаблон:Нп5 в Блетчли-парк, Тьюринг начал обсуждать с коллегами возможность создания машины, способной играть в шахматы и решать иные «интеллектуальные» задачи, а также идею решения задач путём перебора всех возможных ответов с использованием эвристического алгоритма. Ряд работ Тьюринга в сфере криптоанализа, в том числе Bombe, использовали модель вычислительной машины, перебирающей все возможные решения. В 1944 году Тьюринг обсудил свои идеи с экономическим статистиком Шаблон:Нп5, и к 1945 году они пришли к выводу, что машина, способная проводить произвольные вычисления, теоретически способна повторить всё, на что способен человеческий мозг, в том числе игру в шахматы.
После Второй мировой войны Тьюринг работал в Национальной физической лаборатории, где разрабатывал Automatic Computing Engine (ACE) — один из первых прототипов компьютера с хранимой в памяти программой. В 1946 году Тьюринг написал отчёт, озаглавленный «Proposed Electronic Calculator» (Шаблон:Tr-en), где перечислил проекты, для которых он собирался использовать ACE — одним из них была игра в шахматы. Годом спустя он выступил с докладом перед Лондонским математическим обществом, в котором представил идею машины, запрограммированной играть в шахматы и обучаться на собственном игровом опыте. В 1948 году он отправил новый отчёт «Intelligent Machinery» (Шаблон:Tr-en), в котором предложил способ имитировать шахматную игру.
В конце лета 1948 года Тьюринг и Чамперноун, работавшие в Королевском колледже в Кембридже, разработали систему теоретических правил для определения оптимального следующего хода в шахматной игре. Они реализовали этот алгоритм в виде компьютерной программы, однако она оказалась слишком сложной для ACE или любого другого компьютера того времени. Программа была названа Turochamp — в честь фамилий создателей (Шаблон:Lang-en2 и Шаблон:Lang-en2). В прессе её иногда ошибочно называют Turbochamp. По словам Чамперноуна, его жена разыграла шахматную партию против программы, названной «бумажным компьютером», и проиграла. Тьюринг попытался реализовать алгоритм на манчестерском компьютере Шаблон:Нп5 1951 года выпуска, однако в силу сложности кода не добился успеха. Шаблон:Нп5, автор монографий о Тьюринге, писал, что неудачные попытки написать программу для реального компьютера не беспокоили Тьюринга, так как он был убеждён, что скорость и сложность компьютеров вскоре вырастут, и написать подобную программу станет возможно. Летом 1952 года Тьюринг разыграл партию против Шаблон:Нп5 с помощью программы, пошагово исполнив алгоритм самостоятельно. Матч, запись которого сохранилась, длился 29 ходов и закончился поражением Turochamp, а каждый ход программы занимал вплоть до 30 минут расчётов. Этот матч продемонстрировал, что программа, способная сыграть полноценный матч против человека, возможна. В 1954 году Тьюринг умер, так и не добившись работы Turochamp на реальном компьютере.
Исходный код и алгоритм, написанный Тьюрингом и Чемперноуном, не сохранился. В 1980 году Чемперноун описал, как работал алгоритм, однако он не смог вспомнить все подробности рассчёта метрики. По этому описанию в 2012 году Turochamp была воссоздана. Реконструкция алгоритма, однако, не смогла воспроизвести записанный матч Тьюринга против Гленни. В попытках правильно интерпретировать сохранившиеся описания программы авторы решили проконсультироваться с рядом шахматных экспертов и современников Тьюринга, в том числе с Кеном Томпсоном, создателем шахматного автомата Шаблон:Нп5 и операционной системы Unix, однако никто из них не мог найти причину расхождений. Наконец, Дональд Михи предположил, что Тьюринг во время игры не следовал алгоритму дотошно; в дальнейшем исследователям удалось доказать, что Тьюринг начиная с самого первого хода ошибочно исключал из рассмотрения ходы, которые казались ему неоптимальными, чтобы сэкономить время на их анализе{{efn|В частности, Тьюринг открылся ходом королевской пешки на два поля, поскольку посчитал, что ход на E4 очевидно лучше хода на E3. Однако алгоритм считает ход на E4 менее удачным, так как он в теории оставляет сопернику больше пространства для атаки на короля — несмотря на то, что ни одна вражеская фигура не могла добраться до поля E3 в тот момент. Полученная реконструкция была представлена в рамках Шаблон:Нп5, проведённой 22—25 июля 2012 года, в матче против гроссмейстера и экс-чемпиона мира Гарри Каспарова. Каспаров обыграл программу за 16 ходов.
Наследие
[[Файл:Garry Kasparov IMG 0130.JPG|thumb|Гарри Каспаров произносит речь на Шаблон:Нп5 25 июня 2012 года]] Несмотря на то, что алгоритм так и не был формализован в виде программы, Turochamp претендует на звание первой шахматной программы в истории. Одновременно с Turochamp разрабатывались и обсуждались и другие шахматные программы: в 1950 году Клод Шеннон опубликовал статью «Programming a Computer for Playing Chess» (Шаблон:Tr-en), Конрад Цузе в 1941—1945 годах решал шахматные задачи на разрабатываемом им языке планкалкюль, а Шаблон:Нп5 и Шаблон:Нп5 разрабатывали шахматный алгоритм Machiavelli, которую Тьюринг безуспешно пытался реализовать на Ferranti Mark I одновременно с Turochamp. В ноябре 1951 года Шаблон:Нп5, сотрудник Ferranti, вдохновился работой Тьюринга над Turochamp и на её основе разработал первую успешную шахматную программу для Ferranti Mark I, которая ограничивалась решением задач на мат в два хода.
Turochamp была воссоздана в 2012 году и представлена в рамках Шаблон:Нп5. Гарри Каспаров, принявший участие на конференции, произнёс речь, в которой назвал «выдающимся достижением» создание шахматной программы в условиях, когда результат своей работы невозможно выполнить на компьютере, и заявил, что Turochamp нашла своё место в истории.
