«Крестики-нолики»

.

В английском языке название этой игры пишут по-разному: и tic-tac-toe, и tick-tack-toe, и даже tit-tat-toe. Оно ведет свое происхождение от старинной английской детской считалки, начинающейся словами «Tit-tat-toe, Му first go» и входящей в классический сборник «Стихи Матушки-гусыни».


По-английски ее также называют noughts and crosses, — собственно, и каждому из нас она с детства известна именно как крестики-нолики. Играют в нее два игрока, которые по очереди ставят крестики и кружки в клеточках игрового поля размером 3×3. Побеждает тот, кто сумеет расположить три крестика (или кружка) в ряд по любой из горизонталей, вертикалей или больших «Крестики-нолики», пожалуй, едва ли не самая древняя из известных сегодня игр. В той или иной форме она была известна уже в Древнем мире — в Китае, Греции, Риме, а в Средние века пользовалась немалой популярностью в Англии и Франции. И пусть в варианте 3×3 игра действительно очень проста, она в то же время далеко не столь тривиальна, как кажется, и дает немало пищи для размышлений.
Большой интерес вызывали «крестики-нолики» у людей науки. Например, в XIX веке их исследовали Чарльз Бэббидж и американский логик и философ Чарльз Сандерс Пирс, а в XX веке — основоположник теории информации Клод Шеннон и другие выдающиеся ученые.
Заметный след оставили «крестики-нолики» в истории вычислительной техники. Например, первый механический игровой автомат был спроектирован (хотя и не построен) еще в середине позапрошлого столетия именно для игры в «крестики-нолики». В середине XX века для игры в «крестики-нолики» строились первые релейные автоматы (практически одновременно с автоматами для игры в «ним»), и они же стали первой «интеллектуальной» игрой, для которой была написана игровая программа для электронного компьютера. С помощью крестиков-ноликов проверяли новые идеи в области искусственного интеллекта, и именно в крестики-нолики играют сегодня первые биологические компьютеры — прототипы вычислительных машин будущего.
Механический автомат для игры в «крестики-нолики» был разработан Чарльзом Бэббиджем. Этот гениальный английский ученый и изобретатель больше всего известен проектом аналитической машины — фактически механического прототипа современного компьютера. Ее замысел возник у него около 1834 года, и работа над ней продолжалась вплоть до самой смерти ученого.

