Часто приходится слышать, - в основном, к счастью, от шахматистов уровня ниже мастера, хотя придерживаются такого мнения и некоторые гроссмейстеры, - что компьютер "убивает" (или уже убил) шахматы. В самом деле, современные программы шутя решают задачи, в доли секунды рассчитывают десятиходовые комбинации, находят эффектные и неожиданные ресурсы, не приходившие в голову чемпионам мира. Более того, программист "Рыбки" и шахматный мастер В. Райлих не сомневается в том, что в ближайшие годы программы достигнут рейтинга Эло в 3000 пунктов.

Что ж, более чем вероятно. И здесь как раз самое время вспомнить, из чего складываются эти цифры. Во-первых и в-главных, коэффициент Эло - чисто спортивный. При его расчёте не учитывается ничего, кроме результата. Что происходило на доске во время партии, не имеет никакого значения. Чигорин проиграл Стейницу матч на первенство мира, обладая более развитым чувством позиции и комбинационным зрением. Причина его рокового просмотра - вне шахмат... Во-вторых, компьютерные программы в большинстве случаев зарабатывают рейтинги, играя с себе подобными. Если, скажем, "Джуниор" выигрывает турнир с участием гроссмейстеров (благодаря просмотрам, неподготовленности, неверной стратегии людей) и набирает рейтинг 2700, а затем у "Джуниора" выигрывает матч, к примеру, "Фритц", то, естественно, "Фритцу" припишут уже 2750 и т. д. Процесс идёт, дутые рейтинги растут, как на дрожжах. На самом же деле "Фритц" может играть сильнее... только "Джуниора". В компьютерных шахматах несовместимость партнёров - явление очень распространённое и, кроме того, СТАБИЛЬНОЕ. Программы принципиально не могут "приспособиться" друг к другу; слабости в их стиле игры, которые без зазрения совести и даже не подозревая того, используют коллеги, постоянны.

Если учитывать исключительно спортивную репрезентативность коэффициента Эло, то нетрудно становится понять, кстати, и почему В. Топалов стоит в рейтинг-листе выше, чем чемпион мира, добившийся этого звания в матче не с кем-нибудь, а с самим Топаловым. Для меня очевидно, что результат матча не случаен, и Крамник действительно "играет сильнее". Но Владимир - исключительно добродушный и, возможно, чуточку ленивый человек. Он не стремится, как Фишер, к победе любыми средствами, обычно довольствуясь "чуть лучше". Превосходно понимая позицию, он, как Смыслов, предоставляет противнику шанс ошибиться. И если противник умудряется-таки не ошибиться, партия закономерно заканчивается вничью... Такой стиль игры даёт меньше единичек в турнирной таблице, чем наступательный и рискованный стиль В. Топалова, отсюда и разница в рейтинге, но в матче с ним Крамник убедительно доказал, что в шахматы выгоднее играть именно так.

Вернёмся теперь к нашим электронным баранам. Для человека с такой чистой манерой игры, тем более человека, много игравшего с машинами, свести партию вничью с "Дип Фритцем" любым цветом не представляет никакой сложности. Предыдущие матчи Владимир так и заканчивал. Однако сейчас перед ним стоит задача посложнее. Ходом 34...Фe3?? во второй партии он подписал негласное обязательство выиграть у программы хотя бы одну партию. Причины этого просмотра, конечно, те же, что и всегда в таких случаях: величайшее напряжение, усталость, но главная, на мой взгляд, - проснувшееся желание выиграть, переключение мышления с профилактики на наступление. Итак, насколько велики шансы Крамника на победу - хотя бы в одной партии? Хотелось бы быть оптимистом, но, глядя на игру Крамника, я не верю, что он сможет спасти матч. Нет, играет он великолепно, но... не так, как нужно в сложившейся ситуации. Спокойно упрощая позицию, он доказал, что играет, как минимум, не хуже. Но, одними упрощениями, как с горечью заметил на chesspro.ru комментатор А. Девяткин, машину уже не одолеть. Крамнику сейчас, как это ни покажется странным, надо стремиться, напротив, к максимальному усложнению игры. Я бы предложил следующий план борьбы. 1) Разыграть скромный, непритязательный дебют с минимумом тактики на выходе. Каталонское начало за белых - вполне подходит, но, пожалуй, ещё более перспективным выглядело бы в борьбе с машиной 1. b3, с дальнейшим развитием на три горизонтали. Компьютер, естественно, захватит центр. Ну что ж, пусть немного порадуется... 2) Если удастся, закрыть центр, пусть даже с образованием "клина", создающего серьёзные неудобства в маневрировании. Идеальной является структура с пешками c4+d3+e4 и c5+d4+e5 (при игре белыми). Машины очень склонны к переоценке позиции стороны, обладающей преимуществом в пространстве. Если центр закрыть возможности не дадут - стремиться к размену ферзей, избегая, тем не менее, менять другие фигуры (особенно коней). 3) Обеспечить безопасность собственного короля и начать постепенно переводить фигуры на фланг, где расположится король "Дип Фритца", располагая основные силы по Филидору, позади пешечной цепи. 4) После завершения подготовки, не считаясь с материальными потерями, - быстрый пешечный штурм.

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

