Обучающий двигатель Matchbox Naughty and Crossers
Механический компьютер из спичечных коробков

УГРОЗА отдых
Реконструкция MENACE, созданная в 2015 году.

Обучаемая игра «Крестики-нолики» на основе спичечных коробков (иногда называемая обучаемой машиной «Крестики-нолики» или MENACE ) — механический компьютер , сделанный из 304 спичечных коробков , разработанный и построенный исследователем искусственного интеллекта Дональдом Мичи в 1961 году. Он был разработан для игры с людьми в крестики-нолики (крестики-нолики), возвращая ход для любого заданного состояния игры и совершенствуя свою стратегию посредством обучения с подкреплением .

У Мичи не было компьютера, поэтому он обошел это ограничение, построив его из спичечных коробков. Каждый из спичечных коробков, используемых Мичи, представлял собой одну возможную схему сетки крестиков-ноликов. Когда компьютер впервые играл, он случайным образом выбирал ходы на основе текущей схемы. По мере того, как он играл больше игр, через цикл подкрепления он дисквалифицировал стратегии, которые приводили к проигрышу, и дополнял стратегии, которые приводили к победе. Мичи провел турнир против MENACE в 1961 году, где он экспериментировал с различными дебютами.

После первого турнира MENACE против Michie, он продемонстрировал успешный искусственный интеллект в своей стратегии. Очерки Michie об инициализации веса MENACE и алгоритме BOXES, используемом MENACE, стали популярными в области компьютерных исследований. Michie был удостоен награды за свой вклад в исследования машинного обучения и дважды был уполномочен программировать симуляцию MENACE на реальном компьютере.

Источник

Дональд Мичи в 1986 году
Дональд Мичи , 1986

Дональд Мичи (1923–2007) был в команде, расшифровывавшей немецкий код Тунни во время Второй мировой войны . [1] Пятнадцать лет спустя он захотел еще больше продемонстрировать свои математические и вычислительные способности с помощью ранней сверточной нейронной сети . Поскольку компьютерное оборудование для таких целей было недоступно, [2] а у Мичи не было компьютера под рукой, [2] он решил продемонстрировать искусственный интеллект в более эзотерическом формате и сконструировал функциональный механический компьютер из спичечных коробков и бусинок. [3] [4]

MENACE был создан в результате спора с коллегой по информатике, который предположил, что такая машина невозможна. [5] Мичи взял на себя задачу сбора и описания каждого спичечного коробка как «забавного проекта», позже превратившегося в демонстрационный инструмент. [6] Мичи завершил свое эссе по MENACE в 1963 году, [4] «Эксперименты по механизации игрового обучения», а также свое эссе по алгоритму BOXES, написанное совместно с Р. А. Чемберсом [6] и создал исследовательское подразделение ИИ в Хоуп-Парк-сквер, Эдинбург , Шотландия . [7]

MENACE обучалась, играя в увеличивающиеся пары крестиков и ноликов. Каждый раз она исключала проигрышную стратегию, поскольку игрок-человек конфисковывал бусины, соответствующие каждому ходу. [4] Она усиливала выигрышные стратегии, делая ходы более вероятными, предоставляя дополнительные бусины. [8] Это была одна из самых ранних версий цикла подкрепления , схематического алгоритма зацикливания алгоритма, отбрасывающего неудачные стратегии до тех пор, пока не останутся только выигрышные. [4] Эта модель начинается как полностью случайная и постепенно обучается. [9]

Состав

MENACE была сделана из 304 спичечных коробков, склеенных вместе в виде комода. [10] У каждой коробки был кодовый номер, который был введен в таблицу. Эта таблица содержала рисунки игровых сеток крестиков-ноликов с различными конфигурациями X , O и пустых квадратов, [4] соответствующих всем возможным перестановкам, которые могла пройти игра по мере ее развития. [11] После удаления дублирующихся расположений (тех, которые были просто вращениями или зеркальными отражениями других конфигураций), MENACE использовала 304 перестановки в своей таблице и, следовательно, столько же спичечных коробков. [12]

