Адвансед

 

шахматы

Меню

Появление шахматных программ

Закон развития шахмат

Шахматы - пробный камень моделирования мышления

Адвансер или оператор (статья Кевина)

Адванс для начинающих. Краткое руководство

Адвансер или оператор (статья Кевина)



 

Появление шахматных программ

 

Развитие шахматного программирования как часть искусственного интеллекта началось с одной проблемы, которая сегодня исчезла, и уже никто ею даже не интересуется, а окончилось другой проблемой, которая становится все более и более актуальной.

Первая проблема – само предназначение вычислительных машин. Компьютер – сейчас это уже русское слово, тоже от слова "вычислять", по-русски "электронные вычислительные машины" были как-то в оппозиции аналоговым вычислительным машинам, которые тогда были. И вот сама идея, что эти машины можно использовать не только для расчетов, а и для информационных задач, была, как это ни смешно сказать (т. к. год ее рождения 1948-й), серьезной проблемой. И Клод Шеннон, один из родоначальников информатики, пытался доказать, что машина, обладающая огромной вычислительной мощностью, на самом деле предназначена для информационных задач, а не для вычислений. В качестве примера такой информационной задачи он объявил шахматную программу.
Он сказал, что компьютеры могут играть в шахматы, а уж эта задача никак не вычислительная. Он ввел термин "символическое программирование" в отличие от "численного программирования" (термин не прижившийся). Эта борьба продолжалась очень недолго, но что оказалось удивительным: первая вычислительная машина, созданная на белом свете, была информационной. Она была очень засекречена, сейчас о ней стало известно, она была создана Аланом Тьюрингом, британской разведкой, для расшифровки немецких сообщений, называлась "Энигмой".

Сейчас об этом пишут романы. "Энигма" была рассекречена только в 88-м году, а до этого об ее существовании никто не знал.
Приходилось доказывать, что машины могут выполнять чисто информационные алгоритмы, искать решения и т. д.

Вторым человеком, сказавшим о шахматных программах как о примере, был тот же самый Алан Тьюринг. Загорая с Джоном МакКарти на пляже в Сан-Диего, они решили, что вообще машины могут решать задачи, которые принято считать интеллектуальными. И тогда они придумали сам термин "искусственный интеллект" на этом пляже. Тогда же возник и тест Тьюринга, который сейчас проходят в школах. И тогда же Алан Тьюринг набросал первый алгоритм шахматной программы, который не был никогда реализован как программа, но был реализован как алгоритм.

В 1958 г. донеслись слухи о создании первой, по-настоящему играющей шахматной программы. Владимир Львович Арлазаров сделал эту шахматную программу. Интересно, что первые центры развития шахматных программ, как нарочно, совпадают с центрами развития атомного оружия. В Москве это был Институт теоретической и экспериментальной физики, в Америке – Лос-Аламосская лаборатория, в Англии это была лаборатория Резерфорда. И понятно – почему. Потому что в то время, в начале 50-х годов, всю лучшую вычислительную технику отдавали физикам-ядерщикам. Поскольку оставалось время от основных занятий на машине, в свободное время они развлекались интересными вещами.

А что может быть интереснее, чем игровые программы? И поэтому, несмотря на начальство, прикрываясь крупными авторитетами, были сделаны такие первые шахматные программы.

В 1967 г. состоялся первый матч шахматных программ, первые соревнования шахматных программ. И с того момента начался самый длительный в истории кибернетики научный эксперимент. Сначала ежегодные турниры, североамериканские турниры, потом раз в три года – чемпионат мира среди шахматных программ. А в 1967 г. был матч по переписке между Стенфордским университетом, где тот же самый Джон МакКарти, отец искусственного интеллекта, автор языка Лисп, прикрывал молодого своего аспиранта Котка (Kotok), который сделал тамошнюю первую шахматную программу, с нашей стороны Институтом теоретической и экспериментальной физики, где первый советский программист Александр Семенович Кронрод, прикрывал своим авторитетом программы тогда еще очень молодых разработчиков Арлазарова, Ускова, Животовского, Битмана. И можете себе представить начальника почтового отделения рядом с ИТЭФом, который должен был отправлять в Америку телеграммы, где были сложные нотации шахматных ходов. Тем, кто тогда решился это представить, за это могли дать 25 лет без права переписки.
Тем не менее, это происходило.