Теперь о статье А. Девяткина "Blow Up". Автор утверждает, что шахматы - "одну из конечных логических игр" - ждёт скорая смерть, и приводит в пример шашки, где компьютер уже в дебюте просчитывает варианты до эндшпиля. К счастью, как известно, шахматы - не шашки. И "фактор ветвления" (branching factor, среднее количество возможных ходов в позиции) в них - в пять раз больше. Это ни в коем случае не означает, что если взять в пять раз более мощный компьютер, то можно просчитать шахматы "до конца" (т. е. однозначно определить оценку каждой позиции в терминах +/-/=). Из-за степенной прогрессии увеличение скорости вычислений в пять раз приводит к повышению глубины перебора вариантов всего на 1 полуход. Количество же возможных позиций в шахматах не идёт вообще ни в какое сравнение с шашками (10^120 против, если не ошибаюсь, примерно 10^20). Это число превышает количество элементарных частиц во Вселенной и гарантирует вечнозелёную юность нашей древней игры...

Для всерьёз опасающихся за судьбу шахмат приведу цитату из работы профессора Маастрихтского университета Джоса Уйтервийка (Jos Uiterwijk) "Computer Chess: State of Art":

"A second argument disfavouring a great future for computer chess runs that computer chess is killing the game of chess. And when chess is dead, interest in computer chess of course also will diminish. I do not agree with this argument either. The complexity of chess is such that even in our fanciest dreams we should not think about SOLVING the game of chess (which, according to many discussions on the Internet, many people confuse with surpassing the human world champion's level). On the contrary, the computer still has us a lot to learn. Notwithstanding the thorough analyses and investigations chess theory still has many mysteries and uncomprehended facts. I feel that, after digesting of the shock caused by the loss [пока никакой "loss", между тем, не наблюдается, и при существующих алгоритмах, убеждён, долгое время наблюдаться не будет. - Д_в_О.] of the human supremacy at the chessboard, humans will quickly realize that the chess machine is no longer an enemy, to be contended, but instead a teacher and tutor, from which much can be learnt".

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