В мемуарах, озаглавленных «Страницы жизни философа», Бэббидж подробно описал свою работу над аналитической машиной. Но есть в этой книге несколько страниц, которые редко привлекают внимание биографов ученого. В них Бэббидж пишет, что однажды стал задумываться над тем, что же представляет собой будущая аналитическая машина — может ли она лишь выполнять предписанные ей действия, или же способна на нечто большее, т. е. действовать в некотором роде «самостоятельно», без непосредственных указаний человека.
И он решил, используя те же принципы, построить машину (автомат), играющую в какую-нибудь «интеллектуальную игру» — шашки, шахматы или «крестики-нолики».
Бэббидж приводит крайне интересный анализ принципов построения такого автомата. По его мнению, эта задача сводится к тому, чтобы автомат умел делать наилучший ход в любой возможной позиции. Перечисляя вопросы, на которые автомат должен ответить в процессе игры, Бэббидж фактически описывает алгоритм его действий (который легко можно записать в виде блок-схемы):
1. Допустима ли анализируемая позиция правилами игры?
2. Если да, то проиграл ли автомат?
3. Если нет, то выиграл ли автомат?
4. Если нет, то может ли он выиграть следующим ходом? Если да, то сделать этот ход.
5. Если нет, может ли его соперник выиграть, сделав следующий ход?
6. Если да, то автомат должен, если возможно, предотвратить этот ход.
7. Если его соперник не может выиграть игру следующим ходом, автомат должен проверить, может ли он сделать такой ход, что если ему будет позволено сделать подряд два хода, он может выиграть на втором ходе двумя разными способами. Если же ни одно из приведенных условий не выполняется, то автомат должен провести такой же анализ на три или более последующих ходов.
Разумеется, здесь «за кадром» остается главный вопрос — а каким образом автомат будет проводить анализ текущей позиции? Ответа на него Бэббидж не дает. Зато он нашел оригинальный ответ на другой принципиальный вопрос. Во всех известных во времена Бэббиджа автоматах последовательность их действий (движений) была жестко предопределена, т. е. «алгоритм» их работы был реализован аппаратно. В игре же постоянно требуется выбирать следующее действие (следующий ход) в зависимости от хода соперника. Конечно, в общем случае этот выбор зависит от анализа текущей позиции. Но в частном случае, когда надо выбрать один ход из нескольких равносильных (ситуация, часто встречающаяся в игре «крестики-нолики», обладающей свойством симметричности), Бэббидж механизм выбора предложил.
Он ввел в конструкцию счетчик выигранных автоматом партий, и если его значение в данный момент было четным, то из двух возможных ходов автомат выбирал первый, а если нечетным — то второй. Если равных по силе ходов было три, то текущее значение счетчика делилось на три, и в зависимости от значения остатка (о, 1 или 2) автомат выбирал один из ходов. Бэббидж писал: «Очевидно, что таким образом можно производить выбор при любом числе условий. Пытливому зрителю пришлось бы длительное время наблюдать за игрой автомата, прежде чем он открыл бы принцип его действия». Таким образом, Бэббидж впервые предложил механизм, в некотором роде имитирующий в поведении автомата волю человека, принимающего свое решение с учетом тех или иных факторов.
По словам Бэббиджа, своей работой он был полностью удовлетворен и не сомневался в том, что сумеет изготовить такой автомат. Однако здесь стали возникать сугубо практические соображения. Важнейшим делом своей жизни Бэббидж считал построение аналитической машины. Многолетняя борьба ученого с британским правительством, не желавшим финансировать эту разработку, составляет, пожалуй, одну из самых драматичных страниц в истории вычислительной техники.
Бэббидж, потративший огромные суммы на свою работу, испытывал крайний недостаток в средствах и в течение многих лет напряженно изобретал различные схемы для зарабатывания денег. Одно время он даже пытался создать беспроигрышную систему ставок на скачках. Работа над автоматом для игры в «крестики-нолики» навела Бэббиджа на новую мысль. Он решил проверить, «имеется ли вероятность того, что если такой автомат будет выставлен на публике, то принесет за приемлемое время достаточно денег для изготовления аналитической машины».
К проверке Бэббидж подошел со всей основательностью истинного ученого. Так, по его замыслу, автомат должен был иметь «привлекательный вид». Он решил, что внешне он может представлять несколько фигур — «двух детей, играющих друг против друга, и сопровождающих их ягненка и петуха. Что ребенок, выигравший игру, может хлопать в ладоши, в то время как петух будет кукарекать, а ребенок проигравший может плакать и ломать руки, а ягненок блеять».
Далее Бэббидж проанализировал причины, по которым люди захотят сыграть с такой машиной и даже заплатят за это деньги: «Когда станет известно, что автомат побеждает в эту детскую игру не только детей, но даже пап и мам, не кажется неразумным ожидать, что каждый услышавший об этом ребенок упросит маму показать автомат ему.
С другой стороны, каждая мама и некоторые папы, услыхав о нем, несомненно, возьмут с собой детей, чтобы показать им такое невиданное и интересное зрелище». Кроме того, он решил, что надо изготовить не один, а несколько игровых автоматов, чтобы выставить их одновременно в трех разных местах. При этом каждый хозяин «один автомат будет держать в резерве, на случай неожиданной поломки».
В своем предприятии Бэббидж, кажется, предусмотрел все до мелочей. К сожалению, хотя анализ психологических, эстетических и даже организационных аспектов дела, казалось, сулил успех, его экономическая сторона, как это часто бывает, оказалась далеко не столь привлекательной. Изучив состояние дел на самых популярных выставках Лондона, Бэббидж к своему глубокому разочарованию убедился, что механические чудеса публику не слишком интересуют. Так, даже два наиболее интересных изобретения того времени — «говорящая машина» немца Йозефа Фабера и «сочиняющая» стихи на латыни машина английского изобретателя-самоучки Джона Кларка, как выяснил Бэббидж, «были с точки зрения прибыльности абсолютным провалом». О вкусах публики лучше всего говорит тот факт, что наибольший доход устроителям выставок различных диковин приносил карлик по прозвищу Генерал Мальчик-с-пальчик.
Бэббидж был человеком крайне увлекающимся. Захваченный новой идеей, он зачастую оставлял предыдущую работу незавершенной. Но в данном случае ситуация сложилась иная — прекратить работу над автоматом для игры в «крестики-нолики» Бэббиджа заставил строгий анализ.
Инженеры и историки до сих пор спорят, мог ли Бэббидж построить свою аналитическую машину. Ответы на него даются разные, но, по крайней мере, эти ответы основываются на изучении огромного материала — чертежей самого Бэббиджа и изготовленных им фрагментов машины. К сожалению, какие-либо чертежи или хотя бы наброски, которые позволили бы оценить возможность изготовления автомата, отсутствуют. И хотя сам Бэббидж написал, что «с легкостью начертил механизм, управляющий таким автоматом», мы о его конструкции можем только строить догадки.
Следующим «устройством» для игры в «крестики-нолики» стал релейный автомат Уильяма Кейстера.

