Турочамп
| Турочамп | |
|---|---|
| Разработчик(и) | Алан Тьюринг , Дэвид Чамперноун |
| Жанр (ы) | Компьютерные шахматы |
| Режим(ы) | Одиночная игра |
| Эта статья является частью серии, посвящённой |
| Шахматное программирование |
|---|
 |
Turochamp — это шахматная программа , разработанная Аланом Тьюрингом и Дэвидом Чамперноуном в 1948 году. Она была создана в рамках исследований пары в области информатики и машинного обучения. Турочамп способен сыграть всю шахматную партию против игрока-человека на низком уровне игры, вычисляя все потенциальные ходы и все потенциальные ходы игрока в ответ, а также некоторые дальнейшие ходы, которые он считает значительными. Затем он присваивает значения очков каждому состоянию игры и выбирает ход, приводящий к наибольшему значению очков.
Turochamp — самая ранняя известная компьютерная игра, вошедшая в разработку, но она так и не была завершена Тьюрингом и Чамперноуном, поскольку ее алгоритм был слишком сложен, чтобы его могли запускать ранние компьютеры того времени, такие как Автоматическая вычислительная машина . Тьюринг попытался преобразовать программу в исполняемый код для компьютера Ferranti Mark 1 1951 года в Манчестере, но не смог этого сделать. Тьюринг сыграл матч против ученого-компьютерщика Алика Гленни Летом 1952 года , используя программу, шаг за шагом выполняя ее вручную, но к моменту своей смерти в 1954 году он все еще не мог запустить программу на реальном компьютере. Чамперноун не продолжил проект, и исходная программа не сохранилась.
Несмотря на то, что программа никогда не запускалась на компьютере, она является кандидатом на роль первой шахматной программы; Примерно в то же время было разработано или предложено несколько других шахматных программ, в том числе еще одна, которую Тьюринг безуспешно пытался запустить на Ferranti Mark 1. Первая успешная программа в 1951 году, также разработанная для Mark 1, была непосредственно вдохновлена Турочампом и была способен только решать задачи « мат-в-два ». Воссоздание Турочампа было построено в 2012 году к конференции столетия Алана Тьюринга . Эта версия была использована в матче с гроссмейстером Гарри Каспаровым , выступавшим с основным докладом на конференции.
Геймплей
[ редактировать ]Турочамп имитирует игру в шахматы против игрока, принимая ходы игрока в качестве входных данных и выдавая его ход в ответ. Алгоритм программы использует эвристику для определения наилучшего хода, вычисляя все потенциальные ходы, которые он может сделать, затем все потенциальные ответы игрока, которые могут быть сделаны по очереди, а также дальнейшие «значительные» ходы, такие как захват незащищенные фигуры, повторные захваты и захват фигуры более высокой ценности фигурой меньшей ценности. Затем программа присваивает значение в баллах каждому результирующему состоянию, а затем выполняет ход с наибольшим результатом, используя для этого минимаксный алгоритм. [1] [2] [3] Очки определяются на основе нескольких критериев, таких как подвижность каждой фигуры, безопасность каждой фигуры, угроза мата, ценность фигуры игрока в случае ее взятия и ряд других факторов. Разным ходам присваивается разное количество очков; например, взятие ферзя дает 10 очков, а пешка - только одно очко, а установка шаха королю дает очко или половину очка в зависимости от расположения доски. [4] По словам Чамперноуна, алгоритм в первую очередь основан на решении брать фигуру или нет; По словам Тьюринга, в результате получается игра в шахматы низкого уровня, которую он считал соизмеримой с его самопровозглашенным средним уровнем навыков игры. [1] [4]
История
[ редактировать ]
Алан Тьюринг был английским математиком , ученым-компьютерщиком , логиком , криптоаналитиком , философом и биологом-теоретиком . [5] Тьюринг оказал большое влияние на развитие теоретической информатики , обеспечив формализацию понятий алгоритма и вычислений с помощью машины Тьюринга , которую можно считать моделью компьютера общего назначения . [6] [7] [8] Тьюринг широко считается отцом теоретической информатики и искусственного интеллекта . [9] Начиная с 1941 года, работая над криптоанализом военного времени в Блетчли-парке , Тьюринг начал обсуждать со своими коллегами возможность того, что машина сможет играть в шахматы или выполнять другие «разумные» задачи, а также идею компьютера, решающего задачу с помощью поиск всех возможных решений с использованием эвристики или алгоритма. [10] [11] Некоторые работы Тьюринга по криптоанализу, например, над « Бомбой» , были выполнены с помощью этой модели вычислительной машины, ищущей возможности решения. [11] Он продолжал обсуждать эту идею со своими коллегами на протяжении всей войны, например, с экономическим статистиком Д. Г. Чамперноуном в 1944 году, и к 1945 году он был убежден, что машина, способная выполнять общие вычисления, теоретически способна воспроизвести все, что может сделать человеческий мозг. включая игру в шахматы. [10] [12]
После Второй мировой войны Тьюринг работал в Национальной физической лаборатории (NPL), где разработал автоматическую вычислительную машину (ACE), одну из первых разработок компьютера с хранимой программой. В 1946 году Тьюринг написал для НПЛ отчет под названием «Предлагаемый электронный калькулятор», в котором описал несколько проектов, для которых он планировал использовать ACE; одной из них была программа для игры в шахматы. В следующем году он выступил с лекцией в Лондонском математическом обществе , на которой представил идею о том, что машина, запрограммированная для игры в шахматы, может обучаться самостоятельно и приобретать собственный опыт. Впоследствии, в 1948 году, он написал для НПЛ новый отчет под названием «Интеллектуальная техника», в котором предложил форму имитации шахмат. [13]
В конце лета 1948 года Тьюринг и Чамперноун, тогда его коллега по Королевскому колледжу в Кембридже , разработали систему теоретических правил для определения следующих ходов шахматной партии. Они разработали программу, которая реализовывала алгоритм, который следовал этим правилам, хотя программа была слишком сложной, чтобы ее можно было запустить на ACE или любом другом компьютере того времени. [1] Программа получила название Turochamp , сочетание их фамилий. [13] Иногда его ошибочно называют «Турбочемпион». [14] По словам Чамперноуна, его жена сыграла в симуляцию игры против программы, получившей прозвище «бумажная машина», и проиграла. [13] [15] Тьюринг попытался преобразовать программу в исполняемый код для компьютера Ferranti Mark 1 1951 года в Манчестере, но не смог этого сделать из-за сложности кода. [14] По словам Джека Коупленда , автора нескольких книг о Тьюринге, его не беспокоило то, что программу невозможно запустить, поскольку он был убежден, что скорость и сложность компьютеров вскоре повысятся, чтобы сделать это возможным. [16] В том же году он написал статью, описывающую, как работает алгоритм программы, хотя и не назвал программу, которая была переиздана в 1953 году в книге « Быстрее, чем мысль» . [17] Летом 1952 года Тьюринг сыграл матч против ученого-компьютерщика Алика Гленни, используя программу, шаг за шагом выполняя ее вручную. В матче, который был записан, программа Турочампа проиграла Гленни за 29 ходов, причем на оценку каждого хода программы уходило до 30 минут. Хотя матч продемонстрировал, что программа может успешно играть против человека в полной игре, до смерти Тьюринга в 1954 году она не запускалась на реальном компьютере. [14]
Наследие
[ редактировать ]
Турочамп является кандидатом на создание первой шахматной программы, хотя оригинальная программа никогда не запускалась на компьютере. Примерно в то же время были разработаны и опробованы несколько других шахматных программ, например, в статье Клода Шеннона 1950 года « Программирование компьютера для игры в шахматы» , Конрада Цузе шахматные программы , разработанные с 1941 по 1945 год для предложенного им языка программирования Plankalkül , и Дональд Мичи. и Шона Уайли шахматная программа «Макиавелли» , которую Тьюринг безуспешно пытался запустить на Ферранти Марк I одновременно с Турочампом . [13] [18] [19] [20] В ноябре 1951 года Дитрих Принц , работавший в Ферранти и вдохновленный работой Тьюринга над Турочампом , разработал первую работоспособную компьютерную шахматную программу для Ферранти Марк I, которая могла решать « мат в два ». задачи [1]
Исходный код и алгоритм, написанные Тьюрингом и Чамперноуном, не сохранились. В 1980 году Чамперноун описал, как работал Турочамп , но не смог вспомнить всех деталей правил игры. [1] [16] Версия Turochamp была разработана в 2012 году на основе описаний алгоритма игры как символическое воссоздание. [21] После того, как первоначальное воссоздание не смогло воссоздать смоделированный матч Тьюринга против Гленни, к интерпретации описаний программы Тьюрингом и Чамперноуном были привлечены несколько экспертов по компьютерным шахматам и современники Тьюринга, включая Кена Томпсона , создателя шахматной машины Belle 1983 года и Unix. операционной системы . Они не смогли найти объяснение отклонения, пока не проконсультировались с Дональдом Мичи, который предположил, что Тьюринг не был озабочен тщательным определением того, какой именно ход Турочамп порекомендует . Имея это в виду, они смогли доказать, что с самого первого хода игры Тьюринг неправильно отклонялся от ходов, которые казались неоптимальными, без определения их очковой ценности. [а] Получившаяся игра была представлена на конференции столетия Алана Тьюринга 22–25 июня 2012 года в игре с гроссмейстером и бывшим чемпионом мира Гарри Каспаровым . [22] Каспаров выиграл партию за 16 ходов и похвалил программу за ее место в истории и за «исключительное достижение» в разработке работающей компьютерной шахматной программы, не имея возможности запустить ее на компьютере. [23]
См. также
[ редактировать ]
Примечания
[ редактировать ]- ^ В частности, Тьюринг открыл ход, переместив свою пешку на 2 поля на E4, поскольку он, вероятно, считал, что это явно лучший ход по сравнению с перемещением пешки на одно поле на E3, хотя на самом деле алгоритм дает ей меньшее значение в очках, поскольку теоретически оставляет короля открытым для атаковать с Е3, хотя в этот момент игры ни одна фигура противника не могла достичь этого места. [22]
Ссылки
[ редактировать ]- ^ Jump up to: а б с д и Коупленд , стр. 563-564.
- ^ «Дэвид Чамперноун (1912–2000)» . Журнал ICGA . 23 (4): 262. Декабрь 2000 г. doi : 10.3233/ICG-2000-23419 .
- ^ Кохлин, Дэниел (26 июня 2012 г.). «Каспаров против Тьюринга» . Университет Манчестера . Проверено 9 апреля 2019 г.
- ^ Jump up to: а б Леви; Новорожденный , с. 35
- ^ «Тьюринг, Алан Мэтисон» . Кто есть кто (онлайн- изд. Oxford University Press ). Оксфорд: A&C Black. 2017. doi : 10.1093/ww/9780199540884.013.U243891 . (Требуется подписка или членство в публичной библиотеке Великобритании .)
- ^ Ньюман, MHA (1955). «Алан Мэтисон Тьюринг. 1912–1954» . Биографические мемуары членов Королевского общества . 1 : 253–263. дои : 10.1098/rsbm.1955.0019 . JSTOR 769256 .
- ^ Грей, Пол (29 марта 1999 г.). «Алан Тьюринг – 100 человек века по версии журнала Time» . Время . Проверено 7 февраля 2019 г.
- ^ Сипсер , с. 37
- ^ Бобры , стр. 481–485.
- ^ Jump up to: а б Ходжес, Эндрю (30 сентября 2013 г.). «Алан Тьюринг» . Стэнфордская энциклопедия философии . Стэнфордский университет . Проверено 22 мая 2019 г.
- ^ Jump up to: а б Коупленд, Джек ; Праудфут, Дайан (2012). «Алан Тьюринг, основатель современного компьютера» . Резерфордский журнал . 1 (4). ISSN 1177-1380 .
- ^ Ходжес , с. 488
- ^ Jump up to: а б с д Бобры , стр. 644–650.
- ^ Jump up to: а б с Кларк, Лиат; Стедман, Ян (7 июня 2017 г.). «Вспоминая Алана Тьюринга: от взлома кодов до искусственного интеллекта, Тьюринг сделал мир таким, какой он есть сегодня» . Проводной . Конде Наст . Проверено 7 февраля 2019 г.
- ^ «Реконструкция «бумажной машины» Тьюринга ». Журнал ICGA . 40 (2): 1–8. Июнь 2018.
- ^ Jump up to: а б Оппи; Тракакис , стр. 13–14.
- ^ Тьюринг 1953 , гл. Глава 25: Цифровые компьютеры, применяемые в играх
- ^ Дасгупта , с. 193
- ^ Тьюринг 2015 , гл. 9
- ^ Аткинсон , с. 39
- ^ «Игрок века». Новое в шахматах . Интерчесс. Август 1999 г. стр. 6–7. ISSN 0168-8782 .
- ^ Jump up to: а б Каспаров, Гарри (июнь 2012 г.). Реконструкция «бумажной машины» Тьюринга . Конференция, посвященная столетию Алана Тьюринга . Манчестер, Англия . Проверено 9 апреля 2019 г. - через VideoLectures.net .
- ^ Парнелл, Брид-Эн (26 июня 2012 г.). «Шахматный алгоритм, написанный Аланом Тьюрингом, противостоит Каспарову» . Регистр . Ситуация Публикация . Проверено 9 апреля 2019 г.
Источники
[ редактировать ]- Ходжес, Эндрю (2014). Алан Тьюринг: Загадка . Издательство Принстонского университета . ISBN 978-1-4008-6512-3 .
- Бобры, Энтони (2013). Купер, С. Барри; ван Леувен, Ян (ред.). Алан Тьюринг: его работа и влияние . Эльзевир . ISBN 978-0-12-386980-7 .
- Оппи, Грэм; Тракакис, Ник (2011). Философ-антипод . Лексингтонские книги . ISBN 978-0-7391-6655-0 .
- Аткинсон, Джордж В. (1998). Шахматы и машинная интуиция . Интеллектуальные книги. ISBN 978-1-871516-44-9 .
- Коупленд, Б. Джек (2004). Эссенциальный Тьюринг . Издательство Оксфордского университета . ISBN 978-0-19-825079-1 .
- Леви, Дэвид ; Новорожденный, Монти (2009). Как компьютеры играют в шахматы . Иши Пресс . ISBN 978-4-87187-801-2 .
- Сипсер, Майкл (2006). Введение в теорию вычислений . Издательство ПВС. ISBN 978-0-534-95097-2 .
- Дасгупта, Субрата (2014). Все началось с «Бэббиджа: генезис информатики» . Издательство Оксфордского университета . ISBN 978-0-19-930941-2 .
- Тьюринг, Алан (1953). Боуэн, Б.В. (ред.). Быстрее, чем думалось: симпозиум по цифровым вычислительным машинам . Сэр Исаак Питман и сыновья .
- Тьюринг, Дермот (2015). Профессор: Расшифровка Алана Тьюринга . Историческая пресса . ISBN 978-0-7509-6524-8 .
Внешние ссылки
[ редактировать ]- Видео шахматного матча Гарри Каспарова и Турочампа отдыха
- Алан Тьюринг против Алика Гленни (1952) «Тест Тьюринга» на Chessgames.com
- Турочамп (компьютер) против Гарри Каспарова (2012) на Chessgames.com
- PyTuroChamp на GitHub — реализация Turochamp с открытым исходным кодом на Python.
- Turochamp в веб-браузере на основе этой версии Nim : nimTUROCHAMP на GitHub.