Компьютерные шахматы. Кто создал первую компьютерную шахматную программу
Развитие искусственного интеллекта в шахматных программах ≪ ∀ x, y, z
– Когда выяснили, что компьютеры умеют не только вычислять, как это было придумано с самого начала, что за арифметическими действиями есть логическое действо, которое не только выполняет вспомогательные функции в деятельности вычислительных программ, но и с помощью которого можно решать самостоятельные задачи, то стало ясно: стоит попробовать положить на компьютер интеллектуальные задачи. Где-то с конца 40-х годов и до конца 50-х это активно обсуждалось, более того, ставились полу философские вопросы: а может, компьютеры будут умнее людей? И что тогда? И все на полном серьезе. Сейчас такие вопросы не ставят, все-таки 40 лет прошло. Тогда, на заре вычислительной техники, мы только осознали, что принципиально могут делать машины. Мы поняли, что человеческий мозг есть устройство, аналогичное вычислительной машине, и в тысячу, в миллион раз более мощное, но оно принципиально немножко отличается. Стало понятно, что, по крайней мере, большинство рациональных задач, которые решает человек, могут быть поставлены перед машиной. Следовательно, можно попробовать написать программы, которые эти задачи решают. Одну, две, тысячу... ведь человек тоже решает не бесконечное множество задач. И можно, так сказать, всю интеллектуальную деятельность человека запрограммировать.
– А почему все же решили обратиться к игре?
– Как я уже говорил, широко обсуждалось, может ли машина мыслить. Однако совершенно ясно, что если речь идет о программистах, о людях, которые имеют дело не с философией, а с реальным компьютером, то вопрос не в том, может ли машина принципиально что-то делать, а в поиске примеров того, где машины решают интеллектуальные задачи, причем такие, которые доступны и человеку в его интеллектуальной деятельности. Грань здесь, конечно, не четкая. Но понятно, что если человек множит 20значные числа, то он при этом не имеет дело с глубоко интеллектуальной задачей, поскольку для ее выполнения очень легко найти тривиальный алгоритм, который известен каждому школьнику. А вот те задачи, где совершенно ясно, что никакого априорного алгоритма у человека нет, а он тем не менее хорошо их решает, мы и будем называть интеллектуальными. Первым претендентом на роль таких задач являются игры, по той простой причине, что, по крайней мере, правила четко сформулированы. Задача чрезвычайно трудная, а правила игры сформулировать легко, и тем самым легко определить и функции машины. С другой стороны, шахматы для человека трудная задача, что как-то никогда не обсуждалось и сейчас не обсуждается.
– А почему из игр выбрали все-таки шахматы? Может быть, традиция?
– Почему только шахматы? Пробовали и крестикинолики, другие игры. Но у шахмат немало преимуществ перед другими играми. Если в простых играх машина обыгрывает человека, то это никого не удивляет. Шахматы — игра сложная, и победа компьютера здесь значима. Затем в шахматах, в отличие от ряда других игр, много дифференцируемых критериев качества, то есть можно определить: машина играет хорошо, машина играет лучше, лучше, лучше. Во многих других играх подобные градации установить очень трудно. В некоторых же из них машину либо обучают играть абсолютно точно, и тем самым сразу теряется всякий интерес к игре, либо она играет из рук вон плохо. А в шахматах, не абстрактных, а, так сказать, освоенных, уровней столько, что с их помощью можно определить класс игры машины.
– Итак, понятно, почему шахматы были одной из первых и важнейших задач искусственного интеллекта. А какие методы применялись для ее решения?
– С самого начала постепенно осваивалась методика решения задачи шахматной игры. В принципе, шахматы — игра конечная, и с математической строгостью можно доказать, что в любой позиции абстрактно существует наилучший ход для каждого из противников, а значит, и какой-то результат. Поэтому нужно описать алгоритм, в котором эта игра может быть рассчитана до конца. Единственный недостаток такого алгоритма состоит в том, что он требует много времени. И мы не приблизились к тем порядкам времени, которые нужны, чтобы рассчитать, скажем, шахматы до конца из начальной позиции. За прошедшие пятьдесят лет задача в смысле времени так и осталась бесконечно сложной. Ну, бесконечность минус десять — все равно бесконечность. Но если вам нужно время, скажем, 10 в 100-й степени лет, и вы ускорите машину, скажем, в 100 раз, и получите 10 в 98-й степени лет, то вам вряд ли от этого станет легче. Поэтому основной алгоритм — переборный, тривиальный: если я пойду так, то у противника есть столько-то возможностей. Варианты растут в геометрической прогрессии и образуют цепочки. Но количество позиций вообще конечно, и их на каждой цепочке не так уж много. Цепочки объединяются в деревья, которые опять же не бесконечны. Правда, растут они в геометрической прогрессии, и количество цепочек увеличивается. Так вот, встает важный вопрос: нужен ли полный, до самого конца, перебор — до всех матов, патов, троекратных повторений и прочих окончаний игры по шахматным правилам? Ведь если алгоритм ведет к позициям, которые не обязательны на этом дереве, то, возможно, все это дерево и не нужно рассматривать. Заметьте себе, что в диспозиции, где белые дают мат в один ход, можно построить такое же бесконечное дерево, но рассматривать-то его не нужно, а достаточно найти этот один-единственный ход. Может, такая же ситуация и в шахматах в целом? Вообще алгоритм перебора, перебора вариантов имеет отношение к такому количеству решаемых человеком задач, что, если бы мы умели его организовывать каким-нибудь уж очень оригинальным способом, то он был бы, в каком-то смысле, как бы изобретением колеса для человечества — одного из фундаментальнейших открытий. Так вот, перебор мог бы быть, а может, и является таковым — колесом искусственного интеллекта.
– В одной из статей об искусственном интеллекте я читал, что интеллект — это умение понимать и выбирать. Естественно, что научить компьютер выбирать из множества вариантов очень сложно. Но ведь наверняка возможны какие-то решения, специфические для шахмат?
– Да, да. Эту задачу нужно было быстро и эффективно решать, и в шахматах довольно быстро пришли к следующей теоретической постановке вопроса: а давайте смотреть не бесконечное количество ходов, а лишь несколько ходов вперед. Скажем, посмотрим на 5 ходов вперед. Это очень много. Если вы любите шахматы и 5 ходов вам кажется мало, то давайте возьмем 10. И тогда машина на 10 ходов, на 20 полуходов вперед не будет ни в чем ошибаться и гарантирует, что через 10 ходов у вас фигур окажется не меньше. Ясно, что мы имеем дело с сильной играющей машиной. Так что дерево игры придется сократить и решать задачу в гораздо более ограниченном пространстве. Другой вопрос, что и это дерево стараются рассматривать не полностью, с помощью математических методов отсечения. Об одном из них я уже рассказывал: если есть мат в один ход, незачем просматривать остальные варианты. Другие алгоритмы имеют эвристический, не точный характер. В среднем они работают правильно, многие абсолютно точные, но могут и ошибаться. Например, мы можем перебирать не все ходы, а только взятие, и просчитывать их намного вперед, потому что взятий-то мало. Общая углубленность ходов невелика: больше тридцати двух фигур не съесть. Поэтому и длины цепочек небольшие и ветвлений мало. Конечно, ясно, что на одних только взятиях нельзя построить игру, должны быть какие-то позиционные соображения. Комбинация форсирующих (взятие, шах) и позиционных соображений, а также некоторой глубины перебора — основа всех существующих алгоритмов, и она особо не меняется. Другой вопрос: как отбирать те ходы, которые я буду рассматривать дальше? На основании ли только простых формальных критериев (взятие, шах) или же связывать эти ходы, как шахматисты любят говорить, планом, придумывать какие-то цепочки, которые обладают каким-то общим свойством? Во всяком случае, об этом написано очень много серьезных работ, имеющих практическое применение. Не зря созданием шахматных программ занимаются достаточно солидные фирмы.
– А когда появились первые шахматные программы?
– Реальные шахматные программы впервые появились где-то в конце 50-х годов в Америке, а потом где-то в начале 60-х годов — и у нас. Программы были очень слабые, потому что тогда были и предельно примитивные машины и не привычное еще к новизне наше мышление. Включились мы в это дело примерно в 1963 году. Тогда на наших отечественных машинах и были какие-то матчи. По-моему, в 1967 году был первый матч СССР — США. Он так назывался, хотя, конечно, проходил между двумя коллективами, а не странами. Это был матч между нашей программой, разработанной в Институте теоретической и экспериментальной физики, и программой Джона Маккарти, очень известного в компьютерном мире человека, одного из создателей языков программирования, который увлекался тогда шахматными программами. Ходы передавались по телеграфу, тогда ведь никаких сетей не было.
– И кто победил?
– Мы тогда выиграли 3:1. Играли 4 партии. Делался ход в день, поскольку у американцев были более мощные и глубокие программы, которые долго думали, а мы играли на разных вариантах программ, думающих и быстро, и медленно. Наш выигрыш был первым нашим достижением. Это направление стало постепенно развиваться и особенно активизировалось в 70-е годы. Примерно в 1974 году состоялся первый чемпионат мира среди шахматных программ в Стокгольме. Участвовало около восьми программ, в том числе и наших. И мы тогда тоже победили и стали первыми чемпионами мира. С тех пор чемпионаты мира проводятся регулярно, каждые 3 года. Мы в них участвовали еще 2 раза — в 1977 г. и в 1980 г. Лавров мы тогда не снискали, потому что в 1977 г. поделили 2-е и 3-е место (участвовало много шахматных программ, были даже региональные отборы), а в 1980 г. — 4-е и 5-е место. В общем, потихоньку откатывались. Дело в том, что к этому моменту был уже громадный прогресс в вычислительной технике, а мы все еще играли на компьютерах довольно устарелых. И к 1980 г. нам стало ясно, что соревноваться на тех машинах, на которых мы работаем, потеряло всякий смысл, да и вообще в России работы в области шахматных программ стали сходить на нет. Хотя и было довольно много интересных теоретических работ. Чуть позднее создали первую, пожалуй, программу, которая прошла по миру, она умела абсолютно точно разыгрывать сложный эндшпиль, т. е. ферзь и пешка против ферзя, или ладья и пешка против ладьи. Такие эндшпили программа просто до конца рассматривала, т. е. в любой позиции она давала идеально верный ход. Алгоритм был построен на немножко отличных от простого перебора принципах, на полном осмотре всего множества позиций. Ну, и потом в шахматах делали некоторые работы такого характера. А с практической игрой мы тогда распрощались, потому что разности в скоростях были уже в сотни раз. Но чемпионаты продолжались, и развитие шахматных программ продвинулось на совершенно новый уровень, как только все перешло на РС. В результате широкой коммерциализации, в шахматные программы стали вкладывать огромные деньги, сразу все засекретили. А раньше они принадлежали ученым, которые, если не заставить специально, не скрывают своих достижений, а, наоборот, пропагандируют их. В 1980 г. мы впервые почувствовали, что наступило время коммерческого программирования. Этот мир, конечно, своеобразен. Во-первых, потому что в него ведь вкладываются деньги, во-вторых, потому что из него извлекаются деньги. Хотя и существуют журналы по шахматным программам, но за последние 15 — 17 лет реальный обмен идеями сильно сошел на нет, потому что на PC они стали огромным бизнесом.
– Но ведь коммерция стимулирует развитие рынка шахматного ПО?
– Раньше компьютерные соревнования приурочивались к форумам вычислительной техники. Есть такая организация — МФИ (Международная федерация по информатике) и, обычно, к ее конгрессу приурочивались чемпионаты мира. Сейчас они стали абсолютно самостоятельными мероприятиями, достаточно престижными. Таких программ уже сотни и сотни. Сам уровень программирования и уровень наших знаний уже таков, что сделать простенькую шахматную программу не составляет ни малейшего труда. Это нормальная студенческая работа. Я ее как раз и поручаю какому-нибудь студенту. Обыграть шахматную программу стало, так сказать, расхожим местом.
– Но, как всегда, низший уровень упрощается, а высший усложняется?
– Вот именно. Поэтому последние программы, те, что сейчас побеждают, в частности, программа, которая победила Каспарова, стали намного сильнее. Глубина перебора значительно выросла и, конечно, это результат наших математических продвижений, а отчасти просто прогресса вычислительной техники. Ведь если раньше рассмотрение 1000 позиций в секунду считалось очень много, то сейчас в тех деревьях, о которых мы с вами уже говорили, рассматривается более миллиона позиций. А лишний миллион — это несколько уровней ходов при правильном отборе. А каждый уровень глубины перебора очень усиливает программу. Каждый уровень на ход вперед — это примерно разряд, и, скажем, глубина перебора в четыре хода — это третий разряд, в пять ходов — уже второй разряд. Когда мы достигаем уровня в 11–13 ходов — это мастерский уровень и дальше играть с машиной довольно сложно. Конечно, сейчас лидируют американцы, потому что умеют вкладывать большие деньги в такие вещи.
– Любая программа искусственного интеллекта для принятия решений нуждается не только в эвристических механизмах, но и в какой-то базе знаний. В каком соотношении в шахматных программах находятся база знаний и алгоритмы, генерирующие позиции?
– В точности никто не скажет, потому что это предмет спекуляции. Были достаточно сильные программы с просто минимальными знаниями, сознательно минимальными, специально для того, чтобы посмотреть, что можно выжать из чистой математики. В какой-то момент это было связано с коммерциализацией и особенно с тем, что стали делать максимально сильные программы — не важно уже за счет чего. Но отчасти из-за того, что работа с заложенными знаниями — самостоятельная задача, то их стало очень много. Прежде всего был создан огромнейший справочник. Сейчас справочники — это сотни тысяч позиций. Затем очень много шахматного интеллекта вкладывают всегда в оценку позиций. Она сводится, конечно, и к игровому материалу, что тривиально, и к некоторым позиционным факторам. Так вот, позиционные факторы — чисто шахматный интеллект, который, конечно, программируется, но здесь его закладывается много и он все время совершенствуется. И чем больше факторов туда вкладывается, тем сильнее программа. В каком-то смысле умение оценить позицию и глубина перебора — вещи взаимозаменяемые. Если бы мы умели оценивать позицию гениально, то нам было бы достаточно попробовать все первые ходы. Это как крайний пример. Понятно, что лучшая оценка позиции соответственно больше влияет на глубину перебора. Таков второй, принципиальный метод. Существует довольно много программ, где шахматный интеллект закладывается в выбор самих рассматриваемых вариантов, то есть каких-то чисто шахматных соображений, каких-то планов. Таких соображений довольно много, что ограничивает круг перебора. Область их действия не очень широкая, и интеллектуально-шахматные специфические данные замедляют перебор. Кстати, именно за интеллектуальные вещи, когда-то очень сильно ратовал Ботвинник. Он был большим энтузиастом машинных шахмат и внес туда некоторые идеи. Хотя ему так и не удалось создать действующую программу, но тем не менее его авторитет был тогда очень высок. Так вот, он очень расстраивался, что, в общем, направление не такое "интеллектуальное", как ему хотелось бы, и в программы вкладывался очень ограниченный объем чисто шахматных знаний.
– А специализированные шахматные компьютеры? Они, видимо, действуют именно методом генерации?
– Конечно, конечно. Во-первых, в смысле генерации перебор схематичен. Во-вторых, не менее важны всякие таблицы позиций, потому что в шахматах повторяемость позиций очень велика. Вы пойдете Е4Е6D4 или же D4Е6Е4 — позиция получится одна и та же, а ведь это всего лишь 3 полухода. А когда мы начинаем углубляться, то повторяемость позиций очень велика. В-третьих, техническая область. Вообще-то в свое время мы строили теории про то, для каких позиций локальные изменения принципиально не могут вести к изменению форсированных вариантов, как создавать своего рода шаблоны. Шаблоны таких вариантов хорошо укладываются в разные чисто технические схемы компьютера. Конечно же, очень важны справочные схемы.
– Есть ли средства для создания универсального мыслительного аппарата, в который можно было бы заложить базу знаний — неважно, шахматные позиции или что-нибудь еще, правила, по которым с этими знаниями надо работать — и получать от него адекватные результаты?
– Ясно, что в плане конструктивности, такая задача сегодня не решаема, не актуальна. Хотя многие интеллектуальные задачи сейчас решаются, такие, например, как распознавание текста. Вы можете положить в сканер листок с текстом и получить его на экране в Word. Он сам прочтется, каждая буковка распознается. Реально мы продвинулись во многих интеллектуальных задачах. Одни из них уже решены, другие решаются. В чем-то получается сравнительно лучше, нежели при участии человека, в чем-то пока еще хуже. Можно привести много примеров практических задач. Что касается универсального искусственного мыслительного механизма, то это, скорее, проблема философская, чем практическая. Ведь даже для такой простой игры, как шахматы, нам потребовалось 30 — 40 лет, чтобы фактически чего-то добиться. Всякая философия основывается на мнениях. Каждый думает, что он прав, а может, каждый прав по-своему. Например, я всю жизнь имел дело с искусственным интеллектом и полагаю, что мозг человека не более чем большая вычислительная машина, следовательно, нельзя сказать, что принципиально невозможно создать аналогичную ей. Вопрос в ее мощности, скоростных характеристиках, в наполнении ее знаниями. Ничего непостижимого здесь нет. Это моя личная точка зрения. Но существуют и другие мнения. Конечно, если мы признаем божественную природу человека, то тогда уже надо выбрать один из двух гносеологических вариантов. Либо да, мы имеем божественную природу, но она познаваема. В таком случае нам не удастся воспроизвести по-настоящему то, что сумел сделать Господь Бог, но, по крайней мере, мы сможем Его творения хотя бы частично воссоздать. Либо же мы стоим на позиции агностицизма, и тогда она непознаваема, и вопрос полностью снимается. Выходит, что некоторые задачи человеческий мозг решает — и тут ни у кого сомнений нет. Но догнать мозг мы не можем, потому что, с одной стороны, он создан Богом, а с другой — познать его мы не в состоянии. Все три позиции связаны с верой, поскольку в реальности-то необязательно познавать все функции мозга. Если мы сделаем машину, по мощности равную мозгу, то ей ни к чему думать так, как мозг. Она по-другому будет работать.
– В психологии, насколько я знаю, интеллектуальное развитие человека определяют по трем критериям: способности абстрагироваться, создавать интеллектуальный ряд и какому-то еще... Насколько эти возможности реализуются в искусственном интеллекте и реализуются ли вообще?
– Полно программ, которые специально нацелены на то, чтобы создавать понятия, абстрагирующиеся от существующего фактического материала. Такие программы хорошо работают. Другой вопрос, что человек умеет создавать эти понятия как бы по своим собственным законам, которые он сам себе придумывает. Все наши попытки перевести эти его законы на язык алгебры логики оказываются бесперспективными. У человека гораздо более мощный мыслительный механизм, который мы просто не знаем. Мы ничего не умеем делать "вообще". Мы создаем необходимые нам формулировки, но "выразить" их в точных машинных задачах не можем. К механическим задачам все сводится с трудом, и даже если сводится, то медленно. Наверное, мы пока не знаем более прямых путей к достижению цели. Заложить-то в компьютер можно все, что угодно. Вопрос в том, что человек способен манипулировать этими знаниями все время, но он еще не умеет заставить делать то же самое машину из-за ограниченного объема и скорости данных.
– Но, может быть, не имеет никакого смысла заставлять машину манипулировать знаниями?
– Здесь затрагивается и аморальный, и конструктивный аспект. Нам пока еще далеко до бунтующих машин. Уж на мой век, да и на ваш тоже спокойствия хватит точно. Мы даже в ограниченных областях не научились пока заставлять машину манипулировать задачами, даже теми, которые она умеет решать. Мы ставим задачу, и она думает лишь по команде.
– Владимир Львович, скажите, если бы сейчас снова была заря компьютерной техники, стоило бы заниматься шахматными программами? Действительно ли они настолько способствовали прогрессу?
– Все-таки шахматы расширяют наши горизонты. В шахматных программах поставлены задачи, результат виден, мы его оцениваем. Все-таки должно быть много решенных, интересных задач, что способствует прогрессу в вычислительной технике.
forany.xyz
История развития компьютерных шахмат ≪ Scisne?
Следующий шаг был сделан после Второй Мировой войны, когда один из лучших математиков того времени Алан Тьюринг создал алгоритм для обучения машины игре в шахматы. В 1947 году он специфицировал первую шахматную программу.
Одновременно с Тьюрингом этой задачей занимался еще один математик – Клод Шеннон. В 1949-1950 годах он обозначил главную проблему: с каждым ходом число вариантов продолжений будет расти. Исследователь выделил два способа перебора вариантов: А-стратегия, с перебором всех без исключения вариантов, и B-стратегия, отбрасывающая неподходящие варианты, исходя из шахматного опыта людей.
Первый компьютер был спроектирован фон Нейманом для ведения сложных расчетов при создании ядерного оружия. В 1950 году появился первый образец, способный производить 10000 операций в секунду. Одним из первых экспериментов с аппаратом стало написание шахматной программы, правда, шахматы были нестандартные – на доске 6*6 без слонов. Через несколько лет этот компьютер ("MANIAC") сыграл с людьми: сильный шахматист одержал уверенную победу, а новичок проиграл за 23 хода.
В СССР разработкой шахматных компьютеров занялись в 1963 году. До 1980 года "Каисса" обыгрывала американские варианты, но дальше, как известно, отставание в развитии вычислительной техники не позволило добиваться новых результатов.
Принципы и алгоритмы компьютерных шахмат
Как уже было сказано, главная проблема – это слишком большое количество вариантов. А сколько это в реальности? В обычной позиции в среднем существует порядка 40 возможных ходов, и столько же ответных. Т.е. каждая пара полуходов – это 1600 позиций, две пары 1600*1600=2,5 млн. позиций, три пары – 4 млрд. позиций.Математики оценивают количество различных шахматных партий величиной 10 в 120 степени – так называемое Число Шеннона (для сравнения – число атомов в изученной части вселенной – 1080). Число различных позиций, возникающих на шахматной доске во время игры, несомненно, меньше, ведь в разных партиях могут возникать одинаковые позиции. Рассчитанное число позиций в шахматах около 1043, включая некоторые невозможные позиции. Условно, с учетом легальности позиций, можно считать их количество приблизительно равным 1040.
Если заложить абсолютно все позиции в базу данных компьютера, то игра шахматной программы станет идеальной из любой позиции и всегда будет приводить к лучшему исходу (если позицию хотя бы в каком-то варианте можно выиграть, программа обязательно найдет этот выигрыш). Однако, чтобы записать все эти позиции на носитель информации, понадобится хранилище данных, физические размеры которого сопоставимы с размером Луны.
Поэтому компьютерам остается только возможность делать анализ по ходу партии, рассчитывать ближайшие несколько ходов и оценивать позицию в перспективе.
Сколько ходов могли просчитать компьютеры? Производительность первых моделей составляла лишь 500 позиций в секунду, т.е. лишь 1.5 хода, если считать время хода – 3 минуты, а это – уровень начинающего шахматиста.
В 1958 году ученые Питтсбургского университета придумали "алгоритм альфа-бета", позволяющий отбросить большое количество вариантов без ущерба для конечного результата. Стоит отметить, что альфа-бета-поиск и его разновидности составляют ядро и современных шахматных программ. В чем суть: анализируется первый вариант, если второй вариант хуже первого – его не надо считать до конца, так как в любом случае из этих двух вариантов будет выбран первый. В результате работы данного алгоритма требуется просмотреть на порядок меньше позиций, и ЭВМ смогли просчитывать уже 5-6 полуходов, самые быстрые – даже 7. Компьютеры стали играть сильнее, но все же соревноваться с сильными игроками еще не удавалось.
Кстати, в разработку эффективных методов перебора внесли большой вклад и советские математики Брудно и Арлазаров. Известным математиком Александром Брудно, много сделавшим в области шахматного программирования, был разработан специальный алгоритм так называемого ранжирования, позволяющий компьютеру в опредленной позиции играть наилучшим образом. Это был прототип современных баз малофигурных окончаний. Правда, в те далекие времена требовались не одни сутки для расчетов 4-5 фигурных окончаний. Владимир Арлазаров - один из создателей шахматной "Каиссы", победившей на чемпионате мира среди шахматных программ в 1974 году.
При разработке вышеперечисленных алгоритмов решалась, прежде всего, математическая задача, то есть подход изначально был "компьютерным". Но есть и другой вариант: проанализировать опыт ведущих шахматистов и формализовать принципы игры, которыми пользуется человек. Такой компьютер будет играть быстрее и "по-человечески". Задача не из легких, первым за нее взялся Михаил Ботвинник. Он потратил много лет на создание собственного шахматного компьютера, но, к сожалению, не довел работу до конца, оставив лишь массу теоретических материалов.Суперкомпьютеры
Следующим шагом было создание компьютеров специально для шахмат, позволяющих совершать большое количество операций в секунду. Первый такой компьютер был создан в лаборатории Белл Кеном Томпсоном, он производил 180000 операций в секунду (обычные компьютеры – лишь 5000) и просчитывал позицию на 8-9 полуходов, что соответствовало уровню мастера. Этот компьютер победил Всемирном шахматном турнире компьютеров, и во многих других турнирах в начале 80-х, но уступил новому гораздо более мощному Cray X_MPs. Компьютер Томпсона был усовершенствован, но так и не смог победить лидера. Далее появился Chip Test и Deep Thought, способный считать 500 000 операций в секунду. DT сыграл две партии с действующим чемпионом мира Каспаровым и проиграл обе, зато одержал победу над несколькими гроссмейстерами.Этой разработкой заинтересовались представители IBM, и работа продолжилась – был создан знаменитый Deep Blue, победивший на турнире компьютеров, и выигравший у сильнейшей шахматистки мира – Юдит Полгар. Одновременно проводился блиц-турнир с участием программы Fritz, поделившей первое место с Каспаровым, и уступившей ему лишь в дополнительном матче.
Насколько глубоко должен считать компьютер, чтобы соревноваться с сильнейшими шахматистами? Нагляднее всего оценить соотношение с уровнем Эло:
- 1 полуход – 200 Эло
- 4 полухода – 1230 Эло
- 9 полуходов – 2328 Эло
- 14 полуходов – 2800 Эло
В 1996 году состоялся первый матч Deep Blue с Каспаровым, в котором чемпион мира одержал победу со счетом 4:2. Deep Blue – это 6-ти процессорный суперкомпьютер, способный просчитывать 100 млн позиций в секунду. Через год состоялся матч реванш с модернизированным 8-процессорным Deep Blue, считающим вдвое быстрее. Компьютер впервые победил лучшего шахматиста со счетом 3.5:2.5. В то время компьютер не умел оценивать позицию и строить игру на основании этой оценки. Рост силы игры достигался исключительно за счет увеличения мощности "железа". Даже алгоритм перебора все еще использовался "брутфорс", то есть перебирались все варианты, но очень быстро.
Суперкомпьютер – вещь штучная, рядовому пользователю недоступная. Дальнейшее развитие было связано с улучшением алгоритмов и снижением требований к аппаратной части, тем более, что и персональные компьютеры все это время не стояли на месте. В матче с Крамником играл Deep Fritz на двухпроцессорном сервере Compaq ProLiant DL760 на процессорах Xeon и RAM 2-16Гб. Такой компьютер, конечно, рядовому пользователю еще недоступен, но все же он выпускается серийно. Матч закончился вничью со счетом 4:4.
В 2003 году состоялся еще один матч Каспарова против компьютера – с Deep Junior, работавшем на 4х-процессорной системе с процессорами Pentium IV 1.9 ГГц и 3 Гб оперативной памяти. Junior – первая программа, демонстрирующая "человечную" игру, и способная пойти на жертву ради инициативы. Матч закончился вничью. В следующем матче Каспаров играл на виртуальной трехмерной доске в 3D-очках, делая ходы при помощи голосовых команд. Этот матч также закончился вничью.
Шахматные базы данных
Было бы странно не использовать накопленный людьми опыт. Создание дебютных баз позволило вообще не считать позицию первые 20-25 ходов, а пользоваться готовыми наработками. Но и опыт компьютеров также пригодился: начиная с 1980-х годов Кен Томпсон стал создавать базу 4-х и 5-ти фигурных эндшпильных окончаний. Теперь компьютеру не надо считать по новой – можно использовать существующие наработки. Эндшпильные базы постоянно дорабатываются и пополняются, в ход пошли уже 6-7-фигурные эндшпили.Соревноваться с компьютером в эндшпиле стало гораздо сложнее – ведь ошибки программа не допустит, сколько бы ходов не занял розыгрыш, зато ошибкой шахматиста очень даже воспользуется. Иногда для победы нужно сделать сотню точных ходов, что человеку удается крайне редко.
Возможна ли ситуация, когда дебютная база соединится с эндшпильной, и компьютер будет "начинать и выигрывать"? С увеличением на 1 фигуру количество возможных ходов увеличивается значительно, а значит, требуется гораздо больше времени и ресурсов, и 7-фигурные эндшпили пока еще только начали просчитывать.
Эндшпильные таблицы Налимова – базы данных шахматных окончанийТаблицы Налимова названы именем новосибирского программиста Евгения Налимова, который предложил эффективный алгоритм для абсолютно точного расчета шахматных окончаний. Созданные Налимовым удачные алгоритмы используются для генерации эндшпильных баз данных.
В настоящее время все ведущие компьютерные программы для игры в шахматы имеют опцию для подключения таблиц Налимова в целях ускорения рассчета эндшпильных окончаний.
В таблицах Налимова имеются абсолютно точные варианты развития шахматной партии в эндшпиле. С помощью таблиц Налимова определяются все возможные варианты продолжения игры, все возможные результаты и через сколько ходов, при идеальной игре, партия придет к тому или иному результату.
Время расчета таблиц Налимова экспоненциально возрастает с количеством участвующих фигур. Для расчета всех 5-фигурных таблиц на компьютере требуется 3 дня, для расчета 6-фигурных таблиц - около 1-2 лет, а всех 7-фигурных – уже около 300 лет. Таким образом время становится непреодолимой преградой для расчета точных баз всех 32-х фигур. С возрастанием производительности современных компьютеров, сроки рассчета значительно снижаются.
К настоящему времени имеются базы данных, рассчитанных по таблицам Налимова, для всех 3-х, 4-х, 5-и, 6-и (включая двух королей) фигурных окончаний. Решения для 7-фигурных окончаний все еще рассчитываются, предположительно (с учетом роста произвдительности компьютеров), такие таблицы будут готовы к уже 2015 году.
Можно ли победить компьютер в шахматы
Компьютеры стали играть гораздо сильнее, а при игре в быстрые шахматы, где времени на счет мало, шансов у шахматиста практически не оставалось. Пришло время искать слабые места.Чем отличается игра компьютера? В первую очередь, надежностью. Программа строго следует алгоритму и неспособна на авантюры. Логика игры не соответствует человеческой, например, в одной из партий компьютер предпочел мат в пять ходов с жертвой ладьи взятию ферзя в один ход, хотя большинство шахматистов выбрали бы второй вариант – ведь с лишним ферзем сложно не выиграть. Компьютер опирается на базы, поэтому найденная дебютная новинка или просто нестандартный, пусть и слабый, ход – это шанс в борьбе с ним.
В 5-6, и частично в 7-фигурном эндшпиле программа заведомо будет играть идеально, без ошибок. А вот при большем количестве фигур возможности живого игрока возрастают.
При переборе позиций на некоторую глубину, компьютер их оценивает, и в конечном итоге выбирает вариант, в котором получит преимущество. Как производится оценка? По формальным факторам, выраженным в условных пешках. Оценивается непосредственно наличие фигур, их активность, расположение пешек: изолированные, сдвоенные, проходные, отсталые, контроль полей в центре и вблизи короля и т.д. Чем точнее модель оценки позиции, тем лучше программа владеет позиционной игрой, но поскольку модель жестко задана, то именно здесь компьютер легче всего "подловить" – например, программа неуверенно ведет себя в закрытых позициях. Ну и главное "оружие" человека – это нестандартность мышления. "Антикомпьютерные шахматы" повысили шансы гроссмейстеров в игре с искусственным интеллектом. Но выявление слабостей немедленно привело к работе по их устранению.
Современные шахматные программы
С развитием технологий производительности персональных компьютеров стало хватать для работы программ с высоким рейтингом Эло. Программы стали модульными: отдельно создаются интерфейс, базы данных и движки. Отдельные модули совместимы и используют единый протокол UCI. Базы данных включают в себя дебютную энциклопедию, эндшпильные окончания, а также все партии, сыгранные на турнирах высокого уровня. Базы регулярно обновляются и доступны для любителей и профессионалов.Помимо коммерческих программ стали появляться частные разработки. Первым появился движок Ruffian, который сначала потеснил Fritz и Shredder, но новые версии "гигантов" оказались сильнее. Следующим "нарушителем спокойствия" стал движок Fruit, игравший с каждой версией все лучше и лучше. Fritz’у понадобилось выпустить девятую версию, чтобы на равных вести борьбу с новичком.
А пока "старички" воевали с "новичками" появилась она – шахматная программа Рыбка. Созданная шахматистом с высоким рейтингом, побеждающая всех и вся и с каждой версией подтверждающая свое превосходство. Первая версия "рыбки" не умела играть эндшпили – но до них и не доходило дело! Впервые программа научилась хорошо вести позиционную игру. Васик Райлих отошел от традиционной оценки позиции, а вместо нее использовал таблицы готовых оценок, полученных в результате анализа большого количества партий. Рыбка-3 на двухпроцессорном компьютере имеет рейтинг 3250 Эло, что гораздо выше, чем у действующего чемпиона мира.
Сегодня количество шахматных движков насчитывает несколько сотен имен, причем в списке периодически появляются новые. Регулярно проводятся турниры с целью выявить самый сильный движок. Высокая конкуренция и частый выход новых версий способствует постоянному росту уровня игры.
Перспективы шахматных программ
При игре человека с компьютером, есть некая несправедливость – компьютер имеет доступ к множеству баз: дебютных, эндшпильных, партий ведущих игроков. Логично такой доступ дать и шахматисту-человеку. В этом случае борьба искусственного интеллекта с биологическим будет идти в более равных условиях: нестандартность мышления человека против счетных способностей машины. Во многих движках уже реализована возможность игры в шахматы Фишера. В этом случае влияние дебютных наработок также сводится к нулю.Но человеку не обязательно соперничать с компьютером – память (дебютная, эндшпильная и пр.) и безупречный счет вариантов машины в симбиозе с позиционным и творческим мышлением человека могут обогатить и усилить игру. Вспомним матч Каспарова с Deep Blue, где "человечная" игра машины вызвала подозрение, что ее направлял шахматист.
Создатель Рыбки считает, что его программа – это, в первую очередь, аналитический инструмент для самоподготовки шахматиста. И в самом деле, подавляющее большинство серьезных игроков уже используют компьютеры для просчета дебютных вариантов, анализа сыгранных в сильнейших турнирах партий.
Сотрудничество или мошенничество? В крупных турнирах организаторы контролируют отсутствие компьютерных подсказок, но на менее важных турнирах это не всегда реально, что открывает читерам простор для "творчества". Если легализовать использование шахматных программ на турнирах, в партиях, без сомнения, будет намного меньше счетных ошибок, но будет ли интересной такая игра?
И такая легализация уже произошла: интересным шагом в плане развития компьютерных шахмат стали турниры по переписке. По сути, это уже соединение возможностей человеческого интеллекта и математического анализа компьютерной техники. При этом шахматист не должен выполнять функцию оператора ЭВМ, а может активно включаться в анализ вариантов развития партии, помогая компьютеру выбрать лучший.
Казалось бы, если основная схватка происходит между программами, партии будут предопределены и скучны. И действительно, очень много партий по переписке заканчивается вничью. Но не будем забывать, что лишь человек способен играть ярко, рискованно, неожиданно. Пока – лишь человек. А что будет дальше – увидим…
Максим Наумов декабрь 2008 GAMBITER.RU
scisne.net
Компьютерные алгоритмы игры в шахматы ≪ ∀ x, y, z
Почему результат игры в шахматы предопределен? Как происходило развитие шахматных программ? Чем различаются шахматные программы? На эти и другие вопросы отвечает кандидат физико-математических наук Дмитрий Дагаев.
В 1997 году состоялось знаменательное событие — компьютерная программа Deep Blue обыграла чемпиона мира по шахматам Гарри Каспарова в матче из шести партий со счетом 3½ на 2½. Это событие стало поворотным в истории противостояния человека и компьютера.История началась намного раньше. Шахматы — одна из древнейших игр, которая дошла до наших дней. Первые прародители шахмат появились примерно в V–VI веках н. э. В том виде, в котором шахматы дошли до наших дней, они появились к концу XV века. Уже в 1886 году состоялся первый чемпионат мира по шахматам, в котором Вильгельм Стейниц обыграл Цукерторта и получил звание чемпиона мира. Со всеми оговорками, что соперники сами назвали этот матч чемпионатом мира, тем не менее стоит отметить, что, например, первый чемпионат мира по футболу пройдет лишь через 44 года после этой даты. Таким образом, шахматы действительно одна из самых древних, самых устоявшихся и самых традиционных в каком-то смысле игр.
В это же время начинает активно развиваться теория игр — область науки, которая занимается изучением стратегического взаимодействия агентов: людей, компаний, правительств. В 1913 году математик Эрнст Цермело опубликует на немецком языке работу, из которой следует, что результат игры в шахматы предопределен, а именно: если оба соперника играют правильно, то в каждой шахматной партии либо будут выигрывать белые, либо будут выигрывать черные, либо будет ничья. То есть не может произойти такого, что при правильной игре соперников в одной партии выиграют белые, а в другой партии выиграют черные.
Это следует вот из какого соображения. На самом деле шахматы — конечная игра. Благодаря тому, что в шахматах есть положение, согласно которому в случае, если позиция повторяется три раза, фиксируется ничья. В результате этого и в силу конечности различных расстановок фигур на шахматной доске получается, что может быть сыграно хоть и большое, но тем не менее конечное число различных шахматных партий.
Поэтому чисто теоретически можно проделать следующее — можно нарисовать дерево игры в шахматы. Мы начинаем со стартовой позиции, с первого хода белых. Белые на своем первом ходу могут сделать двадцать различных ходов — шестнадцать ходов пешками и четыре хода конями. В ответ на это в каждом из этих случаев черные могут ответить тоже двадцатью различными способами. Таким образом, уже после первого хода в шахматах будет 400 различных возможных позиций. Дальше это дерево будет разрастаться, разрастаться и разрастаться.
Тем не менее в какой-то момент мы всегда придем к терминальной вершине, то есть к такой вершине, в которой игра закончится, но тогда можно проделать следующее. Давайте рассмотрим все поддеревья этого дерева, в которых остается сделать один-единственный ход. Тогда в таком поддереве можно понять, кто выигрывает, если позиция дошла до этого состояния. Игрок, которому принадлежит ход в таком поддереве, выбирает свое оптимальное продолжение, игра заканчивается, становится понятен результат, которым заканчивается игра в этой ситуации, и благодаря этому мы знаем, чем закончится игра, если она дойдет до этой вершины.
Но точно так же можно проанализировать все поддеревья последнего уровня. После этого можно сдвинуться на один уровень назад. Мы уже знаем, чем завершится игра на поддеревьях последнего уровня, поэтому мы сможем понять, чем завершится игра на поддеревьях предпоследнего уровня, и так далее. Значит, мы однажды дойдем до самой первой вершины, с которой и начинается шахматная партия. Таким образом, будет понятно, кто же выигрывает в шахматах.
Проблема заключается в том, что, как я уже сказал, дерево очень большое и просчитать его человеку невозможно. В 1950 году Клод Шеннон высказывает идею о том, что если мы напишем компьютерную программу, которая сможет смотреть вдоль этого дерева на много ходов вперед, то рано или поздно мы просчитаем это дерево до конца. После этого в ведущих математических институтах мира начинается создание шахматных алгоритмов.
Первая шахматная программа была подготовлена в MIT. А уже в 1967 году состоялся первый шахматный матч между шахматными программами. В нем шахматная программа, которая была подготовлена специалистами Института теоретической и экспериментальной физики (ИТЭФ), обыграла со счетом 3:1 программу Стэнфордского университета. Чуть позже состоялся первый чемпионат мира по шахматам среди шахматных программ. К 1974 году были десятки различных алгоритмов, и шахматная программа «Каисса», написанная специалистами Института проблем управления, завоевала в этом турнире первое место, она выиграла все четыре партии из четырех. С тех пор чемпионаты мира среди шахматных программ проводятся регулярно.
В это время программы пока еще проигрывают человеку. В чем, собственно, проблема компьютерных программ? Есть два основных параметра, по которым программы различаются. Во-первых, это глубина просчета. Но эта глубина зависит в основном от мощности процессора. Таким образом, нужно не просто написать программу, которая хорошо играет в шахматы, а нужно, чтобы был достаточно мощный компьютер, который позволит просчитывать дерево игры в шахматы на как можно более далекое число ходов.
Второй компонент, которым различаются шахматные программы, — это оценка конкретной позиции. Чтобы оценить ту или иную позицию, недостаточно просто сравнить наличие одинакового количества фигур на шахматной доске. Нужно понять, у кого стратегическое преимущество, а это невозможно понять без просчета той же самой позиции на несколько ходов вперед. Чтобы адекватно оценить позицию, нужно фактически просмотреть дерево игры на как можно большее число ходов вперед, выбрать то продолжение, приносящее в этот момент стороне, которой принадлежит ход, оптимальную позицию, и присвоить этой ситуации, этой позиции значение оценки, которое получится достичь в лучшем возможном исходе через то количество ходов, на которое мы можем просчитать.
Поэтому чем дальше умеет компьютер, программа просчитывать эту шахматную позицию, тем точнее будет ее оценка конкретной позиции и тем лучше она сможет выбирать из нескольких различных продолжений то, которое будет в каком-то смысле оптимальным. Если теоретически появится компьютер, который будет способен однажды досчитать дерево игры в шахматы до конца, то мы получим ответ на вопрос: «Какой же игрой на самом деле являются шахматы: выигрышные для белых, выигрышные для черных или при правильной игре соперников она будет заканчиваться вничью?»
На 2015 год не существует компьютера, который был бы способен просчитать дерево игры в шахматы до конца.
В 2007 году компьютеры закончили просчет дерева игры в шашки. Оказалось, что шашки — это ничейная игра. Что это означает? Это означает, что против компьютеров в шашки играть теперь абсолютно бесполезно. Компьютер в каждой возможной позиции знает, как играть правильно. Однако это не означает, что людям больше не интересно играть в шашки друг с другом. В каком-то смысле это вопрос, кто где будет ошибаться. Возможность выиграть партию будет означать, что выигравшая сторона сумела найти ошибочное решение другой стороны и эксплуатировать это решение.
В 2015 году была опубликована статья, в которой авторы объявили о том, что они завершили просчет дерева игры в самую простую версию покера. Эти деревья существенно меньше, чем дерево игры в шахматы.
За что сейчас идет борьба? За сокращение различных вариантов, которые нужно просчитывать. Дело в том, что для того, чтобы понять, что происходит в игре, не обязательно рассматривать абсолютно безнадежные позиции для того или иного игрока. Если одна из сторон играет без ферзя и двух ладей, то, скорее всего, она не сможет добиться победы. Тем самым можно существенно сократить размер дерева и упростить задачу для компьютера. Можно выбирать только те продолжения, в которых игроки по-прежнему находятся в игре, то есть борются за результат, и результат еще не предопределен. Однако уже на сегодняшний момент компьютерные программы зашли настолько далеко, что человеку против них играть бесполезно.
В 1996 году Deep Blue сыграл свой первый матч против Гарри Каспарова, и тогда человек был сильнее. Однако уже через год программисты Deep Blue обновили дебютную базу и тем самым существенно упростили задачу для программы — ей больше не нужно просчитывать первые несколько десятков ходов: у нее уже есть все известные варианты, и она понимает, какие из них являются хорошими, а какие нет. То есть она фактически может начинать работать не с первого хода, а с двадцатого, и просчитывать варианты, начиная с этого двадцатого хода. И такой обновленной программы оказалось достаточно, чтобы победить чемпиона мира. В 1997 году Гарри Каспаров признал свое поражение. С тех считается, что человек больше не может на равных противостоять компьютеру.
К 2015 году отдельно проводятся чемпионаты мира среди компьютерных программ, то есть среди софта, среди компьютеров, то есть среди железа и софта, и отдельно среди людей. Соревноваться друг с другом им уже не интересно.
Дмитрий Дагаев кандидат физико-математических наук, доцент кафедры высшей математики НИУ ВШЭПостНаука
forany.xyz
Лучшие шахматные программы для игры и анализа партий
День добрый, дорогой друг!
Компьютеры уже давно играют сильнее человека. Лучшие шахматные программы и подавно, напрямую соперничать с ними на равных невозможно даже сильнейшим шахматистам.
Однако «железный монстр» не так уж и велик и могуч, как можно подумать. У него есть слабые места и недостатки. Которые шахматист любого уровня просто обязан учитывать.
Об этом в конце статьи, а пока заглянем на секунду во внутрь компьютера и сделаем обзор лучших движков и пользовательских интерфейсов.
Что там внутри?
Компьютерная программа (движок) это счетный агрегат. Он считает, оперирует числами и совершенно не понимает, что такое шахматы.
Программа переводит шахматный язык в математические действия. Складывает, вычитает и сравнивает числа. В конце каждого варианта выставляет численную оценку.
Так работают шахматные движки.
Движки
Между движками также проводятся соревнования, состоящие из большого количества игр, гораздо больших, чем между людьми. По результатам составляются рейтинг-листы.
Рейтинг движков 2016
Один из таких наиболее авторитетных листов выглядит так:
Есть и другие рейтинги. В некоторых на первом месте стоит Стокфиш, на втором Комодо.
В целом,можно считать, что эти два движка занимают лидирующие позиции на сегодняшний день. О них чуть подробнее.
Komodo
Komodo занимает первое место в большинстве рейтнгов. Интресно то, что комодо отличается своими мозгами от большинства собратьев.
Он научился лучше оцениватьпозицию и делает ставку на оценку в большей степени, а на глубину расчета - меньшей.
Возможно в этом и кроется секрет. Движок совместил в себе лучшие качества человека и машины. Впрочем это мои предпложения, которые, разумеется, не являются истиной в последней инстанции
Последний коммерческий вариант движка – 11.2. Для бесплатного свободного распространения предлагается Komodo 9 и версии старше.
Скачать можно на главном портале издателя
Stockfish
Это логотип такой. В переводе стокфиш-вяленая рыба. Откуда такая аллегория – не берусь судить
Стокиш соревнуется последнее время с Komodo и Houdini и по ряду показателей оперtжает своих соперников
Успехи Stockfish во многом обязаны политике распространения. Создав усиление, разработчики выкладывают версию для тестирования всем пользователям. Возможно по этой причине серьезных багов почти не осталось.
В большинстве рейтингов Стокфиш занимает 2 или 1 строчку.
Подробнее об этом движке можно прочитать в отдельной статье
Программа бесплатная. Самая последняя версия — восьмерка. Скачать можно здесь: https://stockfishchess.org/download/
Но это еще не все. Движок без интерфейса использовать в практических целях затруднительно.
Оболочки и клиентские программы
Для того, чтобы использовать возможности движка, видеть его работу, нужна оболочка, интерфейс. Пользовательская шахматная программа (оболочка) плюс движок (или несколько) – это и есть готовый, пригодный для использования человеком продукт.
Приведу примеры лучших по моему мнению, оболочек и клиентских программ:
Арена
Одна из самых известных и мощных программ. Можно использовать в качестве пользовательского интерфейса, оболочки для практически всех лучших движков
Скачать/установить можно на официальном сайте Арены.
Chessbase
Пожалуй, самая продвинутая аналитическая программа из известных автору.
ChessBase предоствляет весь необходимый аналитический инструментарий и может:
- Работать с базами партий– смотреть сыгранные партии и анализировать
- Проводить поиск по опрееленным параметрам: дебюты, позиции, соотношение материала, эндшпили и другое.
- Загружать свои партии, с комментариями и картнками
- Анализировать, подбирая различные движки
- Создавать досье игроков, на основе баз данных
- Распечатывать партии и диаграммы в различных конфигурациях
А также многое другое.
Последняя версия программы – ChessBase-13
Официальный сайт издателя: http://en.chessbase.com/ Ссылок на скачивание бесплатных версий не даю, ибо пиарить сомнительные для меня сайты и файлохранилища не считаю возможным.
Как русифисировать интерфейс и подключить движок, я писал в этой статье
Shredder Classic 3
Один из лучших шахматных движков Шреддер в комплекте с интерфейсом.
Возможности
- Загрузка и редактирование позиций
- Возможность игры как с движком на разных уровнях, так и по сети с реальными соперниками
- Выбор контролей времени, возможность создать свой контроль.
- Анализ и партий и позиций
- Настройка интерфейса: дизайн доски и фигур и т.п фигур и т.п дальше.
Полная версия не бесплатная. Для начала можно скачать условно-бесплатный вариант.
Шахматная планета
Специализированная программа, связанная с порталом http://chessplanet.ru/, где можно играть онлайн, в турнирах, по переписке, играть по переписке. Проводятся конкурсы и много всего интересного.
Клиентская программа устанавливается на компьютере пользователя и предоставляет возможность играть, общаться на форуме, просматривать и анализировать партии, смотреть уроки, и другое.
Есть и упрощенная версия, когда можно играть в браузере без установки клиентской программы на комп.
Установить клиент и познакомиться с порталом подробнее можно здесь
BabasChess
Многоязычный интерфейс (русского правда не нашел) для игры через интернет.
Сочетает простоту использования и довольно широкий спектр функций. Этим и подкупает.
Работает на Windows. Также может работать в Linux
Установить можно здесь
Для обучения
Для начинающих шахматистов и для обучения, на мой взгляд, лучше использовать многопрофильные шахматные порталы или онлайн-школу.
Однако есть и автономные программы. Например, на смартфон можно установить:
Обучение шахматам — от простого к сложному
Что-то вроде навигатора в мире шахмат. Приложение покажет основные правила и даст советы по улучшению игры.
Обучающий курс содержит более сотни тем. В том числе основные приемы и типичные комбинации. Более 1000 различных примеров.
Ознакомиться подробнее и установить можно здесь
Не верь глазам своим
Лучшие шахматные движки уже отчасти «очеловечены» и в плане оценки позиции похожи на людей. Однако и они ошибаются. Причем грубо.
Всего один пример, самый простой:
Позиция «в доску» ничейная и это известно большинству шахматистов, не только мастерам. Да и догадаться не трудно – черный король сидит в углу и выкурить его оттуда невозможно. Ни мат поставить, ни пешку провести. А прижал углу — пат.
Так вот, большинство движков, даже самых современных, — оценивает эту позицию как выигранную за белых. Стокфиш дает +7. Не верите – можете проверить сами.
На самом деле таких примеров, когда машина грубо ошибается в оценке позиции, — я мог бы привести с десяток точно. Почему это происходит, мне неизвестно, но факт есть факт.
Отсюда вывод: обожествляя компьютер, не лишним будет помнить, что и «на старуху бывает проруха». Получается, что не только мы проверяем свои расчеты с помощью компьютера. Иногда требуется и обратный процесс. Вот такие дела.
Благодарю за интерес к статье.
Если вы нашли ее полезной, сделайте следующее:
- Поделитесь с друзьями, нажав на кнопки социальных сетей.
- Напишите комментарий (внизу страницы)
- Подпишитесь на обновления блога (форма под кнопками соцсетей) и получайте статьи к себе на почту.
Удачного дня!
chessmatenok.ru
Шахматный компьютер - это... Что такое Шахматный компьютер?
Шахматный компьютер — специализированное устройство для игры в шахматы. Обычно используется для развлечения и практики игроков в шахматы при отсутствии партнёра-человека, в качестве средства для анализа различных игровых ситуаций, для соревнования компьютеров между собой. Представляют собой развитие идеи «шахматного автомата», возникшей в XVIII веке.
Потребительские шахматные компьютеры обычно выполняются в виде шахматной доски с дисплеем и набором клавиш для выполнения необходимых игровых действий. В зависимости от конструкции, доска может быть никак не связана с компьютерной частью и не иметь электроники, или наоборот, представлять собой дисплей, отображающий графическое представление игровой ситуации.
В СССР с середины 1980-х годов выпускались потребительские шахматные компьютеры Электроника ИМ-01, Электроника ИМ-05, Электроника ИМ-29 («Шахматный партнёр»), Интеллект-01 и Интеллект-02, Дебют, Феникс и другие.
Большинство программ основано на методе перебора ходов, существуют программы, основанные на эвристических методах. Попытка создать настоящую шахматную программу, на основе алгоритма шахматного мастера, предпринималась экс-чемпионом мира М. Ботвинником и его ассистентами-программистами — Б. Штильманом и А. Резницким.
См. также
Ссылки
Фотографии отечественных шахматных компьютеров
| В этой статье не хватает ссылок на источники информации. Информация должна быть проверяема, иначе она может быть поставлена под сомнение и удалена. Вы можете отредактировать эту статью, добавив ссылки на авторитетные источники. Эта отметка установлена 27 июня 2012. |
dic.academic.ru
Шахматная машина — гроссмейстер ≪ ∀ x, y, z
Сорок лет назад в журнале "Scientific American" была опубликована статья с описанием оригинального проекта шахматного компьютера. С тех пор машины побеждали сначала новичков, затем мастеров, а теперь уже и гроссмейстеров. Будет ли следующим Гарри Каспаров?
В ЯНВАРЕ 1988 г. на пресс-конференции в Париже чемпиона мира по шахматам Гарри Каспарова спросили, сумеет ли компьютер выиграть у гроссмейстера до 2000 года? «Ни в коем случае, - ответил он, - и если у кого-нибудь из гроссмейстеров возникнут затруднения в игре с компьютером, я с удовольствием дам им совет».
 ЧЕМПИОН МИРА Гарри Каспаров и компьютер IBM PS/2, с помощью которого осуществляется связь с «Глубокой мыслью», перед началом матча против машины, состоявшегося в конце 1989 г. Каспаров победил, несмотря на гроссмейстерский рейтинг «Глубокой мысли». |