Американский ученый Уильям Кейстер являл собой редкий образец верности однажды избранному делу. После окончания университета его приняли на работу в один из самых знаменитых научно-исследовательских центров — Bell Laboratories, и он проработал там 38 лет.
Начав карьеру простым инженером, Кейстер спустя недолгое время стал одним из ведущих специалистов и много лет возглавлял ключевые департаменты компании. Он занимался релейными, а после Второй мировой войны — электронными переключательными схемами для систем телефонной связи, был автором нескольких статей и монографий, а также пяти патентов. Но если научные публикации Кейстера посвящены вопросам, связанным со специальностью, то три из его патентов относятся к совершенно другой области — играм и головоломкам. Два из этих патентов — на головоломки «Locking disc puzzle» (№ 3637216) и «Pattern-Matching Puzzle» (№ 3637216), в которых требуется разобрать на части или, наоборот, собрать из деталей сложной конфигурации одну из нескольких конструкций, были выданы ему в январе 1972 года, незадолго перед уходом на пенсию. А вот патент № 2877019, полученный Кейстером за 13 лет до этого, заслуживает более пристального внимания.

 

В этом патенте был описан релейный автомат, предназначенный для игры в крестики-нолики. На лицевой панели машины расположены девять индикаторных панелей игрового поля A-J. Рядом с каждой из панелей помещена кнопка. Нажимая на нее, игрок сообщает автомату свой ход, при этом на индикаторной панели загорается соответствующий символ. Также имеются две индикаторных кнопки: WIN (загорается, когда автомат выигрывает партию) и AL1 (загорается, если игрок случайно нажимает две кнопки одновременно) и две управляющие кнопки RL и AL, предназначенные для «очистки» состояния автомата перед началом новой партии.
Отдельно стоит отметить интересное решение, которое применил Кейстер для того, чтобы иметь возможность отображать на каждой индикаторной панели как крестики, так и нолики. Оно основано на применении поляризационных фильтров. На рисунке представлен разрез индикаторной панели (1 — кнопка ввода очередного хода).
Сверху панель прикрыта слоем прозрачного материала з, а пространство за ним разделено светонепроницаемой перегородкой 8 на две половины, в каждой из которых имеется по электрической лампочке (4 и 5). Обе половины закрыты поляризационными фильтрами, причем фильтр 6 пропускает только вертикально, а фильтр 7 — горизонтально поляризованную составляющую света лампочки. Под слоем прозрачного материала 3 имеются еще два поляризующих фильтра — 9 (с той же поляризацией, что и 6) и 10 (с той же поляризацией, что и 7). При этом в фильтре 9 имеется вырез в виде креста, а в фильтре 10 — в виде ноля. Таким образом, когда загорается лампа 5, лучи горизонтально поляризованной составляющей пройдут сквозь фильтры 7 и 10 и будут задержаны фильтром 9, в вырезе которого будет светиться символ «X». Аналогично, когда загорается лампа 4, в вырезе фильтра 10 виден светящийся символ «о».
Заявку на патент Кейстер подал еще в ноябре 1950 года, а получил его лишь спустя 9 лет, однако в это десятилетие получили широкое распространение другие игровые машины. И немаловажную роль в этом сыграли релейные автоматы Эдмунда Беркли.

