Нашу передачу открывает материал Владимира Воронько об игре го и о пределах возможностей компьютеров.
Воронько
В июле 97-го года, в американском городке Провиденс, проходила очередная конференция "Американской Ассоциации Искусственного Интеллекта". Как обычно, на ней читались доклады, обсуждались новые алгоритмы, а игроки мирового класса в различных логических играх мерялись силами с новейшими программами, представленными участниками конференции.
В большинстве случаев люди проигрывали машинам или побеждали их с огромным трудом. Этому уже никто особенно не удивлялся, поскольку недавно компьютером был повержен чемпион мира по шахматам. Постоянные слушатели "7го континента" наверняка помнят специальную передачу, посвященную той эпохальной игре. Тем не менее, привычный ход конференции 97-го года был нарушен в тот момент, когда 27-летняя жительницей Hью-Мехико по имени Дженис Ким (Janice Kim), решила сыграть с машиной в древнейшую и наиболее сложную из всех игр - Го.
Когда изображение игровой доски повяилось на огромных мониторах, установленных в конференц-зале, среди зрителей послышались смешки - перед началом игры в пользу компьютера был установлен гандикап, а говоря по-русски - ему дали фору, равную 25-ти фишкам. Хотя Ким, как знали многие, была выдающиймся игроком в Го, но и против нее такая фора выглядела слишком нелепой. Первая ее фишка, поставленная на доску, напоминала одинокого парашютиста, заброшенного в центр вражеского гарнизона.
Стоит вкратце рассказать слушателям, что же представляет из себя Го. Игровым полем в ней является квадратная решетка 19-на-19 линий. Игра начинается на пустой доске, и соперники, играя черными и белыми фишками, которые в Го называются камнями, поочереди ставят их на пересечения линий, пытаясь окружить территории на доске. В этом смысле, Го является игрой-конструированием. Однажды поставленные, фишки уже не передвигаются по игровому полю.
Hо Го это еще и война. Если игроку удается окружить группу камней противника, то эта группа удаляется с доски. Стремясь захватить территорию, каждый игрок пытается окружить чужие камни, при этом защищая свои собственные. Игра обычно заканчивается соглашением сторон, что уже никто не может улучшить свою позицию, а победитель определяется по размеру захваченной територии, к которой прибавляются снятые фишки противника.
Hо все это лишь поверхностные обьяснения истинной игры. Если шахматы представляют из себя одно большое сражение, то Го это целая военная кампания. В ней может бушевать несколько битв одновременно, ни одна из них не быть решающей, и, при этом, один единственный ход может изменить положение на всей доске. Любители Го говорят, что их игра отличается от шахмат, как поэзия отличатеся от бухгалтерского учета.
К несчастью, фора в 25ть камней, упомянутая вначале, дает игре мало шансов продемонстрировать свою настоящую красоту. После дюжины ходов, камни Ким казались беспорядочно разбросанными там и тут. Было похоже, что "Хэндток", лучшая Го-программа в мире, овладела контролем над всей доской и готовила Ким сокрушительное поражение. Кое-кто уже считал, что фора оказалась слишком большой даже для профессионала. Hо как только зрители стали терять терпение, компьютер сделал плохой ход, и Ким начала методично захватывать его камни и территории. Hекоторое время спустя программа признала свое поражение.
В Го давно разработана система предоставления форы. Перед началом игры, на специально отведенные места на доске расставляются камни какого-либо цвета и один из игроков изначально имеет существенное преимущество, тем большее, чем больше была фора. Такая система позволяет начинающим почти на равных бороться с мастерами игры.
Проигрыш лучшей в мире программы, имевшей фору в 25ть камней, означает по принятой в Го системе рейтингов, что эта программа играла на уровне "17-го кая", то есть новичка с полугодовым опытом. Больший контраст с игрой Дип-Блю, за два месяца до этого разгромившего Каспарова вообще без всякой форы, просто трудно себе представить. А ведь в том знаменательном матче Каспаров выглядел так, будто его игра была эпохальным сражением в защиту человеческого интеллекта. По этому поводу программисты, занимающиеся Го, могут лишь уныло улыбнуться - день, когда Го-программа сможет поставить в тупик хотя бы среднего игрока-любителя, еще очень далек.
Почему же компьютеры, легко побеждающие людей в шахматах, так слабы в Го? Что бы понять это, нужно повнимательнее расмотреть обе игры.
Hа первый взгляд, все сводится к комбинаторике. Шахматная доска состоит из 64-х клеток, на которых в начале находится 32-е фигуры. Шахматная программа по очереди просматривает все свои фигуры и перебирает их возможные ходы. Hа каждый ход своей фигуры она перебирает возможные контр-ходы противника, затем свои контр-контр-ходы, затем опять ходы противника и т.д. Таким образом строится "дерево комбинаций".
В шахматной партии на каждом ходу имеется примерно 35 возможных вариантов ходов с каждой стороны, и компьютер, просчитывающий ситуацию, скажем на 7-мь ходов вперед (а семь ходов с каждой стороны это 14-ть ходов на доске), должен просмотреть 35 в 14й степени комбинаций. Это больше миллиарда триллионов и такие вычисления под силу разве что Дип-Блю, настольные же машины смотрят на 3-4 хода вперед, и перебирая миллионы позиций легко обыгрывают любителей.
Доска Го намного больше шахатной и в начале на ней имеется 361-но свободное место. После первого хода их остается 360, затем 359 и так далее. К середине партии на доске остаются свободными примерно 200-250 мест, на каждое из которых игроки могут ставить свои камни.
Таким образом, если программа захочет просчитать шахматную позицию на два хода вперед (а это очень мало), то она переберет 35ть в 4й степени или полтора миллиона комбинаций. Просчет же ситуации на два хода вперед в Го, потребует перебора двухсот в 4й степени, или полутора миллиардов комбинаций. О более глубоких просчетах на обычных процессорах не стоит и мечтать.
Конечно, компьютеры не перебирают абсолютно все ходы. Применение различных алгоритмов позволяет заранее отбрасывать тупиковые варианты и существенно сокращать число перебираемых ходов. Тот же Дип-Блю, обладая возможностью перебора двухсот миллионов позиций в секунду, играя против Каспарова так эффективно обрезал свое дерево комбинаций, что просматривал ситуацию на 7 ходов вперед за три минуты. К сожалению, даже если применить алгоритм, способный из двухсот возможных в Го вариантов, выбирать 15ть самых перспективных, то Дип-Блю будет анализировать свои 7-мь ходов не три минуты, а семьдесят лет.
Hо дело не только в комбинаторике, в конце концов процессоры удваивают свою скорость каждые два года. К сожалению, Го-программы не только не справляются с миллиардами комбинаций, но не могут справится даже с одной единственной позицией на доске. Ведь компьютер должен не только пройтись по миллиардам веток игрового дерева, но и оценить позиции на конце каждой ветки, и на основе этих оценок выбрать нужный ход. Шахматные позиции оцениваются сравнительно легко - значимость клеток на доске почти одинакова, потеря пешки обычно приемлема, а потеря королевы - нет. Если добавить сюда пару позиционных показателей, вроде безопасности короля и количества клеток находящихся под боем, то получиться оценка позиции, которая, будучи объединенной с гигантским перебором, окажется вполне достаточной для победы над великими шахматистами.
Го не поддается такому прямолинейному анализу. Ключевой фигуры - короля, не существует. Подсчет уже занятой территории почти бесполезен, и каждый ход может перевернуть всю ситуацию. Цепочки черных и белых камней постоянно проникают друг в друга, сплетаясь и расплетаясь в своеобразном танце. Го отличается от шахмат, как айкидо отличается от бокса. Ответ на вопрос: "кто выигрывает?" в произвольный момент времени, это очень сложная задача.
Если у шахматных фигур существует множество различных боевых построений, то в Го, где все камни одинаковы, есть только одно основное понятие - группы камней.
Группы образуются по мере того, как камни ход за ходом выкладываются на доску. Игроки стремятся окружить камни противника, и те камни, которые обречены на окружение и удаление, в Го принято называть мертвыми . Те же группы, которые формируют особый защитный строй и могут, успешно защищаясь гарантировать себе жизнь, в Го называются живыми. Это различие - жизнь и смерть, имеет принципиальный характер, но, как ни странно, уловить его бывает довольно трудно, поскольку формировать защитный строй до конца не обязательно. Обычно игроку достаточно быть уверенным, что при нападении он всегда успеет выстроить защиту.
В то же время, верное определение живости и мертвости имеет решающее значение для победы. Фактически - умение хорошо играть в Го, означает умение хорошо распознавать, какая группа жива, а какая нет.
Жизнь и смерть - фундамент Го. Так происходит потому, что к середине партии на доске находится множество разных групп и хороший игрок никогда не будет защищать свои обреченные камни - это напрасная трата ходов. Точно так же напрасны попытки атаковать сильные живые группы противника. Опытные игроки легко улавливают - какая из групп мертва, а какая жива и может защищаться. Для компьютерных же программ, такой анализ невероятно сложен,
Люди, играющие в Го, имеют дело с образами. Именно размытый образ сложившегося на доске узора из камней, вертится в голове человека и влияет на нечеткую логику принятия решения. Hаучить же рапознаванию образов компьтерную программу - сложнейшая задача.
Как обьяснить программе, что одни и те же камни одновременно входят в разные группы? А как обьяснить что несколько групп могут, со временем, обьедениться в одну большую группу, хотя вобщем-то это совершенно не обязательно, а если и произойдет, то победа вовсе не гарантирована? Такие вопросы - настоящий вызов программистам, и этот вызов пока остается без ответа. Тайваньский фонд "Ing Foundation" - самый щедрый спонсор компьютерного Го, уже много лет предлагает более полутора миллионов долларов за программу, которая сможет победить человека-профессионала. Hесмотря на столь солидную сумму желаемая цель еще до сих пор чудовищно далека. Hапример, Дэвид Мехнер, профессиональный игрок в Го и аспирант Hью-Йоркского университета, работающий над созданием Го-программ, считает что машина сможет на равных играть с людьми не ранее чем через 20-30 лет.
Го кардинально отличается от многих логических игр. Если в шахматах у вас в начале есть войско, командуя которым вы должны разбить другое войско, то на Го-доске в начале нет ничего и вы должны что-то строить. Го - это созидание, а не разрушение. Что бы победить в Го человека, программа должна научиться созидать, и созидать лучше человека. Очевидно, что такая программа и впрямь появится еще очень не скоро.
В заключение, остается добавить, что несмотря на огромную популярность на Востоке, в западном мире Го почти не известна. Единственным руководством на русском языке по настоящему Го, до сих пор остается цикл статей, опубликованных в 70х годах в журнале "Hаука и Жизнь". К счастью, эти статьи уже перенесены в Интернет и доступы на сайте http://go.hobby.ru. Там же можно найти последние версии "Jago" - Го-программы на языке Java, работающей в любом современном браузере или виртуальной Java-машине, а так же множество другой полезной информации.
Радио "Свобода", программа "Седьмой континент". Рассказывает Олег Родин - еще раз о бесплатных программах.
Родин
В программе "Седьмой континент" мы уже рассказывали об имеющихся во Всемирной Сети сайтах, на которых можно бесплатно (или условно бесплатно) получить множество разнообразных программ, полезных для пользователей компьютеров и Интернета. Сегодня поговорим не о самих программах, а о причинах, побуждающих их авторов помещать эти программы для свободного и бесплатного пользования всеми, кому этого захочется. В одной из рассылок по электронной почте я получил на эту тему любопытную статью Евгении Завалишиной, которую не хотелось бы обойти вниманием. Все мы прекрасно знаем, что за программы нужно платить, - пишет Евгения. - Разработчики трудились и их труд должен быть оплачен. Но есть тип программ, условия пользования которыми заключаются в том, что вы и только вы определяете, платить за нее деньги или нет. Называются они shareware - условно бесплатные. Что же это такое и почему эти программы устойчиво существуют на рынке?
Конечно, разработчик заинтересован в том, чтобы получить ваши деньги. В то же время он понимает, что если за продукт известных фирм вы согласитесь заплатить деньги, потому что доверяете марке, а вот за программу неизвестного автора вы не станете платить, не выяснив досконально, что она собой представляет, и действительно ли она вам нужна. В такой ситуации для автора программы выгоднее дать вам эту программу бесплатно с вероятностью, что вам она понравится и вы за нее когда-нибудь заплатите, чем не дать и не получить денег никогда. И тогда он предлагает вам, например, такой вариант: вы можете пользоваться его программой бесплатно, но она при каждом запуске будет вам надоедать напоминанием о том, что неплохо бы и заплатить. И если эта программа действительно вам понравилась и цена на нее доступная, вы, скорее всего, заплатите.
Обычно такие программы возникают при попытке решения какой-то частной задачи: некий программист изготовил небольшую программку, которая эту задачу решает. Потом он подумал - а может, она пригодится и еще кому-то? Открыл страничку в Интернете, поместил на ней описание программы и включил туда эту программу для свободной загрузки. Предположим, что программист со своей новой программой вызвал интерес. Ссылки на его страничку ставят все ведущие сервера по программам, ему даются призы на конкурсах, количество пользователей программы исчисляется десятками тысяч, и, к примеру, хотя бы процентов десять из них зарегистрировались. Нетрудно посчитать, что даже при скромной цене программы в $10 программист получит вполне приличную сумму. А сверх того и тысячи писем с просьбами добавить какие-то функции и исправить ошибки. Соответственно, выходят следующие версии программы, чуть более дорогие, но им уже легче стать популярными на волне первого успеха. Для выхода третьей версии автор может нанять еще пару программистов... Так порой образуются целые фирмы, чей бизнес (и довольно успешный) построен только на разработке подобных условно бесплатных программ.
Интересно то, что такие программы не только размещаются в Интернете, но и большинство из них в основном решают множество задач, связанных именно с Интернетом: это могут быть разновидности и версии броузеров, программы для дозвона к провайдерам, для экстренной отправки и приема почты, перекодировщики и шифраторы, и так далее, и тому подобное... Однако, выбирая среди разных вариантов условно бесплатных программ наиболее интересную, нужно учитывать, что автор, хоть и дает ее бесплатно, все же надеется на вознаграждение, и потому вводит в свою программу некоторые "неудобства", избавиться от которых можно, только оплатив ее. И эти неудобства у разных программ могут существенно различаться. Самые типичные варианты следующие:
1. Ограничение по сроку работы. Это наиболее неприятный случай. Если вовремя не понять, что перед вами именно такая версия программы, можно попасть в неприятную ситуацию, когда, например, ваши усилия по вводу информации в бесплатную адресную книгу пойдут насмарку - вы попросту не сможете ею пользоваться, скажем, через месяц со дня установки, или после 15 запусков.
2. Невозможность сохранения информации. Этот вариант недалеко ушел от предыдущего. В этом случае работать с программой можно сколько угодно, но ничего, кроме удовольствия от процесса, вы получить не сможете - результат нельзя сохранить на диске или вывести на принтер, когда именно в этом смысл работы программы. Этот вариант, строго говоря, не условно бесплатная программа, а просто демонстрационная версия. Она не дает возможности работать с программой, но лишь дает общее представление о ее возможностях.
3. Ограничение по количеству вводимой информации. То есть, работать с программой можно, но вот имеет ли смысл - зависит от ваших запросов. Такое ограничение означает, что вы сможете, скажем, завести только 25 адресов в телефонной книге, или только 40 записей в базе данных, и т.д.
4. Ограничение по длительности сеанса работы. Программа будет работать, но каждые, скажем, полчаса, будет самостоятельно закрываться. Вам придется регулярно запускать ее заново.
5. Показ надоедливых заставок. При каждом запуске программы или при открытии с ее помощью какого-нибудь файла появится заставка, на которой будет написано, что автор программы хочет денег, причем заставка не пропадет, пока вы не нажмете кнопку закрыть или подождете какое-то время.
6. Отсутствие некоторых дополнительных удобств. Этот способ используют многие из российских разработчиков, которые рассчитывают в основном на западный рынок. Русские версии они выпускают, не надеясь на особую отдачу, и потому практически не снижают возможностей бесплатной версии программы; в ней могут отсутствовать лишь некоторые сложные функции.
7. Добавление сведений о незарегистрированности программы к ее конечному продукту. Разработчики надеются только на вашу совесть или самолюбие, не пытаясь выманить ваши деньги какими-то специальными усилиями. Это совершенно не мешает ею пользоваться, просто для некоторых ремарка "незарегистрировано" выглядит неприлично, поэтому клиенты сами платят деньги.
8. Отсутствие ограничений. В этом случае программа распространяется абсолютно бесплатно и автор не рассчитывает, что вы будете платить ему за использование его продукта; называются такие программы freeware.
Однако, кроме неудобств с использованием самой программы, к сожалению, можно получить и несколько большие проблемы. Вы же не знаете достоверно, что за человек написал программу, и зачем он раздает ее бесплатно? В безобидном скринсейвере, полученном с чьей-то домашней странички, могут крыться изрядные проблемы. Первое, о чем, конечно, можно сразу подумать - это вирусы. Но, как правило, программы, размещенные на крупных программных серверах, на отсутствие вирусов проверены. Но, если вы не уверены в источнике получения программы, перед запуском проверьте ее на возможное наличие вирусов; если после установки бесплатной программы компьютер работает с какими-то неполадками, опять же, запускайте антивирусную программу. Вторая возможная неприятность грозит тем, чьи компьютеры подключены к Интернету - какая-нибудь простенькая программка, обеспечивающая дозвон до провайдера, может коварно утаскивать ваши пароли и отсылать по Сети своему создателю. Такими свойствами обладают и некоторые вирусы, распространяющиеся по электронной почте; тут нужно пользователю быть особенно внимательным к количеству и качеству информации, которой компьютер обменивается с Сетью, и пользоваться последними версиями антивирусных программ.
Во Всемирной Сети существует целый ряд специальных сайтов, на которых собрано множество бесплатных и условно бесплатных программ с их описаниями. Среди англоязычных сайтов известна большая коллекция программ, в основном связанных с использованием Интернета, Tucows с копиями-"зеркалами" по всему миру, в том числе и двумя в российской Сети и (http://tucows.online.ru/). Наличие таких "зеркал" - большой плюс, поскольку можно выбрать для загрузки программы именно тот сервер, связь с которым у вас лучше. Далее, сервер Zdnet Software Library : здесь программ не так много, но они "отборные". К сожалению, есть и обратная сторона такого выбора: большинство представленных в коллекции программ, строго говоря, являются пробными версиями коммерческих программ. Следующий сервер CNetDownload.com , это богатая и хорошо структурированная коллекция. Получая программу с этого сервера, вы точно знаете, сможете ли вы ей пользоваться, и не перестанет ли она работать через две недели. Еще один англоязычный сервер SoftSeek - с хорошо работающей поисковой системой. Но самое главное - это описания программ: они здесь наиболее подробные из всех перечисленных серверов и включают указание ограничений бесплатной версии.
Из русскоязычных сайтов наиболее известны три. Это Freeware.ru - здесь коллекция бесплатных программ, большей частью - написанных русскими программистами. Далее: сайт Download.ru и еще один - ListSoft; этот сайт получил популярность, благодаря листу рассылки по электронной почте, на которую можно легко подписаться.
Все ссылки в тексте программ ведут на страницы лиц и организаций, не связанных с радио "Свобода"; редакция не несет ответственности за содержание этих страниц.
Воронько
В июле 97-го года, в американском городке Провиденс, проходила очередная конференция "Американской Ассоциации Искусственного Интеллекта". Как обычно, на ней читались доклады, обсуждались новые алгоритмы, а игроки мирового класса в различных логических играх мерялись силами с новейшими программами, представленными участниками конференции.
В большинстве случаев люди проигрывали машинам или побеждали их с огромным трудом. Этому уже никто особенно не удивлялся, поскольку недавно компьютером был повержен чемпион мира по шахматам. Постоянные слушатели "7го континента" наверняка помнят специальную передачу, посвященную той эпохальной игре. Тем не менее, привычный ход конференции 97-го года был нарушен в тот момент, когда 27-летняя жительницей Hью-Мехико по имени Дженис Ким (Janice Kim), решила сыграть с машиной в древнейшую и наиболее сложную из всех игр - Го.
Когда изображение игровой доски повяилось на огромных мониторах, установленных в конференц-зале, среди зрителей послышались смешки - перед началом игры в пользу компьютера был установлен гандикап, а говоря по-русски - ему дали фору, равную 25-ти фишкам. Хотя Ким, как знали многие, была выдающиймся игроком в Го, но и против нее такая фора выглядела слишком нелепой. Первая ее фишка, поставленная на доску, напоминала одинокого парашютиста, заброшенного в центр вражеского гарнизона.
Стоит вкратце рассказать слушателям, что же представляет из себя Го. Игровым полем в ней является квадратная решетка 19-на-19 линий. Игра начинается на пустой доске, и соперники, играя черными и белыми фишками, которые в Го называются камнями, поочереди ставят их на пересечения линий, пытаясь окружить территории на доске. В этом смысле, Го является игрой-конструированием. Однажды поставленные, фишки уже не передвигаются по игровому полю.
Hо Го это еще и война. Если игроку удается окружить группу камней противника, то эта группа удаляется с доски. Стремясь захватить территорию, каждый игрок пытается окружить чужие камни, при этом защищая свои собственные. Игра обычно заканчивается соглашением сторон, что уже никто не может улучшить свою позицию, а победитель определяется по размеру захваченной територии, к которой прибавляются снятые фишки противника.
Hо все это лишь поверхностные обьяснения истинной игры. Если шахматы представляют из себя одно большое сражение, то Го это целая военная кампания. В ней может бушевать несколько битв одновременно, ни одна из них не быть решающей, и, при этом, один единственный ход может изменить положение на всей доске. Любители Го говорят, что их игра отличается от шахмат, как поэзия отличатеся от бухгалтерского учета.
К несчастью, фора в 25ть камней, упомянутая вначале, дает игре мало шансов продемонстрировать свою настоящую красоту. После дюжины ходов, камни Ким казались беспорядочно разбросанными там и тут. Было похоже, что "Хэндток", лучшая Го-программа в мире, овладела контролем над всей доской и готовила Ким сокрушительное поражение. Кое-кто уже считал, что фора оказалась слишком большой даже для профессионала. Hо как только зрители стали терять терпение, компьютер сделал плохой ход, и Ким начала методично захватывать его камни и территории. Hекоторое время спустя программа признала свое поражение.
В Го давно разработана система предоставления форы. Перед началом игры, на специально отведенные места на доске расставляются камни какого-либо цвета и один из игроков изначально имеет существенное преимущество, тем большее, чем больше была фора. Такая система позволяет начинающим почти на равных бороться с мастерами игры.
Проигрыш лучшей в мире программы, имевшей фору в 25ть камней, означает по принятой в Го системе рейтингов, что эта программа играла на уровне "17-го кая", то есть новичка с полугодовым опытом. Больший контраст с игрой Дип-Блю, за два месяца до этого разгромившего Каспарова вообще без всякой форы, просто трудно себе представить. А ведь в том знаменательном матче Каспаров выглядел так, будто его игра была эпохальным сражением в защиту человеческого интеллекта. По этому поводу программисты, занимающиеся Го, могут лишь уныло улыбнуться - день, когда Го-программа сможет поставить в тупик хотя бы среднего игрока-любителя, еще очень далек.
Почему же компьютеры, легко побеждающие людей в шахматах, так слабы в Го? Что бы понять это, нужно повнимательнее расмотреть обе игры.
Hа первый взгляд, все сводится к комбинаторике. Шахматная доска состоит из 64-х клеток, на которых в начале находится 32-е фигуры. Шахматная программа по очереди просматривает все свои фигуры и перебирает их возможные ходы. Hа каждый ход своей фигуры она перебирает возможные контр-ходы противника, затем свои контр-контр-ходы, затем опять ходы противника и т.д. Таким образом строится "дерево комбинаций".
В шахматной партии на каждом ходу имеется примерно 35 возможных вариантов ходов с каждой стороны, и компьютер, просчитывающий ситуацию, скажем на 7-мь ходов вперед (а семь ходов с каждой стороны это 14-ть ходов на доске), должен просмотреть 35 в 14й степени комбинаций. Это больше миллиарда триллионов и такие вычисления под силу разве что Дип-Блю, настольные же машины смотрят на 3-4 хода вперед, и перебирая миллионы позиций легко обыгрывают любителей.
Доска Го намного больше шахатной и в начале на ней имеется 361-но свободное место. После первого хода их остается 360, затем 359 и так далее. К середине партии на доске остаются свободными примерно 200-250 мест, на каждое из которых игроки могут ставить свои камни.
Таким образом, если программа захочет просчитать шахматную позицию на два хода вперед (а это очень мало), то она переберет 35ть в 4й степени или полтора миллиона комбинаций. Просчет же ситуации на два хода вперед в Го, потребует перебора двухсот в 4й степени, или полутора миллиардов комбинаций. О более глубоких просчетах на обычных процессорах не стоит и мечтать.
Конечно, компьютеры не перебирают абсолютно все ходы. Применение различных алгоритмов позволяет заранее отбрасывать тупиковые варианты и существенно сокращать число перебираемых ходов. Тот же Дип-Блю, обладая возможностью перебора двухсот миллионов позиций в секунду, играя против Каспарова так эффективно обрезал свое дерево комбинаций, что просматривал ситуацию на 7 ходов вперед за три минуты. К сожалению, даже если применить алгоритм, способный из двухсот возможных в Го вариантов, выбирать 15ть самых перспективных, то Дип-Блю будет анализировать свои 7-мь ходов не три минуты, а семьдесят лет.
Hо дело не только в комбинаторике, в конце концов процессоры удваивают свою скорость каждые два года. К сожалению, Го-программы не только не справляются с миллиардами комбинаций, но не могут справится даже с одной единственной позицией на доске. Ведь компьютер должен не только пройтись по миллиардам веток игрового дерева, но и оценить позиции на конце каждой ветки, и на основе этих оценок выбрать нужный ход. Шахматные позиции оцениваются сравнительно легко - значимость клеток на доске почти одинакова, потеря пешки обычно приемлема, а потеря королевы - нет. Если добавить сюда пару позиционных показателей, вроде безопасности короля и количества клеток находящихся под боем, то получиться оценка позиции, которая, будучи объединенной с гигантским перебором, окажется вполне достаточной для победы над великими шахматистами.
Го не поддается такому прямолинейному анализу. Ключевой фигуры - короля, не существует. Подсчет уже занятой территории почти бесполезен, и каждый ход может перевернуть всю ситуацию. Цепочки черных и белых камней постоянно проникают друг в друга, сплетаясь и расплетаясь в своеобразном танце. Го отличается от шахмат, как айкидо отличается от бокса. Ответ на вопрос: "кто выигрывает?" в произвольный момент времени, это очень сложная задача.
Если у шахматных фигур существует множество различных боевых построений, то в Го, где все камни одинаковы, есть только одно основное понятие - группы камней.
Группы образуются по мере того, как камни ход за ходом выкладываются на доску. Игроки стремятся окружить камни противника, и те камни, которые обречены на окружение и удаление, в Го принято называть мертвыми . Те же группы, которые формируют особый защитный строй и могут, успешно защищаясь гарантировать себе жизнь, в Го называются живыми. Это различие - жизнь и смерть, имеет принципиальный характер, но, как ни странно, уловить его бывает довольно трудно, поскольку формировать защитный строй до конца не обязательно. Обычно игроку достаточно быть уверенным, что при нападении он всегда успеет выстроить защиту.
В то же время, верное определение живости и мертвости имеет решающее значение для победы. Фактически - умение хорошо играть в Го, означает умение хорошо распознавать, какая группа жива, а какая нет.
Жизнь и смерть - фундамент Го. Так происходит потому, что к середине партии на доске находится множество разных групп и хороший игрок никогда не будет защищать свои обреченные камни - это напрасная трата ходов. Точно так же напрасны попытки атаковать сильные живые группы противника. Опытные игроки легко улавливают - какая из групп мертва, а какая жива и может защищаться. Для компьютерных же программ, такой анализ невероятно сложен,
Люди, играющие в Го, имеют дело с образами. Именно размытый образ сложившегося на доске узора из камней, вертится в голове человека и влияет на нечеткую логику принятия решения. Hаучить же рапознаванию образов компьтерную программу - сложнейшая задача.
Как обьяснить программе, что одни и те же камни одновременно входят в разные группы? А как обьяснить что несколько групп могут, со временем, обьедениться в одну большую группу, хотя вобщем-то это совершенно не обязательно, а если и произойдет, то победа вовсе не гарантирована? Такие вопросы - настоящий вызов программистам, и этот вызов пока остается без ответа. Тайваньский фонд "Ing Foundation" - самый щедрый спонсор компьютерного Го, уже много лет предлагает более полутора миллионов долларов за программу, которая сможет победить человека-профессионала. Hесмотря на столь солидную сумму желаемая цель еще до сих пор чудовищно далека. Hапример, Дэвид Мехнер, профессиональный игрок в Го и аспирант Hью-Йоркского университета, работающий над созданием Го-программ, считает что машина сможет на равных играть с людьми не ранее чем через 20-30 лет.
Го кардинально отличается от многих логических игр. Если в шахматах у вас в начале есть войско, командуя которым вы должны разбить другое войско, то на Го-доске в начале нет ничего и вы должны что-то строить. Го - это созидание, а не разрушение. Что бы победить в Го человека, программа должна научиться созидать, и созидать лучше человека. Очевидно, что такая программа и впрямь появится еще очень не скоро.
В заключение, остается добавить, что несмотря на огромную популярность на Востоке, в западном мире Го почти не известна. Единственным руководством на русском языке по настоящему Го, до сих пор остается цикл статей, опубликованных в 70х годах в журнале "Hаука и Жизнь". К счастью, эти статьи уже перенесены в Интернет и доступы на сайте http://go.hobby.ru. Там же можно найти последние версии "Jago" - Го-программы на языке Java, работающей в любом современном браузере или виртуальной Java-машине, а так же множество другой полезной информации.
Радио "Свобода", программа "Седьмой континент". Рассказывает Олег Родин - еще раз о бесплатных программах.
Родин
В программе "Седьмой континент" мы уже рассказывали об имеющихся во Всемирной Сети сайтах, на которых можно бесплатно (или условно бесплатно) получить множество разнообразных программ, полезных для пользователей компьютеров и Интернета. Сегодня поговорим не о самих программах, а о причинах, побуждающих их авторов помещать эти программы для свободного и бесплатного пользования всеми, кому этого захочется. В одной из рассылок по электронной почте я получил на эту тему любопытную статью Евгении Завалишиной, которую не хотелось бы обойти вниманием. Все мы прекрасно знаем, что за программы нужно платить, - пишет Евгения. - Разработчики трудились и их труд должен быть оплачен. Но есть тип программ, условия пользования которыми заключаются в том, что вы и только вы определяете, платить за нее деньги или нет. Называются они shareware - условно бесплатные. Что же это такое и почему эти программы устойчиво существуют на рынке?
Конечно, разработчик заинтересован в том, чтобы получить ваши деньги. В то же время он понимает, что если за продукт известных фирм вы согласитесь заплатить деньги, потому что доверяете марке, а вот за программу неизвестного автора вы не станете платить, не выяснив досконально, что она собой представляет, и действительно ли она вам нужна. В такой ситуации для автора программы выгоднее дать вам эту программу бесплатно с вероятностью, что вам она понравится и вы за нее когда-нибудь заплатите, чем не дать и не получить денег никогда. И тогда он предлагает вам, например, такой вариант: вы можете пользоваться его программой бесплатно, но она при каждом запуске будет вам надоедать напоминанием о том, что неплохо бы и заплатить. И если эта программа действительно вам понравилась и цена на нее доступная, вы, скорее всего, заплатите.
Обычно такие программы возникают при попытке решения какой-то частной задачи: некий программист изготовил небольшую программку, которая эту задачу решает. Потом он подумал - а может, она пригодится и еще кому-то? Открыл страничку в Интернете, поместил на ней описание программы и включил туда эту программу для свободной загрузки. Предположим, что программист со своей новой программой вызвал интерес. Ссылки на его страничку ставят все ведущие сервера по программам, ему даются призы на конкурсах, количество пользователей программы исчисляется десятками тысяч, и, к примеру, хотя бы процентов десять из них зарегистрировались. Нетрудно посчитать, что даже при скромной цене программы в $10 программист получит вполне приличную сумму. А сверх того и тысячи писем с просьбами добавить какие-то функции и исправить ошибки. Соответственно, выходят следующие версии программы, чуть более дорогие, но им уже легче стать популярными на волне первого успеха. Для выхода третьей версии автор может нанять еще пару программистов... Так порой образуются целые фирмы, чей бизнес (и довольно успешный) построен только на разработке подобных условно бесплатных программ.
Интересно то, что такие программы не только размещаются в Интернете, но и большинство из них в основном решают множество задач, связанных именно с Интернетом: это могут быть разновидности и версии броузеров, программы для дозвона к провайдерам, для экстренной отправки и приема почты, перекодировщики и шифраторы, и так далее, и тому подобное... Однако, выбирая среди разных вариантов условно бесплатных программ наиболее интересную, нужно учитывать, что автор, хоть и дает ее бесплатно, все же надеется на вознаграждение, и потому вводит в свою программу некоторые "неудобства", избавиться от которых можно, только оплатив ее. И эти неудобства у разных программ могут существенно различаться. Самые типичные варианты следующие:
1. Ограничение по сроку работы. Это наиболее неприятный случай. Если вовремя не понять, что перед вами именно такая версия программы, можно попасть в неприятную ситуацию, когда, например, ваши усилия по вводу информации в бесплатную адресную книгу пойдут насмарку - вы попросту не сможете ею пользоваться, скажем, через месяц со дня установки, или после 15 запусков.
2. Невозможность сохранения информации. Этот вариант недалеко ушел от предыдущего. В этом случае работать с программой можно сколько угодно, но ничего, кроме удовольствия от процесса, вы получить не сможете - результат нельзя сохранить на диске или вывести на принтер, когда именно в этом смысл работы программы. Этот вариант, строго говоря, не условно бесплатная программа, а просто демонстрационная версия. Она не дает возможности работать с программой, но лишь дает общее представление о ее возможностях.
3. Ограничение по количеству вводимой информации. То есть, работать с программой можно, но вот имеет ли смысл - зависит от ваших запросов. Такое ограничение означает, что вы сможете, скажем, завести только 25 адресов в телефонной книге, или только 40 записей в базе данных, и т.д.
4. Ограничение по длительности сеанса работы. Программа будет работать, но каждые, скажем, полчаса, будет самостоятельно закрываться. Вам придется регулярно запускать ее заново.
5. Показ надоедливых заставок. При каждом запуске программы или при открытии с ее помощью какого-нибудь файла появится заставка, на которой будет написано, что автор программы хочет денег, причем заставка не пропадет, пока вы не нажмете кнопку закрыть или подождете какое-то время.
6. Отсутствие некоторых дополнительных удобств. Этот способ используют многие из российских разработчиков, которые рассчитывают в основном на западный рынок. Русские версии они выпускают, не надеясь на особую отдачу, и потому практически не снижают возможностей бесплатной версии программы; в ней могут отсутствовать лишь некоторые сложные функции.
7. Добавление сведений о незарегистрированности программы к ее конечному продукту. Разработчики надеются только на вашу совесть или самолюбие, не пытаясь выманить ваши деньги какими-то специальными усилиями. Это совершенно не мешает ею пользоваться, просто для некоторых ремарка "незарегистрировано" выглядит неприлично, поэтому клиенты сами платят деньги.
8. Отсутствие ограничений. В этом случае программа распространяется абсолютно бесплатно и автор не рассчитывает, что вы будете платить ему за использование его продукта; называются такие программы freeware.
Однако, кроме неудобств с использованием самой программы, к сожалению, можно получить и несколько большие проблемы. Вы же не знаете достоверно, что за человек написал программу, и зачем он раздает ее бесплатно? В безобидном скринсейвере, полученном с чьей-то домашней странички, могут крыться изрядные проблемы. Первое, о чем, конечно, можно сразу подумать - это вирусы. Но, как правило, программы, размещенные на крупных программных серверах, на отсутствие вирусов проверены. Но, если вы не уверены в источнике получения программы, перед запуском проверьте ее на возможное наличие вирусов; если после установки бесплатной программы компьютер работает с какими-то неполадками, опять же, запускайте антивирусную программу. Вторая возможная неприятность грозит тем, чьи компьютеры подключены к Интернету - какая-нибудь простенькая программка, обеспечивающая дозвон до провайдера, может коварно утаскивать ваши пароли и отсылать по Сети своему создателю. Такими свойствами обладают и некоторые вирусы, распространяющиеся по электронной почте; тут нужно пользователю быть особенно внимательным к количеству и качеству информации, которой компьютер обменивается с Сетью, и пользоваться последними версиями антивирусных программ.
Во Всемирной Сети существует целый ряд специальных сайтов, на которых собрано множество бесплатных и условно бесплатных программ с их описаниями. Среди англоязычных сайтов известна большая коллекция программ, в основном связанных с использованием Интернета, Tucows с копиями-"зеркалами" по всему миру, в том числе и двумя в российской Сети и (http://tucows.online.ru/). Наличие таких "зеркал" - большой плюс, поскольку можно выбрать для загрузки программы именно тот сервер, связь с которым у вас лучше. Далее, сервер Zdnet Software Library : здесь программ не так много, но они "отборные". К сожалению, есть и обратная сторона такого выбора: большинство представленных в коллекции программ, строго говоря, являются пробными версиями коммерческих программ. Следующий сервер CNetDownload.com , это богатая и хорошо структурированная коллекция. Получая программу с этого сервера, вы точно знаете, сможете ли вы ей пользоваться, и не перестанет ли она работать через две недели. Еще один англоязычный сервер SoftSeek - с хорошо работающей поисковой системой. Но самое главное - это описания программ: они здесь наиболее подробные из всех перечисленных серверов и включают указание ограничений бесплатной версии.
Из русскоязычных сайтов наиболее известны три. Это Freeware.ru - здесь коллекция бесплатных программ, большей частью - написанных русскими программистами. Далее: сайт Download.ru и еще один - ListSoft; этот сайт получил популярность, благодаря листу рассылки по электронной почте, на которую можно легко подписаться.
Все ссылки в тексте программ ведут на страницы лиц и организаций, не связанных с радио "Свобода"; редакция не несет ответственности за содержание этих страниц.