Обучаемый двигатель со спичечными коробками и крестиками
Двигатель «Обучаемые крестики-нолики и крестики из спичечных коробков» (иногда называемый « Машинный механизм обучения крестиков-ноликов» или «MENACE» ) представлял собой механический компьютер , сделанный из 304 спичечных коробков , разработанный и построенный искусственного интеллекта исследователем Дональдом Мичи в 1961 году. Он был разработан для игры с людьми-противниками в играх крестики-нолики (крестики-нолики), возвращая ход для любого заданного состояния игры и совершенствуя свою стратегию посредством обучения с подкреплением .
У Мичи не было под рукой компьютера, поэтому он обошёл это ограничение, собрав его из спичечных коробков. Каждый из спичечных коробков, использованных Мичи, представлял собой единственную возможную раскладку сетки с крестиками и ноликами. Когда компьютер впервые играл, он случайным образом выбирал ходы в зависимости от текущей раскладки. По мере того, как он играл больше игр, посредством цикла подкрепления он дисквалифицировал стратегии, которые приводили к проигрышу игр, и дополнял стратегии, которые приводили к победам. Мичи провел турнир против MENACE в 1961 году, экспериментируя с разными дебютами.
После первого турнира MENACE против Мичи компания продемонстрировала успешную стратегию искусственного интеллекта. Эссе Мичи об инициализации веса MENACE и алгоритме BOXES, используемом MENACE, стали популярными в области компьютерных исследований. Мичи был удостоен награды за вклад в исследования в области машинного обучения, и ему дважды было поручено запрограммировать симуляцию УГРОЗЫ на реальном компьютере.
Источник
[ редактировать ]
Дональд Мичи (1923–2007) был в команде, расшифровывающей немецкий код тунца во время Второй мировой войны . [1] Пятнадцать лет спустя он захотел еще больше продемонстрировать свои математические и вычислительные способности с помощью ранней сверточной нейронной сети . Поскольку для таких целей не было компьютерного оборудования, [2] а у Мичи не было под рукой компьютера, [2] он решил продемонстрировать искусственный интеллект в более эзотерическом формате и сконструировал функциональный механический компьютер из спичечных коробков и бус. [3] [4]
MENACE была создана в результате пари с коллегой-компьютерщиком, который постулировал, что такая машина невозможна. [5] Мичи взяла на себя задачу собрать и определить каждый спичечный коробок как «забавный проект», который позже превратился в демонстрационный инструмент. [6] Мичи завершил свое эссе об УГРОЗЕ в 1963 году. [4] «Эксперименты по механизации игрового обучения», а также его эссе об алгоритме BOXES, написанное совместно с Р.А. Чемберсом. [6] и создал исследовательский отдел искусственного интеллекта на Хоуп-Парк-сквер в Эдинбурге , Шотландия . [7]
УГРОЗА изучается, играя в возрастающие числа крестиков и ноликов. Каждый раз это исключало бы проигрышную стратегию, когда игрок-человек конфисковывал бусинки, соответствующие каждому ходу. [4] Он усилил выигрышные стратегии, сделав ходы более вероятными и предоставив дополнительные бусинки. [8] Это была одна из самых ранних версий « Петли подкрепления» , схематического алгоритма зацикливания алгоритма, отбрасывающего неудачные стратегии до тех пор, пока не останутся только выигрышные. [4] Эта модель начинается как совершенно случайная и постепенно обучается. [9]
Состав
[ редактировать ]УГРОЗА была сделана из 304 спичечных коробков, склеенных вместе в виде комода. [10] У каждой коробки был кодовый номер, который был введен в карту. На этой диаграмме были рисунки сеток для игры в крестики-нолики с различными конфигурациями X , O и пустыми квадратами. [4] соответствующий всем возможным перестановкам, через которые может пройти игра по ходу ее развития. [11] После удаления повторяющихся компоновок (которые представляли собой просто повороты или зеркальные отображения других конфигураций), MENACE использовала в своей диаграмме 304 перестановки и, следовательно, столько же спичечных коробков. [12]
В каждом лотке из спичечных коробков лежала коллекция цветных бусинок. [13] Каждый цвет представлял собой ход по клетке игровой сетки, поэтому спичечные коробки с расположением, в котором позиции в сетке уже заняты, не будут иметь бусинок для этой позиции. Кроме того, в передней части лотка лежали две дополнительные карточки V-образной формы. [10] острие буквы «V» должно быть направлено на переднюю часть спичечного коробка. [11] Мичи и его команда по искусственному интеллекту назвали алгоритм MENACE «Коробками». [7] после устройства, используемого для машины. Первый этап «Коробки» состоял из пяти этапов, каждый из которых устанавливал определение и прецедент правил алгоритма применительно к игре. [14]
Операция
[ редактировать ]
УГРОЗА разыгрывалась первой, как O, поскольку все спичечные коробки представляли собой перестановки, относящиеся только к игроку «X». [12] [17] Чтобы получить выбор хода MENACE, противник или оператор находили спичечный коробок, соответствующий текущему состоянию игры, или его вращение или зеркальное отображение. Например, в начале игры это будет спичечный коробок для пустой сетки. Лоток можно было снять и слегка встряхнуть, чтобы переместить бусинки. [4] Затем шарик, который свернулся в точку в форме буквы «V» в передней части подноса, был ходом, который решила сделать УГРОЗА. [4] Затем его цвет использовался в качестве позиции для игры, и после учета любых необходимых вращений или переворотов в зависимости от отношения выбранной конфигурации спичечного коробка к текущей сетке, буква «О» помещалась на этот квадрат. Затем игрок выполнял свой ход, определялось новое состояние, выбирался новый ход и так далее, пока игра не была закончена. [12]
Когда игра закончилась, игрок-человек наблюдал за ее исходом. Во время игры лоток каждого спичечного коробка, который использовался для хода УГРОЗЫ, возвращался в него приоткрытым, а использованная бусинка оставлялась в стороне, так что выбор ходов УГРОЗЫ и игровые состояния, к которым они принадлежали, были записаны. Мичи описал свою систему подкрепления с помощью «наград» и «наказания». По завершении игры, если бы MENACE выиграла, она получила бы «награду» за свою победу. Снятые бусины показывали последовательность выигрышных ходов. [17] Они были возвращены на соответствующие лотки, их легко идентифицировать, поскольку они были слегка открыты, а также три бонусные бусины того же цвета. [11] Таким образом, в будущих играх УГРОЗА с большей вероятностью будет повторять эти выигрышные ходы, усиливая выигрышные стратегии. В случае проигрыша удаленные бусинки не возвращались, «наказывая» УГРОЗУ, а это означает, что в будущем будет менее вероятно и, в конечном итоге, неспособно, если этот цвет бусинок исчезнет, повторить ходы, которые приводят к проигрышу. [3] [8] Если игра была ничьей, в каждую коробку добавлялась по одной дополнительной бусине. [11]
Результаты на практике
[ редактировать ]Оптимальная стратегия
[ редактировать ]
Крестики-нолики имеют известную оптимальную стратегию. [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» |
|---|---|---|
| Вариант 0 | 0 | 0 |
| Вариант 1 | 20 | -5 |
| Вариант 0 | 60 | 5 |
| Вариант 2 | 70 | 10 |
| Вариант 3 | 110 | 20 |
| Вариант 4 | 135 | 25 |
| Вариант 1 | 190 | 100 |
| Вариант 0 | 210 | 120 |
Корреляция
[ редактировать ]
В зависимости от стратегии, используемой игроком-человеком, MENACE дает различную тенденцию на графиках разброса выигрышей. [4] Использование случайного хода игрока-человека приводит к почти идеальной положительной тенденции. Игра по оптимальной стратегии дает немного более медленный рост. [3] Подкрепление не создает идеальный стандарт побед; алгоритм каждый раз будет делать случайные неопределенные выводы. После j -го раунда соотношение почти идеальной игры выглядит следующим образом:
Где V i — результат (+1 — победа, 0 — ничья и -1 — проигрыш), а D — коэффициент затухания (среднее значение прошлых значений выигрышей и проигрышей). Ниже M n — множитель для n -го раунда игры. [4]
| Исход | Армирование |
|---|---|
| Выиграл | |
| Рисовать | |
| Потерянный |
Наследие
[ редактировать ]«УГРОЗА» Дональда Мичи доказала, что компьютер может учиться на неудачах и успехах, чтобы хорошо справляться с задачей. [17] Он использовал то, что впоследствии стало ключевыми принципами в области машинного обучения, прежде чем они были должным образом теоретически обоснованы. Например, сочетание того, как УГРОЗА начинается с одинакового количества типов бусин в каждом спичечном коробке, и того, как они затем выбираются случайным образом, создает поведение обучения, подобное инициализации веса в современных искусственных нейронных сетях . [20] В 1968 году Дональд Мичи и Р.А. Чемберс создали еще один алгоритм на основе BOXES под названием GLEE (Game Learning Expectimaxing Engine), который должен был научиться балансировать шест на тележке. [21]
После оглушительного приема MENACE Мичи был приглашен в Управление военно-морских исследований США, где ему было поручено создать программу, работающую на BOXES, для компьютера IBM для использования в Стэнфордском университете . [22] Мичи создала программу моделирования УГРОЗЫ на компьютере Pegasus 2 с помощью Д. Мартина. [4] В последние годы было множество воссозданий УГРОЗЫ, как в исходной физической форме, так и в виде компьютерной программы. [12] Позже его алгоритм был объединен с алгоритмом Q-Learning Кристофера Уоткина. [23] Хотя MENACE не является функциональным компьютером, в демонстрационных примерах он использовался в качестве учебного пособия для различных классов нейронных сетей. [24] [25] [26] включая публичную демонстрацию исследователя Университетского колледжа Лондона Мэтью Скроггса. [27] [28] Копия MENACE, созданная Скроггсом, была представлена на рождественских лекциях Королевского института в 2019 году . [29] [30] и в эпизоде QI XL 2023 года . [31]
УГРОЗА в популярной культуре
[ редактировать ]УГРОЗА упоминается в рассказе Фреда Саберхагена 1963 года «Без мысли» и в романе Томаса Райана 1977 года «Подросток П-1» . [32] В свою книгу «Будущее» 2023 года автор Наоми Олдерман включает вымышленную лекцию с подробным обзором УГРОЗЫ.
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Боден, Маргарет (15 августа 2007 г.). «Дональд Мичи (1923–2007)» . Природа . 448 (7155): 765. дои : 10.1038/448765a . ISSN 1476-4687 . ПМИД 17700692 . S2CID 5239830 .
- ^ Jump up to: а б Райт, Мэтт (31 марта 2020 г.). «Дональд Мичи: пионер искусственного интеллекта, протестировавший свою компьютерную программу с помощью спичечного коробка и бусинок» . Прокрутка.в . Архивировано из оригинала 20 октября 2020 года . Проверено 18 октября 2020 г.
- ^ Jump up to: а б с д Чайлд, Оливер (13 марта 2016 г.). «Угроза: машинно-обучаемый двигатель крестиков-ноликов» . Меловая пыль . Архивировано из оригинала 12 мая 2020 года . Проверено 17 мая 2020 г.
- ^ Jump up to: а б с д и ж г час я дж к Мичи, Дональд. «Эксперименты по механизации игрового обучения. Часть 1. Характеристика модели и ее параметров» (PDF) . Архивировано (PDF) из оригинала 21 ноября 2019 года . Проверено 1 июня 2020 г.
- ^ «Некролог Daily Telegraph Дональду Мичи» . «Дейли телеграф» . 9 июля 2007 г. Архивировано из оригинала 11 июня 2020 г. . Проверено 25 мая 2021 г.
- ^ Jump up to: а б Дональд, Мичи (1968). КОРОБКИ: Эксперимент по адаптивному управлению . Эдинбургский университет. п. 137. CiteSeerX 10.1.1.474.2430 . Архивировано из оригинала 26 июня 2020 года . Проверено 31 июля 2020 г.
- ^ Jump up to: а б Магглтон, Стивен (10 июля 2007 г.). «Некролог Дональда Мичи, статья в The Guardian за 2007 год» . Хранитель . Архивировано из оригинала 1 октября 2020 года . Проверено 22 мая 2021 г.
- ^ Jump up to: а б Хардингем, Саманта; Фрейзер, Джон; Джонс, Эмма Летиция (2012). «Джон Фрейзер в разговоре с Самантой Хардингем» . Файлы АА (64): 69–77. ISSN 0261-6823 . JSTOR 41762307 .
- ^ Уайли, Каспар (5 октября 2018 г.). «Как 300 спичечных коробков научились играть в крестики-нолики с помощью УГРОЗЫ» . Наука открытых данных . Архивировано из оригинала 15 мая 2021 года . Проверено 15 мая 2021 г.
- ^ Jump up to: а б Научная книга, второе издание, Dorling Kindersley Ltd., 2015, стр. 288
- ^ Jump up to: а б с д Гарднер, Мартин (1962). «Математические игры». Научный американец . 206 (3): 138–154. Бибкод : 1962SciAm.206c.138G . doi : 10.1038/scientificamerican0362-138 . JSTOR 24937263 .
- ^ Jump up to: а б с д «Обучаемый двигатель «нолики и крестики» из спичечных коробков в эмпирическом моделировании» (PDF) . Университет Уорика . Проверено 22 мая 2021 г.
- ^ Де Рэдт, Люк. « Революция машинного обучения в искусственном интеллекте ». Архивировано из оригинала 12 июня 2020 года.
- ^ Рассел, Дэвид (2012). Отрывок из «Методологии BOXES». (Глава 2. Метафора игры) . Лондон: Springer Professional. ISBN 978-1849965279 .
- ^ «Угроза: машинно-обучаемый двигатель крестиков-ноликов» . 13 марта 2016 г.
- ^ http://people.csail.mit.edu/brooks/idocs/matchbox.pdf
- ^ Jump up to: а б с «УГРОЗА 2, искусственный интеллект из деревянных ящиков и цветных бус» . 12 апреля 2016 г. Архивировано из оригинала 12 июля 2020 г. . Проверено 22 мая 2021 г.
- ^ Jump up to: а б Кэппиелл, Эмили (30 ноября 2020 г.). «Как выиграть в крестики-нолики: стратегии, которые вам нужно освоить» . Читательский дайджест . Архивировано из оригинала 22 января 2021 года . Проверено 6 февраля 2021 г.
- ^ Jump up to: а б Метод проб и ошибок, Мичи Дональд, Penguin Science Surveys, 1961, том 2
- ^ Ям, Джим Ю.Ф.; Чоу, Томми WS (1 января 2000 г.). «Метод инициализации веса для повышения скорости обучения в нейронной сети прямого распространения» . Нейрокомпьютинг . 30 (1): 219–232. дои : 10.1016/S0925-2312(99)00127-7 . ISSN 0925-2312 .
- ^ Саттон, Ричард С.; Барто, Эндрю Г. (2018). Обучение с подкреплением: Введение . МТИ Пресс. п. 753. ИСБН 978-0262039246 .
- ^ «Профессор Дональд Мичи» . «Дейли телеграф» . 8 июля 2007 г. ISSN 0307-1235 . Архивировано из оригинала 11 июня 2020 года . Проверено 11 июня 2020 г.
- ^ Скаруффи, Пьеро (2014). Интеллект не является искусственным – почему сингулярность не наступит в ближайшее время и другие размышления о постчеловеческом состоянии и будущем интеллекта . Всестороннее ПО. п. 27. ISBN 978-0976553199 .
- ^ Чжао, Ибо (1 декабря 2013 г.). «Машинообучаемая машина на крестиках и нулях в моделировании» . Университет Уорика. Архивировано из оригинала 11 июня 2020 года . Проверено 22 мая 2021 г.
- ^ «Темы искусственного интеллекта. Стратегия крестики-нолики в вычислительном мышлении, Введение, УГРОЗА» . Архивировано из оригинала 8 февраля 2021 года . Проверено 22 мая 2021 г.
- ^ Уте Шмид - «Интерактивное обучение с взаимными объяснениями» (Как люди и системы машинного обучения могут извлекать выгоду друг из друга) - Университет Бамберга, Германия Ссылка
- ^ Скроггс, Мэтью (3 июля 2017 г.). «Создание машины УГРОЗЫ», Мэтью Скроггс, Университетский колледж Лондона (Youtube).
- ^ «Вдохновляя новое поколение ученых-компьютерщиков | Кингс Вустер» . Королевский Вустер . 11 ноября 2019 года. Архивировано из оригинала 12 июня 2020 года . Проверено 12 июня 2020 г.
- ^ Скроггс, Мэтью (27 декабря 2019 г.). «Визуализация обучения MENACE» . mscroggs.co.uk . Архивировано из оригинала 11 июля 2020 года . Проверено 30 июля 2020 г.
- ^ @rsi_science (27 декабря 2019 г.). «Создатель машины-угрозы представил свои 304 спичечных коробка, чтобы объяснить, как он это сделал» ( твит ) . Проверено 14 октября 2020 г. - через Twitter .
- ^ «QI XL Series T, тикающие пальцы ног» . Би-би-си . 6 января 2023 г. Проверено 4 февраля 2023 г.
- ^ Скроггс, Мэтью (16 декабря 2018 г.). «УГРОЗА в художественной литературе» . mscroggs.co.uk . Архивировано из оригинала 11 июля 2020 года . Проверено 18 марта 2020 г.
Источники
[ редактировать ]- Мичи, Д.; Чемберс, Р.А. (1968), «BOXES: An Experiment in Adaptive Control», Machine Intelligence , Эдинбург, Великобритания: Оливер и Бойд, S2CID 18229198 – через семантического ученого , Мичи и Р. Статья Чемберса о последствиях BOXES и R. УГРОЗА.
- Рассел, Дэвид В. (2012), Методология BOXES: динамическое управление черным ящиком , Springer London, ISBN 978-1849965286 , книга об алгоритме «Коробки», используемом MENACE.