Имя Эдмунда Каллиса Беркли хорошо известно в компьютерном мире и пользуется в нем огромным уважением. Окончив Гарвардский университет с дипломом математика, он работал в одной из крупнейших американских страховых компаний, и эта работа привела его к мысли о необходимости использования в страховом деле вычислительных машин. Он живо интересовался ходом работ Дж. Стибица и Г. Айкена над релейными компьютерами и сам принимал в них участие, выдвигал собственные предложения по созданию электронного компьютера и убеждал свою компанию заказать ЭВМ у создателей ENIAC Д. Моучли и П. Эккерта. Беркли был одним из организаторов первых профессиональных обществ в области вычислительной техники и автором первых популярных книг о компьютерах. Однако компьютер в понимании Беркли вовсе не был большим арифмометром для решения вычислительных задач. Он считал, что компьютер должен решать задачи интеллектуальные — отсюда возник его многолетний интерес к роботам.
В 1950–1951 годах он построил свои первые релейные автоматы — вычислитель Саймон и робота-белку Скви. За ними последовали другие роботы и автоматы. В марте 1956 года на одной из выставок он показал релейную машину для игры в «крестики-нолики», которую назвал Релейным Моу (Relay Мое — это название рифмуется с названием игры «tit-tat-toe»).
Внешне машина Беркли походила на машину Кейстера. Автомат состоял из 90 реле и мог играть на поле 3×3 против человека, причем можно было выбрать один из нескольких режимов (безошибочная игра, при которой робот не проигрывал, менее сильная игра, когда противник мог одержать победу и др.).
Еще один свой автомат для игры в крестики-нолики Беркли назвал Переключательной машиной (Switch Tit Tat Toe Machine) — поскольку каждая клетка игрового поля в нем была представлена многопозиционным переключателем. Точнее, это был полуавтомат — когда человек делал свой ход (изменял положение соответствующего переключателя), машина посредством загорающейся лампочки немедленно сообщала ему свой ответ, и тот должен был сделать этот ход за нее.
В 1954 году Беркли основал компанию Berkeley Enterprises, которая продавала и сдавала в аренду (по цене от 15 до 150 долларов в день) самые разные роботы собственного изготовления.
К сожалению, данных об объемах производства игровых машин нет, но, скорее всего, они были небольшими — ведь стоимость Релейного Моу была достаточно велика — она составляла около 3000 долларов, а стоимость Переключательной машины — около 200 долларов.
Однако самым интересным продуктом компании Беркли были уникальные конструкторы для сборки разнообразных автоматов и роботов — Беркли назвал их Geniac (Genius Almost-Automatic Computer), Tyniac (Tiny Almost-Automatic Computer) и Brainiac (Brainy Almost-Automatic Computer, что можно приблизительно перевести как «умный почти автоматический компьютер», от английского brain — «мозг»).
Набор Geniac № 1 (1954 год) ценой 20 долларов состоял из 6 многопозиционных переключателей и 400 деталей, из которых можно было собрать 33 различные машины, работавшие от обычной батареи для карманного фонарика. В 1958 году в продажу поступил самый популярный — и недорогой — всего 9 долларов 95 центов — набор Brainiac К2. Из его четырех переключателей и 300 деталей можно было собрать 31 машину, в числе которых были головоломки, машины для игры в «крестики-нолики» и «ним», арифметические и логические машины, машины для шифрования и дешифрирования, тестирования и т. д.
Конструкторы Беркли пользовались огромным спросом. Но здесь надо сказать, что своей главной целью он полагал отнюдь не извлечение прибыли. Эдмунд Беркли был страстным борцом против ядерного оружия, видным активистом движения за мир и разоружение. Он был убежден, что необходимо всемерно пропагандировать знания и интеллект, учить людей мыслить — ведь разумно мыслящий человек не может не понимать, чем грозит человечеству гонка ядерных вооружений.
Судя по длительной задержке с выдачей патента, автомат Кейстера так и не был построен. Автоматы Беркли тоже постепенно теряли популярность. И это вполне объяснимо. Век релейных машин заканчивался, и они уже воспринимались как анахронизм — ведь к концу 1950-х годов широкое распространение получили полупроводниковые электронные компьютеры. И в это же время появились первые программы для игры в шашки и шахматы, т. е. более сложные игры. Понятно, что гораздо более простые «крестики-нолики» также попали в поле зрения программистов.
Создание первой игровой программы для электронного компьютера связано с именем англичанина Александра Дугласа.
Компьютер EDSAC (Electronic Delay Storage Automatic Calculator — Электронный автоматический вычислитель с памятью на линиях задержки) был построен в 1946–1949 годах в Кембриджском университете под руководством выдающегося британского ученого Мориса Уилкса. Он занимает особое место в истории вычислительной техники благодаря событию, произошедшему 6 мая 1949 года. В этот день оператор нажал кнопку «Старт», замигали лампочки на панели и начала вращаться бобина с перфолентой, на которой была записана последовательность целых чисел. Спустя несколько секунд застучал телетайп, печатая посчитанные компьютером значения квадратов этих чисел: 1, 4, 9,16, 25, 36. Для того, чтобы вычислить квадраты чисел от 1 до 99, потребовалось 2 минуты и 35 секунд. Таким образом, EDSAC стал первым в мире компьютером с хранимой в памяти программой, на котором была решена реальная задача.
Система команд EDSAC состояла из 18 одноадресных команд; выполнение операций сложения, умножения и деления занимало в среднем 1,4; 5,4 и 200 миллисекунд соответственно (операции выполнялись над числами с фиксированной запятой). Данные и программы вводились с 5-канальной бумажной перфоленты, а результаты вычислений печатал принтер телетайпа. Машина содержала около 3 000 ламп, потребляла примерно 12 киловатт электроэнергии и занимала комнату площадью 20 квадратных метров. В целом можно сказать, что в архитектуре и схемотехнике EDSAC никаких серьезных новаций, по сравнению с другими компьютерами того времени, не было. Зато в области программирования кембриджские компьютерщики совершили настоящий прорыв. За полтора года они создали библиотеку из 87 подпрограмм, позволявших работать с числами с плавающей запятой, вычислять логарифмы и тригонометрические функции, решать дифференциальные уравнения и т. д. Результаты этой работы Уилкс и его коллеги Дэвид Уилер и Стенли Гилл обобщили в первом в мире учебнике по программированию «Подготовка программ для электронных цифровых вычислительных машин» (1951 год), переведенном на многие языки, в том числе русский.

