Турошам - Turochamp

Турошам
Разработчики)Алан Тьюринг, Дэвид Чамперноун
Жанр (ы)Компьютерные шахматы
Режим (ы)Один игрок

Турошам это шахматная программа разработан Алан Тьюринг и Дэвид Чамперноун в 1948 году. Он был создан в рамках исследования пары в области информатики и машинного обучения. Турошам способен сыграть всю шахматную партию против игрока-человека на низком уровне игры, вычисляя все потенциальные ходы и все ходы потенциального игрока в ответ, присваивая значения очков каждому состоянию игры и выбирая ход с максимально возможным средним значением значение пункта.

Турошам самый ранний из известных компьютерная игра чтобы войти в разработку, но так и не был завершен Тьюрингом и Чамперноуном, поскольку его алгоритм был слишком сложен для запуска на ранних компьютерах того времени, таких как Автоматическая вычислительная машина. Тьюринг попытался преобразовать программу в исполняемый код для 1951 г. Ферранти Марк 1 компьютер в Манчестере, но не смог этого сделать. Тьюринг сыграл матч против компьютерного ученого Алик Гленни использовал программу летом 1952 года, выполняя ее вручную, шаг за шагом, но к своей смерти в 1954 году все еще не смог запустить программу на реальном компьютере. Champernowne не продолжил проект, и первоначальный дизайн программы не был сохранен. Несмотря на то, что программа никогда не запускалась на компьютере, она является кандидатом на роль первой шахматной программы; несколько других шахматных программ были разработаны или предложены примерно в то же время, в том числе еще одна, которую Тьюринг безуспешно пытался запустить на Ferranti Mark 1. Первая успешная программа в 1951 году, также разработанная для Mark 1, была непосредственно вдохновлена Турошам, и был способен только решать "товарищ по двое "проблемы. Воспроизведение Турошам построен в 2012 году для Конференция по случаю столетия Алана Тьюринга. Эта версия использовалась в матче с шахматами. гроссмейстер Гарри Каспаров, выступивший с основным докладом на конференции.

Геймплей

Турошам имитирует игру в шахматы против игрока, принимая ходы игрока как входные и выводя его ход в ответ. В алгоритме программы используется двухходовой эвристический чтобы определить лучший ход, который нужно сделать: он вычисляет все возможные ходы, которые он может сделать, затем все потенциальные ответы игрока, которые могут быть сделаны по очереди, присваивает значение балла каждому результирующему состоянию, затем делает ход с наибольшим средние итоговые баллы.[1][2][3] Очки определяются на основании нескольких критериев, таких как подвижность каждой фигуры, безопасность каждой фигуры, угроза матом, ценность фигуры игрока, если она взята, и несколько других факторов. Разным ходам даются разные баллы; например, взятие ферзя дает 10 очков, а пешка только одно очко, а размещение короля под шахом дает очко или половину очка в зависимости от расположения доски.[4] По словам Чамперноуна, алгоритм в первую очередь разработан вокруг решения брать кусок или нет; согласно Тьюрингу, в результате получается игра в шахматы низкого уровня, которую он считал соизмеримой с его самоописанным средним уровнем мастерства в игре.[1][4]

История

Алан Тьюринг в 16 лет

Алан Тьюринг был англичанином математик, специалист в области информатики, логик, криптоаналитик, философ и биолог-теоретик.[5] Тьюринг оказал большое влияние на развитие теоретическая информатика, обеспечивающий формализацию понятий алгоритм и вычисление с Машина Тьюринга, который можно рассматривать как образец универсального компьютер.[6][7][8] Тьюринг считается отцом теоретической информатики и искусственный интеллект.[9] Начиная с 1941 г., работая в криптоанализ военного времени в Bletchley Park, Тьюринг начал обсуждать со своими коллегами возможность машины играть в шахматы или выполнять другие «умные» задачи, а также идею о том, что компьютер решает проблему путем поиска всех возможных решений с использованием эвристический или алгоритм.[10][11] Некоторые из работ Тьюринга по криптоанализу, например, Бомба, было сделано с помощью этой модели вычислительной машины, ищущей возможности решения.[11] Он продолжал обсуждать эту идею со своими коллегами на протяжении всей войны, например, со специалистом по экономической статистике. Д. Г. Чамперноун в 1944 г., а к 1945 г. он был убежден, что машина, способная выполнять общие вычисления, теоретически будет способна воспроизвести все, что может делать человеческий мозг, включая игру в шахматы.[10][12]