Каждый отдельный лоток для спичек содержал набор цветных бусин. [13] Каждый цвет представлял собой ход на клетке на игровой сетке, и поэтому спичечные коробки с расстановками, где позиции на сетке уже были заняты, не имели бы бусин для этой позиции. Кроме того, в передней части лотка были два дополнительных куска карты в форме «V», [10] острие «V» указывало на переднюю часть спичечного коробка. [11] Мичи и его команда искусственного интеллекта назвали алгоритм MENACE «Коробками», [7] в честь аппарата, используемого для машины. Первый этап «Коробки» работал в пять фаз, каждая из которых устанавливала определение и прецедент для правил алгоритма по отношению к игре. [14]

Операция

Пример игры, в которую играют MENACE (O) и человек (X), используя бусины оригинальных цветов Мичи. Поскольку MENACE проиграла эту игру, все показанные бусины убраны из соответствующих коробок [15] [16]

MENACE играл первым, как O, поскольку все спичечные коробки представляли собой перестановки, имеющие отношение только к игроку «X». [12] [17] Чтобы получить выбор хода MENACE, противник или оператор находил спичечный коробок, который соответствовал текущему состоянию игры, или его вращение или зеркальное отражение. Например, в начале игры это был бы спичечный коробок для пустой сетки. Лоток убирали и слегка встряхивали, чтобы переместить бусины. [4] Затем бусина, которая закатилась в точку формы «V» в передней части лотка, была ходом, который выбрал MENACE. [4] Затем ее цвет использовался в качестве позиции для игры, и после учета любых вращений или переворотов, необходимых на основе отношения выбранной конфигурации спичечного коробка к текущей сетке, O помещался на этот квадрат. Затем игрок выполнял свой ход, новое состояние находилось, выбирался новый ход и так далее, пока игра не заканчивалась. [12]

Когда игра заканчивалась, игрок-человек наблюдал за результатом игры. По мере игры каждый спичечный коробок, который использовался для хода MENACE, возвращался на свой лоток приоткрытым, а использованная бусина откладывалась в сторону, так что выбор ходов MENACE и игровые состояния, к которым они принадлежали, записывались. Мичи описал свою систему подкрепления с помощью «вознаграждения» и «наказания». После окончания игры, если MENACE побеждал, он получал «вознаграждение» за свою победу. Удаленные бусины показывали последовательность выигрышных ходов. [17] Их возвращали на соответствующие лотки, которые легко идентифицировались, поскольку они были слегка приоткрыты, а также три бонусные бусины того же цвета. [11] Таким образом, в будущих играх MENACE с большей вероятностью повторял эти выигрышные ходы, подкрепляя выигрышные стратегии. Если он проигрывал, то снятые бусины не возвращались, «наказывая» УГРОЗУ, и это означало, что в будущем он будет менее склонен, а в конечном итоге и не сможет, если этот цвет бусины исчезнет, ​​повторять ходы, которые приводят к проигрышу. [3] [8] Если игра заканчивалась вничью, в каждую коробку добавлялась одна дополнительная бусина. [11]

Результаты на практике

Оптимальная стратегия

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

Крестики-нолики имеют хорошо известную оптимальную стратегию. [18] Игрок должен разместить свой символ таким образом, чтобы заблокировать другому игроку возможность получить какие-либо ряды, одновременно составляя ряд самому. Однако, если оба игрока используют эту стратегию, игра всегда заканчивается вничью. [18] Если игрок-человек знаком с оптимальной стратегией, а MENACE может быстро ее изучить, то игры в конечном итоге будут заканчиваться только вничью. Вероятность победы компьютера быстро увеличивается, когда компьютер играет против случайного противника. [3]

При игре против игрока, использующего оптимальную стратегию, шансы на ничью возрастают до 100%. В официальном турнире Дональда Мичи против MENACE в 1961 году [4] он использовал оптимальную стратегию, и он и компьютер начали стабильно играть вничью после двадцати игр. Турнир Мичи [19] имел следующие вехи: Мичи начал с последовательного открытия с «Варианта 0», среднего квадрата. В 15 играх MENACE отказался от всех неугловых дебютов. Чуть больше 20 Мичи перешел на постоянное использование «Варианта 1», нижнего правого квадрата. В 60 он вернулся к Варианту 0. Когда он приблизился к 80 играм, он перешел на «Вариант 2», верхний средний. В 110 он перешел на «Вариант 3», верхний правый. В 135 он перешел на «Вариант 4», средний правый. В 190 он вернулся к Варианту 1, а в 210 — к Варианту 0.