Так что нет ничего удивительного в том, что именно один из членов этого коллектива программистов написал и первую в мире игровую программу. Это был Александр Дуглас, работавший в то время над диссертацией, посвященной анализу возможностей взаимодействия человека и компьютера.
Поскольку это взаимодействие должно быть оперативным, как можно более наглядным и, главное, двусторонним, Дуглас пришел к мысли о необходимости использовать для этого визуальное представление хранящейся в памяти компьютера информации. Однако в то время современных мониторов еще не было, и визуальную информацию можно было вывести только на экран электронно-лучевой трубки (ЭЛТ). Одна из трех работавших в составе EDSAC трубок могла отображать состояние памяти, на ее экране можно было показать 560 (35×16) светящихся точек, соответствующих значениям 560 бит. Этим и решил воспользоваться Дуглас. Управляя с помощью программы положением светящихся точек, можно было получить на экране то или иное изображение. В качестве устройства ввода Дуглас использовал дисковый телефонный номеронабиратель.

В начале партии на экран трубки выводилось игровое поле, после чего игрок выбирал право первого хода. Набранная на телефонном диске цифра «о» сообщала компьютеру, что первый ход принадлежит ему; набрав цифру «1», игрок оставлял первый ход за собой (за ходящим первым закреплен символ «X»). Для того чтобы сообщить компьютеру свой ход, игрок набирал посредством телефонного диска одну из цифр от «1» до «9», которые соответствовали одной из девяти клеток игрового поля. Программа рисовала в выбранной клеточке выбранный игроком символ, и тут же компьютер делал ответный ход, который тоже отображался на экране.
Свою программу Дуглас назвал ОХО — эти буквы вовсе не являются аббревиатурой, а символизируют нолики и крестики. Как мы видим, Дуглас написал ее не для забавы, а с весьма серьезной целью проверки возможности и выработки основных принципов взаимодействия человека с компьютером в ходе работы программы. К сожалению, информация о том, играли в эту игру коллеги Дугласа по кембриджскому университету или нет и если играли, то сколь успешно, отсутствует. А за пределы лаборатории игра так и не вышла — по той простой причине, что компьютер EDSAC существовал в одном-единственном экземпляре. Но в любом случае написанная Александром Дугласом программа стала первой в истории компьютерной игрой, в которую человек сыграл против вычислительной машины.
Если Кейстеру и Беркли при создании их машин требовалось воплотить в релейных схемах оптимальный алгоритм игры, то английский ученый Дональд Мичи поставил перед собой совсем иную задачу.

