stringtranslate.com

Коток-Маккарти

компьютерный принтер или машинописный вывод игровой доски
Из «Программы игры в шахматы для компьютера IBM 7090» , дипломной работы Алана Котока, научный руководитель Джона Маккарти, Массачусетский технологический институт, 1962 г.

Kotok-McCarthy, также известная как A Chess Playing Program for the IBM 7090 Computer, была первой компьютерной программой, убедительно игравшей в шахматы . Она также запомнилась тем, что участвовала и проиграла первый шахматный матч между двумя компьютерными программами. Псевдокод программы представлен на рисунке 11.15. [1]

Разработка

В период с 1959 по 1962 год однокурсники Элвин Берлекамп , Алан Коток , Майкл Либерман, Чарльз Ниссен и Роберт А. Вагнер написали программу, будучи студентами Джона Маккарти в Массачусетском технологическом институте .

Основываясь на знаковой программе Алекса Бернстайна 1957 года [2], созданной в IBM , и на процедурах IBM 704 Маккарти и Пола В. Абрахамса, они добавили альфа-бета-обрезку к minmax по предложению Маккарти, чтобы улучшить генератор правдоподобных ходов. Они писали на Фортране и FAP на очищенном машинном времени. После того, как MIT получил 7090 от IBM , один ход занимал от пяти до двадцати минут. К 1962 году, когда они окончили университет, программа завершила фрагменты четырех игр на уровне, «сравнимом с любителем, имеющим опыт около 100 игр». [3] Коток, примерно в возрасте 20 лет, опубликовал их работу в MIT Artificial Intelligence Memo 41 и свою бакалаврскую диссертацию. [3]

Совпадение с ИТЭФ

В 1965 году Маккарти, к тому времени работавший в Стэнфордском университете , посетил Советский Союз . Группа, использовавшая компьютер М-2 в лаборатории Александра Кронрода в Московском институте теоретической и экспериментальной физики (ИТЭФ), бросила ему вызов на матч. [4] Кронрод считал Kotok-McCarthy лучшей программой в Соединенных Штатах в то время. [5] Хотя некоторые из ее недостатков были известны в 1965 году [6] и были исправлены в программе Гринблатта в проекте MAC MIT , Kotok-McCarthy уже не находилась в разработке и устарела на три года.

Георгий Адельсон-Вельский , Владимир Арлазаров , Битман, Анатолий Усков и Александр Животовский выиграли матч по переписке , который проводился по телеграфу в течение девяти месяцев в 1966-1967 годах. Программа Котока-Маккарти проиграла матч со счетом три к одному [5] , и первые две партии были сыграны со слабой версией. [7] Группу ИТЭФ консультировали русский шахматный мастер [ нужна ссылка ] Александр Р. Битман и трехкратный чемпион мира Михаил Ботвинник . [8] По данным Музея компьютерной истории , Маккарти «использовал улучшенную версию» [9] в 1967 году, но какие именно улучшения были сделаны, неизвестно.

Влияние

В 1967 году Mac Hack VI [10] Ричарда Гринблатта с Дональдом Э. Истлейком III стал почетным членом Шахматной федерации США [ требуется ссылка ], когда кто-то проиграл ему в турнире в Массачусетсе . Кронрод потерял свое директорство в ИТЭФ и свою профессорскую должность из-за жалоб пользователей физики на то, что математические ресурсы ИТЭФ использовались для игр. Михаил Донской, Арлазаров и Усков разработали программу ИТЭФ в Каиссу [ требуется ссылка ] в Институте наук об управлении, и в 1974 году она стала чемпионом мира по компьютерным шахматам . [11] Дебаты продолжались [12] около сорока лет после первого теста о том, превосходит ли подход Шеннона [13] типа А методом грубой силы, используемый ИТЭФ, селективную стратегию типа B, используемую Котоком-Маккарти. [7] Однако успех таких программ, как Chess 4.5 Северо-Западного университета, в которой использовалась стратегия типа A, [14] [15] привел к тому, что стратегия типа A стала более предпочтительной, по крайней мере для проектов, где целью была игровая сила, а не понимание мыслительных процессов человека. [16] Однако в последнее время шахматные программы, использующие нейронные сети для оценки позиций, такие как Giraffe, Alpha Chess Zero и Leela Chess Zero , используют поиск по дереву Монте-Карло , чтобы обеспечить более глубокий поиск, не оценивая каждую позицию.

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

