Мартин Гарднер "Самообучающаяся машина из спичечных коробков"

Мартин Гарднер "Математические головоломки"

"На шахматной доске оставалось мало фигур, и даже мне, совсем не шахматисту, сразу стало ясно, что игра подходит к концу... Лицо его (Моксона) было мертвенно бледно, глаза сверкали как алмазы. Второго игрока я видел только со спины, но и этого было достаточно, чтобы у меня пропала всякая охота видеть его лицо".

Приведенный отрывок взят из классического рассказа Амброза Бирса "Хозяин Моксона". Изобретатель Моксон построил робота, играющего в шахматы. После того, как Моксон выиграл одну партию, робот задушил своего создателя.

В рассказе Бирса отражена все нарастающая тревога людей: неужели когда-нибудь машины выйдут из повиновения и начнут делать, что им заблагорассудится? Не думайте, что подобные опасения высказывают лишь те, кто не разбирается в вычислительных машинах. Норберт Винер перед своей смертью с ужасом ждал дня, когда важные правительственные решения будут приниматься машинами, запрограммированными с учетом последних достижений теории игр. Винер предостерегал, что машины могут вовлечь человечество в самоубийственную войну. Наибольшие опасения вызывают самообучающиеся машины (то есть машины, совершенствующиеся по мере накопления опыта), потому что их поведение становится непредсказуемым. Такие машины делают не то, что им приказывают, а то, чему они научились. Они довольно быстро достигают уровня, когда программист уже больше не может сказать, какие изменения произошли в схеме машины. Большинство самообучающихся машин обычно содержит так называемые "рандомизирующие устройства". Если действие такого устройства основано на случайном распаде радиоактивного образца, то поведение машины, даже в принципе непредсказуемо (так, во всяком случае, считает большинство физиков). Большая часть современных исследований направлена на совершенствование самообучающихся машин, "умеющих" играть в различные игры. Некоторые из этих работ строго засекречены: в них под "игрой" понимается война. Одной из первых самообучающихся машин была IBM 704. Программу для нее составил Артур Л. Сэмюел.

В 1959 году Сэмюел создал программу, которая позволяла машине не только правильно играть в шашки, но и улучшать стратегию игры, используя опыт, накопленный в предыдущих партиях. Вначале Самюел с легкостью обыгрывал машину, но IBM 704 не стала душить своего программиста, а вместо этого начала быстро совершенствоваться. Вскоре она достигла такого уровня, что с блеском выигрывала у Сэмюела все партии подряд! Насколько мне известно, существует несколько остроумных шахматных программ для обычных (несамообучающихся) машин.

Лет 10 назад советский гроссмейстер Михаил Ботвинник заявил, что придет день, когда машина научится играть не хуже гроссмейстера. "Это, конечно, чепуха", - отреагировал на выступление Ботвинника американский эксперт по шахматам Эдвард Ласкер. Но чепухой скорее следовало назвать замечание Ласкера. Играя в шахматы, машина имеет три огромных преимущества перед противником-человеком:
1) она никогда не "зевает";
2) может анализировать ходы значительно быстрее человека;
3) способна безгранично совершенствовать свое мастерство.
Поэтому есть все основания надеяться, что, сыграв несколько тысяч партий с шахматистами высокого класса, машина достигнет уровня гроссмейстера. Возможен и такой вариант: шахматная программа будет составлена так, что машина станет непрерывно и исступленно играть сама с собой. Благодаря своему быстродействию она за короткое время сможет накопить опыт, намного превосходящий опыт любого шахматиста-человека.

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

Счастливая идея создания простой и надежной самообучающейся машины из спичечных коробков принадлежит Дональду Мичи.

В статье "Метод проб и ошибок" Мичи описывает самообучающуюся машину для игры в крестики - нолики, которую можно собрать из трехсот спичечных коробков. Называется эта машина MENACE.

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

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

