Это хорошая статья. Для получения дополнительной информации нажмите здесь.
Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

MENACE отдых
Воссоздание MENACE, созданное Мэтью Скроггсом.

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

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

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

Происхождение [ править ]

Дональд Мичи учит
Дональд Мичи обучает группу студентов в Институте Тьюринга

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

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

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

Состав [ править ]

MENACE был сделан из 304 спичечных коробок, склеенных вместе, как у комода. [12] На каждой коробке был кодовый номер, который был введен в таблицу. На этой диаграмме были рисунки игровых сеток в крестики-нолики с различными конфигурациями крестиков , нулей и пустых квадратов [6], соответствующих всем возможным перестановкам, через которые игра могла проходить по мере развития. [10] [13] После удаления повторяющихся расположений (те, которые были просто вращениями или зеркальными отображениями других конфигураций), MENACE использовал 304 перестановки в своей таблице и, следовательно, столько спичечных коробок. [14]

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

Операция [ править ]

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

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

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

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

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

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

При игре против игрока, использующего оптимальную стратегию, шансы на ничью возрастают до 100%. В официальном турнире Дональда Мичи против MENACE (1961) [6] он использовал оптимальную стратегию, и он и компьютер начали последовательно рисовать после двадцати игр. Турнир Мичи [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 выдает различную тенденцию на диаграммах разброса выигрышей. [6] Использование случайного хода игрока-человека приводит к почти идеальной положительной тенденции. Использование оптимальной стратегии дает немного более медленный рост. [5] Подкрепление не создает идеального стандарта побед; алгоритм будет каждый раз делать случайные неопределенные выводы. После j- го начинается корреляция почти идеального люфта:

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

ИсходАрмирование
Выиграл
Рисовать
Потерял

Наследие [ править ]

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

После громкого приема MENACE, Мичи был приглашен в Управление военно-морских исследований США, где ему было поручено создать программу «Ящики» для компьютера IBM для использования в Стэнфордском университете . [22] Мичи с помощью Д. Мартина создала программу моделирования MENACE на компьютере Pegasus 2. [6] В последние годы MENACE было многократно воссоздано, как в его первоначальной физической форме, так и в виде компьютерной программы. [14] Его алгоритм позже был преобразован в алгоритм Кристофера Уоткина Q-Learning. [23]Хотя это и не функциональный компьютер, в демонстрационных примерах, MENACE использовался в качестве учебного пособия для различных классов нейронных сетей [24] [25] [26], включая широко разрекламированную демонстрацию, проведенную кембриджским исследователем Мэтью Скроггсом. [27] [28] Копия MENACE, построенная Скроггсом, была показана на Рождественских лекциях Королевского института в 2019 году . [29] [30]

См. Также [ править ]

  • Hexapawn

Ссылки [ править ]

  1. ^ "Компьютерные пионеры - Дональд Мичи" . history.computer.org . Проверено 19 июля 2020 .
  2. ^ Лекции Исследовательской группы по культурной информатике
  3. ^ Райт, Мэтт. «Дональд Мичи: пионер искусственного интеллекта, который протестировал свою компьютерную программу с помощью спичечного коробки и бусинок» . Scroll.in . Проверено 18 октября 2020 года .
  4. ^ "Доктор Дональд Мичи" . Общество истории информационных технологий . 21 декабря 2015 . Проверено 18 октября 2020 года .
  5. ^ a b c d "Угроза: Машинно-обучающая машина" крестики-нолики " . Мел . 13 марта 2016 . Дата обращения 17 мая 2020 .
  6. ^ a b c d e f g h i j "Эксперименты по механизации игрового обучения. Часть 1. Характеристика модели и ее параметров" (PDF) . Дата обращения 1 июня 2020 .
  7. ^ "Дейли Телеграф некролог Дональду Мичи" . Дейли телеграф . 9 июля 2007 г.
  8. ^ а б Дональд, Мичи. КОРОБКИ: эксперимент по адаптивному управлению . Эдинбургский университет. п. 137. CiteSeerX 10.1.1.474.2430 . 
  9. ^ a b Muggleton, Стивен (10 июля 2007 г.). «Некролог Дональда Мичи, статья в The Guardian от 2007 года» . Хранитель .
  10. ^ а б «История нейронных сетей и ИИ: Часть II» . Наука открытых данных . 23 мая 2018 . Проверено 19 сентября 2020 года .
  11. ^ a b Хардингем, Саманта; Фрейзер, Джон; Джонс, Эмма Летиция (2012). «Джон Фрейзер в разговоре с Самантой Хардингэм» . Файлы AA (64): 69–77. ISSN 0261-6823 . 
  12. ^ a b Научная книга, второе издание, Dorling Kindersley Ltd., 2015, стр. 288
  13. ^ a b c d Гарднер, Мартин (1962). «Математические игры». Scientific American . 206 (3): 138–154. Bibcode : 1962SciAm.206c.138G . DOI : 10.1038 / Scientificamerican0362-138 . JSTOR 24937263 . 
  14. ^ a b c d Спичечный коробок обучающий механизм крестиков и ноликов в эмпирическом моделировании
  15. ^ core.ac.uk - Революция машинного обучения в ИИ , Люк Де Рэдт Линк
  16. ^ Рассел, Дэвид (2012). Springer Professional - выдержка из «Методологии BOXES». (Глава 2. Метафора игры) . Лондон: Springer London. ISBN 9781849965279.
  17. ^ a b c «MENACE 2, искусственный интеллект, сделанный из деревянных ящиков и цветных бус» . 12 апреля 2016 г.
  18. ^ a b Каппьелл, Эмили (30 ноября 2020 г.). «Как выиграть крестики-нолики: стратегии, которые вам нужно освоить» . Ридерз Дайджест . Проверено 6 февраля 2021 года .
  19. ^ a b Метод проб и ошибок, Мичи Дональд, Penguin Science Surveys 1961 Vol 2
  20. ^ Yam, Джим YF; Чоу, Томми WS (1 января 2000 г.). «Метод инициализации веса для повышения скорости обучения в нейронной сети с прямой связью» . Нейрокомпьютеры . 30 (1): 219–232. DOI : 10.1016 / S0925-2312 (99) 00127-7 . ISSN 0925-2312 . 
  21. ^ Саттон, Ричард С .; Барто, Эндрю Г. (13 ноября 2018 г.). Обучение с подкреплением: Введение . MIT Press. п. 753. ISBN. 978-0-262-03924-6.
  22. ^ "Профессор Дональд Мичи" . Дейли телеграф . 8 июля 2007 г. ISSN 0307-1235 . Проверено 11 июня 2020 . 
  23. ^ Скаруффи, Пьеро (2016). Интеллект не является искусственным - почему сингулярность не наступит в ближайшее время и другие размышления о постчеловеческих условиях и будущем интеллекта. п. 27. ISBN 978-0-9765531-9-9.
  24. ↑ Чжао, Ибо (1 декабря 2013 г.). "Машинно-обучаемый двигатель на крестиках-ноликах в моделировании" . Уорикский университет.
  25. ^ "Темы AI .. Стратегия крестики-нолики в вычислительном мышлении, введение, MENACE" .
  26. ^ Уте Шмид - «Интерактивное обучение с взаимными объяснениями» (Как люди и системы машинного обучения могут получать прибыль друг от друга) - Бамбергский университет, Германия Ссылка
  27. ^ Scroggs, Мэтью (3 июля 2017). «Создание машины MENACE», Мэтью Скроггс, Университетский колледж Лондона (Youtube).
  28. ^ «Вдохновляя следующее поколение компьютерных ученых | King's Worcester» . Кингс-Вустер . 11 ноября 2019 . Проверено 12 июня 2020 .
  29. ^ Scroggs, Мэтью (27 декабря 2019). «Визуализация обучения MENACE» . mscroggs.co.uk .
  30. ^ @rsi_science (27 декабря 2019 г.). «Создатель Menace Machine выложил свои 304 спичечных коробок, чтобы объяснить, как он это сделал» (твит) . Проверено 14 октября 2020 г. - через Twitter .

Источники [ править ]

  • Методология BOXES , книга об алгоритме "Boxes", используемом MENACE.
  • КОРОБКИ: эксперимент в адаптивном управлении , статья Мичи и Р.А. Чемберса о значениях ИИ для BOXES и MENACE.

Внешние ссылки [ править ]

  • Онлайн-симуляция MENACE