Спустя 10 месяцев после заявления Каспарова, на крупном турнире, состоявшемся в Лонг-Биче (шт. Калифорния), гроссмейстер БентЛарсен, в прошлом претендент на мировую корону, потерпел поражение в поединке с играющей машиной, которую мы сконструировали в качестве своего аспирантского проекта в Университете Карнеги - Меллона. Машина, представляющая собой сочетание программ и специализированной аппаратуры и названная "Deep Thought" («Глубокая мысль»), выиграла еще 5 встреч, одну проиграла и одну свела вничью, разделив с гроссмейстером Энтони Майлсом первое место на турнире. Поскольку машинам не присуждается денежная премия за победу в турнире, Майлс положил в свой карман первый приз в размере 10 тыс. долл. («Глубокая мысль» все же победила Майлса через год в показательном матче.)
К лету 1990 г., когда трое из нас поступили на службу в корпорацию IBM, «Глубокая мысль» достигла 50%-ного успеха в 10 встречах с гроссмейстерами и 86%-ного успеха в 14 играх против мастеров международного класса. Некоторые из числа этих матчей, а также десятки других игр, сыгранных против менее именитых соперников, проходили под эгидой шахматной федерации США, которая по результатам игр определила шахматный рейтинг машины. Он оказался равным 2552. Этот рейтинг соответствует уровню нижней половины гроссмейстерского диапазона. В то же время средний турнирный игрок имеет рейтинг примерно 1500 очков). Теперь, когда компьютер достиг своей нынешней скорости анализа ситуаций на доске - 750 тыс. позиций в секунду, - рейтинг машины еще более возрос и превысил 2600.
Машина следующего поколения, которая, как ожидается, сыграет свою первую партию в 1992 г., будет обладать значительно более мощными аппаратными средствами. Быстродействие при анализе ситуаций возрастет более чем в 1000 раз и выйдет на уровень примерно одного миллиарда позиций в секунду. Благодаря только этой способности «Глубокая мысль», вполне возможно, станет играть в шахматы сильнее Каспарова или любого другого даже более способного шахматиста, если такой появится.
Зачем же потребовалось учить машину загонять в угол деревянного короля на шахматной доске? Во-первых, шахматы всегда рассматривались в традициях западной культуры как изысканная игра разума и, по словам Гете, «как пробный камень интеллекта». Многие люди утверждают, что успех машины в шахматной игре послужит доказательством того, что человеческое мышление можно смоделировать, или же, наоборот, что шахматы не требуют мышления как такового. В любом случае, однако, тот или иной вывод значительно изменит наши представления о том, что мы обычно называем интеллектом.
С другой стороны, создание компьютера, умеющего играть в шахматы, представляет собой увлекательную техническую проблему. Она была описана на страницах журнала "Scientific American" 40 лет назад Клодом Шенноном, основоположником теории информации (см.: Shannon С.Е., A Chess-Playing Machine, "Scientific American", February, 1950). Приведем выдержку из этой статьи:
Цель исследований, связанных с созданием шахматной машины, заключается в том, чтобы разработать техническое средство, которое можно было бы применить в практически более важных приложениях. Построение шахматной машины является идеальным началом по нескольким причинам. Задача строго определена как в смысле дозволенных операций (шахматные ходы), так и в смысле конечной цели (поставить «мат» королю). Она не настолько проста, чтобы быть тривиальной, но и не настолько трудна, чтобы не поддавалась решению. Кроме того, такая машина могла бы соревноваться с человеком, что позволило бы однозначно судить о способности машины к логическим рассуждениям подобного типа.
По-видимому, наиболее важное практическое значение разрабатываемых шахматных программ заключается в демонстрации эффективности выбираемых методов компьютерного анализа. Усовершенствование используемых в этих программах методов обещает определенный прогресс в конструировании сетей, моделировании химических реакций и даже лингвистическом анализе.
ПЕРВАЯ попытка практически реализовать идею создания играющей в шахматы машины была предпринята в 60-х годах XVIII в., когда барон Вольфганг фон Кемпелен начал демонстрировать свой шахматный автомат, разъезжая по Европе. Машину прозвали «турком», поскольку ходы на доске выполняла усатая кукла с тюрбаном на голове, которая, очевидно, приводилась в движение замысловатым механизмом, спрятанным в основании машины. Обычно машина играла довольно хорошо и однажды привела в бешенство Наполеона Бонапарта, выиграв у него за 19 ходов. Эдгар Алан По, как и многие другие, впоследствии разгадал секрет автомата: его ходы делал опытный шахматист карликового роста, скрытый в потайном отделении. Однако По неправильно аргументировал свою догадку: по его мнению, эпизодические проигрыши «турка» находились в противоречии с предполагаемым совершенством, присущим настоящему автомату.
Алан М. Тьюринг, английский математик, пионер информатики и специалист в области криптографии, был в числе первых, кто начал рассматривать перспективу создания компьютера, играющего в шахматы. Однако ему было легче разработать свою простую программу, генерирующую ходы и оценивающую позиции на доске, при помощи карандаша и бумаги, чем прибегнуть к помощи компьютера. Аналогичные попытки совершали Конрад Цузе в Германии и другие ученые, однако основополагающая работа была выполнена Шенноном. Ему удалось развить идеи Джона фон Неймана и Оскара Моргенштерна, которые в рамках своей универсальной теории игр изобрели так называемый минимаксный алгоритм, позволяющий вычислять наилучший ход в заданной ситуации.
Эта процедура определенным образом представляет произвольно большое число позиций, могущих возникнуть в результате каждой возможной последовательности ходов, ставит им в соответствие некую числовую оценку и затем движется в обратном направлении, отправляясь от этих конечных оценок, чтобы выбрать наилучший первый ход. Процедура начинает свою работу после того, как генератор ходов получит все ходы, которые компьютер может сделать в данной позиции, затем все возможные ходы противника и т.д. Каждый шаг по цепочке событий на доске называется полуходом в шахматной терминологии или слоем в терминологии теории игр.
Каждый новый слой в ветвящемся дереве анализа охватывает приблизительно в 38 раз большее количество позиций (среднее количество ходов в шахматной позиции), чем предыдущий слой, или в 6 раз большее количество позиций в случае, когда используется метод «альфа-бета-усечения» (см. диаграмму). Поэтому большинство возможных позиций находится на самых внешних частях ветвей дерева игры, «наращиваемых» до тех пор, пока не кончится игра, или время, отпущенное компьютеру, не будет исчерпано. Оценивающий функционал присваивает каждой конечной позиции определенное числовое значение, например 1 для позиции «мат» противнику, - 1 для позиции, в которой выигрывает противник, и 0 для ничейного исхода. Можно регистрировать также и менее явные преимущества и недостатки позиций. Например, компьютер может подсчитывать материальный баланс, выражаемый в количестве фигур и пешек, и вычислять оценку позиций с учетом расположения фигур на доске, положения пешек, занятия ими свободной вертикали, контроля за центральной частью доски и т.д.
 Чтобы найти наилучший ход, программа генерирует дерево вариантов, оценивает конечные позиции и возвращается назад. Позиции программа оценивает по своему разумению; чем больше очков, тем лучше позиция. Простой метод, называемый минимаксным алгоритмом, отбирает лучшие варианты, отыскивая максимальные оценки для ходов компьютера и минимальные оценки для ответов противника. На верхнем дереве узлы В и Е минимизируются до 3 и -1 соответственно, а узел А максимизируется до 3. С помощью этого простого подхода прибавить еще один слой поиска можно, если увеличить объем обработки данных в 38 раз (число ходов в типичной шахматной позиции). Альфа-бета усечение повышает эффективность алгоритма, позволяя игнорировать не представляющие интереса линии игры, поэтому достаточно шестикратного увеличения быстродействия, чтобы анализировать лишний слой. Если, например, оценивание начинается с узла С и следует по правой ветви, то компьютер присваивает В значение 3 и затем замечает, что оценка Е меньше или равна 2, и ему уже не нужно анализировать F. Другой метод, называемый сингулярным продолжением, фокусирует внимание на критических позициях. На нижнем дереве значение В сильно зависит от С, в то время как значение D не зависит ни от одной из последующих ситуаций. Чтобы увеличить надежность оценки А, алгоритм, следовательно, проанализирует С на один слой глубже, чем обычно. Этот прием позволяет «Глубокой мысли» очень хорошо и далеко предвидеть развитие игры во многих, тактически сложных позициях. |
Можно усилить игру компьютера, повышая его способность к поиску или улучшая чувствительность к факторам, влияющим на оценку позиции. Безупречной игра компьютера будет в том случае, когда он сумеет генерировать все возможные направления развития игры вплоть до конечных позиций, в которых либо машина, либо ее противник попадут в матовую ситуацию или игра закончится вничью. Такой компьютер мог бы удивить своего противника, объявив на первом же ходе: «Белые начинают и выигрывают на 137 ходу» или же, наоборот, сдавшись в неочевидной позиции, признав ее как безнадежную. Подобный исчерпывающий анализ не представляет серьезных затруднений в таких простых играх, как «крестики-нолики», но неосуществим в шахматах, допускающих 10120 различных развитии игры. В одинаковой степени совершенной игра могла бы стать и при исследовании только одного слоя игры при условии, что оценка позиций настолько же хороша, насколько ее можно охарактеризовать словами Ричарда Рети, шахматного мастера, успешно выступавшего в 20-х годах, когда он сказал, что видит игру лишь на один ход вперед - наилучший.
ОЧЕНЬ далеко до таких заявлений было тем программистам, которые первыми пытались создавать шахматные программы. До 1958 г. они даже не могли научить машину строго соблюдать правила игры. Прошло еще восемь лет, прежде чем программа "МасНаск-6", написанная Ричардом Д.Гринблаттом из Масса-чусетского технологического института, впервые достигла уровня средних турнирных игроков.
По мере того как число людей, занимавшихся шахматными программами, росло, они стали делиться на два лагеря. Назовем их условно лагерем моделирования и техническим лагерем. Сторонники первого направления утверждали, что компьютеры должны играть так же, как люди, и быть способными логически «рассуждать» при выборе хода. Представители другой группы придерживались менее строгих требований к компьютеру. То, что хорошо для людей, говорили они, может оказаться неприменимым для компьютера. Сторонники моделирования имели преимущество на начальном этапе, пока компьютерные шахматы оставались скорее теорией, чем практикой.
В 70-х годах технический лагерь вышел на первый план, когда выяснилось, что глубина анализа игровой ситуации почти линейно коррелирует с рейтингом шахматной программы. Каждый дополнительный слой анализа прибавлял примерно 200 очков в оценке способностей компьютера. Поэтому программисты стали обращаться ко все более быстродействующим машинам и изобретать различные технические уловки, позволявшие добиться большей глубины анализа при доступных вычислительных мощностях.
 ВОЗРАСТАЮЩАЯ СИЛА компьютеров проявляется при наложении рейтингов 35 тыс членов шахматной федерации США и машин, обладающих различной глубиной анализа (зеленый). Компьютеры приобретают примерно по 200 очков на каждый дополнительный полуход, или слой игры, который они анализируют. Сейчас «Глубокая мысль» исследует 10 слоев и имеет рейтинг примерно 2600 очков. Ее преемница будет способна анализировать 14 или 15 слоев, и ее рейтинг будет намного выше. |
Однако глубокий анализ - это лишь полдела. В самом начале шахматного программирования программы поиска лучшего хода генерировали позиции практически без всякого их анализа. Вариации, ведущие к одной и той же позиции, они рассматривали как различные ветви в процессе поиска. Такое излишнее дублирование теперь блокируется путем слежения за позициями в массивах памяти, известных под названием кэш-таблиц. Кэш-таблицы обеспечивают еще большее преимущество, помогая альфа-бета-алгоритму отбрасывать многие не представляющие интереса ветви в развитии игры.
Важнейшая проблема в анализе возможных ситуаций и поиске наилучшего хода - это умение определить, в какой момент следует прекратить анализ бесчисленных ветвей игрового дерева. Невозможно исследовать все ветви до конца, но желательно не прекращать анализа по крайней мере в нестабильной позиции. Такие ситуации могут, например, возникать, когда анализ прекращается в процессе размена фигур. Предположим, что компьютер просматривает все ветви вперед ровно на восемь уровней и доходит до позиции, в которой он на этом восьмом уровне, кажется, выигрывает коня в обмен на пешку. Даже в том случае, если противник следующим ходом вернет себе коня и сохранит преимущество в одну пешку, компьютер все-таки будет стремиться к этой позиции, дающей ему мнимое материальное преимущество.
Этот так называемый эффект горизонта может вынудить компьютер совершить своеобразное шахматное самоубийство, чего нельзя ожидать при игре даже самого слабого игрока с сильным. Совершенно неожиданно и, казалось бы, без всякой причины с точки зрения наивного наблюдателя машина начинает раздавать свои пешки и фигуры, безнадежно ухудшая свою позицию. Чтобы снизить вероятность подобных ошибок, практически во всех шахматных программах дополнительно к основному анализу предусматривается стадия стабилизирующего анализа. При таком дополнительном анализе исследуются лишь те последовательности ходов, в которых теряются или приобретаются пешки и фигуры, и поиск хода продолжается до тех пор, пока не будет достигнута стабильная позиция, легко поддающаяся оценке при помощи статических параметров.
В 70-е и 80-е годы доминировали так называемые «силовые» машины (brute-force machine), поскольку эффективность их игры в основном определялась замысловатой реализацией стратегии основного и стабилизирующего анализа. Почти весь этот период проходил под знаком превосходства программы Северо-западного университета "Chess 4.0" и программ из серии «4-Х», которые последовали за ней. Программа Северозападного университета переходила с одного поколения компьютерной аппаратуры на другое, постоянно увеличивая свой рейтинг, пока он не превзошел мастерского уровня (2000 очков) в 1979 г.
В 70-х годах было сделано также несколько первых попыток создания специализированных шахматных машин. Наиболее известная из этих машин, созданная в компании AT&T Bell Laboratories и названная "Belle", преодолела в 1983 г. барьер в 2200 очков, соответствующий уровню мастера в американской шахматной федерации. Эра чисто силовых машин достигла своего апогея в 1986 г., когда на шахматной арене появилась программа "Cray Blitz", выполняющаяся на суперкомпьютерах серии "Cray", а также система "Hitech" - специализированная шахматная машина, генерировавшая ходы на 64 процессорных микросхемах, по одной на каждую клетку игрового поля. "Hitech" выиграла чемпионат Северной Америки по шахматам среди компьютеров в 1985 г., а "Cray Blitz" победила на чемпионате мира 1986 г., выиграв в дополнительном матче у "Hitech", так сказать, в последнем раунде. "Cray Blitz" и "Hitech" анализировали соответственно 100 и 120 тыс позиций в секунду.
У «Глубокой мысли» довольно необычная история. Во-первых, она разрабатывалась группой выпускников университета, не имевших официальной финансовой поддержки или прямого руководства на факультете. (Сотрудники факультета, занимавшиеся в Университете Карнеги - Меллона исследованиями в области шахматных программ, не сотрудничали с группой разработчиков «Глубокой мысли».) Во-вторых, члены группы специализировались до этого в разных областях и потому их подходы часто оказывались нетрадиционными.
В ИЮНЕ 1985 г. один из нас (Сюй) пришел к выводу, что можно создать генератор ходов в виде единого процессора на базе сверхбольших интегральных микросхем (СБИС), поставляемых научным учреждениям Агентством по научно-исследовательским разработкам в области обороны (DARPA). Сюй построил генератор ходов на базе системы "Belle", придумав несколько усовершенствований, благодаря которым устройство можно было реализовать в единой микросхеме очень высокой степени интеграции. Ему удалось также сконструировать кристалл таким образом, чтобы эффективно расположить его электронные элементы (включая 35 925 транзисторов), несмотря на то, что самые мелкие элементы имели довольно большие размеры (3 мкм). Изготовление кристалла с элементами указанного размера взяла на себя фирма MOSIS, работающая по контракту с агентством DARPA. Сюй затратил шесть месяцев на конструирование, моделирование и разводку микросхемы, после чего прошло еще четыре месяца, прежде чем он получил первые рабочие образцы устройства. Он проверил работу процессора, подключив его к компьютерной рабочей станции,и установил, что устройство способно обрабатывать до двух миллионов ходов в секунду, т.е. в 10 раз быстрее, чем матрица "Hitech", состоявшая из 64 микропроцессоров.
После этого Сюй привлек к проводимой им работе Т. Анантарамана - аспиранта с факультета информатики, специализировавшегося на распознавании речи. Анантараман написал небольшую шахматную программу, генерировавшую ходы на основе программного моделирования. Заменив программный модуль генерирования ходов тестером Сюя, Анантараман повысил скорость анализа программы в пять раз, и в результате быстродействие шахматной машины увеличилось до 50 тыс. позиций в секунду.
Сюй и Анантараман были полны честолюбивых замыслов и, не долго думая, решили подготовить свою машину к Североамериканскому чемпионату по шахматам среди компьютеров 1986 г., который должен был начаться всего через семь недель. К проекту были привлечены еще два аспиранта, М. Кэмпбелл и А. Новацик, также с факультета информатики. Задача заключалась в том, чтобы построить более совершенный оценивающий функционал, и Кэмпбелл, ранее принимавший участие в шахматных соревнованиях, согласился попробовать свои силы. Вторая, и более трудная, задача, учитывая ограничения во времени, состояла в расширении функции тестера микросхем так, чтобы он мог играть роль простой анализирующей машины. Такая машина должна была полнее использовать потенциальные скоростные возможности микросхемы генератора ходов по сравнению с рабочей станцией.
Сюй принял решительные меры, чтобы вовремя подготовить технику: он решил, что его машина будет игнорировать две шахматные ситуации - рокировку и повторение позиций. (Игрок может настоять на ничейном результате, если докажет, что определенная позиция трижды повторена в игре и ходить в этой позиции должен тот же игрок.) Чтобы компенсировать этот недостаток, была принята гибридная стратегия поиска, согласно которой ранние слои игрового дерева анализировались управляющим компьютером, учитывавшим рокировку и повторение позиций. Последующие слои (включающие, конечно, большую часть возможных позиций) анализировались уже специализированной машиной поиска.
Мы не располагали никакими денежными средствами и поэтому собрали нашу первую машину "ChipTest" из деталей, заимствованных из других проектов. Суммарная стоимость всех компонентов не превышала 500 или 1000 долл. с учетом ориентировочной стоимости кристаллов, производство которых финансировалось агентством DARPA. Однако ни аппаратура поисковой машины, ни программное обеспечение управляющего компьютера не были полностью отлажены к началу чемпионата, и не лишенная недостатков машина сумела добиться на турнире лишь ничейного результата. Тем не менее это было немалым достижением если учесть, что вся работа была проделана в течение семи недель.
Этот дебют научил нас многому. Например, Сюй подметил, что две другие программы избрали такую тактику, при которой каждый их ход был вынужденным и ни одна из сторон заранее не предвидела исхода игры. Другими словами, программа, добившаяся лучшей позиции, достигала этого благодаря чисто случайным факторам. Сюй предложил исправить этот дефект при помощи приема, названного им алгоритмом сингулярного продолжения. Алгоритм как бы заглядывает глубже, т.е. продолжает анализ на большей глубине, в тех ситуациях, когда компьютер «видит» лишь один хороший ход. В данном случае цель заключалась в том, чтобы особое внимание обращалось на критические позиции.
Когда одна сторона близка к выигрышу, скажем слон противника попал в безвыходное положение, у защищающегося по мере углубления анализа остается все меньше и меньше хороших ответных ходов. В конце концов остается лишь один хороший ход, после которого слон все же оказывается потерянным. В подобных случаях в бой вступает сингулярное продолжение. Благодаря ему в одной из игр компьютер привел мастера в состояние шока, объявив ему форсированный мат за 19 ходов.
Анантараман, единственный член группы, умевший программировать управляющий компьютер системы "ChipTest", написал программу, реализующую алгоритм сингулярного продолжения. Тем временем Сюй завершил написание микропрограмм, управляющих аппаратурой на самом низшем уровне. Анализируя от 400 до 500 тыс позиций в секунду, система "ChipTest" выиграла чемпионат Северной Америки по шахматам среди компьютеров в 1987 г., победив всех своих соперников, в том числе машину, носившую титул чемпиона мира, - "Cray Blitz". Таким образом закончилась эпоха чисто силовых машин. Сейчас почти все сильнейшие программы содержат по крайней мере некоторые элементы выборочного анализа.
Наш опыт показал, что быстродействие системы "ChipTest" можно повысить еще больше, а анализ проводить, так сказать, более разумно. Первоначальное финансирование этого проекта, теперь называющегося «Глубокая мысль», было предоставлено X. Кунгом, консультантом Сюя.
Шахматная машина «Глубокая мысль» в своем основном варианте содержит 250 микросхем, включая два процессора, установленные на одной плате, размерами в половину формата этого журнала. Машина управляется программой, так называемым управляющим программным обеспечением, выполняющейся на компьютере рабочей станции. Процессоры машины едва ли обладают более высоким физическим быстродействием по сравнению с системой "ChipTest", однако усовершенствованное управление алгоритмом анализа позволяет им проводить поиск лучшего хода на 30% эффективнее.
 СЕРДЦЕ «Глубокой мысли» помещается на плате размером с большую пиццу. Каждый из двух ее процессоров способен анализировать 500 тыс позиций в секунду. Машина следующего поколения превратит «Глубокую мысль» в одну микросхему; в ней 1000 таких процессоров будут работать параллельно. |