P. S. Что касается дебютов, которые некоторые, деликатно выражаясь, энтузиасты прорабатывают до эндшпиля, то цена большинству таких "проработок" - грош в базарный день (за исключением очень немногих форсированных продолжений, например, в итальянской партии или защите двух коней). Очень хорошо, что "Дип Фритц" не играет сам с первого хода, а использует дебютную библиотеку. Хорошо - для Крамника. Когда компьютер сам разыгрывает дебют, то хочешь - не хочешь, а он располагает фигуры разумно, руководствуясь заложенным в программу здравым смыслом второразрядника. Пусть стратегически беспланово, но как минимум - универсально, по центру. Когда же машину заставляют исполнять ходы, придуманные теоретиками, то несчастный робот может оказаться белыми после второго хода в такой, например, ситуации (реальный эксперимент с моим "Фритцем 9". После 1. Кf3 d5 и 2. b3 чёрные сыграли 2...Фd6!?, превращая мегабайты занесённых в память вариантов в бесполезный мусор. Компьютер задумался. Но не просто задумался, а над вопросом: что делает его пешка на b3, если надо играть по центру?! И сделал "активный" ход 3. Сa3?, выигрывая темп для c4 или d4. То есть фактически уже на третьем ходу, белыми, "Дип Фритц" совершил серьёзную позиционную ошибку. Слон на a3 абсолютно неуместен, и человек, разумеется, сыграл бы просто 3. Сb2 с равными шансами после, например, 3...Кd7. Ход же "Фритца", в сущности, является [/B]потерей[B] темпа. После 3. Сa3 Фb6! (робот после некоторого размышления начинает даже колебаться, не лучше ли 3...Фc6?, хотя смысл этого хода, блокирующего пешку "c", объяснить трудно) 4. d4 (врождённый машинный рефлекс; относительно лучше сразу вернуться - 4. Сb2) e6! у белых печальный выбор: отступить на b2 с потерей темпа и уже вбитой заглушкой в ствол собственной гаубицы (пешка на d4) или разменяться на f8, оставив на ферзевом фланге целый комплекс слабостей в подарок чёрным. Забавно, но компьютер очень "радуется" возможности лишить чёрных права рокировать и оценивает позицию после 5. Сxf8 Крxf8 в пользу белых, не понимая того, что сам добровольно помог чёрным убрать короля туда, где ему и надлежит быть (а ладья h8 войдёт в игру через h6 после h5, и сразу - на королевский фланг, ведь компьютер может ещё и рокировать!. Ещё забавнее, что после нормального 6. e3 "Фритц" долго предлагает чёрным отвечать 6...Фd6?, и только потом рассматривает, казалось бы, напрашивающееся 6...Кf6. Но на глубине в 16 полуходов (! возвращается... к ходу ферзём. Чем глубже считаем, тем хуже понимаем позицию? А стратегически точный ход 6...Кe7! подготавливая продвижение в дальнейшем пешки "f", компьютеру даже не пришёл в голову...

Итак, налицо полное непонимание программой стратегии дебюта и упорное стремление к определённым, очень жёстко заданным схемам развития - даже в ущерб позиции. Я думаю, что Владимир неправильно поступает, используя дебютную библиотеку "Фритца". Немного творчества в начале (после трёх - четырёх теоретических ходов) - и машина сломает о колено стратегическую идею любого дебюта. Нужно только правильно выбрать момент и дебют.

Это сообщение отредактировал Дед_в_очках - 30/11/2006, 06:26

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

Автор утверждает что количество позиций в шахматах составляет около 10 в 120 степени -
сразу возникает вопрос: это количество вариантов позиций возникающих за какое
количество ходов? Предположим, что это число оценивает варианты развития ситуации
за некое разумное количество ходов, логично ограничивающее длительность партии.
Тогда давайте подумаем, о том, что это значит. Такое огромное число может
характеризовать только количество вариантов комбинаторного перебора, а таким
образом сложность (математическая) шахмат оцениваться не может! Такой подход
противоречит сути самой игры.
Попробую обосновать. Насколько я помню теорию игр, согласно теореме Неша (того самого из фильма
Игры Разума), любая конечная игра с полной информацией имеет оптимальную стратегию для каждого
игрока. На практике это означает, что два суперумных и суперзнающих шахматиста сыграют вничью.
Автор утверждает, что разработать такую стратегию невозможно ввиду комбинаторной сложности задачи.
Но ведь шахматы - это алгоритмическая игра, а суть любого алгоритма в теории графов, комбинаторике
и т.д. и заключается в значительном сужении области значений целевой функции (т.е. к сокращению
количества возможных вариантов). Очевидно, что большинство ходов в усредненной позиции неверны.
Сложно оценить количественно, но здравый смысл подсказывает, что их абсолютное большинство.
Отсюда, вспоминая слова автора об экспоненциальном росте сложности (а думается и факториальном -
неохота размышлять), можно сделать такой вывод: уменьшение вариантов в начале задачи ведет
к экспоненциальному же снижению комбинаторной сложности!
Теперь давайте учтем постоянное совершенствование алгоритма программы, вспомним закон Мура о
росте производительности компьютеров, добавим вполне возможный революционный скачок мощности
компьютера - и станет очевидно, что решение задачи не за горами (я уже упоминал, что оно точно
есть - см.выше).

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

С уважением, Дмитрий

Вывод неверен.

Так, насколько, я помню говорил мне доктор технических наук, профессор Безгинов А.Н. ))) Кроме того,
так, вроде бы, утверждалось в книге по теории игр кого - то из основателей, типа фон Неймана или Колмогорова. Кстати, интересно было бы узнать Ваш вывод, надеюсь с тем, что шахматы удовлетворяют
условиям теоремы вы не будете спорить?