Чтобы узнать очередной ход машины, надо встряхнуть и перевернуть коробок, затем открыть его и посмотреть, какого цвета "вершинная" бусинка, то есть бусинка, закатившаяся в вершину картонного уголка коробка; "принявшие участие" в игре коробки остаются открытыми до конца партии. Если машина выигрывает, ее поощряют, добавляя в каждый открытый коробок по три бусинки того же цвета, что и "вершинная" бусинка. Если игра заканчивается вничью, в каждый коробок добавляют только по одной бусинке (того же цвета, что и "вершинная"). Если же машина проигрывает, ее ."наказывают", вынимая из каждого коробка бусинку, закатившуюся в вершину уголка. Такой метод кнута и пряника находит весьма близкие параллели в обучении животных и даже людей. Чем больше партий в крестики и нолики играет машина Мичи, тем лучше она "запоминает" выигрышные ходы и тем упорнее стремится избегать проигрышных. Это и означает, что она представляет собой хотя и очень простое, но все же самообучающееся устройство. Правда, в отличие от IBM 704, работающей по шахматной программе Сэмюела, наша "спичечная" машина не умеет анализировать сыгранные партии и разрабатывать новые "стратегические замыслы" в соответствии с накопленным опытом.

Первый двухдневный турнир между Мичи и его машиной состоял из 220 партий. Сначала Мичи все время наказывал свое детище за плохую игру, но после семнадцати партий машина начала ставить первый крестик только в угловую клетку, а после двадцатой партии заканчивать все игры вничью. В надежде заманить противника в ловушку Мичи начал делать самые бессмысленные ходы. Такая тактика оправдывала себя лишь до тех пор, пока машина не научилась справляться и с этими хитростями. Закончился матч сокрушительным поражением Мичи: он выбыл из турнира, проиграв восемь партий из десяти. Самообучающаяся машина из спичечных коробков стала гроссмейстером крестиков и ноликов!

Поскольку вряд-ли кто-нибудь из читателей возьмется за изготовление самообучающейся машины из трехсот спичечных коробков, я придумал игру попроще. Чтобы построить играющую в нее машину, достаточно взять всего лишь двадцать четыре коробка. Теория игры в шесть пешек (так я назвал свою игру) совершенно тривиальна, тем не менее я убедительно прошу читателя не проводить никакого анализа. Построив машину и постигнув все тонкости "шестипешия" в процессе обучения ее игре, вы получите гораздо больше удовольствия.

В шесть пешек играют на доске размером 3Х3 клетки. Каждый из игроков имеет по 3 пешки. Начальная позиция показана на рисунке. Вместо "настоящих" пешек с тем же успехом можно воспользоваться монетками двух различных достоинств или фишками. Ходы разрешается делать лишь двух типов: 1) пешка может передвинуться на одну клетку вперед, если эта клетка пуста;. 2) пешка может взять пешку другого цвета, стоящую справа или слева на соседней клетке и по диагонали, и остаться на освободившейся клетке.

Взятая пешка снимается с доски. Ходы пешек, как видно из этих правил, в основном совпадают с ходами пешек в обычных шахматах. Однако в отличие от шахмат нашим пешкам не разрешается делать двойной ход в начале партии, брать пешку противника на проходе и превращаться в какие-либо другие фигуры того же цвета. Партия считается выигранной в следующих трех случаях:
1) когда одну из пешек удается провести в третий ряд;
2) когда взяты все пешки противника;
3) когда противник не может сделать очередного хода.
Играющие делают ходы по очереди, передвигая каждый раз по одной пешке. Очевидно, что закончиться вничью игра не может; далеко не так очевидно, какой из игроков имеет преимущество: делающий второй ход (или тот, кто начинает игру.

Для изготовления машины САМА (САмообучающаяся Машина с Адаптацией) нужно взять двадцать четыре пустых спичечных коробка и много разноцветных бусинок. Вместо бусинок можно взять разноцветные леденцы или раскрашенные горошины. На каждый коробок наклейте рисунок одной из позиций, встречающихся; при игре в шесть пешек (они показаны на рисунке). В каждой партии робот должен делать ход вторым. Диаграммы, обозначенные цифрой 2, изображают две позиции, которые могут возникнуть перед вторым ходом. Делая первый ход, вы можете передвинуть либо среднюю пешку, либо одну из крайних. Мы будем рассматривать только те случаи, когда из двух крайних игру начинает левая пешка, потому что, начав игру правой пешкой, вы получите зеркально-симметричную последовательность ходов. Диаграммы, обозначенные цифрой 4, 'представляют собой одиннадцать позиций, с которыми может столкнуться ваш робот перед своим вторым (четвертым после начала игры) ходом. Цифрой 6 обозначены одиннадцать возможных позиций перед последним ходом робота (шестым после начала игры). (На рисунках изображены все возможные позиции, в том числе и зеркально-симметричные. Я это сделал просто для того, чтобы читателю было легче обращаться с машиной. В действительности же достаточно девятнадцати "коробков). В каждый коробок положите столько - бусинок, сколько стрелок на диаграмме. Каждой стрелке должна отвечать бусинка определенного цвета. Теперь робот готов к игре.

Каждая стрелка обозначает допустимый, то есть согласующийся с правилами игры, ход. На диаграммах изображены все допустимые ходы. Отсюда следует, что машина, во-первых, будет ходить только "по правилам", и, во-вторых, сможет сделать любой разрешенный ход. Однако никакой определенной стратегии у нашего робота нет и пока он еще ничего не умеет. Обучение происходит следующим образом. Сделав первый ход, вы берете коробок, на котором нарисована создавшаяся на доске позиция, встряхиваете его и, закрыв глаза, отодвигаете крышку. Вынув из коробка наугад одну бусинку, вы закрываете его, ставите на стол, а сверху кладете вынутую бусинку. Теперь откройте глаза, посмотрите, какого цвета бусинка, и, найдя на диаграмме соответствующую стрелку, сделайте указанный ею ход. После этого вы делаете свой очередной ход (предыдущий был ходом машины). Сделав его, повторите описанную процедуру. Так следует продолжать до тех пор, пока партия не закончится. Если выиграет робот, положите все вынутые бусинки на место и начните следующую партию. Если же робот проиграет, его надо - наказать. Заберите у него одну бусинку, соответствующую его последнему ходу. Все остальные бусинки положите на место и продолжайте курс обучения-начните следующую игру. Если последний коробок окажется пустым (так иногда бывает), это означает, что все ходы машины приводят к ее проигрышу и она отказывается играть дальше. В этом случае бусинку надо вынуть из предпоследнего коробка.

В первых пятидесяти партиях записывайте все победы и поражения робота, а потом составьте график. На рисунке показаны типичные результаты такого турнира. Из диаграммы видно, что, сыграв тридцать шесть партий (и проиграв из них одиннадцать), робот стал очень сильным противником. Система наказаний придумана специально для того, чтобы максимально сократить время обучения, однако это время существенно зависит от мастерства учителя. Машина учится играть тем быстрее, чем искуснее ее противник.

Можно придумать и другую систему обучения. Пусть, например, вам хочется, чтобы робот одерживал максимальное число побед в каждых двадцати пяти играх. Тогда лучше всего поощрять его (равно как и наказывать), добавляя в каждый коробок бусинки нужного цвета. При таком способе неправильные ходы ликвидируются несколько медленнее, но зато машина делает их все реже. Интересно было бы соорудить еще одну машину, которая вначале тоже не умеет играть, и обучить ее по второй системе. Этот робот можно назвать САМ (САмообучающаяся Машина). Увеличив число элементов-спичечных коробков-в той и в другой машине, их : можно было бы научить делать не только четные, но и нечетные ходы, и в частности первый ход. Затем можно .было бы устроить турнир из шестидесяти партий между машинами и посмотреть, какая из машин - САМ или САМА-одержит больше побед. Первый ход в каждой партии роботы делают по очереди. Аналогичные машины нетрудно придумать и для других игр.