Оценочное устройство состоит из четырех компонентов. Оценка расположения фигур (единственная операция, перешедшая по наследству от системы "ChipTest") базируется на близости фигуры к центру доски, на ее подвижности и других соображениях. Размещение пешек оценивается в зависимости от таких параметров, как их взаимная поддержка, контроль за цетральной частью доски и способность защитить короля. Оцениваются также так называемые проходные пешки, которым не препятствуют пешки противника и поэтому они могут пройти до восьмого ряда и превратиться в ферзя. Проводится еще и дополнительная оценка, учитывающая более сложные позиции пешек и ладей на определенной линии.
Мы начали также работу по настройке примерно 120 параметров оценивающего функционала, фигурирующих в нашем программном обеспечении. Как правило, шахматные мастера вручную настраивали весовые коэффициенты, приписываемые программой материальным факторам (пешкам и фигурам) и позиционным показателям. По нашему мнению, мы располагаем единственной добротной программой, которая настраивает свои весовые коэффициенты автоматически.
МЫ ОТОБРАЛ И 900 игр с участием мастеров для анализа и произвольно определили оптимальные веса, которые обеспечивают наилучшее соответствие между ходами, получившими наиболее высокую оценку у машины, и ходами, в действительности сделанными мастерами. Оценивающая часть программного обеспечения была полностью переписана Кэмпбеллом и Новациком с целью реализации этой стратегии. Вместо того чтобы однозначно присваивать определенное численное значение каждой позиции, оценочная функция, работающая в режиме настройки, возвращает цепочку линейных членов. Другими словами, она вычисляет вектор.
Было применено два механизма настройки. При использовании первого метода, который мы называем методом подъема, данный оценочный параметр просто устанавливается в произвольное значение, а затем проводится анализ на глубину, скажем, пяти или шести уровней для каждой позиции, содержащейся в игровой базе данных, чтобы найти ходы, которые сделала бы машина. После этого в значение параметра вносится поправка и проводится перерасчет. Если количество совпадений между ходами компьютера и гроссмейстера возрастает, параметр опять корректируется в том же направлении. Процесс продолжается до тех пор, пока все параметры не достигнут оптимального значения, или высшего уровня эффективности. Однако чтобы с помощью этого метода оптимизировать все параметры, потребуются годы, поэтому мы воспользовались им лишь в нескольких сложных случаях.
Второй метод настройки, предложенный и реализованный Новациком, работал значительно быстрее. Он сформировался в процессе того, как мы пытались найти наилучшее соответствие между функцией оценки позиций, применяемой машиной, и предположительно верными их значениями. Наилучшее соответствие получается при наименьшем среднеквадратичном отклонении между моделью и истинными значениями. Истинные значения можно приблизительно вычислить по результатам глубокого поиска (если тонкой настройке подвергается какая-то конкретная, известная оценочная компонента) или путем сравнения решений, принятых машиной, с ходами, выбранными первоклассными игроками в аналогичной ситуации.
Образцы партий, сыгранных мастерами, дают хороший критерий для относительной оценки позиций: любая позиция, полученная в результате хода гроссмейстера, с большой вероятностью будет лучше любой другой позиции, возникающей в результате альтернативного хода. Вместо того чтобы вычислять оценку позиции по ее параметрам, Новацик рассчитывал параметры, основываясь на предполагаемой разнице между позицией, выбранной гроссмейстером, и альтернативными позициями, которые были им отвергнуты. Вычисления по его алгоритму выполняются всего за несколько дней, но в отличие от метода подъема он не позволяет оптимизировать значения конкретных параметров. Скорее, с помощью этого метода повышается общая эффективность всего набора параметров.
Наша автоматически настраиваемая оценочная функция, пожалуй, не хуже, если не лучше настроенных вручную функций в таких знаменитых академических шахматных программах, как "Hitech" и "Cray Blitz". Однако, по-видимому, все же остается разрыв между оценочной функцией «Глубокой мысли» и лучшими коммерческими образцами шахматных машин, создание которых потребовало многих человеко-лет. Мы надеемся в недалеком будущем преодолеть этот разрыв за счет усовершенствования обратных связей в процедурах автоматической настройки.
Может показаться странным, что наша машина, вмещающая относительно небольшой объем знаний об игре в шахматы, все же обыгрывает первоклассных игроков. Однако не следует забывать, что компьютер не моделирует человеческое мышление, он достигает того же эффекта за счет других средств. «Глубокая мысль» способна проследить игру на много ходов вперед, но замечает мало; помнит все, но ничему не учится; не совершает грубых ошибок, но и не превосходит саму себя в минуты вдохновения. И тем не менее она иногда находит решения, которые ускользают от внимания даже сильнейших гроссмейстеров.
Возможно, именно этот нестандартный, отличный от присущего человеку взгляд на игру, свойственный машине, привлек внимание гроссмейстера Кевина Спрэггета, решившего потренироваться с помощью машины перед четвертьфинальным матчем претендентов т.а звание чемпиона мира с гроссмейстером Артуром Юсуповым. Участие машины не оказало заметного влияния на матч, но все же имел место один интересный прецедент.
В октябре 1989 г. «Глубокая мысль» в экспериментальной шестипроцессорной версии сыграла показательный матч из двух партий против Каспарова. Матч проходил в Нью-Йорке. Хотя новая версия могла «просматривать» более двух миллионов позиций в секунду, Каспаров довольно легко с ней справился. Результат не был неожиданным, но игра «Глубокой мысли» оказалась, пожалуй, разочаровывающей.
В феврале нынешнего года «Глубокая мысль» провела показательную игру с Анатолием Карповым - бывшим чемпионом мира и соперником Каспарова в матче за звание чемпиона мира, который начался в октябре 1990 г. в Нью-Йорке и завершится во Франции в Лионе. Дефекты, выявленные в экспериментальном программном обеспечении шести- и четырехпроцессорной версий, заставили нас вернуться к двухпроцессорной версии. Благодаря ряду усовершенствований в оценочной функции «Глубокая мысль» сыграла одну из лучших своих игр в течение первых 50 ходов, но затем, совершив досадную ошибку, упустила явную ничью. У стабильной шестипроцессорной версии хватило бы скорости, чтобы избежать этой ошибки:
 БЫСТРОДЕЙСТВИЕ является ключевым фактором в работе, проводимой сейчас в Исследовательском центре им. Томаса Дж.Уотсона фирмы IBM, где конструируется машина следующего поколения. По скорости вычислений она будет превосходить свою предшественницу по крайней мере в 1000 раз. Задуманная нами машина, таким образом, будет анализировать более миллиарда позиций в секунду. Этого будет достаточно, чтобы проводить поиск на 14 или 15 слоев в большинстве случаев и от 30 до 60 слоев в критических ситуациях. Если наблюдавшаяся до сих пор связь между быстродействием и качеством игры сохранится, то машина следующего поколения будет играть на уровне мастера с рейтингом 3400 очков, по крайней мере на 800 очков превосходящий сегодняшний рейтинг «Глубокой мысли» и на 500 - рейтинг Каспарова. Чтобы достичь такой скорости, Сюй конструирует специализированный шахматный микропроцессор, который по проектным данным должен генерировать по меньшей мере 3 млн ходов в секунду, что более чем в три раза превосходит возможности нынешней версии «Глубокой мысли». Одновременно он разрабатывает вычислительную систему с высокой степенью параллелизма, в которой объединяется мощность более тысячи таких процессоров, что обеспечит дополнительный прирост скорости приблизительно еще в 300 раз. Анантараман и Кэмпбелл заняты усовершенствованием ряда аспектов нынешней версии «Глубокой мысли», с тем чтобы эти усовершенствования также «встроить» в машину следующего поколения. Новацик теперь увлечен другими идеями. Мы полагаем, что за счет одной только скорости наша система сможет стать достойным соперником чемпиона мира. Мы считаем также, что благодаря большому числу других запланированных усовершенствований машина получит преимущество, возможно, уже в 1992 г. Ну что ж, Каспаров задал нам работы, и мы должны прислушиваться к его мнению. Возможно, он только сейчас всерьез занялся изучением сильных и слабых сторон, присущих шахматным машинам. В частной беседе Каспаров признал, что машина, анализирующая миллиард позиций в секунду, способна побеждать гроссмейстеров среднего уровня, добавив, однако: «Но не Карпова и не меня!». Он утверждает, что творчество и воображение человеческого ума, а в особенности его собственное творчество и воображение, определенно должны оказаться сильнее простого кремниевого кристалла и соединительных проволочек. Однако в действительности за шахматной доской столкнутся два подхода - изобретательность одного, в высшей степени талантливого, человека будет противопоставлена работе нескольких поколений математиков, электронщиков и программистов. Мы считаем, что результат поединка между нынешним чемпионом мира и компьютером не ответит на вопрос, может ли машина мыслить, а скорее покажет, могут ли усилия коллектива людей превзойти достижения одной, пусть даже наиболее талантливой, личности. |
