...Такого робота изобрел Дональд Мичи. Сообщение о нем появилось в статье "Метод проб и ошибок" во втором номере журнала Penguin Science Survey за 1961 год. С тех пор робот, названный MENACE (от Mathbox Educable Naughts and Crosses Engine), кочует по страницам научно-популярных изданий.
Модель Мичи играла в крестики-нолики. Для ее изготовления изобретателю понадобилось триста спичечных коробков и несколько сотен разноцветных бусинок. Устройство машины очень простое. На каждом коробке изображена позиция, встречающаяся при игре в крестики-нолики. Внутрь коробка положено столько разноцветных бусинок, сколько существует возможных ходов в данной позиции.
Мичи вклеивал в каждый коробок уголок из картона, где могла поместиться лишь одна бусинка. Чтобы определить ход машины, он встряхивал коробок, открывал его и смотрел, какая бусинка закатилась в ловушку. Пометив за робота ход, Мичи делал собственный, после чего игра переходила в другую позицию. Для очередного хода робота выбирался коробок с изображением соответствующей позиции, и игра продолжалась по описанной схеме.
Поскольку Мичи решил, что первый ход всегда делает робот, на коробки он нанес все позиции для 1-го, 3-го и последующих нечетных ходов. Мы, конечно, можем поступить иначе, создав универсального робота.
Обучение машины проводится методом кнута и пряника. Во время игры коробки, принявшие участие в совершении ходов, откладываются в сторону. Если человек выиграл, то робота следует наказать, достав из каждого сыгравшего коробка бусинку, определившую ход. Таким образом удаляется последовательность ходов, приведших к проигрышу. В случае ничьей машина умеренно поощряется, для чего в каждый из сыгравших коробков добавляется по бусинке того же цвета, что сделала ход. Если же робот выиграл, в коробки добавляется сразу по три бусинки цвета выигрышных ходов.
Ниже есть продолжение.
Первый турнир между Мичи и его машиной состоял из 220 партий и занял два дня. Сперва робота все время приходилось наказывать, но после 20-й партии он начал все игры сводить вничью. Мичи стал делать нарочито бессмысленные ходы, чем ненадолго сбил с толку свое детище. Однако в конце концов он выбыл из турнира с разгромным счетом, проиграв роботу в последнем круге 8 партий из 10.
Перспектива возни с сотнями спичечных коробков вряд ли может кого-нибудь прельстить, а вот запрограммировать такого робота можно без особого труда. Единственная сложность состоит в создании качественного генератора случайных чисел для выбора ходов. Впрочем, если считывать показания системного таймера каждый раз, когда человек нажимает на клавиши, значения младших разрядов счетчика будут вполне случайной величиной, так как клавиши не могут нажиматься через совершенно одинаковые промежутки времени.
Читателям, у которых нет возможности программировать робота, можно посоветовать построить машину, предложенную постоянным автором журнала Scientific American Мартином Гарднером. Роботов, сделанных по принципу MENACE Дональда Мичи, может быть сколько угодно. Их сложность, то есть количество необходимых спичечных коробков, находится в прямой зависимости от комбинаторной сложности игры, в которую машины должны играть.
Гарднер придумал игру в шесть пешек, для которой достаточно робота из 24 коробков. Правила игры следующие. Доска имеет 3х3 клетки. У каждого из игроков в начале игры по 3 пешки. В исходной позиции пешки противников выстроены в два ряда на противоположных сторонах доски.
Есть всего два вида ходов: во-первых, перемещение на одну клетку вперед, когда она свободна, во-вторых, ход со взятием пешки противника. Брать чужую пешку разрешается, если она стоит на соседней по горизонтали или по диагонали клетке. Выигрывает тот, кто возьмет все пешки противника, либо проведет свою пешку через все поле в третий ряд, либо "запрет" противника, то есть не даст сделать очередной ход.
Гарднер предлагает ничего не вклеивать в спичечные коробки, а просто вынимать из них бусинки с закрытыми глазами и класть их сверху на коробок, сделавший ход. Кроме того, он предлагает поэкспериментировать с размером поощрения и/или наказания роботов в процессе обучения. Можно попробовать наказание полностью исключить.
Далее, он советует сделать машины для четных и нечетных ходов и устроить соревнование между ними. Право слово, если писать программы, это сделать совсем нетрудно. Представляете, каким захватывающим мог бы стать кубковый матч между роботами разных авторов, использовавших неодинаковые методики обучения! Разумеется, никто не мешает нам придумывать свои игры и свои самообучающиеся машины, чтобы разнообразить удовольствие.
Что же касается развлечений, то один из читателей Scientific American устроил следующий розыгрыш. Он пригласил двух студентов, юношу и девушку, не знакомых с игрой в шесть пешек, объяснил им правила и устроил между ними заочные соревнования. Я процитирую часть его письма Гарднеру:
"Каждый участник турнира сидел в отдельной комнате, называя свои ходы судье. По секрету от игроков судьи (их тоже было двое) сообщали о сделанных ходах в третью комнату, где находились роботы и велся счет побед и поражений. Противники считали, что играют друг с другом через посредников; на деле же каждый из них играл с машиной. Начиная новую партию, участники менялись фигурами (игравший белыми брал черные и наоборот). Те, кто сидел в средней комнате, были заняты: им приходилось следить, чтобы ходы не были перепутаны, встряхивать и открывать коробки (обслуживать машины) и вести счет матча.
Студентов просили по ходу игры комментировать свои ходы и ходы противника. Вот некоторые из этих комментариев.
- Какой же я болван!
- Великолепный ход! Думаю, что проиграю эту партию.
- По-моему, он совсем не думает. Мог бы уже и не зевать.
- Здорово играет! Она начинает понимать, чего я добиваюсь.
- Наконец он начал думать, и играть стало куда интересней.
- Какой странный ход! Разве не видит, что я выиграю, если он пойдет вперед?
- Мой противник играл хорошо, но, по-моему, я первой раскусила игру.
- Первым игру раскусил я.
Не правда ли, забавно? Когда студентам показали роботов, с которыми они сражались, несчастные никак не могли поверить, что играли не друг с другом, а со спичечными коробками.
На мой взгляд, эта история настолько занимательна, что возникает желание соорудить самообучающегося робота, чтобы разыграть своих друзей или представить его "гвоздем" вечеринки.
Евгений Щербатюк
http://kg.fdd5-25.net/9703/k1211.htm
No comments:
Post a Comment