С уважением, Дмитрий

Кстати интересно откуда получена оценка числа позиций в шахматах 10**120? Эта оценка встречается во многих местах, например тут, но я нигде не нашёл её обоснования.

У меня получилась грубая оценка сверху 10**68,339202105793072320187547973901 без учёта поворотов и отражений, но и без учёта очерёдности хода (т.е. примерно ещё в 8/2=4 раза меньше). Так и быть, поворотами мы пренебрежём, потому что пешки могут попасть на 1 или 8 горизонталь, а отражение с переходом a<->h компенсируется очередью хода.

Ход моих мыслей (поправьте, если я что-то упустил):

Белый король может стоять на любой из 64 клеток.
Для чёрного короля остаётся не более 60 клеток.
Фигуры (14 штук) по максимуму могут стоять каждая на 62 клетках + ещё 1 вариант - фигура сбита. Имеем 63**14. Пешка может быть пешкой на 48 полях + одной из 4 фигур на 62 поле + пешка может быть сбита.
Имеем (48+62*4+1)**16

То есть 10**(lg(64)+lg(60)+14*lg(63)+16*lg(297))

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

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

Это сообщение отредактировал VKB - 4/12/2006, 16:17

Хотелось бы попробовать ещё раз донести идею: неважно сколько позиций - позиция без хода игры не имеет значения, сколько - нибудь разумным можно считать количество вариантов развития игры (количество стратегий), из которых и состоит общее решение (смешанная стратегия). Но, повторюсь - комбинаторный подход неприемлем и не применяется в чистом виде, как например в "задаче коммивояжера", поскольку шахматные задачи, как мне думается, решаются с применением алгоритма сужения области значений (ОДЗ)целевой функции!
Кстати, про число 10^120 - интересное сравнение с количеством частиц во Вселенной - никто не имеет представления, что это вообще такое, а уже подсчитали количество частиц, причём элементарных о коих также представления нет, со времени моей учёбы в школе наверняка нашли ещё более "элементарные" частицы
чем кварки - не интересовался, так что сравнение так себе ))

С уважением, Дмитрий

Утверждение о ничейном исходе легко опровергнуть примером: рассмотрим крестики-нолики на доске два на два. Игра конечная, с полной информацией, а крестики (те, кто ходят первыми) легко и надежно выигрывают.

Наличие оптимальных стратегий не ведет к ничье.

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

Ссылки на знакомство с профессором Безгиновым и теорему без формулировки, в авторстве которой есть сомнения (фон Нейман или Колмогоров), к сожалению не добавляют убедительности выводу.

Замечу, во-первых, что я не профессор и никогда им не был. Однако получил советское образование, и сведения по теории игр почерпнул не из художественных фильмов.

К сожалению, люди, для которых шахматы - "одна из конечных логических игр", люди, чужие шахматам, не видят большой разницы между ними и крестиками-ноликами в квадрате 3x3. Им кажется, что перебрать все варианты, тем более при современной вычислительной мощности, - плёвое дело. К счастью (не для них), здесь именно тот случай, когда количество переходит в качество. Повторяю ещё раз со всей ответственностью: РЕШИТЬ ШАХМАТЫ ПРИНЦИПИАЛЬНО НЕВОЗМОЖНО. Ни при какой вычислительной мощности. Полную информацию об этой игре может иметь только Господь Бог.