Мичи родился в Бирме и получил классическое образование в одной из привилегированных английских школ. В годы Второй мировой войны он работал в Блетчли-парке, где английские ученые и инженеры создали первый в мире специализированный электронный компьютер Colossus, предназначенный для расшифровки немецких кодов (предложенный Мичи метод дешифрирования считают одним из ключевых факторов, способствовавших успешной работе компьютера). Здесь он познакомился и подружился с гениальным математиком Аланом Тьюрингом.
После войны Мичи изучал в Оксфорде медицину и биологию, занимался генетикой и продолжал сотрудничество с Тьюрингом, который в то время как раз намечал обширную программу исследований в области искусственного интеллекта. Так, они с Мичи собирались написать компьютерные программы для игры в шахматы и надеялись, что эти программы сыграют друг против друга. Смерть Тьюринга не позволила осуществиться многим их планам.
Тьюринг и Мичи сходились в том, что компьютер, обладающий огромной вычислительной мощью, может неимоверно увеличить силу Дональд Мичи человеческого интеллекта. Однако человек, в отличие от машины, способен обучаться. А можно ли применительно к компьютеру говорить об обучении? Они не раз обсуждали этот вопрос. Работа Мичи, выполненная около i960 года, стала одной из первых, в которых была предложена модель обучения компьютера методом проб и ошибок.
Дональд Мичи решил обучать компьютер — и обучать игре в «крестики-нолики». Возможно, имей Мичи в своем распоряжении настоящий компьютер, он предпочел бы написать программу, моделирующую процесс обучения. Но компьютера у него не было, и Мичи создал удивительное устройство — модель компьютера, состоящую из 304 спичечных коробков. Он назвал его MENACE (Match box Educable Noughts And Crosses Engine — «Обучающаяся машина из спичечных коробков для игры в «крестики-нолики»»).
Каждый коробок представлял собой одну из позиций, которые могут возникнуть в ходе партии; позиция изображалась на его крышке. Первый ход всегда был за «машиной», поэтому на коробках показывались только позиции с четным количеством символов. Коробки были наполнены бусинками девяти разных цветов, причем каждый цвет был соотнесен с одной из девяти клеток игрового поля.

Коробок, соответствующий начальной позиции (т. е. пустому игровому полю перед первым ходом), содержал по 4 бусинки каждого цвета; позиции перед третьим ходом — по 3, перед пятым ходом — по 2 и перед седьмым ходом — по одной бусинке каждого цвета. При этом число различающихся цветов в каждом коробке совпадает с числом возможных в данной позиции ходов машины.
Очередной ход машины производился так. Игрок выбирал коробок с изображением текущей позиции, брал его, тряс, чтобы хорошо перемешать бусинки, и затем открывал. Бусинка, оказавшаяся в вершине имевшейся внутри каждого коробка перегородки в виде утла, определяла следующий ход машины. Игрок вынимал эту бусинку и, оставив использованный коробок открытым, откладывал его в сторону. Затем он решал, какой сделает ход, выбирал коробок, соответствующий возникающей после этого хода позиции, и повторял описанные действия вплоть до окончания партии. Если машина проигрывала, то взятые бусинки на место не возвращались (благодаря этому вероятность сделать тот же — т. е. приведший к поражению — ход в следующих партиях уменьшалась); если партия заканчивалась вничью, все бусинки возвращались на место, т. е. состояние машины не изменялось; если машина выигрывала, то взятые бусинки возвращались на место, и, кроме того, в каждый открытый коробок добавлялись еще по одной бусинке того же цвета (это увеличивало вероятность сделать тот же ход в последующих партиях).
Такая методика обучения оказалась весьма эффективной. Первое состязание между Мичи и его компьютером состояло из 220 партий. Сначала он все время выигрывал, но после 17-й партии машина стала делать первый ход в центральную клетку, а после 20-й — играть вничью. Под конец Мичи уже проигрывал 8 партий из ю.
Сегодня концепция обучения является одной из ключевых в искусственном интеллекте и нейроинформатике, так что когда в 2007 году Дональд Мичи погиб в автокатастрофе, во всех некрологах его заслуженно называли патриархом искусственного интеллекта в Великобритании.

