Страницы истории. MENACE

Сейчас уже никого не удивишь тем, что искусственная нейронная сеть побеждает человека на широком множестве задач, в частности - в таких играх, как Го, шахматы, Дота, Старкрафт2 и даже покер. Однако, самообучающиеся машины появились задолго до современных нейросетевых архитектур.
Более того, одна из таких машин не содержала не только процессора, но и электроники вовсе. Речь идет о "MENACE" (Machine Educable Noughts And Crosses Engine), разработанной Дональдом Мичи в 1960г, состоящей из 304 спичечных коробков и обучающейся игре в крестики-нолики.

Машина была устроена следующим образом: каждый из 304 спичечных коробков соответствовал позиции на игровом поле. Для уменьшения количества используемых коробков, варианты, соответствующие поворотам или зеркальным отображениям одной и той же позиции соответствовали одному и тому же коробку. В коробках размещались разноцветные бусины, при этом цвет каждой из них кодировал позицию на игровом поле, в которой следовало разместить крестик (ну, или нолик, если игру начинал человек) - например, черная бусина соответствовала нижней правой клетке.

Игра с MENACE (и ее обучение) выглядела так: сделав свой ход, человек выбирал коробок, соответствующий текущему состоянию игрового поля, вытаскивал оттуда бусину наугад, и ставил в позицию, закодированную цветом бусины, крестик (или нолик!) за машину. Изначально количество бусин каждого цвета было равным, поэтому машина совершала случайные ходы и победить могла только из-за невнимательности оппонента.

Однако, самое интересное происходило после игры: в случае победы машины, в каждый из коробков, участвующих в этом матче добавлялось по три бусины того же цвета, что и выпавшие в процессе игры. В случае проигрыша одна бусина этого цвета забиралась из коробка. Ну и одна бусина добавлялась, если итогом игры была ничья.
Узнаете алгоритм? Ведь он (правда "на стероидах", совместно с современной сверточной нейронной сетью) был использован в первой версии алгоритма, победившего мирового чемпиона в Го - АльФаГо!

После большого количества сыгранных матчей, количество бусин разных цветов существенно отличалось, что делало одни ходы более вероятными, чем другие. Например, чтобы обучиться до уровня, эквивалентного идеальному алгоритму, спичесным коробкам с бусинами хватало всего около сотни матчей.

Посмотреть, как это выглядело на практике можно, например, тут: http://www.mscroggs.co.uk/menace/
А почитать статью автора 60-летней давности можно вот здесь: https://people.csail.mit.edu/brooks/idocs/matchbox.pdf

Источник: m.vk.com

Комментарии: