"Математические досуги" - 14

Мартин Гарднер "Математические досуги" - 14

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

      “На шахматной доске оставалось мало фигур, и даже мне, совсем не шахматисту, сразу стало ясно, что игра подходит к концу... Лицо его (Моксона) было мертвенно бледно, глаза сверкали как алмазы. Второго игрока я видел только со спины, но и этого было достаточно, чтобы у меня пропала всякая охота видеть его лицо”. (А. Бирс, Хозяин Моксона, сб. “Словарь Сатаны и другие рассказы”, М., изд-во “Художественная литература”, 1966)
      Приведенный отрывок взят из классического рассказа Амброза Бирса “Хозяин Моксона”. Изобретатель Мок-сон построил робота, играющего в шахматы. После того как Моксон выиграл одну партию, робот задушил своего создателя.
      В рассказе Бирса отражена все нарастающая тревога людей: неужели когда-нибудь машины выйдут из повиновения и начнут делать, что им заблагорассудится? Не думайте, что подобные опасения высказывают лишь те, кто не разбирается в вычислительных машинах. Норберт Винер перед своей смертью с ужасом ждал дня, когда важные правительственные решения будут приниматься машинами, запрограммированными с учетом последних достижений теории игр. Винер предостерегал, что машины могут вовлечь человечество в самоубийственную войну.
      Наибольшие опасения вызывают самообучающиеся машины (то есть машины, совершенствующиеся по мере накопления опыта), потому что их поведение становится - непредсказуемым. Такие машины делают не то, что им приказывают, а то, чему они научились. Они довольно быстро достигают уровня, когда программист уже больше не может сказать, какие изменения произошли в схеме машины. Большинство самообучающихся машин обычно содержит так называемые “рандомизирующие устройства”. Если действие такого устройства основано на случайном распаде радиоактивного образца, то поведение машины даже в принципе непредсказуемо (так, во всяком случае, считает большинство физиков).
      Большая часть современных исследований направлена на совершенствование самообучающихся машин, “умеющих” играть в различные игры. Некоторые из этих работ строго засекречены: в них под “игрой” понимается война. Одной из первых самообучающихся машин была IBM 704. Программу для нее составил Артур Л. Сэмюел.
      В 1959 году Сэмюел создал программу, которая позволяла машине не только правильно играть в шашки, но и улучшать стратегию игры, используя опыт, накопленный в предыдущих партиях. Вначале Самюел с легкостью обыгрывал машину, но IBM 704 не стала душить своего программиста, а вместо этого начала быстро совершенствоваться. Вскоре она достигла такого уровня, что с блеском выигрывала у Сэмюела все партии подряд! Насколько мне известно, такая программа для игры в шахматы еще не создана. Существует только несколько остроумных шахматных программ для обычных (несамообучающихся) машин.
      Лет 10 назад советский гроссмейстер Михаил Ботвинник заявил, что придет день, когда машина научится играть не хуже гроссмейстера. “Это, конечно, чепуха”, — отреагировал на выступление Ботвинника американский эксперт по шахматам Эдвард Ласкер. Но чепухой скорее следовало назвать замечание Ласкера. Играя в шахматы, машина имеет три огромных преимущества перед противником — человеком: 1) она никогда не “зевает”; 2) может анализировать ходы значительно быстрее человека; 3) способна безгранично совершенствовать свое мастерство. Поэтому есть все основания надеяться, что, сыграв несколько тысяч партий с шахматистами высокого класса, машина достигнет уровня гроссмейстера. Возможен и такой вариант: шахматная программа будет составлена так, что машина станет непрерывно и исступленно играть сама с собой. Благодаря своему быстродействию она за короткое время сможет накопить опыт, намного превосходящий опыт любого шахматиста-человека.
      Для экспериментов с самообучающимися машинами, умеющими играть в различные игры, совсем не обязательно покупать электронную вычислительную машину (ЭВМ). Нужно лишь набрать побольше пустых спичечных коробок и разноцветных бусинок.
      Счастливая идея создания простой и надежной самообучающейся машины из спичечных коробков принадлежит Дональду Мичи.
      В статье “Метод проб и ошибок” (Penguin Science Survey, 2, 1961) Мичи описывает самообучающуюся машину для игры в крестики и нолики, которую можно собрать из трехсот спичечных коробков. Называется эта машина MENACE (Mathbox Educable Naughts and Crosses Engine — машина из спичечных коробков, умеющая играть в крестики и нолики; menace (англ.) — угроза, опасность.))
      MENACE работает очень просто. На каждом коробке нарисована какая-нибудь позиция, встречающаяся при игре в крестики и нолики. Первый ход (а следовательно, и все нечетные) всегда делает машина, поэтому на коробках достаточно написать лишь те позиции, которые возникают перед нечетными ходами. Внутри каждого коробка лежат разноцветные стеклянные бусинки небольшого диаметра (каждый цвет соответствует одному из возможных ходов машины).
      Внутрь каждого коробка вклеен картонный уголок. При встряхивании и переворачивании коробка бусинки закатываются в картонный “загон”. Цвет бусинки, попавшей в вершину уголка, случаен. В коробках, относящихся к первому ходу, лежит по четыре бусинки каждого цвета, в коробках третьего хода — по три, в коробках пятого хода — по две бусинки каждого цвета и, наконец, в коробках седьмого хода каждый цвет представлен лишь одной бусинкой.
      Чтобы узнать очередной ход машины, надо встряхнуть и перевернуть коробок, затем открыть его и посмотреть, какого цвета “вершинная” бусинка, то есть бусинка, закатившаяся в вершину картонного уголка коробка; “принявшие участие” в игре коробки остаются открытыми до конца партии. Если машина выигрывает, ее поощряют, добавляя в каждый открытый коробок по три бусинки того же цвета, что и “вершинная” бусинка. Если игра заканчивается вничью, в каждый коробок добавляют только по одной бусинке (того же цвета, что и “вершинная”). Если же машина проигрывает, ее “наказывают”, вынимая из каждого коробка бусинку, закатившуюся в вершину уголка. Такой метод кнута и пряника находит весьма близкие параллели в обучении животных и даже людей. Чем больше партий в крестики и нолики играет машина Мичи, тем лучше она “запоминает” выигрышные ходы и тем упорнее стремится избегать проигрышных. Это и означает, что она представляет собой хотя и очень простое, но все же самообучающееся устройство. Правда, в отличие от IBM 704, работающей по шахматной программе Сэмюела, наша “спичечная” машина не умеет анализировать сыгранные партии и разрабатывать новые “стратегические замыслы” в соответствии с накопленным опытом.
      Первый двухдневный турнир между Мичи и его машиной состоял из 220 партий. Сначала Мичи все время наказывал свое детище за плохую игру, но после семнадцати партий машина начала ставить первый крестик только в угловую клетку, а после двадцатой партии заканчивать все игры вничью. В надежде заманить противника в ловушку Мичи начал делать самые бессмысленные ходы. Такая тактика оправдывала себя лишь до тех пор, пока машина не научилась справляться и с этими хитростями. Закончился матч сокрушительным поражением Мичи: он выбыл из турнира, проиграв восемь партий из десяти. Самообучающаяся машина из спичечных коробков стала гроссмейстером крестиков и ноликов!
      Поскольку вряд ли кто-нибудь из читателей возьмется за изготовление самообучающейся машины из трехсот спичечных коробков, я придумал игру попроще. Чтобы построить играющую в нее машину, достаточно взять всего лишь двадцать четыре коробка. Теория игры в шесть пешек (так я назвал свою игру) совершенно тривиальна, тем не менее я убедительно прошу читателя не проводить никакого анализа. Построив машину и постигнув все тонкости “шестипешия” в процессе обучения ее игре, вы получите гораздо больше удовольствия.

Игра в шесть пешек
Рис. 80. Игра в шесть пешек.

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

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

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

Картинки, которые нужно наклеить на спичечные коробки-элементы самообучающееся машины САМА
Рис. 81. Картинки, которые нужно наклеить на спичечные коробки-элементы самообучающееся машины САМА. (четыре типа стрелок означают стрелки четырех различных цветов)

      В каждый коробок положите столько бусинок, сколько стрелок на диаграмме. Каждой стрелке должна отвечать бусинка определенного цвета. Теперь робот готов к игре.
      Каждая стрелка обозначает допустимый, то есть согласующийся с правилами игры, ход. На диаграммах изображены все допустимые ходы. Отсюда следует, что машина, во-первых, будет ходить только “по правилам” и, во-вторых, сможет сделать любой разрешенный ход. Однако никакой определенной стратегии у нашего робота нет и пока он еще ничего не умеет.
      Обучение происходит следующим образом. Сделав первый ход, вы берете коробок, на котором нарисована создавшаяся на доске позиция, встряхиваете его и, закрыв глаза, отодвигаете крышку. Вынув из коробка наугад одну бусинку, вы закрываете его, ставите на стол, а сверху кладете вынутую бусинку. Теперь откройте глаза, посмотрите, какого цвета бусинка, и, найдя на диаграмме соответствующую стрелку, сделайте указанный ею ход. После этого вы делаете свой очередной ход (предыдущий был ходом машины). Сделав его, повторите описанную процедуру. Так следует продолжать до тех пор, пока партия не закончится. Если выиграет робот, положите все вынутые бусинки на место и начните следующую партию. Если же робот проиграет, его надо наказать. Заберите у него одну бусинку, соответствующую его последнему ходу. Все остальные бусинки положите на место и продолжайте курс обучения — начните следующую игру. Если последний коробок окажется пустым (так иногда бывает), это означает, что все ходы машины приводят к ее проигрышу и она отказывается играть дальше. В этом случае бусинку надо вынуть из предпоследнего коробка.
      В первых пятидесяти партиях записывайте все победы и поражения робота, а потом составьте график. Система наказаний придумана специально для того, чтобы максимально сократить время обучения, однако это время существенно зависит от мастерства учителя. Машина учится играть тем быстрее, чем искуснее ее противник.
      Можно придумать и другую систему обучения. Пусть, например, вам хочется, чтобы робот одерживал максимальное число побед в каждых двадцати пяти играх. Тогда лучше всего поощрять его (равно как и наказывать), добавляя в каждый коробок бусинки нужного цвета. При таком способе неправильные ходы ликвидируются несколько медленнее, но зато машина делает их все реже. Интересно было бы соорудить еще, одну машину, которая вначале тоже не умеет играть, и обучить ее по второй системе. Этот робот можно назвать САМ (САмообучающаяся Машина). Увеличив число элементов — спичечных коробков — в той и в другой машине, их можно было бы научить делать не только четные, но и нечетные ходы, и в частности первый ход. Затем можно было бы устроить турнир из шестидесяти партий между машинами и посмотреть, какая из машин — САМ или САМА-одержит больше побед. Первый ход в каждой партии роботы делают по очереди. Аналогичные машины нетрудно придумать и для других игр. Например, Стьюарт К. Хайт недавно сконструировал из спичечных коробков робота NIMBLE (NIM Box Logic Engine — логическое устройство из коробков для игры в ним), обучающегося игре в ним по схеме 3-3-3 (фишки разделены на три кучки, по три фишки в каждой). Робот Хайта может делать как первый, так и второй ход; после каждой партии его либо поощряют, либо наказывают. NIMBLE состоит всего из восемнадцати спичечных коробков; после тридцати партий он уже почти непобедим. Игра ним подробно разобрана в главе 14, моей первой книги.

минишашки минишахматы
Рис. 83. Доски для игры в минишашки (слева) и в минишахматы (справа).

      Многие популярные игры настолько упрощаются при уменьшении размеров доски, что оказываются в пределах возможностей спичечных роботов. Так, в го еще можно играть на доске размером 2Х2. Наименьшая доска для шашек, на которой игра еще не становится тривиальной, изображена на рис. 83 слева. Построить из спичечных коробков машину для игры в такие “минишашки” совсем нетрудно; если вам не захочется этого делать, займитесь анализом игры. Попробуйте ответичь на вопрос: должна ли партия в минишашки непременно заканчиваться вничью или же один из игроков всегда одерживает победу (предполагается, что оба противника играют наилучшим образом)?
      Игра в шахматы остается далеко за пределами возможностей любой самообучающейся машины из спичечных коробков, даже если мы максимально уменьшив шахматную доску (следя, однако, за тем, чтобы на ней можно было сделать любой ход, разрешенный правилами; доска, удовлетворяющая этому условию, изображена на рис. 83 справа). Определить, имеет ли хоть один игрок преимущество, и если да, то какой, повидимому, невозможно. Минишахматы могут помочь в составлении упрощенной шахматной программы для самообучающейся электронно-вычислительной машины. Полезны они и тем, кто захочет сыграть в шахматы во время небольшого перерыва в работе.
      Многие читатели сообщили мне о своих экспериментах с самообучающимися машинами из спичечных коробков. Один из них демонстрировал машину САМА на студенческом карнавале. Обучение робота проводилось по второй системе, то есть бусинки только добавлялись, поэтому его противники всегда имели (правда, непрерывно уменьшающиеся) шансы на выигрыш. Победителям выдавались призы, ценность которых увеличивалась по мере того, как возрастало мастерство машины.
      Некоторые читатели построили по моему совету две машины и организовали между ними турнир. Один читатель назвал такую пару роботов ОНИ (Обучающиеся Неодинаково Инструктируемые машины). Машины играли между собой до тех пор, пока одна из них не начала выигрывать все партии подряд. Другой читатель назвал вторую машину RAT* (Retless Auto-learning Tyrant-безжалостный самообучающийся тиран; Rat (англ.) — крыса. — Прим. Перев.) Он сообщил, что после восемнадцати партий RAT сдался, признав победу во всех последующих партиях за САМА.
      Автор одного из писем назвал машины Марк-1 и Марк-2. Как и следовало ожидать. Марку-1 повадобилось восемнадцать партии, чтобы научиться одерживать победу в каждой игре, а Марк-2 за это время научился как можно дольше оттягивать свое поражение. Автор письма разработал дьявольский план. Пригласив юношу и девушку из студенческого математического кружка, на знакомых с игрой в шесть пешек, он дал им прочесть правила игры и устроил между ними турнир. Цитирую его письмо:
      “Каждый участник турнира сидел в отдельной комнате, называя свои ходы судье. По секрету от игроков судьи (их тоже было двое) сообщали о сделанных ходах в третью комнату, где находились “машины” и велся счет побед и поражений. Противники считали, что они играют друг с другом через посредников; на самом же деле каждый из них играл с машиной. Начиная новую партию, участники менялись фигурами (игравший белыми брал черные, и наоборот). Те, кто находился в средней комнате, тоже были заняты: им приходилось следить, чтобы ходы не были перепутаны, встряхивать и открывать коробки (“обслуживать машины”) и вести счет матча.
      Студентов просили комментировать по ходу игры свои ходы и ходы противника. Вот некоторые из этих комментариев.

      “Самый безопасный ход, который только можно сделать, чтобы противник не взял мою пешку. Я почти наверняка выиграю”
      “Он взял пешку у меня, но и я не остался в долгу и взял его пешку. Если он пойдет так, как я думаю, то я потеряю одну пешку, зато на следующем ходу смогу запереть все его фигуры”.
      “Какой же я болван!”
      “Великолепный ход! Думаю, что я проиграю эту партию”.
      “По-моему, он совсем не думает. Мог бы теперь уже и не зевать”.
      “Здорово играет! Она начинает понимать, чего я хочу”.
      “Наконец-то он стал думать, и играть стало куда интересней”.
      “Какой странный ход! Разве не видит, что я выиграю, если он пойдет вперед?”
      “Мой противник играл хорошо, но, по-моему, я первой раскусила игру”.
      “Первым раскусил игру я”.

      Когда участникам соревнования показали “машины”, с которыми они играли, студенты никак не могли поверить, что их противниками были не люди.
      Математики из Массачусетского технологического института составили программу для обучения машины IBM 1620 игре в восемь пешек. Игра в восемь пешек — один из вариантов игры в шесть пешек (играют по тем же правилам, но на “минидоске” 4х4 и у каждого из противников имеется по четыре пешки). Автор программы сообщил мне, что если начинающий игру делает первый ход фигурой, стоящей в углу, то он наверняка одерживает победу. Других дебютов, когда первый ход делается не угловой, а какой-то из центральных пешек, в программе предусмотрено не было.
      Одна из читательниц сообщила, что она научилась играть в шесть пешек быстрее, чем построенная ею машина (вместо бусин были использованы леденцы), несмотря на то, что начинали они вместе. “Дело в том, — пишет она, — что после каждого проигрыша я забирала у машины один леденец и съедала его”.
      Автор другого письма воспользовался принципами обучения “спичечных” машин при составлении программы по обучению игре в крестики и нолики для вычислительной машины. Сначала машина играла без всякой системы, выбирая ходы случайным образом, и люди легко одерживали над ней победы. Затем, сыграв сама с собой две тысячи партий (это заняло две-три минуты), машина приобрела необходимые навыки, и после этого ее турниры с людьми уже проходили на чрезвычайно высоком уровне.
      Выступив в защиту замечания Ботвинника о том, что машина когда-нибудь в совершенстве овладеет игрой в шахматы, я вызвал бурю гневных писем от шахматистов. Один гроссмейстер уверял меня, что Ботвинник говорил неискренне. Вы можете это сами проверить, прочитав статью Ботвинника в номере газеты “Комсомольская правда” от 3 января 1961 года. В ней, в частности, говорится следующее: “Наступит время, когда машинам, играющим в шахматы, будут присваивать звание международного гроссмейстера... Тогда понадобится проводить два чемпионата мира: один — для людей, другой — для машин. Второй турнир, разумеется, будет происходить не между машинами, а между теми, кто их создает и программирует”.
      Резкую реакцию со стороны шахматистов на предположение о том, что вычислительные машины когда-нибудь научатся играть на уровне мастера и даже гроссмейстера, понять нетрудно. На эту тему много говорилось и писалось. Игра человека против шахматной машины — излюбленный сюжет научной фантастики. И все же такая реакция особенно забавна. Можно приводить достаточно веские аргументы против возможности создания машин, способных “творить” прекрасные мелодии, стихи или произведения изобразительного искусства, но шахматы, несмотря на всю их сложность, принципиально ничем не отличаются от игры в крестики и нолики. Именно поэтому вычислительные машины как нельзя лучше подходят для обучения игре в шахматы.
      Однако, прежде чем появятся машины-шахматисты, несомненно, будут созданы машины, умеющие играть в шашки. Эта игра уже настолько тщательно исследована, что матчи между чемпионами почти всегда заканчиваются вничью, а чтобы сделать игру интереснее, сейчас принято разыгрывать три первых хода случайным образом. Ричард Бэллман в статье “О применении динамического программирования к нахождению оптимальной стратегии при игре в шахматы и в шашки” (Proceedings of the National Academy of Sciences, 53, February 1965, pp. 244-247) пишет, что, по его мнению, “игра в шашки будет полностью исследована в ближайшие десять лет”.
      Игра в шахматы, безусловно, на несколько порядков сложнее. По-видимому, еще не скоро наступит момент, когда машина после первого сделанного вами хода произведет какие-то подсчеты и напечатает в ответ одно только слово “сдаюсь” (это старая шутка в новом одеянии). Еще в 1958 году некоторые видные математики считали, что через десять лет машина научится играть не хуже гроссмейстера, но, как показывает опыт, их предсказания оказались слишком смелыми. Став чемпионом мира по шахматам, Тигран Петросян заявил в 1963 году корреспонденту газеты “Нью-Йорк тайме”, что, по его мнению, в ближайшие пятнадцать-двадцать лет машина вряд ли достигнет совершенства в игре в шахматы.
      Доску для игры в шесть пешек можно сделать шире, сохранив при этом ее размер по вертикали. Подробному анализу такого обобщенного варианта игры в шесть пешек посвящена специальная статья Джона Р. Брауна. (Mathematical Magazine. 38, November 1965, pp. 216-299) Пусть ширина доски составляет п клеток. Если последняя цифра числа п равна 1, 4, 5, 7 или 8, то одерживает победу тот, кто делает первый ход. Во всех остальных случаях побеждает второй игрок.

