Александр Брудно
Русский учёный-компьютерщик (1918–2009)
Александр Львович Брудно
Рожденный( 1918-01-10 )10 января 1918 г.
Советский Союз
Умер1 декабря 2009 г. (2009-12-01)(91 год)
Израиль
Национальностьсоветский
Альма-матерМосковский государственный университет
ИзвестныйАльфа-бета обрезка
Научная карьера
ПоляИнформатика
научный руководительДмитрий Меньшов

Александр Львович Брудно ( 10 января 1918 — 1 декабря 2009) [1] — российский учёный-компьютерщик , наиболее известный тем, что полностью описал алгоритм альфа -бета-отсечения . [2] С 1991 года и до своей смерти он жил в Израиле.

Биография

Брудно разработал «интерфейс математика/машина» для ЭВМ М-2 , созданной в 1952 году в лаборатории Кржижановского Института энергетики Российской академии наук в Советском Союзе . [3] [4] Он был большим другом Александра Кронрода .

Работа Брудно по альфа-бета-отсечению была опубликована в 1963 году на русском и английском языках.

Алгоритм был использован в компьютерной шахматной программе, написанной Владимиром Арлазаровым и другими в Институте теоретической и экспериментальной физики (ИТЭФ или ИТЭФ). По словам Монти Ньюборна и Музея компьютерной истории , алгоритм был позже использован в Kaissa, чемпионе мира по компьютерным шахматам в 1974 году.

В 1980 году Брудно стал основателем и научным руководителем первой в России школы юных программистов УПЦ ВТ. Он был научным руководителем первых в России олимпиад школьников по программированию, издал сборник задач этих олимпиад.

Семинар Брудно – Кронрода

В 1959 году Брудно и Александр Кронрод организовали семинар, посвященный представлению различных работ в области системного программирования, программирования игр (в том числе шахматных) и искусственного интеллекта. На этом семинаре были представлены и обсуждены многие известные результаты, в том числе: квадратурная формула Гаусса–Кронрода , деревья AVL , компьютерные шахматы , распознавание образов (М. Бонгард ru:Бонгард, Михаил Моисеевич, П. Кунин и др.), метод четырех русских и др.

В 1963 году Брудно опубликовал свою работу по альфа-бета-обрезке . Ключевая идея заключалась в том, что игрок мог избежать оценки определенных ходов, которые были явно хуже уже рассмотренного.

В следующем игровом дереве вершины представляют позиции, а ребра представляют ходы. Оценки позиций указаны в скобках.

 А / \а
  ? / \ Д(1) Э(?)

Предположим, что «белые» должны сделать ход в позиции A, а затем «черные» могут сделать свой ход. «Белые» должны найти лучшую стратегию, чтобы максимизировать свой выигрыш ( стратегия «Минимакс» ).

После оценки AB и CD легко увидеть, что лучшим ходом для «белых» является AB, и нет необходимости проверять ход CE, так как общее значение вершины C будет не лучше 1. Это не изменится, если B, D, E — деревья, а не листья. Такие соображения, принимаемые на всех уровнях игрового дерева, известны как альфа-лучшая обрезка. Она использовалась в различных приложениях для программирования игр еще до работы Брудно; вклад Брудно заключался в формализации алгоритма и анализе его ускорения.

В 1959 году работа Брудно по альфа-бета-обрезке была мотивирована анализом карточной игры, в которой двум игрокам раздают по n карт со значениями 1...2n, и один игрок выбирается, чтобы ходить первым. Каждый игрок кладет одну карту, при этом обладатель большей карты берет взятку, а берущий ходит первым в следующем ходе. Цель состоит в том, чтобы определить оптимальную стратегию с учетом начальной руки игрока и порядка ходов. Анализ этой карточной игры использовался на семинаре для уточнения понимания рекурсии и структурного программирования, а также для разработки обновляемых словарей.

Ранняя обрезка альфа-бета