Еще один «игрушечный» компьютер был разработан Дэнни Хиллисом. Этот американский ученый и изобретатель — фигура в компьютерном мире не просто легендарная, но даже культовая.
Он прославился как создатель и главный идеолог основанной в 1984 году знаменитой компании Thinking Machines, которая разработала самые производительные суперкомпьютеры своего времени Connection Machine. К сожалению, они оказались невостребованными тогдашним рынком, и спустя и лет компания прекратила работы в области суперкомпьютеров.
Однако мало кто помнит о его самой первой, и тоже весьма оригинальной, компьютерной разработке, начало которой относится к 1975 году, когда Хиллис еще учился в Массачусетском технологическом институте. Одним из заданий, полученных студентами его группы, было придумать и собрать из детского конструктора Tin-kertoy какое-либо цифровое устройство. После того, как один из студентов соорудил из деталей конструктора инвертор, который превращает «1» на входе в «о» и наоборот, а второй — логический элемент ИЛИ, стало понятно, что из них можно построить любую другую логическую функцию и, следовательно, любую логическую схему.

Правда, поначалу Хиллис склонялся к мысли построить робота, но затея эта показалась слишком сложной да и требовала немалых затрат, превышавших финансовые возможности студентов. Однако спустя какое-то время директор одного из выставочных центров предложил финансирование, и вскоре Хиллис и его друзья изготовили первый вариант компьютера для игры в «крестики-нолики». Он имел форму куба со стороной 1 метр и был собран из соединенных в логические схемы деталей конструктора. О сделанном ходе компьютер сигнализировал поднимающимся флажком (их было 9, по числу клеток игрового поля). Машина была крайне сложна и требовала тщательной наладки — так что, когда ее в разобранном виде доставили на выставку и вновь собрали, она так и не заработала. Сегодня это уникальное изделие находится в одном из компьютерных музеев США.
В 1979 году из того же выставочного центра поступило предложение — изготовить новый компьютер. Хотя к этому времени Хиллис и его коллеги уже окончили университет и работали не только на разных фирмах, но даже в разных странах, предложение их заинтересовало.
Началась совместная работа — хотя общение в основном шло по телефону.
На этот раз было решено уделить особое внимание надежности — отсюда вытекало требование простоты конструкции. Требовалось решить три основные задачи: как задавать позицию на игровом поле, как ее распознавать и как выбирать следующий ход компьютера. Однако общее число возможных позиций в игре весьма велико, и было необходимо каким-то образом его уменьшить. Понятно, что симметричные позиции можно рассматривать как одну, но ведь надо было научить компьютер такие позиции распознавать. Дерево игры было досконально изучено с помощью специально написанной программы, и было замечено, что многие ходы являются вынужденными: например, если в одном ряду уже стоят два крестика, то, чтобы не проиграть, соперник должен поставить свой нолик именно в этом ряду. Тщательный анализ позволил сократить количество подлежащих рассмотрению значащих позиций до 48.

