Alexander Brudno
Alexander L'vovich Brudno | |
|---|---|
 | |
| Рожденный | 10 января 1918 г. |
| Умер | 1 декабря 2009 г. (91 год) |
| Национальность | Советский |
| Альма-матер | Московский Государственный Университет |
| Известный | Альфа-бета обрезка |
| Научная карьера | |
| Поля | Информатика |
| Докторантура | Dmitrii Menshov |
Alexander L'vovich Brudno ( Russian : Александр Львович Брудно ) (10 January 1918 – 1 December 2009) [1] был российским ученым-компьютерщиком , наиболее известным благодаря полному описанию обрезки альфа-бета алгоритма . [2] С 1991 года и до своей смерти жил в Израиле.
Биография
[ редактировать ]Брудно разработал «математическо-машинный интерфейс» для компьютера М-2 , построенного в 1952 году в лаборатории Кржижановского Института энергетики РАН в Советском Союзе . [3] [4] Он был большим другом Александра Кронрода .
Работа Брудно по альфа-бета-обрезке была опубликована в 1963 году на русском и английском языках.
Алгоритм использовался в компьютерной шахматной программе, написанной Владимиром Арлазаровым и другими в Институте теоретической и экспериментальной физики (ИТЭФ или ИТЭФ). По данным Монти Ньюборна и Музея компьютерной истории , алгоритм позже использовался в Кайссе, чемпионке мира по компьютерным шахматам в 1974 году.
В 1980 году Брудно стал основателем и научным руководителем первой в России школы молодых программистов УПЦ ВТ . Он был научным руководителем первых российских студенческих олимпиад по программированию, издал сборник задач этих соревнований.
Брудно – Кронродский семинар
[ редактировать ]В 1959 году Брудно и Александр Кронрод организовали семинар, посвященный презентации различных работ в области системного программирования, программирования игр (в том числе шахматных) и искусственного интеллекта. На семинаре были представлены и обсуждены многие известные результаты, в том числе: квадратурная формула Гаусса–Кронрода , деревья АВЛ , компьютерные шахматы , распознавание образов (М.Бонгард ru:Бонгард, Михаил Моисеевич , П.Кунин и др.), метод четырёх россиян. и другие.
В 1963 году Брудно опубликовал свою работу по альфа-бета-обрезке . Ключевой интуицией было то, что игрок мог избежать оценки определенных ходов, которые явно уступали уже рассмотренному.
В следующем игровом дереве вершины представляют позиции, а ребра представляют ходы. В скобках указаны оценки позиции. .
A
/ \a
?
/ \
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] и оно продолжало развиваться.
Примечания
[ редактировать ]- ^ Александр Брудно в Публичной библиотеке (на русском языке)
- ^ Марсленд, штат Калифорния (май 1987 г.). «Компьютерные шахматные методы (PDF) из Энциклопедии искусственного интеллекта. С. Шапиро (редактор)» (PDF) . Дж. Уайли и сыновья. стр. 159–171. Архивировано из оригинала (PDF) 5 февраля 2009 г. Проверено 21 декабря 2006 г.
- ^ Э.М. Лэндис , И.М. Яглом , Вспоминая А.С. Кронрода , английский перевод Виолы Брудно. В. Гаучи (ред.) [написано для Успехов математических наук , английское издание Math. Intelligencer (2002), 22–30], доступно в Школе инженерии Стэнфордского университета SCCM-00-01 (PostScript). Проверено 19 декабря 2006 г. Архивировано 13 июня 2007 г. в Wayback Machine.
- ^ «Быстрая универсальная цифровая вычислительная машина М-2» . Российский виртуальный компьютерный музей . 1997–2006 гг. Архивировано из оригинала 20 декабря 2010 г. Проверено 20 декабря 2006 г.
- ^ Маккарти, Джон (27 ноября 2006 г.). «ИИ на человеческом уровне сложнее, чем казалось в 1955 году» . Архивировано из оригинала 6 декабря 2010 г. Проверено 20 декабря 2006 г.
- ^ Ньюэлл, Аллен; Саймон, Герберт А. (март 1976 г.). «Информатика как эмпирическое исследование: символы и поиск». Коммуникации АКМ . 19 (3): 113–126. дои : 10.1145/360018.360022 . S2CID 5581562 .
- ^ Ричардс, диджей; Харт, Т.П. (4 декабря 1961 г. - 28 октября 1963 г.). «Альфа-бета-эвристика». AI-памятки . Массачусетский технологический институт. hdl : 1721.1/6098 . АИМ-030.
- ^ Коток, Алан (3 декабря 2004 г.). «Памятка MIT по искусственному интеллекту 41» . Архивировано из оригинала 21 июля 2011 г. Проверено 1 июля 2006 г.
- ^ * Кнут, Делавэр; Мур, RW (1975). «Анализ альфа-бета-обрезки». Искусственный интеллект . 6 (4): 293–326. дои : 10.1016/0004-3702(75)90019-3 . :* Перепечатано как Глава 9 в Кнут, Дональд Э. (2000). Избранные статьи по анализу алгоритмов . Стэнфорд, Калифорния: Центр изучения языка и информации - Конспекты лекций CSLI, вып. 102. ИСБН 978-1-57586-212-5 .
- ^ Абрамсон, Брюс (июнь 1989 г.). «Стратегии управления для игр с двумя игроками» (PDF) . Обзоры вычислительной техники ACM . 21 (2): 137–161. дои : 10.1145/66443.66444 . S2CID 11526154 . Архивировано из оригинала (PDF) 3 сентября 2006 г. Проверено 21 декабря 2006 г.
Ссылки
[ редактировать ]- «Брудно в Москве» . Музей истории компьютеров . 1980 год . Проверено 25 декабря 2006 г.
- Брудно, А.Л. (1963). «Границы и оценки для сокращения поиска оценок». Проблемы Кибернетики . 10 : 141–150. (Также в «Проблемах кибернетики» , 10 : 225–241)
- Брудно А. Л., Л.И. Каплан, Олимпиады по программированию для школьников, Наука, 1985
Внешние ссылки
[ редактировать ]- Рукописное письмо (12.04.1971) и открытка (19.11.1971) из Брудно А. П. Ершову . (на английском и русском языках)
СМИ, связанные с Александром Брудно, на Викискладе?
| Международный | |
|---|---|
| Национальный | |
| академики | |