После Вторая Мировая Война, Тьюринг работал в Национальная физическая лаборатория (НПЛ), где он разработал Автоматическая вычислительная машина (ACE), среди первых разработок для компьютера с хранимой программой. В 1946 году Тьюринг написал отчет для NPL под названием «Предлагаемый электронный калькулятор», в котором описывалось несколько проектов, для которых он планировал использовать ACE; одна из них была программой для игры в шахматы. Он читал в Лондонское математическое общество В следующем году он представил идею о том, что машина, запрограммированная для игры в шахматы, может учиться сама и приобретать собственный опыт. Впоследствии, в 1948 году, он написал новый отчет для НПЛ под названием «Интеллектуальные машины», в котором предлагал форму имитации шахмат.[13]

В конце лета 1948 года Тьюринг и Чамперноун, тогда его коллега в Королевский колледж, Кембридж, разработал систему теоретических правил для определения следующих ходов шахматной партии. Они разработали программу, которая будет вводить в действие алгоритм, который будет следовать этим правилам, хотя программа была слишком сложной, чтобы ее можно было запустить на ACE или на любом другом компьютере того времени.[1] Программа получила название Турошам, сочетание их фамилий.[13] Иногда его ошибочно называют "Турбочамп".[14] По словам Чамперноуна, его жена сыграла в имитационную игру против программы, получившей прозвище «бумагоделательная машина», и проиграла.[13][15] Тьюринг попытался преобразовать программу в исполняемый код для 1951 г. Ферранти Марк 1 компьютер в Манчестере, но не смог этого сделать из-за сложности кода.[14] Согласно с Джек Коупленд, автор нескольких книг по Тьюрингу, его не беспокоила невозможность запуска программы, поскольку он был убежден, что скорость и сложность компьютеров скоро вырастут, чтобы сделать это возможным.[16] Летом 1952 года Тьюринг сыграл матч против компьютерного ученого. Алик Гленни используя программу, шаг за шагом выполняя ее вручную. Матч, который был записан, имел Турошам программа проигрывает Гленни за 29 ходов, причем оценка каждого хода программы занимает до 30 минут. Хотя матч продемонстрировал, что программа может реально играть против человека в полной игре, она не была запущена на реальном компьютере до смерти Тьюринга в 1954 году.[14]

Наследие

Гарри Каспаров выступая в Конференция по случаю столетия Алана Тьюринга в Манчестер 25 июня 2012 г.

Турошам является кандидатом на роль первой шахматной программы, хотя исходная программа никогда не запускалась на компьютере. Примерно в то же время были разработаны и опробованы несколько других шахматных программ, например, Клод Шеннон статья 1950 года Программирование компьютера для игры в шахматы, Конрад Зузе шахматные программы, разработанные с 1941 по 1945 год для предложенного им языка программирования. Plankalkül, и Дональд Мичи и Шон Уайли шахматная программа Макиавелли, который Тьюринг безуспешно пытался запустить на Ferranti Mark I одновременно с Турошам.[13][17][18][19] В ноябре 1951 г. Дитрих Принц, который работал в Ферранти и был вдохновлен работой Тьюринга над Турошам, разработал первую работающую компьютерную шахматную программу для Ferranti Mark I, которая могла решать "товарищ по двое " проблемы.[1]

Исходный код и алгоритм, написанный Тьюрингом и Чамперноуном, не сохранились. В 1980 году Чамперноун описал способ Турошам работало, но он не мог вспомнить все детали правил игры.[1][16] Версия Турошам был разработан в 2012 году на основе описания алгоритма игры как символическая игра.[20] После того, как первоначальная игра не смогла воссоздать смоделированный матч Тьюринга против Гленни, несколько компьютерных шахматистов и современников Тьюринга были проконсультированы в интерпретации описаний программы Тьюринга и Чамперноу, включая Кен Томпсон, создатель 1983 г. Belle шахматная машина и Unix Операционная система. Они не смогли найти объяснение отклонению, пока не посоветовались с Дональдом Мичи, который предположил, что Тьюринг не был озабочен скрупулезным определением того, какой именно ход Турошам рекомендую. Имея это в виду, они смогли доказать, что с самого первого хода игры Тьюринг неправильно отклонился от ходов, которые казались неоптимальными, не определив их количество очков.[а] Полученный отдых был представлен на Конференция по случаю столетия Алана Тьюринга 22–25 июня 2012 г., в матче с шахматами гроссмейстер и бывший чемпион мира Гарри Каспаров.[21] Каспаров выиграл матч за 16 ходов и похвалил программу за ее место в истории и «исключительное достижение» разработки работающей компьютерной шахматной программы, не имея возможности запустить ее на компьютере.[22]