По первому вопросу создалось впечатление, что требуется небольшой ликбез.
10^120 - это количество всех возможных расстановок 32, 31, 30... и т. д. фигур на доске. Всех легальных позиций, способных возникнуть в процессе игры. Если считать невозможные по правилам игры позиции (оба короля под шахом, пешки на крайних горизонталях, а также различного рода позиции, которые не могли получиться из исходной), то их количество возрастает до 10^123. Максимальная же продолжительность партии ограничивается необходимостью каждые 50 ходов совершать хотя бы одно взятие или ход пешкой и составляет порядка 4000 ходов (известно точное число, но я его не помню).

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

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

Далее мой оппонент утверждает, что поскольку проигрывающих ходов в средней позиции большинство (?), отсекая их, программы смогут значительно сократить дерево перебора. Этот метод, впервые предложенный проф. Брудно, называется альфа-бета-процедурой и успешно используется во всех шахматных программах. Он действительно позволяет оценивать вместо N^D позиций (где N - среднее количество возможных ходов в позиции, а D - глубина, на которой производится оценка) при максимально удачном порядке перебора вариантов "всего лишь" N^D/2 позиций. Размерность шахмат, однако, такова, что это сокращение фактически оказывается пустым звуком.

Это не имеет большого значения, но мой опыт, тем не менее, говорит о том, что проигрывающих ходов в средней позиции отнюдь не большинство, а меньшинство. Специальным подсчётом я не занимался, но приведу в пример хотя бы начальную позицию, где любой ход белых сохраняет ничейную оценку. Ложное впечатление о том, будто хороших ходов так мало, возникает, видимо, из-за внешней бесцельности многих ходов. Но бесцельный ход - ещё не означает проигрывающий. Шахматисты хорошо знают: для того чтобы проиграть партию, одной ошибки мало. После первой ошибки лишь сокращается количество путей, ведущих к ничьей.

И напоследок - о перспективах. Знаете ли вы, что...
Существует такая замечательная константа - скорость света. Именно ей ограничивается предельно возможная скорость вычислений любого компьютера, созданного сейчас или в будущем. Известна точная цифра, сколько бит в секунду сможет обработать такой идеальный компьютер (увы, снова не помню, но интересующиеся легко найдут информацию в интернете). И даже при такой скорости вычислений и при бесконечной (!) скорости работы генератора ходов, с использованием всего времени только на оценку позиций, для полного решения шахмат потребуется время, превышающее время жизни протона - 10^96 лет...

P. S. А возможность, что компьютер будет играть сильнее любого человека, я вполне допускаю. И даже не столько играть в чисто спортивном смысле, пользуясь отсутствием усталости и вообще психики, - интереснее вопрос, сможет ли машина научиться пониманию позиции на уровне, превосходящим уровень человека. Т. е. сможет ли робот принимать в каждой конкретной ситуации стратегически более правильные решения, чем гроссмейстер. Думаю, вот это если и произойдёт, то не сегодня и не завтра. Во-первых, потребуются совершенно другие методы оценки позиции, основанные, возможно, на нейросетях или генетических алгоритмах, - программы будущего должны стать самообучающимися. Во-вторых... люди ведь тоже учатся! Я не могу представить себе ситуацию, чтобы высококлассный гроссмейстер уровня Крамника, сыграв несколько партий даже с компьютером двадцать второго века, не смог бы понять, как его переигрывают. А поняв это - не выстроил встречной стратегии...

насчет указанных оценок 10**120
Это количество различных партий в шахматах, а не количество различных позиций
я многократно видел обоснование этой оценки
например http://www.radioc.ru/programs/hotten/571/
кратко это выглядит так

у каждой стороны имеется где-то 40 вариантов очередного хода
за первые 40 ходов белых и 40 ходов черных получаем
40 ** (40+40) = 1.5 * 10 **128

само же число позиций меньше

P.S. это просто очень грубая и примитивная оценка сверху и не более того

Это сообщение отредактировал B_A_D - 4/12/2006, 16:44