И в этот момент началась работа над очень интересной проблемой, которая и сегодня одна из самых главных проблем. Давайте посмотрим сначала на место шахмат в искусственном интеллекте. Почему они имели к нему отношение? Сейчас это уже не так очевидно.

Искусственный интеллект, грубо говоря, разбивается на две задачи. Одна задача – это представление знаний. Как можно в компьютер ввести знания и как ими пользоваться для решения задач.

А вторая часть – это принятие решения, поиск решения. Это немножко условное деление, потому что при поиске решения необходимо использовать где-то знания, в поиске решения оформлять накопленный опыт для поиска путей ускорения этого решения. Точно так же для того, чтобы найти в больших объемах знаний необходимые – это та же задача, надо использовать некоторые методы принятия решений. Но тем не менее шахматы оказались кристально ясной задачей, потому что правила игры просты и понятны. Т. е. область знаний там была тривиальна. Зато алгоритмы поиска решений очень сложны. На них и нужно было сфокусироваться.

Но оказалось, что алгоритмы поиска решений в виде перебора с сокращением начали развиваться очень бурно и оказали большое влияние на развитие искусственного интеллекта.

Между прочим, первые книги об искусственном интеллекте так и называются "Искусственный интеллект и поиск решений".

И тут возникла чисто философская проблема. Вот играет машина в шахматы. Уже в 1975 г. она играла на уровне 2-го разряда. Сегодня, как известно, она играет на уровне Каспарова. Хорошо это или плохо? Казалось бы, хорошо, она решает поставленные задачи, прекрасно решает. Но нет! Есть у людей в отношении к искусственному интеллекту два течения.

Одни говорят: "Мы должны хорошо решать сложные задачи", это так называемые прагматики. Неважно, кто лучше, кто хуже, это неинтересный вопрос. Интересна сама постановка задачи.

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

Покойный Михаил Моисеевич Ботвинник, один из тех, кто внес заметный вклад в шахматное программирование (хотя, что это странно, он, конечно, не имел ни малейшего отношения к программированию). Вот он был ярким представителем такого теоретического крыла людей, которые говорили, что программа должна играть, как шахматный мастер... Он говорил: "Я знаю... я шахматный мастер... я знаю, как она должна играть. Вот, я буду делать такую программу". Кстати, он все-таки, чтобы получить конкретные результаты, мягко сдрейфовал в сторону прагматиков. Потому что, конечно, то, как компьютеры играют в шахматы, никакого отношения к тому, как человек это делает, не имеет и иметь не может.

Там возникают другие способы представления знаний, другие способы поиска решений, и все это интересно. Вот этот конфликт существует, он реален. И неизвестно, чем он кончится, как и когда, но очень интересно обратить внимание на его существование.

 

 

 

 

Развитие шахматных программ

 

В 1883 г. на четвёртом международном турнире в Лондоне были впервые применены шахматные часы. Во все времена шахматист хотел основательно подумать, прежде чем сделать ход. В непосредственном предшественнике современных шахмат – арабском шатрандже (произошедшем от иранского шатранга) партии тянулись очень долго. Самая сильная ныне шахматная фигура – ферзь – была малоподвижна. И слон тоже. Темп жизни в те далёкие времена позволял до поры до времени подолгу засиживаться за шахматной доской. Однако и современные правила шахмат приводили к тому, что партии затягивались на много часов, а то и не на один день. Против тугодумов до турнира в Лондоне применяли песочные часы. Это было неудобно. Английский инженер Т. Уилсон изобрел специальные шахматные часы – просто два часовых механизма и два циферблата в одном футляре, соединённые одним рычагом, одновременно выключающим часы одного противника и включающим часы другого. Игра ускорилась. Слово «цейтнот» стало широко употребительным за пределами шахматного мира. Наступил новый период шахматной истории, и на сто с лишним лет утвердился контроль времени на обдумывание ходов, соответствующий контролю, который был применен тогда в Лондоне: час на 15 ходов. Классической стала норма 2,5 часа на 40 ходов каждому и далее по часу на 16 ходов каждому.