Смотрите также

Заметки

  1. ^ В частности, Тьюринг открыл, переместив свою пешку на 2 деления на Е4, поскольку он, вероятно, чувствовал, что это был явно лучший ход, чем переместить ее на одну клетку на Е3, хотя на самом деле алгоритм дает ему более низкое значение, поскольку он оставляет короля теоретически открытым для атаки. из E3, даже если на этом этапе игры ни одна фигура противника не могла достичь этого места.[21]

использованная литература

  1. ^ а б c d е Существенный Тьюринг, стр. 563-564
  2. ^ "Дэвид Чамперноун (1912-2000)". Журнал ICGA. 23 (4): 262. Декабрь 2000 г. Дои:10.3233 / ICG-2000-23419.
  3. ^ Кочлин, Дэниел (26.06.2012). «Каспаров против Тьюринга». Манчестерский университет. Получено 2019-04-09.
  4. ^ а б Как компьютеры играют в шахматы, п. 35 год
  5. ^ "Тьюринг, Алан Мэтисон". Кто есть кто. ukwhoswho.com (онлайн Oxford University Press ред.). A&C Black, отпечаток Bloomsbury Publishing plc. 2017 г. Дои:10.1093 / ww / 9780199540884.013.U243891. (подписка или Членство в публичной библиотеке Великобритании требуется) (требуется подписка)
  6. ^ Ньюман, М. Х. А. (1955). «Алан Мэтисон Тьюринг. 1912–1954». Биографические воспоминания членов Королевского общества. 1: 253–263. Дои:10.1098 / рсбм.1955.0019. JSTOR  769256.
  7. ^ Грей, Пол (1999-03-29). «Алан Тьюринг - Время 100 человек века». Время. Получено 2019-02-07.
  8. ^ Введение в теорию вычислений, п. 37
  9. ^ Алан Тьюринг: его работа и влияние, стр. 481–485
  10. ^ а б Ходжес, Эндрю (2013-09-30). "Алан Тьюринг". Стэнфордская энциклопедия философии. Стэндфордский Университет. Получено 2019-05-22.
  11. ^ а б Коупленд, Джек; Праудфут, Дайан (2012). «Алан Тьюринг, основатель современного компьютера». Журнал Резерфорда. 1 (4). ISSN  1177-1380.
  12. ^ Алан Тьюринг: Загадка, п. 488
  13. ^ а б c d Алан Тьюринг: его работа и влияние, стр. 644–650
  14. ^ а б c Кларк, Лиат; Стедман, Ян (07.06.2017). «Вспоминая Алана Тьюринга: от взлома кода до ИИ, Тьюринг сделал мир таким, какой он есть сегодня». Проводной. Condé Nast. Получено 2019-02-07.
  15. ^ "Реконструкция машины Тьюринга""". Журнал ICGA. 40 (2): 1–8. Июнь 2018 г.
  16. ^ а б Философ-антипод, стр. 13–14
  17. ^ Все началось с Бэббиджа: зарождение компьютерных наук, п. 193
  18. ^ Профессор: Алан Тьюринг Декодировано, гл. 9
  19. ^ Шахматы и машинная интуиция, п. 39
  20. ^ «Игрок века». Новое в шахматах. Interchess. Август 1999. С. 6–7. ISSN  0168-8782.
  21. ^ а б Каспаров, Гарри (Июнь 2012 г.). Реконструкция "бумагоделательной машины" Тьюринга. Конференция по случаю столетия Алана Тьюринга. Манчестер, Англия. Получено 2019-04-09 - через VideoLectures.net.
  22. ^ Парнелл, Брид-Эйн (26.06.2012). «Шахматный алгоритм, написанный Аланом Тьюрингом, идет против Каспарова». Реестр. Публикация ситуации. Получено 2019-04-09.

Источники

внешние ссылки