Тенденция изменения количества бусин в ящиках «2» выглядит следующим образом: [19]

ВариантНомер матчаСмена бусин в коробке "2"
Вариант 000
Вариант 120-5
Вариант 0605
Вариант 27010
Вариант 311020
Вариант 413525
Вариант 1190100
Вариант 0210120

Корреляция

Диаграмма рассеяния турнира Мичи.
Диаграмма рассеивания, показывающая результаты игр Дональда Мичи против MENACE

В зависимости от стратегии, используемой игроком-человеком, MENACE создает различную тенденцию на графиках рассеивания выигрышей. [4] Использование случайного хода игрока-человека приводит к почти идеальной положительной тенденции. Игра по оптимальной стратегии возвращает немного более медленный рост. [3] Подкрепление не создает идеального стандарта выигрышей; алгоритм будет делать случайные неопределенные выводы каждый раз. После j -го раунда корреляция почти идеальной игры выполняется:

1 − Д Д − Д ( дж + 2 ) ∑ я = 0 дж Д ( дж я + 1 ) В я {\displaystyle {1-D \over DD^{(j+2)}}\sum _{i=0}^{j}D^{(ji+1)}V_{i}}

Где V i — результат (+1 — победа, 0 — ничья, -1 — поражение), а D — коэффициент распада (среднее значение прошлых значений побед и поражений). Ниже M n — множитель для n -го раунда игры. [4]

ИсходУкрепление
Выиграл Р н = М н − μ + 1 {\displaystyle R_{n}=M_{n}^{-\mu +1}}
Рисовать Р н = М н − μ {\displaystyle R_{n}=M_{n}^{-\mu }}
Потерянный Р н = М н − μ − 1 {\displaystyle R_{n}=M_{n}^{-\mu -1}}

Наследие

MENACE Дональда Мичи доказал, что компьютер может учиться на неудачах и успехах, чтобы стать хорошим в выполнении задачи. [17] Он использовал то, что стало основными принципами в области машинного обучения до того, как они были должным образом теоретически обоснованы. Например, сочетание того, как MENACE начинается с равного количества типов бусин в каждом спичечном коробке, и того, как они затем выбираются случайным образом, создает поведение обучения, похожее на инициализацию веса в современных искусственных нейронных сетях . [20] В 1968 году Дональд Мичи и Р. А. Чемберс создали еще один алгоритм на основе BOXES под названием GLEE (Game Learning Expectimaxing Engine), который должен был научиться балансировать шест на тележке. [21]

После громкого приема MENACE, Мичи был приглашен в Управление военно-морских исследований США, где ему было поручено создать программу, работающую на BOXES, для компьютера IBM для использования в Стэнфордском университете . [22] Мичи создал программу моделирования MENACE на компьютере Pegasus 2 с помощью Д. Мартина. [4] В последние годы было несколько воссозданий MENACE, как в его первоначальной физической форме, так и в виде компьютерной программы. [12] Его алгоритм позже был объединен в алгоритм Q-Learning Кристофера Уоткина. [23] Хотя и не как функциональный компьютер, в демонстрационных примерах MENACE использовался в качестве учебного пособия для различных классов нейронных сетей, [24] [25] [26] включая публичную демонстрацию исследователя из Лондонского университетского колледжа Мэтью Скроггса. [27] [28] Копия MENACE, созданная Скроггсом, была представлена ​​на рождественских лекциях в Королевском институте в 2019 году , [29] [30] и в эпизоде ​​QI XL 2023 года . [31]

УГРОЗА упоминается в рассказе Фреда Саберхагена 1963 года «Без мыслей» и в романе Томаса Дж. Райана 1977 года «Юность П-1» . [32] В своей книге 2023 года «Будущее » автор Наоми Олдерман включает вымышленную лекцию с подробным обзором УГРОЗЫ.

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