Современные шахматы распространялись по планете, множились ряды шахматистов и число соревнований, развивалась теория дебютов – начальной стадии шахматной партии. Последнее делало все более важной для успеха ёмкость памяти шахматиста. Многие партии длились более 40 ходов – тогда они прерывались, доигрывание откладывалось, и важнейшую роль стал играть домашний анализ отложенной позиции. Случалось, блестящий анализ восхищал ценителей шахматного искусства. Однако в матчах на первенство мира, к примеру, соперники играли по три партии в неделю, включая дни доигрывания и выходной день. Правда, за ходом таких матчей следили во всём мире. В Советском Союзе, к примеру, матчи проводились в самых престижных залах, как правило, переполненных.

Однако такие матчи тянулись месяцами, между тем самолёты стали летать все быстрее, всё быстрее двигались ленты конвейеров, все торопливее становились люди. Любители хотят поскорее узнавать имена победителей турниров и матчей. Игроки-любители заинтересованы в том, чтобы не отрываться надолго от повседневной работы и жизни для участия в соревнованиях, а шахматисты-профессионалы – в том, чтобы играть почаще в турнирах, где установлены денежные призы.

Появление компьютерной техники ускорило крушение старых регламентов шахматных турниров и матчей. На первых порах шахматисты спорили, смогут ли появившиеся компьютеры сильно играть в шахматы. Не могу удержаться и не похвастаться тем, что в I960 г. в популярном тогда журнале «Юность» была опубликована моя статья «Машина учится играть». Тогда я угадал, что у компьютера многообещающие шахматные способности. В статье после коротенькой увертюры о хитроумном иллюзионисте Кемпелене и его «автомате» со спрятанным шахматистом я привёл две точки зрения на будущее играющей в шахматы настоящей «машины». Известный мастер Юдович по этому поводу тогда писал: «Не пришло ли время говорить о гибели шахмат, о том, что совершенные машины будут играть безошибочно, побеждая умеющих ошибаться людей? Это время не пришло и вряд ли придет... Машина твёрдо будет знать, что ферзь сильнее коня, но создавать комбинацию, в которой конь побеждает ферзя, ей вряд ли будет по силам». Такая вот романтическая оценка человеческого интеллекта, хотя и не категорическая. Обращают на себя внимание слова «вряд ли». Тогда же М. М. Ботвинник, позже занимавшийся этой проблемой годы, смотрел попроще и подальше: «Машины будут играть сильнее». Сегодня мы знаем, что машины во всяком случае не без успехов могут играть с чемпионами мира. 15 лет спустя, в 1975 г., «Литературная газета» провела заочный круглый стол. Экс-чемпионам мира разослали вопросы, и среди них был такой: «В последнее время повысилась шахматная сила ЭВМ. Будет ли создан электронный гроссмейстер?» М. М. Ботвинник ответил категорично: «Компьютер неизбежно будет сильнее гроссмейстера». Экс-чемпион мира Макс Эйве, математик по профессии, занимавшийся проблемой «ЭВМ и шахматы», сказал: «...вовсе не очарован новыми поисками в этом направлении, хотя должен с прискорбием признать, что компьютеры играют всё лучше и лучше». Тигран Петросян ответил, что, быть может, электронного гроссмейстера создадут, но сомнительно, чтобы он был равен по силе гроссмейстеру-человеку. Василий Смыслов: «Думаю, что не „электронным", а обычным гроссмейстерам присуща оригинальность мышления. Быть может, я не прав, но в близком будущем „электронного гроссмейстера" не будет». Михаил Таль и Борис Спасский от прогнозов воздержались. Первый сказал: «Мне с моим гуманитарным образованием трудно проникать в высшую техническую сферу». Второй тоже ответил скромно: «Для ответа надо быть специалистом в кибернетике, а я лишь экс-чемпион мира по шахматам».

Шахматист высокой квалификации может рассчитать сложную комбинацию на много ходов вперед, но сила его далеко не в этом. Понимание позиции даёт шахматисту возможность с ходу отбрасывать большинство вариантов, не рассматривая их. Законы развития борьбы в партии раскрывались не сразу. Позиционное понимание совершенствовалось исторически, нередко меняя прежние оценки. Случаются положения, где дерево вариантов так разветвляется, что рассчитать всё невозможно. Способность найти верное продолжение в этих ситуациях и определяет класс.

Вначале, когда компьютер только учился играть в шахматы, он считал быстро, но играл тупо. Чемпион мира и доктор технических наук Михаил Моисеевич Ботвинник решил создать программу, которая будет искать продолжение в партии подобно человеку. Он целеустремлённо работал над программой, которой дал имя «Пионер». «Очеловеченная» программа пренебрегала бы ненужными вариантами. Такая программа могла бы решать и другие сложные задачи. Работа над «Пионером» оказалась исключительно трудоёмкой.

Шли годы, быстродействие компьютеров росло лавинообразно. Память становилась всё мощнее. Её начиняли миллионами уже сыгранных партий, огромной дебютной библиотекой. И современные программы достигли высокой силы. Компьютеры, в отличие от «белковых» шахматистов, не страдают ни гриппом, ни зубной болью. Они всегда в боевой форме. Играя с компьютером, можно даже определить свою спортивную форму. У компьютера сила постоянная, она не колеблется, как у человека. Мне кажется, пора сказать: суду все ясно.

В оправдание «белковых» шахматистов следует признать, что именно они создали объёмную и премудрую дебютную теорию, которую сами не в силах удерживать в памяти. Для компьютера упомнить все на свете проще простого. Сами компьютеры так разработать начальную позицию, то есть дебют, как это сделали люди, ещё не могут. Однако новая история шахмат завершилась. Началась новейшая история шахмат. Игра при прежнем контроле времени теперь называется классической. С классическими шахматами конкурируют так называемые быстрые шахматы, где ошибок побольше, замыслы пожиже... Зато азарт!

Доигрывание неоконченных партий ликвидировано «как класс». Обучение, тренировка, подготовка к конкретным противникам стали немыслимы без компьютера. Мастера и гроссмейстеры носятся с турнира на турнир с ноутбуками. Классическая прежде форма турнира – круговая, когда каждый играет с каждым, стала раритетной. Её сменила «швейцарка», которую прежде мастера ценили не выше, чем гурманы ценят гамбургеры. Цветёт так называемая нокаут-система, вышедшая из моды ещё в XIX в. Соревнования проходят побыстрее, а значит, для организаторов подешевле. Участников и публику быстрота устраивает.

Мы являемся свидетелями и других чудес. Число шахматистов в мире умножилось чрезвычайно. Китайцы, игравшие в прошлом в свои сян-ци, отличающиеся от шахмат, освоили классические и быстрые шахматы, а их девушки оттеснили с первых мест в мире прославленных грузинок. Ежегодно проводятся чемпионаты мира для ребят самых юных возрастов. Похоже, идет охота на вундеркиндов. Появилось множество мастеров в коротких штанишках. Есть и гроссмейстеры-школьники. Верно, вундеркинды встречались и раньше. Решевский, например, в младшем школьном возрасте успешно давал сеансы одновременной игры. А нынче вундеркинды стали массовой категорией. Конечно, прежде мастеров и гроссмейстеров было на порядок меньше, получать титулы стало попроще, однако класс игры юных дарований стал, несомненно, выше, чем у их сверстников в прошлом. Произошла какая-то акселерация. Не знаю, как обстоит дело в других случаях, когда требуется соображать. Это особая тема.

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

Характеризуя содержание шахмат, принято хвалить их как сочетание элементов искусства, науки и спорта. Со спортом, как сказано, дело обстоит благополучно. Шахматист должен быть психологически устойчивым, выносливым. Компьютеры нанесли смертельный удар анализу эндшпиля, облегчили анализ и обогатили теорию дебютов. С искусством получились некоторые затруднения. Красивые комбинации, глубокие планы не исчезли, но простора для этого стало поменьше. Часто уже не десяток первых ходов, а два-три десятка являются повторением пройденного. И ещё: не успевает любитель получить удовольствие от разыгрывания выдающейся партии одного соревнования, как уже в СМИ появляются всё новые и новые. Такова спортивная жизнь – очки, голы, секунды...

Сейчас компьютер играет с чемпионом мира на равных. Сила его растёт. Но люди все равно будут играть в шахматы. Совсем не обязательно состязаться в поднятии тяжестей со слоном или подъёмным краном. Тяга к игре заложена в человеческой натуре, и не только к игре в рулетку, кости, орла или решку. К тому же интеллектуальное состязание может быть не только увлекательным, но и полезным.

Могут ли в будущем, близком или отдалённом, произойти изменения правил игры в шахматы? Как известно, всё течёт. Вот Роберт Фишер, шахматист с признаками гениальности, предлагает сейчас расставлять фигуры в начале партии не так, как установлено веками. При этом компьютер в момент лишается преимуществ, которые даёт ему дебютная библиотека. А человек сможет лучше разобраться в незнакомых компьютеру дебютных позициях. Ведь сила компьютера – в конкретном расчёте вариантов, но не в понимании позиции. Неспешные круговые турниры, многомесячные дуэли за титул чемпиона мира уходят в прошлое. Ничего нельзя поделать. Что?то находишь, что-то теряешь. Компьютеризация изменяет не только шахматы.

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

Шахматы – дешёвый вид спорта по сравнению с футболом, теннисом и другими. Зрителю легче наблюдать за полётом мяча, чем за полётом мысли шахматиста. Поэтому круг шахматных болельщиков уже, финансовые вопросы решаются с трудом. Так что рядовым любителям шахмат остается надеяться, что ведущие шахматисты мира и Международная шахматная федерация сумеют преодолеть этот самый человеческий фактор и положить конец вредной неразберихе. Но не всё так мрачно в шахматном королевстве. Компьютеры принесли новые возможности, о которых раньше невозможно было даже и мечтать. В прошлом существовала игра по почте. Когда-то, говорят историки, случалось, что отец завещал сыну доиграть партию. Телеграф, телефон, радио дали новые возможности, но и они несравнимы с игрой по Интернету. Партии идут в реальном времени. Стало возможно, не выходя из дома, не только играть с далекими партнёрами, но и учиться, тренироваться, участвовать в клубной работе и следить в реальном времени за текущими соревнованиями. Так что древняя игра не сметена научной революцией.

Основы программирования шахмат

1. Постановка задачи

Что представляет собой "мозг" шахматной программы;
Каким образом компьютер из моря вариантов выбирает единственный;
Что необходимо, чтобы заставить компьютерного оппонента играть быстрее и т.д.

2. Основные компоненты шахматной программы

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

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

3. Представление данных

Каждый из нас по-разному воспринимает входную информацию. На полотне Леонардо Да Винчи один человек может увидеть Джоконду, другой сто долларовую купюру, третий тещу (или зятя). То же самое и в шахматах. Два соперника во время игры могут видеть совершенно "разные" позиции в один момент времени.

Так чем же компьютер должен отличаться от человека? Ничем. Компьютерные программы, как и люди, не похожи друг на друга: "мыслят" и хранят информацию они по-разному. Но всё же одни из них играют лучше, другие хуже. В чём секрет?

В программировании очень важно правильно выбрать представление данных.

Я думаю, что любой человек в состоянии придумать какой-нибудь способ отображения текущей информации на шахматной доске. Например, можно представить шахматную доску как таблицу (массив) размерами 8х8, где пустой клетке соответствует число - 0, белому королю - 1, и т.д. Увы, у этого способа наряду с преимуществами существует и куча недостатков. Но прогресс, как говорится, не стоит на месте, и был придуман более совершенный способ отображения информации, получивший название "битовые поля" (англ. - bitboards). Это 64-битное слово (то есть последовательность из 64 цифр, каждая из которых может иметь значение 0 либо 1), содержащее информацию об одном аспекте шахматной игры. Каждый бит - это одно поле шахматной доски. (Отсчет может вестись по-разному: поле а8 - это первый бит последовательности, h1 - последний, к примеру.)

Они могут содержать:
Поля, атакованные черной пешкой е6 (d5,f5)
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 1 0 1 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0

Для наглядности число разбито по 8 бит, изображающих горизонтали доски.

поля, занятые белыми пешками (фигурами)

поля, куда может пойти белый конь и т.д.

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

4. Генерация ходов

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

 

5. Методы анализа

Итак, компьютер сможет "видеть" доску, делать всевозможные доступные ходы в данной позиции. Осталось дело за малым: научить его выбирать лучший ход и предоставить ему возможность оценивать позицию, пользуясь какими-то критериями, которые мы ему предоставим. Что касается первого, то пока ничего лучше не придумано, чем лобовое решение: чтобы выбрать лучший из двух ходов, анализируют последствия каждого из них до какого-то момента, скажем анализ на 5-6 ходов вперед, с последующей оценкой получившейся позиции. При этом делается предположение, что соперники стараются выбирать лучшие ответы на каждом ходе. Кстати, последнее предположение лежит в основе алгоритма MiniMax, являющегося ключевым для всех шахматных программ.
Всё бы было хорошо, но… не тут то было. Вам бы пришлось потратить пять, а может и больше, жизней, чтобы сыграть хотя бы одну партию, пусть даже с самым быстрым компьютером. Так что подумайте прежде чем садиться играть партию с компьютером.

6. Оценка позиции

И последнее, что необходимо компьютерной программе, чтобы оказать вам достойное сопротивление - это дать ей возможность оценивать позицию. То есть ввести оценочную функцию, которая по положению на доске возвращает число, соответствующее, с её точки зрения, текущему раскладу сил. Это тоже не самая простая задача, хотя существует огромное количество подходов к решению этой проблемы.

 

Системные требования

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

В мире множество шахматных программ и большинству из них все равно, какой конкретно процессор установлен у вас в компьютере – Pentium или Athlon, с частотой 1 ГГц или 3 ГГц.  Совсем другое дело, если кроме просто «работает» хочется, что бы еще и работало быстро. Здесь конечно выбор процессора играет важную роль и его выбор представляется сложной задачей. Решить ее можно только одним способом – протестировать производительность на большом количестве различных ПК (и конечно процессоров).

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

Для тестов была выбрана одна из популярных программ – Deep Fritz версии 8.0. В ней есть встроенная возможность проверки быстродействия вычислительного ядра. Результат выдается во внутренних «попугаях», непосредственно связанных со скоростью вычислений, измеряемых в «килоузлов в секунду». Для результата действует правило – чем больше цифра, тем быстрее считает программа. Следует отметить, что во время теста программа «играет» определенную партию и у пользователя может возникнуть вопрос – а как этот результат перенести на его собственную партию, да еще и со специально подобранными параметрами? Ответить на этот вопрос достаточно просто – дело в том, что мы будем измерять (пусть и косвенно) быстродействие собственно «ядра» программы.

Аналогия здесь такая – если ПК1 кодирует фильм «Ирония судьбы» с DVD в MPEG4 в два раза быстрее чем ПК2, то если взять вместо фильма подборку мультиков «Ну погоди!» и поменять некоторые настройки но сохранить программы для кодирования, то соотношение сил останется примерное такое же. То есть речь в данном случае идет о скорости некоего «вычислительного ядра»,  а итоговая скорость зависит как от задачи, так и от настроек программы и если эти условия одинаковы, то можно перенести относительное соотношение сил между системами со встроенного бенчмарка Deep Fritz на данную задачу пользователя.

Предварительные исследования показали, что скорость счета зависит исключительно от процессора – ни жесткий диск, ни подсистема памяти, (ни тем более видеокарта) не оказывают на скорость никакого эффекта.

Оказалось, что единственные важные показатели – ядро (архитектура, модель) и частота процессора. Причем по второму зависимость просто линейная – процессор с частотой в два раза большей работает в программе два раза быстрее.

 

Стоит отметить, что в принципе программы типа Deep Fritz обычно умеют использовать многопроцессорные системы, причем достаточно эффективно. Например, тестовый запуск на двухпроцессорной системе с двумя AMD Opteron показал практически двукратный рост производительности. Общее сравнение моделей провести с одной стороны просто – есть все данные, а с другой сложно, поскольку требования к другим задачам могут сильно сказаться на выборе.

 

Первый чемпион мира по шахматам среди компьютерных программ

1974 год положил начало новому, более серьезному этапу в развитии шахматного программирования.

Научить компьютер играть в шахматы — одна из самых интересных задач в сфере искусственного интеллекта. Она была поставлена уже на заре вычислительной техники, в конце 50-х годов. В шахматах существуют определенные уровни мастерства, степени качества игры, которые могут дать четкие критерии интеллектуального роста машины. Поэтому компьютерными шахматами активно занимались ученые умы во всем мире. Но шахматы — игра, соревнование, и чтобы продемонстрировать свои логические способности, компьютеру необходим непосредственный противник. В 1974 году впервые прошел чемпионат мира по шахматам не между людьми, а между компьютерными программами. Победителем этого состязания стала советская шахматная программа «Каисса».

«Каисса» (была такая богиня, покровительница шахмат) создавалась в Москве, в Институте проблем управления Академии наук. Возможностями ЭВМ играть в шахматы здесь всерьез заинтересовались еще в середине 60-х, и уже в 1967 году одна из разработанных нашими программистами систем играла с американской шахматной программой. В начале 70–х в мире накопилось такое количество шахматных разработок, что встал вопрос о создании ассоциации шахматного программирования. Такая ассоциация была образована при поддержке крупнейшей международной организации по информатике International Federation of Information Processing (IFIP). А первый чемпионат мира среди шахматных программ в 1974 году прошел в рамках очередного конгресса IFIP (такие конгрессы собирались раз в три года) в Стокгольме.

Надо помнить габариты тогдашних ЭВМ, на которых работали программы-участники. «Каисса», например, разрабатывалась на машине фирмы ICL, занимавшей в институте зал площадью примерно в 150 кв. метров. Размеры остальных претендентов, как правило, были не менее внушительны. Поэтому разместить непосредственно в Стокгольме удалось только две-три машины, а остальные участники чемпионата общались между собой по телефону (мы имеем в виду, конечно, разработчиков, а не компьютеры). В зале, где происходил конгресс, находились представители команд каждой страны, а к тем ЭВМ, на которых выполнялись шахматные программы, IFIP отправила своих наблюдателей. Они должны были лично удостовериться в том, что играет действительно машина.

Владимир Львович Арлазаров, один из основных разработчиков «Каиссы», рассказывает, что в течение четырех дней 16 участников чемпионата играли друг с другом по швейцарской системе. Каждая команда участвовала в четырех партиях, и победителем становилась программа, набравшая наибольшее число очков.

Победа советской шахматной программы была неожиданной. Все прочили лавры чемпиона американской разработке Chess 4, которую, как это умеют делать американцы, широко разрекламировали в преддверии первого мирового состязания. Создатели «Каиссы» не готовили программу специально к чемпионату. Как мы уже отмечали, шахматное программирование представлялось одной из наиболее интересных задач искусственного интеллекта, на которой лучше всего проверялись методы перебора. Как отмечает Владимир Арлазаров, сейчас ни одна шахматная программа не обходится без использования этих методов, но в те годы у такого «переборного» пути шахматного программирования было немало оппонентов. Разработчики «Каиссы» ставили перед собой сложную задачу — добиться результата как при очень глубоком переборе, но при этом суметь уложиться в конечное время. Победа на чемпионате по компьютерным шахматам свидетельствовала, что эту задачу удалось с успехом решить.

Можно было бы предположить, что шахматную программу должны писать никак не меньше чем кандидаты в мастера. Однако это было не так. В команде разработчиков программы-чемпиона, лидерами которой были Владимир Арлазаров, Михаил Донской и Георгий Адельсон-Вельский, большинство даже не имели разряда. В сочетании «шахматное программирование» на первом месте стоит именно программирование, и для создания эффективной шахматной программы нужны были классные профессионалы в этом деле. А у крупных шахматистов компьютерные шахматы, как правило, не вызывали большого интереса. Это была прежде всего научная задача, а чемпионат мира — научное мероприятие, на котором шло не только соревнование, но и интенсивный обмен идеями. Это потом, в 80-е, особенно с появлением персональной вычислительной техники, создание шахматных программ стало занятием сугубо коммерческим, а в научной сфере интерес к ней постепенно угасал. Коммерция была несовместима со свободным обменом научной информацией.

