Александр Брудно - Alexander Brudno

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

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

биография

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

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

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

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

Брудно - Кронрод семинар

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

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

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

         А /  а
   ? /  D (1) E (?)

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

Оценив 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. ^ Марсленд, Т.А. (Май 1987 г.). "Компьютерные шахматные методы (PDF) из Энциклопедии искусственного интеллекта. С. Шапиро (редактор)" (PDF). J. Wiley & Sons. С. 159–171. Архивировано из оригинал (PDF) на 2009-02-05. Получено 2006-12-21.
  3. ^ Э.М. Лэндис, И. М. Яглом, Вспоминая А.С. Кронрод, Английский перевод Виолы Брудно. В. Гаучи (ред.) [написано для Успехи математических наук., Английское издание Математика. Интеллигенсер (2002), 22-30], доступно на Инженерной школе Стэнфордского университета. SCCM-00-01 (PostScript). Проверено 19 декабря 2006 г. В архиве 13 июня 2007 г. Wayback Machine
  4. ^ Российский виртуальный компьютерный музей (1997–2006). «Быстрая универсальная цифровая вычислительная машина М-2». В архиве из оригинала 20.12.2010. Получено 2006-12-20.
  5. ^ Маккарти, Джон (27 ноября 2006 г.). «ИИ человеческого уровня сложнее, чем казалось в 1955 году». В архиве из оригинала от 06.12.2010. Получено 2006-12-20.
  6. ^ Ньюэлл, Аллен; Герберт А. Саймон (март 1976 г.). «Информатика как эмпирическое исследование: символы и поиск» (PDF). Коммуникации ACM. 19 (3): 113–126. Дои:10.1145/360018.360022. S2CID  5581562. Архивировано из оригинал (PDF) на 2007-10-01. Получено 2006-12-21.
  7. ^ Richards, D.J .; Харт, Т. (4 декабря 1961 - 28 октября 1963). «Альфа-бета-эвристика (AIM-030)». Массачусетский Институт Технологий. HDL:1721.1/6098. Цитировать журнал требует | журнал = (Помогите)
  8. ^ Коток, Алан (3 декабря 2004 г.). "Памятка 41 Массачусетского технологического института по искусственному интеллекту". В архиве из оригинала 2011-07-21. Получено 2006-07-01.
  9. ^ * Knuth, D. E .; Мур, Р. У. (1975). "Анализ альфа-бета обрезки". Искусственный интеллект. 6 (4): 293–326. Дои:10.1016/0004-3702(75)90019-3. : * Перепечатано как Глава 9 в Кнут, Дональд Э. (2000). Избранные статьи по анализу алгоритмов. Стэнфорд, Калифорния: Центр изучения языка и информации - Лекционные заметки CSLI, No. 102. ISBN  978-1-57586-212-5.
  10. ^ Абрамсон, Брюс (июнь 1989 г.). «Стратегии управления для игр для двух игроков» (PDF). Опросы ACM Computing. 21 (2): 137–161. Дои:10.1145/66443.66444. S2CID  11526154. Архивировано из оригинал (PDF) 3 сентября 2006 г.. Получено 2006-12-21.

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

  • Дар Монро Новорожденный (1980). «Брудно в Москве». Инвентарный номер Музея компьютерной истории 102645383. Получено 2006-12-25.
  • Брудно, А. Л. (1963). «Границы и оценки для сокращения поиска оценок». Проблемы Кибернетики. 10: 141–150. (Также в Проблемы кибернетики, 10:225–241)
  • Брудно А. Л., Л.И. Каплан, Олимпиады по программированию для школьников, Наука, 1985 г.

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