Аллен Ньюэлл и Герберт А. Саймон , которые использовали то, что Джон Маккарти называет «приближением» [5] в 1958 году, написали, что альфа-бета «по-видимому, была изобретена заново несколько раз». [6] У Артура Сэмюэля была ранняя версия, а Ричардс, Харт, Левин и/или Эдвардс независимо нашли альфа-бета в Соединенных Штатах . [7] Маккарти предложил похожие идеи во время Дартмутской конференции в 1956 году и предложил их группе своих студентов, включая Алана Котока в Массачусетском технологическом институте в 1961 году. [8] Дональд Кнут и Рональд В. Мур усовершенствовали алгоритм в 1975 году [9] [10] , и он продолжал совершенствоваться.

Примечания

  1. ↑ Александр Брудно в Публичной библиотеке (на русском языке)
  2. ^ Marsland, TA (май 1987). «Computer Chess Methods (PDF) from Encyclopedia of Artificial Intelligence. S. Shapiro (editor)» (PDF) . J. Wiley & Sons. стр.  159–171 . Архивировано из оригинала (PDF) 2009-02-05 . Получено 2006-12-21 .
  3. ^ EM Landis , IM Yaglom , Remembering AS Kronrod , перевод на английский язык Виолы Брудно. W. Gautschi (ред.) [написано для Успехи математических наук , английское издание Math. Intelligencer (2002), 22-30], доступно в Stanford University School of Engineering SCCM-00-01 (PostScript). Получено 19 декабря 2006 г. Архивировано 13 июня 2007 г. на Wayback Machine
  4. ^ "Быстрая универсальная цифровая вычислительная машина М-2". Российский виртуальный компьютерный музей . 1997–2006. Архивировано из оригинала 20.12.2010 . Получено 20.12.2006 .
  5. ^ Маккарти, Джон (27 ноября 2006 г.). «Искусственный интеллект человеческого уровня сложнее, чем казалось в 1955 году». Архивировано из оригинала 2010-12-06 . Получено 2006-12-20 .
  6. ^ Ньюэлл, Аллен; Саймон, Герберт А. (март 1976 г.). «Компьютерная наука как эмпирическое исследование: символы и поиск». Сообщения ACM . 19 (3): 113– 126. doi :10.1145/360018.360022. S2CID  5581562.
  7. ^ Ричардс, DJ; Харт, TP (4 декабря 1961 г. – 28 октября 1963 г.). «Альфа-бета-эвристика». AI Memos . Массачусетский технологический институт. hdl :1721.1/6098. AIM-030.
  8. ^ Коток, Алан (3 декабря 2004 г.). "MIT Artificial Intelligence Memo 41". Архивировано из оригинала 2011-07-21 . Получено 2006-07-01 .
  9. ^ * Кнут, Д. Э.; Мур, Р. В. (1975). «Анализ обрезки альфа-бета». Искусственный интеллект . 6 (4): 293– 326. doi :10.1016/0004-3702(75)90019-3. :* Перепечатано как Глава 9 в Knuth, Donald E. (2000). Избранные статьи по анализу алгоритмов . Стэнфорд, Калифорния: Центр изучения языка и информации - CSLI Lecture Notes, № 102. ISBN 978-1-57586-212-5.
  10. ^ Абрамсон, Брюс (июнь 1989 г.). «Стратегии управления для игр с двумя игроками» (PDF) . ACM Computing Surveys . 21 (2): 137– 161. doi :10.1145/66443.66444. S2CID  11526154. Архивировано из оригинала (PDF) 3 сентября 2006 г. . Получено 21 декабря 2006 г.

Ссылки

  • "Брудно в Москве". Музей истории компьютеров . 1980. Получено 25.12.2006 .
  • Брудно, АЛ (1963). «Границы и оценки для сокращения поиска оценок». Проблемы кибернетики . 10 : 141–150 .(Также в «Проблемах кибернетики» , 10 :225–241)
  • Брудно А. Л., Л.И. Каплан, Олимпиада по программированию для школьников, Наука, 1985.
  • Рукописное письмо (12.04.1971) и почтовая открытка (19.11.1971) от Брудно А.П. Ершову . (на английском и русском языках)
  • Медиа, связанные с Александром Брудно на Wikimedia Commons
Взято с "https://en.wikipedia.org/w/index.php?title=Александр_Брудно&oldid=1255363215"