Примечания

  1. ^ Ньюэлл, Аллен; Саймон, Герберт Александр (2019). Решение человеческих проблем . Браттлборо, Вермонт: Echo Point Books & Media. ISBN 978-1-63561-792-4.
  2. ^ Мастерство игры: история компьютерных шахмат , Музей компьютерной истории (сентябрь 2005 г.). "Дебютные ходы: происхождение компьютерных шахмат" . Получено 17 декабря 2006 г.
  3. ^ ab Kotok, Alan (3 декабря 2004 г.). "MIT Artificial Intelligence Memo 41" . Получено 2006-12-08 .
  4. ^ Маккарти, Джон (8 сентября 2005 г.). История компьютерных шахмат: перспектива ИИ ( Google Video ). Маунтин-Вью, Калифорния, США: Музей компьютерной истории . Получено 08.12.2006 .. Маккарти начинается с 0:43:48.
  5. ^ ab EM Landis , IM Yaglom , Remembering AS Kronrod , перевод на английский язык Виолы Брудно. W. Gautschi (ред.) [написано для Успехи математических наук , английское издание Math. Intelligencer (2002), 22-30], доступно в Stanford University School of Engineering SCCM-00-01 Архивировано 2007-06-13 на Wayback Machine (PostScript). Получено 19 декабря 2006 г.
  6. ^ Гринблатт, Ричард Д. (12 января 2005 г.). «Устная история Ричарда Гринблатта» (PDF) . Музей компьютерной истории. Архивировано из оригинала (PDF) 27 сентября 2011 г. . Получено 01.07.2006 . {{cite journal}}: Цитировать журнал требует |journal=( помощь )
  7. ^ ab Брудно, Майкл (май 2000 г.). "Соревнования, противоречия и компьютерные шахматы" (PDF) . Получено 2006-12-09 . {{cite journal}}: Цитировать журнал требует |journal=( помощь )
  8. ↑ Дар новорожденного Монро (фотографа) (1980). «Международный гроссмейстер и чемпион мира Михаил Ботвинник в Москве». Инвентарный номер Музея компьютерной истории 102645357. Получено 24.12.2006 . {{cite web}}: Внешняя ссылка в |author=( помощь )
  9. ↑ Фото: Джон Маккарти, пионер искусственного интеллекта, играет в шахматы на IBM 7090 в Стэнфорде , неизвестный фотограф. Предоставлено Стэнфордским университетом. (1967). "Номер доступа Музея компьютерной истории L062302006" . Получено 22 декабря 2006 г.
  10. ^ Гринблатт, Ричард Д., Истлейк, Дональд Э. III и Крокер, Стивен Д. (1969). "Программа шахмат Гринблатта" (PDF) . Массачусетский технологический институт. Архивировано из оригинала (PDF) 2017-07-06 . Получено 2006-07-01 . {{cite journal}}: Цитировать журнал требует |journal=( помощь )CS1 maint: несколько имен: список авторов ( ссылка )
  11. ↑ Фото: Арлазаров, Усков и Донской в ​​Москве , неизвестный фотограф. Дар М. М. Ньюборна. (1980). "Инвентарный номер Музея компьютерной истории 102645411" . Получено 18 декабря 2006 г.
  12. ^ Newborn, Monty (28 февраля 2005 г.). "Устная история Monty Newborn" (PDF) . Computer History Museum . Получено 2006-12-17 . {{cite journal}}: Цитировать журнал требует |journal=( помощь )
  13. ^ Шеннон, Клод Э. (март 1950 г.). «Программирование компьютера для игры в шахматы» (PDF) . Philosophical Magazine . 7-я серия. 41 (314). Архивировано из оригинала (PDF) 2010-07-06 . Получено 2006-07-01 .
  14. ^ КОРФ, Ричард Э. (1985). «Итеративное углубление в глубину» (PDF) . {{cite journal}}: Цитировать журнал требует |journal=( помощь )
  15. ^ Фрей, Питер В.; Аткин, Ларри Р. (октябрь 1978 г.). «Создание шахматиста / Эссе о навыках игры в шахматы у человека и компьютера». BYTE . стр. 182. Получено 17 октября 2013 г.
  16. ^ Хит, Дэвид и Аллум, Дерек (апрель 1997 г.). «Историческое развитие компьютерных шахмат и его влияние на искусственный интеллект» (PDF) . Получено 24.11.2018 . {{cite journal}}: Цитировать журнал требует |journal=( помощь )CS1 maint: multiple names: authors list (link)

Ссылки

  • AIM-41 PostScript. Получено 24 декабря 2006 г.
  • AIM-41 PDF. Получено 24 декабря 2006 г.