Ссылки

  1. ↑ Боден, Маргарет (15 августа 2007 г.). «Дональд Мичи (1923–2007)». Nature . 448 (7155): 765. doi :10.1038/448765a. ISSN  1476-4687. PMID  17700692. S2CID  5239830.
  2. ^ ab Wright, Matt (31 марта 2020 г.). «Дональд Мичи: пионер ИИ, который тестировал свою компьютерную программу с помощью спичечного коробка и нескольких бусинок». Scroll.in . Архивировано из оригинала 20 октября 2020 г. . Получено 18 октября 2020 г. .
  3. ^ abcd Child, Oliver (13 марта 2016 г.). «Menace: the Machine Educable Noughts And Crosses Engine». Chalkdust . Архивировано из оригинала 12 мая 2020 г. . Получено 17 мая 2020 г. .
  4. ^ abcdefghijk Мичи, Дональд. "Эксперименты по механизации игрового обучения. Часть 1. Характеристика модели и ее параметров" (PDF) . Архивировано (PDF) из оригинала 21 ноября 2019 г. . Получено 1 июня 2020 г. .
  5. ^ "Daily Telegraph некролог Дональда Мичи". The Daily Telegraph . 9 июля 2007 г. Архивировано из оригинала 11 июня 2020 г. Получено 25 мая 2021 г.
  6. ^ ab Дональд, Мичи (1968). ЯЩИКИ: Эксперимент по адаптивному управлению. Эдинбургский университет. стр. 137. CiteSeerX 10.1.1.474.2430 . Архивировано из оригинала 26 июня 2020 . Получено 31 июля 2020 . 
  7. ^ ab Muggleton, Stephen (10 июля 2007 г.). «Некролог Дональда Мичи, статья в The Guardian от 2007 г.» The Guardian . Архивировано из оригинала 1 октября 2020 г. . Получено 22 мая 2021 г. .
  8. ^ ab Хардингем, Саманта; Фрейзер, Джон; Джонс, Эмма Летиция (2012). «Джон Фрейзер в разговоре с Самантой Хардингем». AA Files (64): 69–77. ISSN  0261-6823. JSTOR  41762307.
  9. ^ Уайли, Каспар (5 октября 2018 г.). «Как 300 спичечных коробков научились играть в крестики-нолики с помощью MENACE». Open Data Science . Архивировано из оригинала 15 мая 2021 г. . Получено 15 мая 2021 г. .
  10. ^ ab The Science Book, второе издание, Dorling Kindersley Ltd., 2015, стр. 288
  11. ^ abcd Гарднер, Мартин (1962). «Математические игры». Scientific American . 206 (3): 138–154. Bibcode : 1962SciAm.206c.138G. doi : 10.1038/scientificamerican0362-138. JSTOR  24937263.
  12. ^ abcd "Matchbox Educable Noughts And Crosses Engine In Empirical Modelling" (PDF) . University of Warwick . Получено 22 мая 2021 г. .
  13. ^ Де Рэдт, Люк. «Революция машинного обучения в ИИ». Архивировано из оригинала 12 июня 2020 г.
  14. ^ Рассел, Дэвид (2012). Отрывок из «Методологии BOXES». (Глава 2. Метафора игры) . Лондон: Springer Professional. ISBN 978-1849965279.
  15. ^ "Угроза: Машинно-обучаемая игра в крестики-нолики". 13 марта 2016 г.
  16. ^ Мичи, Дональд (ноябрь 1963 г.). «Эксперименты по механизации игрового обучения. Часть I: Характеристика модели и ее параметров». The Computer Journal . 6 (3): 232–236. doi :10.1093/comjnl/6.3.232 . Получено 28 августа 2024 г. .
  17. ^ abc "MENACE 2, искусственный интеллект из деревянных ящиков и цветных бусин". 12 апреля 2016 г. Архивировано из оригинала 12 июля 2020 г. Получено 22 мая 2021 г.
  18. ^ ab Cappiell, Emily (30 ноября 2020 г.). «Как выиграть в крестики-нолики: стратегии, которые вам нужно освоить». Reader's Digest . Архивировано из оригинала 22 января 2021 г. Получено 6 февраля 2021 г.
  19. ^ ab Метод проб и ошибок, Мичи Дональд, Penguin Science Surveys 1961 Том 2
  20. ^ Ям, Джим YF; Чоу, Томми WS (1 января 2000 г.). «Метод инициализации веса для повышения скорости обучения в нейронной сети прямого распространения». Neurocomputing . 30 (1): 219–232. doi :10.1016/S0925-2312(99)00127-7. ISSN  0925-2312.
  21. ^ Саттон, Ричард С.; Барто, Эндрю Г. (2018). Обучение с подкреплением: Введение. MIT Press. стр. 753. ISBN 978-0262039246.
  22. ^ "Профессор Дональд Мичи". The Daily Telegraph . 8 июля 2007 г. ISSN  0307-1235. Архивировано из оригинала 11 июня 2020 г. Получено 11 июня 2020 г.
  23. ^ Скаруффи, Пьеро (2014). Интеллект не является искусственным — почему Сингулярность не наступит в ближайшее время и другие размышления о постчеловеческом состоянии и будущем интеллекта. Omniware. стр. 27. ISBN 978-0976553199.
  24. ^ Чжао, Ибо (1 декабря 2013 г.). «Машинно-обучаемый двигатель на крестиках и ноликах в моделировании». Университет Уорика. Архивировано из оригинала 11 июня 2020 г. Получено 22 мая 2021 г.
  25. ^ "AI Topics.. Стратегия крестиков-ноликов в вычислительном мышлении, Введение, УГРОЗА". Архивировано из оригинала 8 февраля 2021 г. Получено 22 мая 2021 г.
  26. ^ Уте Шмид – «Интерактивное обучение с взаимными объяснениями» (Как люди и системы машинного обучения могут извлекать пользу друг из друга) – Университет Бамберга, Германия Ссылка
  27. ^ Скроггс, Мэтью (3 июля 2017 г.). «Создание машины УГРОЗЫ», Мэтью Скроггс, Университетский колледж Лондона (Youtube).
  28. ^ «Вдохновение следующего поколения компьютерных ученых | King's Worcester». King's Worcester . 11 ноября 2019 г. Архивировано из оригинала 12 июня 2020 г. Получено 12 июня 2020 г.
  29. ^ Скроггс, Мэтью (27 декабря 2019 г.). «Визуализация обучения MENACE». mscroggs.co.uk . Архивировано из оригинала 11 июля 2020 г. . Получено 30 июля 2020 г. .
  30. ^ @rsi_science (27 декабря 2019 г.). «Создатель машины-угрозы выступил со своими 304 спичечными коробками, чтобы объяснить, как он ее сделал» ( Твит ) . Получено 14 октября 2020 г. – через Twitter .
  31. ^ "QI XL Series T, Ticks Tax Toes". BBC . 6 января 2023 г. Получено 4 февраля 2023 г.
  32. ^ Скроггс, Мэтью (16 декабря 2018 г.). «УГРОЗА в художественной литературе». mscroggs.co.uk . Архивировано из оригинала 11 июля 2020 г. . Получено 18 марта 2020 г. .

Источники

  • Мичи, Д.; Чемберс, Р.А. (1968), «BOXES: эксперимент по адаптивному управлению», Machine Intelligence , Эдинбург, Великобритания: Oliver and Boyd, S2CID  18229198 – через Semantic Scholar, Мичи и статья Р. А. Чемберса о влиянии ЯЩИКОВ и УГРОЗЫ на ИИ.
  • Рассел, Дэвид В. (2012), Методология BOXES: Динамическое управление черным ящиком , Springer London, ISBN 978-1849965286, книга об алгоритме «Ящики», используемом MENACE.
  • Онлайн-симуляция MENACE
Взято с "https://en.wikipedia.org/w/index.php?title=Matchbox_Educable_Noughts_and_Crosses_Engine&oldid=1242708397"