Ответы

      Если оба противника делают наиболее рациональные ходы, то партия в шашки на доске 4х4 заканчивается вничью. На рис. 84 показаны три возможных первых хода черных: С5; С6; D6.

Рациональный выбор ходов при игре в минишашки (ничья)
Рис. 84. Рациональный выбор ходов при игре в минишашки (ничья).

      Делая первым ход С5, черные проигрывают, если белые отвечают ходом A3. Вторая возможность (ход на С6) независимо от ответственного хода белых приводит к ничьей.
      Черным выгоднее всего начинать игру ходом на D6. Если белые отвечают ходом на ВЗ, то черные выигрывают. Однако, сделав ход на В4, белые заканчивают партию вничью.
      Говоря об играх, которым можно обучить самодельные машины из спичечных коробок, я упомянул об игре в го на доске 3Х3. Игрок, делающий первый ход, обязательно выигрывает, если он этим ходом займет центральную клетку, а потом будет все время придерживаться рациональной стратегии.
      Игра в шашки на доске 4х4 тривиальна, однако, увеличив доску до размеров 5Х5, вы получите совершенно удивительные результаты, безусловно заслуживающие внимания. О последнем варианте игры в минишашки я прочел в одном из писем, автор которого тоже где-то услышал об этой игре. В начале партии три белые шашки ставятся в первый ряд, а три черные — в пятый. Начинают черные. В остальном правила ничем не отличаются от обычных. На первый взгляд может показаться, что при рациональной стратегии игра должна кончаться вничью; в действительности ситуация сложнее, потому что на доске 5х5 отсутствуют ходы типа 2-4, 4-2, которые разрешены дамке. Даже если оба участника играют достаточно хорошо, один из них обязательно побеждает, причем чем выше мастерство проигравшего, тем эффективнее одержанная победа. Чтобы не лишать вас удовольствия, я предоставляю вам возможность самостоятельно проанализировать игру и решить, кто из игроков — тот, кто начинает, или тот, кто делает второй ход — может всегда добиться победы.

Наверх