Фэн-Сюн Сюй, Томас Анантараман, Мюррей Кэмпбелл, Андреас НовацикВ МИРЕ НАУКИ. (Scientific American. Издание на русском языке). 1990. № 12 стр. 6-13.
forany.xyz
Компьютерные шахматы - это... Что такое Компьютерные шахматы?
Компьютерные шахматы — популярный термин из области исследования искусственного интеллекта, означающий создание программного обеспечения и специальных компьютеров для игры в шахматы. Также термин «компьютерные шахматы» употребляется для обозначения игры против компьютерной шахматной программы, игры программ между собой.
История
Шахматный компьютерИстория шахматных машин старше, чем история компьютеров. Идея создать машину, играющую в шахматы, датируется ещё восемнадцатым веком. Около 1769 года появился шахматный автомат «Механический турок». Он был предназначен для развлечения королевы Марии-Терезии. Машина действительно неплохо играла — внутри неё находился сильный шахматист, который и делал ходы.
Создание механических шахматных автоматов прекратилось с появлением цифровых компьютеров в середине XX века. В 1951 году Алан Тьюринг написал алгоритм, с помощью которого машина могла бы играть в шахматы, только в роли машины выступал сам изобретатель. Этот нонсенс даже получил название — «бумажная машина Тьюринга». Человеку требовалось более получаса, чтобы сделать один ход. Алгоритм был довольно условный, и сохранилась даже запись партии, где «бумажная машина» Тьюринга проиграла одному из его коллег[1]. За отсутствием доступа к компьютеру, программа ни разу не проверялась в работе.
Примерно в это же время, в 1951 году, математик Клод Шеннон написал свою первую статью о шахматном программировании. Он писал: «Хотя, возможно, это и не имеет никакого практического значения, сам вопрос представляется теоретически интересным, и будем надеяться, что решение этой задачи послужит толчком для решения других задач аналогичной природы и большего значения». Шеннон также отметил теоретическое существование лучшего хода в шахматах и практическую невозможность его найти.
Следующим шагом в развитии шахматного программирования стала разработка в ядерной лаборатории Лос-Аламоса в 1952 году на компьютере Maniac 1 (тактовая частота 11 кГц) шахматной программы для игры на доске 6x6, без участия слонов. Известно, что этот компьютер сыграл одну партию против сильного шахматиста, она продолжалась 10 часов и закончилась победой шахматиста. Ещё одна партия была сыграна против девушки, которая недавно научилась играть в шахматы. Машина победила на 23-м ходу. Сейчас это выглядит смешно, но для своего времени это было большое достижение.
В 1957 году Алексом Бернстейном была создана первая программа для игры на стандартной шахматной доске и при участии всех фигур[2].
Важное событие для компьютерных шахмат произошло в 1958 году, когда Аллен Ньюэлл, Клифф Шоу и Герберт Саймон разработали алгоритм уменьшения дерева поиска, названный Альфа-бета отсечение[2][3], на основе которого построены функции поиска всех сильных современных программ.
Первой же машиной, которая достигла уровня шахматного мастера, была Belle, законченная в 1983 г. Джо Кондоном и Кеном Томпсоном. «Belle» был первым компьютером, спроектированным только для игры в шахматы. Его официальный рейтинг Эло был 2250, таким образом, это была самая сильная шахматная машина своего времени.
В 1994 Гарри Каспаров проиграл программе Fritz 3 турнирную блиц-партию в Мюнхене. Программа также выиграла у Вишванатана Ананда, Бориса Гельфанда и Владимира Крамника. Гроссмейстер Роберт Хюбнер отказывался играть против программы и автоматически проиграл. Каспаров сыграл второй матч с Fritz и победил с 4 выигрышами и 2 ничьими.
В феврале 1996 года Гарри Каспаров победил шахматный суперкомпьютер Deep Blue со счетом 4-2. Этот матч выдающийся тем, что первую партию выиграл Deep Blue, автоматически став первым компьютером, победившим чемпиона мира по шахматам в турнирных условиях. Deep Blue вычислял 50 миллиардов позиций каждые три минуты, в то время как Каспаров 10 позиций за это же время. В Deep Blue было 200 процессоров. С тех пор шахматные энтузиасты и компьютерные инженеры создали много шахматных машин и компьютерных программ.
Шахматные компьютеры сейчас доступны по очень низкой цене. Появилось много программ с открытыми кодами, в частности Crafty, Fruit и GNU Chess, которые можно свободно загрузить из сети Интернет и которые могут победить многих профессиональных шахматистов. А лучшие коммерческие программы, например, Shredder или Fritz уже превысили уровень людей-чемпионов. Сейчас же движок Houdini находится на первом месте в таких компьютерных рейтинг-листах, как CEGT, CCRL,SCCT и CSS.
Мотивация
Первыми мотивами для компьютеризации шахмат было желание развлечься, создать программы для компьютерных шахматных турниров и провести научное исследование, которое позволило бы глубже понять познавательную способность человека. Для первых двух целей компьютерные шахматы имели феноменальный успех: от первых попыток к созданию шахматной программы, которая могла на равных соперничать с лучшими шахматистами, прошло менее пятидесяти лет.
А. С. Кронрод определил роль компьютерных шахмат известной фразой: «шахматы — это дрозофила искусственного интеллекта». Аналогия лежит на поверхности: шахматы представляют собой безусловно интеллектуальную, но при этом чётко формализованную, простую по структуре и компактную задачу, то есть являются удобным объектом лабораторных исследований в искусственном интеллекте, так же как мушка-дрозофила, благодаря малым размерам, плодовитости и быстрой смене поколений является удобным лабораторным объектом для изучения наследственности. Действительно, на шахматах были апробированы многие известные методы и направления искусственного интеллекта, в том числе методики оптимизации перебора (уход от «комбинаторного взрыва» при просчёте вариантов вперёд на несколько ходов), распознавание образов, экспертные системы, логическое программирование.
Однако, к удивлению и огорчению многих, шахматы мало приблизили людей к созданию машин с человекоподобным интеллектом. Современные шахматные программы, по сути, остановились на наиболее примитивном этапе интеллектуальной деятельности: они исследуют огромное число возможных ходов обоих игроков, применяя различные методы усечения дерева перебора, в том числе относительно простую функцию оценки. В сочетании с базами данных, хранящими заранее рассчитанные готовые варианты дебютов и эндшпилей, благодаря быстродействию и объёмам памяти современных компьютеров эти методы уже обеспечивают игру компьютера в шахматы на гроссмейстерском уровне. По этим причинам компьютерные шахматы больше не имеют такого большого академического интереса. Роль «дрозофилы искусственного интеллекта» перешла к другим интеллектуальным играм, таким как, например, го. Гораздо больший, чем в шахматах, объём перебора вариантов в таких играх ограничивает возможности использования простых методов и требует от ученых применять более умозрительные подходы к игре.
Проблемы реализации
Разработчики шахматных программы должны сделать ряд решений при их написании. Они включают:
- Способ изображения шахматной доски — представление цельной позиции как структуры данных.
- Методы поиска — поиск возможных лучших ходов.
- Листовая оценка — оценка позиции без учета дальнейших ходов.
См. также:
Структура шахматной программы
Первое исследование на тему шахматного программирования сделал в 1950 году американский математик Клод Шеннон, успешно предусмотревший два основных возможных метода поиска, которые можно использовать, и назвал их «Тип А» и «Тип B».
Программы типа А используют так называемый подход «грубой силы» (brute force), изучая каждую возможную позицию на фиксированную глубину с помощью алгоритма Минимакс. Шеннон утверждал, что этот метод будет непрактичным по двум причинам.
Во-первых, с примерно тридцатью ходами, возможными в типичной позиции, на изучение около 10 млрд узловых позиций (просчет примерно на три хода вперед для обеих сторон), надо примерно 16 минут, даже в «очень оптимистичном» случае, когда компьютер сможет оценивать миллион позиций в секунду. (Чтобы достичь этого понадобилось сорок лет.)
Во-вторых, программы Типа А пренебрегали так называемой проблемой статического состояния, пытаясь оценить позицию в начале обмена фигур или другой важной последовательности ходов (например тактических комбинаций). Поэтому Шеннон предполагал, что с применением алгоритма Типа А число позиций, которые надо исследовать чрезвычайно возрастет, что значительно замедлит программу. Вместо бесполезной траты вычислительной мощности компьютера для исследования плохих или незначительных ходов Шеннон предложил использовать программы Типа В. Этот метод имеет два усовершенствования:
- Применяется поиск «по спокойствию» (quietness).
- Исследует не все, а только некоторые пригодные ходы для каждой позиции.
Это давало программам возможность просчитывать важные ходы на бо’льшую глубину и делать это за приемлемое время. Первый подход выдержал испытание временем: все современные программы применяют конечный поиск «по спокойствию» перед оценкой позиции.
Основные алгоритмы современных программ
Примерная схема осуществления альфа-бета отсечения слабых ходовКомпьютерные шахматные программы рассматривают шахматные ходы как игровое дерево. Теоретически, они должны оценивать все позиции, которые возникнут после всех возможных ходов, затем все возможные ходы после этих ходов и т. д. Каждый ход одного игрока называется «узел». Перебор ходов продолжается, пока программа не достигает максимальной глубины поиска или определяет, что достигнута конечная позиция (например мат или пат). Уже на основании оценки позиции выбирает оптимальную стратегию. В каждой позиции количество возможных ходов игрока примерно равно 35. Для полного анализа четырёх ходов (по два хода каждого игрока) нужно исследовать около полутора миллиона возможностей, для шести — почти два миллиарда. Анализ на 3 хода вперед — очень мало для хорошей игры.
Программисты пытаются по-разному ограничить массу ходов, которые надо перебрать (обрезание дерева поиска — game tree pruning). Самым популярным является альфа-бета отсечение, в котором не рассматриваются позиции, имеющие меньшую оценку, чем уже оценённые.
Приблизительная программная реализация:
private int AlphaBeta(int color, int Depth, int alpha, int beta) { if (Depth == 0) return Evaluate(color); int bestmove; Vector moves = GenerateMoves(); for(int i = 0; i < moves.size(); i++) { makeMove(moves.get(i)); eval = -AlphaBeta(-color, Depth-1, -beta, -alpha); unmakeMove(moves.get(i)); if(eval >= beta) return beta; if(eval > alpha) { alpha = eval; if (Depth == defaultDepth) { bestmove = moves.get(i); } } } return alpha; }Пример первого вызова:
AlphaBeta(1, 6, Integer.MIN_VALUE, Integer.MAX_VALUE);При первом вызове метод (функция) вызывается с максимальным окном. При рекурсивных вызовах переменные alpha и beta меняются местами с инверсией знака и «сужают» массу поиска.
Вторым распространенным методом является итерационное заглубление. Сначала перебирается дерево игры до определенной глубины, после чего выделяется несколько лучших ходов. Затем программа оценивает эти ходы применительно к большей глубине, чтобы узнать больше об их последствиях. Эта операция повторяется до наилучшего с точки зрения программы хода. Такой подход позволяет быстро отбросить немалый процент неперспективных вариантов игры. Например, не имеет смысла исследовать, что произойдет, когда обменять ферзя на пешку, если в позиции есть лучшие ходы.
Важный элемент шахматных алгоритмов — это система оценки позиции. Нельзя абсолютно точно оценить позицию, ибо для этого нужно было бы проанализировать триллионы последовательностей ходов от начала и до завершения партии. Если бы существовала функция, которая давала бы возможность достоверно оценить позицию, задача игры в шахматы упростилась бы к оценке каждого из нескольких десятков доступных в данный момент ходов, и не надо было бы вычислять дальнейшие ходы.
Следовательно, оценка программой позиции очень приблизительная, хотя оценочные функции программ постоянно совершенствуются. Функции оценки обычно оценивают позиции в сотых частях пешки. Эти функции оценивают только несколько простых параметров:
- Во-первых, это оценка материала: каждая пешка — это 1 пункт, слон и конь — по 3, ладья — 5, ферзь — 9. Король иногда ценится в 200 пешек (Статья Шеннона) или 1 000 000 000 пешек (программа разработана в СССР в 1961 г.), чтобы гарантировать, что мат перевесит все другие факторы. Более развитые функции имеют точнее установленные коэффициенты ценности фигур, которые зависят от стадии партии и позиции на шахматной доске.
- Во-вторых, позиционное преимущество, которое зависит от положения фигур на доске; например, заблокированная фигура ценится меньше, чем свободная; оценивается также безопасность короля, господство над центром доски и т. д.; существуют также более сложные системы оценки (некоторые даже используют знания о нейронных сетях), однако даже такая простая функция позволяет программе играть очень сильно; в шахматах главная проблема заключается не в оценке позиции, а в переборе дерева возможных ходов.
Функции оценки позиции бывают неэффективны, когда ситуация на доске резко меняется с каждым ходом, когда, например, идёт обмен фигур или реализуется какая-нибудь шахматная комбинация. Отсюда возникло понятие статического состояния (quiescent) и горизонта вычисления. В статическом состоянии на шахматной доске идёт медленная позиционная борьба, а достойный внимания горизонт вычисления очень широк. Это означает, что решающая перемена не наступит в том будущем, которое удается легко предвидеть. В такой ситуации большую роль играют функции оценки позиции, нежели попытки вычисления возможных вариантов.
В динамичной ситуации игра, опирающаяся на функцию оценки позиции, может привести к совершенно ошибочным решениям. В крайнем случае, если программа имеет коротко настроенный горизонт исчисления и в ней учитывается только кратковременная оценка позиции, то конец может прийтись как раз на момент, когда идёт обмен ферзей, и один из них может быть уже побит, а второй взамен ещё нет. Оценка программой такого состояния ведёт к совершенно ошибочному выводу, что один из игроков имеет огромное преимущество, тогда как оно исчезнет через один ход, которого, однако, программа не видит. Если состояние ещё не статическое, нужно продолжить обмен до конца и оценить ситуацию, когда уже нет возможных радикальных изменений. Люди в целом интуитивно различают эти две ситуации — шахматные же программы должны иметь набор критериев, позволяющих изменять способ функционирования в статических и динамических состояниях.
Труднее дать оценку ходам в дебюте. Большинство программ используют при этом написанные заранее дебютные библиотеки, в которых есть определённое небольшое количество начальных ходов и ответов к определенному числу ходов, которое не является постоянным, потому что зависит от типа дебюта.
Компьютер против Человека
Даже в 70-80-х гг оставался открытым вопрос, когда шахматная программа сможет победить сильнейших шахматистов. В 1968 г. Международный гроссмейстер Дэвид Леви пошел на пари, что ни один компьютер не сможет обыграть его в течение ближайших десяти лет. Он выиграл пари, победив в 1978 г. программу Chess 4.7 (сильнейший в то время компьютер), но сознавал, что осталось не так уж много времени до того, когда компьютеры будут побеждать мировых чемпионов. В 1989 г. программа Deep Thought выиграла у Леви.
Но программы все еще были значительно ниже уровня Чемпиона мира, который продемонстрировал Гарри Каспаров, победив ту же Deep Thought дважды в 1991 г.
Это длилось до 1996 г., когда состоялся матч Каспарова с компьютером Deep Blue фирмы IBM, где чемпион проиграл свою первую партию. Впервые компьютерная шахматная программа обыграла чемпиона мира при стандартном часовом контроле. Однако Каспаров изменил свой стиль игры, выиграв три и сведя вничью две из пяти партий, которые остались.
В мае 1997 года усовершенствованная версия Deep Blue нанесла поражение Каспарову со счетом 3,5-2,5. Позже IBM обвинили, что во время партий фирма использовала человека-шахматиста, чтобы увеличить стратегическую силу компьютера.[источник не указан 273 дня]
В 2003 году был снят документальный фильм, в котором исследовались эти упреки, который называется «Матч окончен: Каспаров и машина» (англ. Game Over: Kasparov and the machine), в котором утверждалось, что сильно раскрученная победа Deep Blue подстроена для увеличения рыночной стоимости IBM.
Частично эти упреки были оправданными. Правила позволяли разработчикам изменять программу между играми. Deep Blue был изменен между партиями для лучшего понимания машиной стиля игры Каспарова, помогая избежать ловушки в эндшпиле, в которую дважды попадал искусственный интеллект.
Матч Deep Blue против Каспарова 1996, первая партия.| Финальная позиция. |
IBM разобрала Deep Blue после матча, с тех пор этот компьютер не играл ни разу. Хотя происходили другие матчи «Человек против Машины».
Имея все большую вычислительную мощность, шахматные программы, запущенные на персональных компьютерах, стали достигать уровня лучших шахматистов. В 1998 г. программа Rebel 10 победила Вишванатана Ананда, который тогда занимал второе место в мире. Однако не все партии игрались со стандартным временным контролем. Из восьми партий матча, четыре играли с блиц-контролем (пять минут плюс пять секунд за каждый ход), которые Rebel выиграл со счетом 3-1. Еще две игры были с полу-блиц контролем (пятнадцать минут на каждого), которые программа также выиграла (1,5-1). Наконец, две последние партии были сыграны со стандартным турнирным временным контролем (два часа на 40 ходов и час на остальные партии) и тут выиграл уже Ананд со счетом 0,5-1,5. К тому времени в быстрых партиях компьютеры играли лучше людей, но при классическом временном контроле преимущество было уже не так велико.
В 2000 г. коммерческие шахматные программы Junior и Fritz смогли свести в ничью матчи против предыдущих мировых чемпионов Гарри Каспарова и Владимира Крамника.
В октябре 2002 Владимир Крамник и Deep Fritz соревновались в матче из восьми партий в Бахрейне. Матч закончился вничью. Крамник выиграл вторую и третью партии, используя традиционную противокомпьютерную тактику — играл осторожно, имея целью долгосрочное преимущество, которое компьютер не может увидеть в своем дереве поиска. И все же Fritz выиграл пятую партию после грубой ошибки Крамника. Шестую партию много турнирных комментаторов назвали очень увлекательной. Крамник, имея лучшую позицию в начале миттельшпиля, попытался пожертвовать фигурой, чтобы создать сильную тактическую атаку (такая стратегия — очень рискованная против компьютеров). Fritz нашел сильную защиту, и эта атака значительно ухудшила позицию Крамника. Крамник сдал игру, веря, что партия проиграна. Однако последующий анализ показал, что Fritz вряд ли смог бы довести игру до своего выигрыша. Последние две партии закончились вничью.
В январе 2003 г. Гарри Каспаров играл против программы Junior в Нью-Йорке. Матч закончился со счетом 3-3.
В ноябре 2003, Гарри Каспаров играл с X3D Fritz. Матч закончился со счетом 2-2.
В 2005 г., Hydra, специальный шахматный компьютер с 64 процессорами, победил Майкла Адамса, шахматиста, который в то время был на седьмом месте в мире по рейтингу ЭЛО, в матче из шести партий со счетом 5,5-0,5 (хотя домашняя подготовка Адамса была намного ниже, чем у Каспарова в 2002 году). Некоторые комментаторы верили, что Hydra наконец получит несомненное преимущество над лучшими шахматистами.
В ноябре-декабре 2006, Владимир Крамник играл с программой Deep Fritz. Матч закончился со счетом 2-4.
Базы данных эндшпиля
Подробнее Базы данных эндшпиля
Компьютеры используются для анализа некоторых эндшпильных позиций. Такие базы данных эндшпиля создаются, используя ретроградный анализ, начиная с позиций, где конечный результат известен (например, где одной стороне был поставлен мат) и видя какие еще позиции есть на расстоянии хода, затем на один ход от этих и т. д. Кен Томпсон, известный как главный проектировщик операционной системы UNIX, был пионером в этой области.
Игра в эндшпиле долго была заметной слабостью шахматных программ, так как глубина поиска была недостаточной. Таким образом, даже программы, которые играли в силу мастера не в состоянии выиграть в эндшпильних позициях, где даже шахматист средней силы мог форсировать выигрыш.
Но результаты компьютерного анализа иногда удивляли людей. В 1977 г. шахматная машина Томпсона Belle, используя эндшпильные базы данных король + ладья против короля + ферзь, была способна свести вничью теоретически проигрышные эндшпили против титулованных шахматистов.
Большинство гроссмейстеров отказывались играть против компьютера в эндшпиле ферзь против ладьи, но Уолтер Браун принял вызов. Позицию расставили так, что теоретически можно было выиграть в 30 ходов с безупречной игрой. Брауну дали два с половиной часа на пятьдесят ходов. После сорока пяти ходов Браун согласился на ничью, будучи не способным выиграть в последние пять ходов. В конечной позиции, Браун мог поставить мат только через семнадцать ходов.
В 2002 г. были опубликованы основные форматы эндшпильных баз данных, включая Edward Tablebases, De Koning Endgame Database и Nalimov Endgame Tablebases, которые теперь поддерживают многие шахматные программы, такие как Rybka, Shredder и Fritz. Эндшпили с пятью или менее фигурами были полностью проанализированы. Эндшпили с шестью фигурами были проанализированы, за исключением позиций с пятью фигурами против одинокого короля. Марк Буржуцкий и Яков Коновал проанализировали некоторые эндшпили с семью фигурами. Во всех этих эндшпильных базах данных считается, что рокировка невозможна.
Базы данных генерируются с помощью хранения в памяти оценок позиций, которые возникали до сих пор, и используют этих результаты для уменьшения дерева поиска, если такие позиции возникнут снова. Простая целесообразность запоминания оценок всех ранее достигнутых позиций означает, что ограничивающим фактором при решении эндшпиля является просто количество памяти, которую имеет компьютер. С ростом ёмкости компьютерной памяти, эндшпили повышенной сложности рано или поздно будут решены.
Компьютер, использующий базу данных эндшпиля будет, при достижении позиции в них, способен играть безупречно и безотлагательно определять, является ли позиция выигрышной, проигрышной или ничейной, а также находить самый быстрый и самый долгий способ достижения результата. Знание точной оценки позиции также полезно при увеличении силы компьютера, так как это позволит программе выбирать пути достижения цели в зависимости от ситуации [то есть упрощая и размениваясь получить четко исследованную позицию].
Базы эндшпиля Налимова на пять фигур, которые используют методы современной компрессии, занимают 7.05 Гб на жестком диске. Для хранения баз данных на шесть фигур надо примерно 1.2 терабайт. Оценено, что полная семифигурная база данных потребует больше места, чем будет доступно рядовым пользователям в ближайшем будущем.
Игра против программ
Компьютеры ощутимо опережают людей в коротких тактических маневрах, которые находятся в пределах глубины поиска программы. Особенно опасным в таких случаях является ферзь, который прекрасно подходит для кратковременных маневров. Поэтому в игре против компьютера люди часто делают попытку побудить программу к размену ферзей. Это происходит, например, когда человек в начале партии намеренно ухудшает свою позицию, а компьютер расценивает её, как выгодную ему. Если программа устанавливает оценку позиции как преимущественную для себя, то, скорее всего, будет разменивать фигуры, а это выгодно человеку. Конечно, программисты узнали о таких «трюках», и это учитывается в последних версиях их программ.
Вместо этого шахматисты должны играть против компьютера долгосрочными маневрами, которые программа не может увидеть в рамках своей глубины поиска. Например, Крамник в партии с Deep Fritz выиграл с помощью долгосрочного продвижения проходной пешки, которую Fritz обнаружил слишком поздно.
Шахматы и другие игры
Успех шахматных программ внушает мысль, что можно написать программы, которые играли бы так же хорошо и в другие игры, например сёги или го.
Похожие алгоритмы, пожалуй, можно бы использовать и во время игры в других разновидностях шахмат. В сёги больше возможных ходов, материальное преимущество значит гораздо меньше, зато намного существеннее позиционное преимущество. Строятся сложные системы, имеющие целью гарантировать королю безопасность, но оценка этих систем для компьютера нелегка. Количество фигур в этой игре постоянно, а потому игра не упрощается со временем, что делает невозможным создать базу эндшпилей. Нет здесь также вполне статических состояний, ведь игра на протяжении всего времени сводится к позиционной борьбе. Поэтому написать хорошую программу для игры в сёги значительно тяжелее, чем шахматную программу, хотя огромный опыт в шахматных играх можно приложить и к этой игре.
Настоящим вызовом для программистов стало го. Сложность вычисления го на несколько порядков больше, чем в шахматах. На каждом шаге возможны около 200—300 ходов, статическая же оценка жизни групп пешек фактически невозможна. Одним ходом здесь можно вполне испортить всю игру, даже если остальные ходы были успешны. Поэтому программы для игры в го не используют таких алгоритмов, как шахматные программы, и обычно имеют несколько десятков модулей для оценки различных аспектов игры и при анализе пытаются пользоваться теми же понятиями, что и люди. Несмотря на это, компьютеры в го играют еще очень слабо и проигрывают даже не очень сильным любителям.
Хронология компьютерных шахмат
- 1769, Вольфганг Кемпелен, построил шахматиста-автомата, который стал одной из величайших мистификаций этого периода.
- 1868, Чарльз Хупер представил автомат Ajeeb — в котором тоже был спрятан шахматист.
- 1912, Леонардо Торрес Квеведо построил машину, которая могла играть эндшпиле Король + Ладья против короля.
- 1948, книга Норберта Винера «Кибернетика» описывает, как можно создать шахматную программу, используя поиск минимакса с лимитированной глубиной и оценочной функцией.
- 1950, Клод Шеннон опубликовал «Программирование компьютера для игры в шахматы», одну из первых статей о компьютерных шахматах.
- 1951, Алан Тьюринг разработал на бумаге первую программу, способную играть в шахматы.
- 1952, Дитрих Принц разработал программу, которая решала шахматные задачи.
- 1956, г. Лос-Аламос — первая подобная шахматам игра, которую смогли играть программы, разработанная Полом Штейном и Марком Уэллсом для компьютера MANIAC I.
- 1956, Джон Маккарти изобрел альфа-бета алгоритм поиска.
- 1958, NSS стала первой программой, которая использовала альфа-бета алгоритм поиска.
- 1958, первыми шахматными программами, которые могли играть полные шахматные партии, стали одна, созданная Алексом Бернштайн и вторая российскими программистами.
- 1962, первой программой, которая играла правдоподобно стала Kotok-McCarthy.
- 1966—1967, первый матч между программами.
- 1967, Mac Hack Six, разработанная Ричардом Гринблатт стала первой программой, победившей человека при турнирном контроле времени.
- 1970, первый год Североамериканского Компьютерного Шахматного Чемпионата.
- 1974, Каисса выиграла первый Всемирный Компьютерный Шахматный Чемпионат.
- 1977, создана первая шахматная программа для микрокомпьютеров CHESS CHALLENGER.
- 1977, создание Международной Компьютерной Шахматной Ассоциации.
- 1977, Chess 4.6 стал первым шахматным компьютером, который добился успеха в главном шахматном турнире.
- 1980, первый год Всемирного микрокомпьютерного Шахматного Чемпионата.
- 1981, Cray Blitz выиграл Чемпионат Штата Миссисипи с 5-0 счетом и рейтингом производительности 2258.
- 1982, аппаратный шахматный игрок Кена Томпсона Belle зарабатывает титул мастера США.
- 1988, HiTech, разработанная Гансом Берлинером и Карлом Ебелингом, выигрывает матч против гроссмейстера Арнольда Денкер со счетом 3.5 — 0.5.
- 1988, Deep Thought делит первое место с Тони Майлзом в Чемпионате ПО Toolworks, впереди бывшего чемпиона мира Михаила Таля и нескольких гроссмейстеров, в частности Самуэля Решевского, Уолтера Брауна, Эрнста Грюнфельда и Михаила Гуревича. Программа также нанесла поражения гроссмейстер Бенту Ларсену, и стала первым компьютером, который выиграл у гроссмейстера в турнире.
- 1992, впервые микрокомпьютер, Chessmachine Gideon 3.1, разработанный Эдом Шредером (Ed Schröder) выигрывает VII Всемирный Компьютерный Шахматный Чемпионат впереди суперкомпьютеров.
- 1997, Deep Blue выиграл матч против Гарри Каспарова 2-1 = 3.
- 2002, Владимир Крамник свел вничью матч против Deep Fritz.
- 2003, Каспаров сыграл вничью матч против Deep Junior.
- 2003, Каспаров сыграл вничью матч против X3D Fritz.
- 2005, Hydra выиграла матч с Майклом Адамсом со счетом 5,5-0,5.
- 2005, команда компьютеров (Hydra, Deep Junior и Fritz), обыграла 8.5-3.5 команду из шахматистов (Веселин Топалов, Руслан Пономарев и Сергей Карякин), которые имели средний ЭЛО рейтинг 2681.
- 2006, чемпион мира, Владимир Крамник, побежден 4-2 Deep Fritz.
Теоретики компьютерных шахмат
См. также
Примечания
Ссылки
brokgauz.academic.ru