Надо отметить, что к 1974 году уровень ЭВМ как шахматных игроков был не очень высок.

Машина, победившая на первом компьютерном чемпионате, оценивалась как шахматист третьего разряда. Фактически это первый серьезный уровень, соответствующий игре нормального шахматиста, а не просто человека, знающего, как ходят фигуры. Успех программы в некоторой степени определялся и мощностью вычислительной машины. Участники чемпионата были вольны выбирать, на какой технике они представят свою шахматную разработку, потому оказывались не совсем в равных условиях. Однако накладывать какие-либо ограничения было невозможно — участие в чемпионате поддерживалось теми фирмами и организациями, в которых использовалась машина, либо теми, которые сами производили машины, и для них это была, конечно, прекрасная возможность прорекламировать свои разработки.

Наша команда должна была довольствоваться тем, что имела. И понимая, что делают программу не на самой мощной машине, разработчики стремились компенсировать отставание в быстродействии предельно тщательным подходом к программированию. Именно поэтому был выбран язык Ассемблер.

Конечно, победа «Каиссы» на мировом чемпионате по компьютерным шахматам не могла пройти незамеченной. В стране это событие было воспринято прежде всего как большой успех советской науки. О программе-чемпионе сразу заговорили, появились публикации в центральной прессе. Сам первый чемпионат получил большой резонанс в мире. Он наглядно продемонстрировал всем, что вычислительные машины могут самостоятельно решать такие сложные логические задачи, как игра в шахматы. Проигрыш русским подстегнул американцев, и после 1974 года в исследования по шахматному программированию стали делаться очень серьезные финансовые вложения. Фактически 1974 год положил начало новому, более серьезному этапу в развитии шахматного программирования. До середины 80-х чемпионаты мира по шахматам между вычислительными машинами проходили с той же регулярностью, что и конгрессы IFIP. Мы продолжали принимать в них участие, но с ростом коммерциализации компьютерных шахмат эта задача потеряла для наших разработчиков научный интерес. Кроме того, отставание советской вычислительной техники от западной, где уже появлялись специализированные шахматные машины, росло с угрожающей скоростью, и мы в конце концов потеряли возможность соревноваться на равных.

 

Развитие шахматных платформ

Раньше для шахматных программ использовались гигантские по размерам компьютеры (более 100кв метров). Самые лучшие из них играли на уровне 3разряда, но постепенно с развитием технологий и улучшением алгоритма написания шахматных программ стали уменьшаться габариты компьютеров и увеличиваться возможности шахматных приложений.

В настоящее время шахматы могут широко используются во многих видах электронных устройств: ПК, КПК, телефонах, ноутбуках, специальных шахматных устройств и т.д. Сложность игры с шахматными программами сильно увеличилась – некоторые телефоны сейчас играют на уровне 2-3 разрядов, а ПК выигрывают гроссмейстеров

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

Создатели популярной шахматной программы Deep Fritz, обещают, что через пару лет компьютер будет невозможно победить. Многие шахматисты согласны с ними, потому что сегодня компьютер может просчитывать на 10-12ходов(!) вперед (за себя и за человека), а база компьютера содержит огромный список партий сыгранный человеком за 10и-100и лет. В таком раскладе позиционная игра с ним становится невозможной. Гроссмейстеры стараются завести партию в неизвестное русло или разменять ферзей в начале партии, чтобы получить преимущество.

Прогресс не стоит на месте и будет интересно лет через пять сравнить нынешний уровень шахматных технологий и будущий.

 

 

 

 

 

 

Для письма членам команды заполните следующую форму:

ФОРМА ЗАПОЛНЕНИЯ ПИСЬМА
Напиши свое имя
Обратный e-mail (почтовый ящик)
Напишите о себе и свой вопрос
Число на картинке


На ваш почтовый адрес придет ответное письмо от меня с указанием на следующий урок.

© 2013 год. Охраняется законом об авторских правах.