После этого началась конструкторская работа. Каждую позицию на игровом поле решили представлять осью с набором насаженных на нее колес (назовем ее осью игровых позиций или просто осью позиций). Ось разделена на 9 равных смежных частей, хранящих информацию о состоянии одной из 9 клеток игрового поля. Каждая часть, в свою очередь, содержит три равных отрезка. Отрезок может быть занят колесиком или оставаться незанятым. Если колесики находятся в отрезках 2 и з, это означает, что в соответствующей клетке записан «крестик», если они находятся в отрезках 1 и 2 — «нолик», а в отрезках 1 и з — что клетка пуста (кроме того, отсутствие всех трех колесиков означает, что содержимое клетки не имеет значения). Всего таких осей в машине 48, по количеству значащих позиций. Они закреплены в жесткой установленной вертикально раме.

Задача распознавания позиции была решена следующим образом. В конструкцию была введена еще одна ось — ось управления, состоящая из 9 секций равной длины, каждая из которых содержит одно колесико и соответствует одной клетке игрового поля. В зависимости от содержимого клетки колесико может находиться в одном из трех положений. Оператор приводит ось управления в движение, и она начинает перемещаться в вертикальной плоскости вдоль набора осей позиций. Ось управления при этом стремится повернуться так, чтобы выступающие из ее колесиков стержни заняли положение, перпендикулярное плоскости движения. Однако при несовпадении состояний оси позиций и оси управления этого не происходит — хотя бы один из стержней удерживается колесиком на оси позиций, что не позволяет оси управления повернуться.
Если же их состояния совпадают, то ось управления поворачивается, и при этом посредством весьма хитроумного механизма освобождает сигнальный флажок, находящийся напротив соответствующей оси позиций. Флажок поворачивается и закрывает написанную на вертикальной бумажной ленте цифру. Эта цифра и означает, в какую клетку компьютер сделает свой следующий ход.
К сожалению, позднее «игрушечный компьютер» был разобран (кстати, для его изготовления потребовалось 30 комплектов конструктора по 250 деталей в каждом). Сегодня о нем стоит вспомнить не только потому, что это был первый оригинальный проект будущего выдающегося конструктора). «Игрушечный компьютер» заставляет задуматься о том, что же такое компьютер вообще. Сегодня мы привыкли ассоциировать компьютер с электроникой. Но ведь компьютер может быть построен из самых разных элементов — не только механических (как в данном случае), электрических или оптических, но даже гидравлических или пневматических. И даже — из пока непривычных нам биологических.
По прогнозам ученых, в ближайшие 15–20 лет появятся вычислительные машины совершенно нового типа — молекулярные компьютеры, которые будут в миллиарды раз производительнее, чем нынешние электронные компьютеры. Вместо кремниевых транзисторов в них будут использоваться органические и другие молекулы. Правда, не любые, а имеющие несколько (не менее двух) устойчивых состояний. Изменение их состояния под влиянием различных внешних воздействий (например, химических реакций) в некотором смысле эквивалентно переключению из «о» в «1» и обратно. А это значит, что из таких молекул можно создать устройства, моделирующие работу любой логической схемы. Считается, что впервые идея молекулярного компьютера была реализована в 1994 году американским исследователем Леонардом Аделманом. В своих опытах он показал, как можно успешно решать сложные переборные задачи из области теории графов, и в частности, известную «задачу коммивояжера», в которой требуется найти кратчайший маршрут обхода всех вершин графа. Оказалось, что все варианты решения (каждый из которых закодирован одной из нитей ДНК) могут быть получены в лабораторной пробирке посредством ряда биохимических реакций, после чего остается лишь отделить нить ДНК, соответствующую решению.
С тех пор появилось множество аналогичных работ и были предложены методы решения многих других задач. Мы не будем их описывать и говорить о многочисленных все еще нерешенных проблемах. Отметим лишь, что, пожалуй, одним из наиболее интересных результатов, достигнутых к настоящему времени, является создание ДНК-компьютера, играющего в «крестики-нолики» против человека.
В ноябре 2006 года журнал «Nano Letters» опубликовал статью группы американских ученых, в которой был описан предназначенный для этой цели ДНК-компьютер MAYA-II. Аббревиатура MAYA (Molecular Array of YES and AND gates) переводится как «матрица молекулярных логических элементов ДА и И», а цифра «II» означает, что это вторая версия устройства (первый, гораздо более простой компьютер MAYA I был построен за несколько лет до этого).

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

Комментирование и размещение ссылок запрещено.

Комментарии закрыты.