Как компьютер играет в шахматы?


Хикару Накамура, недавно бросивший вызов компьютеру

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

Если вам интересно, как же устроены шахматные движки — добро пожаловать под кат.

Введение


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

Это, несомненно, очень наивное мнение. Новую позицию в шахматах можно получить к десятому ходу. Хоть в шахматах и меньше позиций, чем в го, тем не менее, уже после 3 ходов (ход — это один ход белых и чёрных, полуход — ход только одной стороны) дерево ходов состоит из почти 120 миллионов узлов. Более того, размер дерева после 14 полуходов из начальной позиции энтузиасты считают уже больше года, продвинувшись пока что примерно на треть.

Ещё я думал, что шахматные программы, несмотря на давнюю победу в матче над чемпионом мира, все еще находятся в пределах досягаемости лучших людей. Это тоже не верно.

В недавнем мини-матче человека с машиной, Хикару Накамура, один из сильнейших шахматистов в мире, играл с Komodo, одной из (двух) сильнейших шахматных программ в мире. Программа была запущена на 24-ядерном Xeon'е. Так как на равных соревноваться с компьютером люди уже не могут, гроссмейстер получил фору в каждой из 4 партий:
  • В первой партии — пешка и ход: компьютер играл чёрными и без пешки f7
  • Во второй — только пешка: компьютер играл белыми без пешки f2
  • В третьей — качество (разница между ладьёй и лёгкой фигурой, оценивается примерно в 2 пешки): компьютер белыми без ладьи a1, человек без коня b8 и с ладьёй a8 на его месте.
  • В четвертой — четыре хода: человек играет белыми и вместо первого хода делает 4 любых хода, не пересекая середину доски.

По поводу форы были определённые споры — например, отсутствие пешки f несколько ослабляет короля, но после рокировки даёт открытую линию ладье. Отсутствие центральной пешки, возможно, даёт большее преимущество. 4 хода дают неплохой позиционный перевес, но если играть закрытый дебют вроде староиндийской защиты, то это преимущество не так уж и сложно свести на нет.

Кроме того, партии игрались с контролем 45"+15', то есть 45 минут на партию и 15 секунд добавления каждый ход. Обычно, более короткие контроли дают дополнительное преимущество компьютеру, в то время как более длинные — несколько повышают шансы человека. Компьютер даже за доли секунды успеет отмести откровенно проигрывающие ходы, в то время как из-за экспоненциального роста дерева вариантов каждое последующее улучшение анализа занимает всё больше времени.

Тем не менее, фора была и человек проиграл в матче 2.5-1.5, сведя в ничью первые 3 партии и проиграв четвёртую. Вместе с тем, слабый гроссмейстер достаточно уверенно выиграл с форой в 2 пешки. Следовательно, преимущество лучших программ над лучшими людьми на данный момент где-то между 1 и 2 пешками форы. Конечно, эта оценка очень грубая, но для точной оценки надо сыграть несколько тысяч партий между людьми и программами, а этим вряд ли кто-то будет заниматься. Обратите внимание, что рейтинг ЭЛО, нередко указываемый для программ, не имеет ничего общего с рейтингом людей.

Что такое шахматный движок?


Чтобы человек мог играть в шахматы с компьютером, кроме собственно поиска лучшего хода, нужен GUI. К счастью, был придуман универсальный интерфейс (даже два, Winboard и UCI, но большинство движков использует UCI) для связи между GUI и собственно шахматной программой (движком). Таким образом, программисты могут сосредоточиться на самом алгоритме игры в шахматы, не задумываясь об интерфейсе. Обратная сторона монеты — так как создание GUI гораздо более скучное занятие, чем написание движка, то бесплатные GUI заметно проигрывают платным. В отличии от движков, где свободный Stockfish уверенно борется за первую строчку рейтинга с платным Komodo.

Как же они все таки играют?


Итак, как же устроен современный шахматный движок?

Представление доски


Основа любого движка — представление шахматной доски. В первую очередь, надо «объяснить» компьютеру все правила шахмат и дать ему возможность хранить шахматную позицию. Без этого невозможно оценивать позицию и делать ходы.

Есть два основных способа хранить представление доски — по фигурам или по клеткам. В первом случае мы храним для каждой фигуры её место на доске, во втором — наоборот, для каждой клетки храним что находится там. У каждого метода есть свои преимущества и недостатки, но на данный момент все топовые движки используют одно и то же представление доски — bitboards.

Bitboards


По счастливому совпадению, на шахматной доске 64 клетки. А значит, если для каждой клетки использовать один бит, мы можем хранить всю доску в 64-битном целом числе.
В одной переменной будем хранить все белые фигуры, в другой — все черные, и ещё в 6 — каждый тип фигур по отдельности (другой вариант — 12 битбордов для каждого цвета и типа фигур по отдельности).

В чем преимущество такого варианта?
Во-первых, память. Как мы узнаем позже, при анализе представление доски копируется много раз, и, соответственно, отъедает оперативку. Битборды — это одно из самых компактных представлений шахматной доски.
Во-вторых, скорость. Многие вычисления, например, расчёт возможных ходов, сводятся к нескольким битовым операциям. За счёт этого, например, использование инструкции POPCNT дает ~15% ускорение современным движкам. Кроме того, за время существования битбордов было придумано немало алгоритмов и оптимизаций, как, например, «магические» битборды.

Поиск


Минимакс


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

Альфа-бета


Первая оптимизация — альфа-бета. Идея альфа-беты проста — если у меня уже есть хороший ход, то можно отсечь ходы, которые заведомо хуже. Рассмотрим пример на жуткой картинке слева. Допустим, у игрока А есть 2 возможных хода — a3 и b3. Проанализировав ход a3, программа получила оценку +1.75. Начав оценивать ход b3, программа увидела, что у игрока B есть два хода — a6 и a5. Оценка хода a6 +0.5. Так как игрок B выбирает ход с минимальной оценкой, то он никак не выберет ход с оценкой выше 0.5, а значит оценка хода b3 меньше 0.5, и рассматривать его смысла нет. Таким образом, все оставшееся поддерево хода b3 отсекается.

Для отсечений мы храним верхнюю и нижнюю границы — альфу и бету. Если при анализе ход получает оценку выше беты — то текущий узел отсекается. Если оценка выше альфы — то альфа обновляется.

Узлы в альфа-бете делятся на 3 категории:
  1. PV-Nodes — узлы, оценка которых попала в окно (между альфой и бетой). Корень и самый левый узел всегда являются узлами этого типа.
  2. Cut-Nodes (или fail-high nodes) — узлы в которых произошло отсечение по бете.
  3. All-Nodes (или fail-low nodes) — узлы, в которых ни один ход не превысил альфу по оценке.


Сортировка ходов


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

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

Для взятий может использоваться, например, простая эвристика MVV-LVA (Most Valuable Victim — Least Valuable Aggressor). Мы сортируем все взятия по убыванию ценности «жертвы», а внутри соритруем еще раз по возрастанию ценности «агрессора». Очевидно, что обычно забрать пешкой ферзя выгоднее, чем наоборот.

Для «тихих» ходов используется метод «убийственных» (killer) ходов — ходов которые вызвали отсечение по бете. Это ходы обычно проверяются сразу после ходов из хеша и взятий.

Хеш таблицы или таблицы перестановок


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

Итерационный поиск


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

Эти проблемы решает итерационный поиск. Для начала мы проводим анализ на глубину 1, потом на глубину 2 и т.д. Таким образом, каждый раз мы спускаемся чуть глубже, чем в прошлый раз, пока анализ не будет остановлен. Чтобы уменьшить размеры дерева поиска, результаты прошлой итерации обычно используются, чтобы отсекать заведомо плохие ходы на текущей. Этот метод называется «окно стремлений» (aspiration window) и используется повсеместно.

Поиск спокойствия(Quiescence Search)


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

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

Выборочный поиск


Идея выборочного поиска в том, чтобы дольше рассматривать «интересные» ходы и меньше — неинтересные. Для этого используются продления, которые увеличивают глубину поиска в определённых позициях, и сокращения, уменьшающие глубину поиска.

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

Отсечения и сокращения


С отсечениями и сокращениями всё гораздо интереснее. Именно они позволяют значительно сократить размер дерева.

Вкратце об отсечениях:
  • Дельта-отсечение — проверяем, может ли взятие улучшить текущую альфу. Для этого к оценке узла добавим ценность взятой фигуры и еще немного и посмотрим, больше ли получившееся значение, чем альфа. Например, если у белых не хватает ладьи, то взятие пешки вряд ли им поможет, с другой стороны, взятие слона может помочь.
  • Отсечение бесполезности — то же самое, только для не-взятий. Если текущая оценка настолько меньше альфы, что никакое позиционное преимущество не сможет это скомпенсировать, то такие узлы отсекаются. Обычно применяется на низкой глубине (1-2).
  • Историческое отсечение — для каждого хода мы храним, сколько раз данный ход спровоцировал отсечение, независимо от позиции. Ходы с высоким значением этой эвристики отсекаются. Обычно применяется начиная с определенной глубины и не применятся на PV узлы. Иногда объединяется с предыдущим методом.
  • Multi-Cut — если из первых M(например, 6) узлов хотя бы C(например, 3) являются Cut-node, то отсекаем все узлы.
  • Отсечение по null-ходу — если после null-хода (простая передача очереди хода сопернику) оценка все равно выше беты, то отсекаем узел. Проще говоря, если позиция настолько плоха, что даже сделав два хода подряд, игрок все равно не может ее улучшить, то нет смысла рассматривать эту позицию.


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

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

NegaScout и PVS


Две очень похожие техники, которые используют тот факт, что после того как мы нашли PV-node (приусловии что наши ходы достаточно хорошо отсортированы), она скорее всего не изменится, то есть все оставшиеся узлы вернут оценку ниже, чем альфа. Поэтому вместо поиска с окном от альфа до бета, мы ищем с окном от альфа до альфа+1, что позволяет ускорить поиск. Конечно, если в каком-то узле мы получаем отсечение по бете, то его надо ценить заново, уже нормальным поиском.

Разница между двумя методами лишь в формулировке — они были разработаны примерно в одно время, но независимо, и поэтому известны под разными названиями.

Параллельный поиск


Распараллеливание альфа-беты — отдельная большая тема. Я вкратце пройдусь по ней, а кому интересно — почитайте Parallel Alpha-Beta Search on Shared Memory Multiprocessors. Сложность в том, что при параллельном поиске многие Cut-nodes анализируются до того, как другой поток найдет опровержение (установит бету), в то время как в последовательном поиске, при хорошей сортировке многие из этих узлов отсеклись бы.

Lazy SMP


Очень простой алгоритм. Мы просто запускаем все потоки одновременно с одним и тем же поиском. Коммуникация потоков происходит за счёт хеш-таблицы. Lazy SMP оказался неожиданно эффективным, настолько, что топовый Stockfish перешел на него с YBW. Правда, некоторые считают, что улучшение произошло из-за плохой реализации YBWC и слишком агрессивных отсечений, а не из-за преимущества Lazy SMP.

Young Brothers Wait Concept (YBWC)


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

Dynamic Tree Splitting (DTS)


Быстрый и сложный алгоритм. Немного о скорости: скорость поиска измеряется через ttd (time to depth), то есть время, за которое поиск достигает определенной глубины. Этот показатель обычно можно использовать для сравнения работы разных версий движка или движка, запущенного на разном количестве ядер (хотя Komodo, например, увеличивает ширину дерева при большем количестве доступных ядер). Кроме того, во время работы движок отображает скорость поиска в nps (nodes per second). Это метрика гораздо более популярная, но она не позволяет сравнивать даже движок сам с собой. Lazy SMP, в котором нет никакой синхронизации, практически линейно увеличивает nps, но из-за большого объема лишней работы, его ttd не так впечатляющ. В то время как для DTS nps и ttd изменяются практически одинаково.

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

Оценка


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

Компьютер оценивает позицию в пешках: +1.0 означает, что у белых преимущество равноценное 1 пешке, -0.5 означает, что у черных преимущество в полпешки. Мат оценивается в 300 пешек, а позиция в которой известно количество ходов до мата x — в (300-0.01x) пешек. +299.85 значит, что белые ставят мат в 15 ходов. При этом сама программа обычно оперирует целыми оценками в сантипешках (1/100 пешки).

Какие параметры компьютер учитывает при оценке позиции?

Материал и мобильность


Самое простое. Ферзь 9-12 пешек, ладья 5-6, конь и слон 2.5-4 и пешка, соответственно, одна пешка. В общем, материал — это достойная эвристика оценки позиции и любое позиционное преимущество обычно трансформируется в конце концов в материальное.

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

Таблицы позиций фигур


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

Пешечная структура


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


Этапы игры


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

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

Прочее


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

Точная оценка или быстрый поиск?


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

Дебютные книги и эндшпильные таблицы


Дебютные книги


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

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

Эндшпильные таблицы


Вернемся к введению. Помните идею хранить много позиций в памяти и выбирать нужную. Вот она. Для малого (до 7) количества фигур просчитаны все существующие позиции. То есть в этих позициях компьютер начинает играть идеально, выигрывая в минимальное количество ходов. Минус — размер и время генерации. Создание этих таблиц помогло в исследовании эндшпилей.

Генерация таблиц


Сгенерируем все возможные (с учетом симметрии) позиции с определенным набором фигур. Среди них найдем и обозначим все позиции, где стоит мат. Следующим проходом обозначим все позиции, в которых можно попасть в позиции с матом — в этих позициях ставится мат в 1 ход. Таким образом находим все позиции с матом 2,3,4,549 ходов. Во всех неотмеченных позициях — ничья.

Таблицы Налимова


Первые эндшпильные таблицы, опубликованные в далёком 1998 году. Для каждой позиции хранится результат игры и количество ходов до мата при идеальной игре. Размер всех шестифигурных окончаний — 1.2 терабайта.

Таблицы Ломоносова


В 2012 году на суперкомпьютере Ломоносов в МГУ были посчитаны все семифигурные окончания (кроме 6 против 1). Эти базы доступны только за деньги и это единственные существующие полные семифигурные эндшпильные таблицы.

Syzygy


Стандарт де-факто. Эти базы гораздо компактнее баз Налимова. Они состоят из двух частей — WDL (Win Draw Lose) и DTZ (Distance to zeroing). WDL базы предназначены для использования во время поиска. Как только узел дерева найден в таблице, у нас есть точный результат игры в этой позиции. DTZ предназначены для использования в корне — они хранят количество ходов до обнуляющего счётчик ходов хода (хода пешкой или взятия). таким образом для анализа достаточно WDL баз, а DTZ базы могут пригодиться при анализе эндшпилей. Размер Syzygy гораздо меньше — 68 гигабайт для шестифигурных WDL и 83 для DTZ. Семифигурных баз не существует, так как их генерация требует примерно терабайт оперативной памяти.

Использование


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

Прочие интересности


Жираф или нейронные сети играют в шахматы


Некоторые из вас возможно слышали о шахматном движке на нейронных сетях, достигшем уровня IM (что, как мы поняли во введении, не так уж и круто для движка). Его написал и выложил на Bitbucket Matthew Lai, который, к сожалению прекратил работу над ним из-за того, что начал работать в Google DeepMind.

Тюнинг параметров


Добавить новую функцию в движок несложно, но как проверить что она дала усиление? Простейший вариант — сыграть несколько партий между старой и новой версией и посмотреть кто победит. Но если улучшение небольшое, а так оно обычно и бывает после того, как все основные фичи добавлены, игр должно быть несколько тысяч, иначе достоверности не будет.

Stockfish


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

Их решение типично для опенсорса — добровольцы предоставляют свои мощности чтобы прогнать на них сотни тысяч игр.

CLOP


Программа, которая оптимизирует параметры через линейную регрессию, используя результаты игр движка с самим собой с разными параметрами. Из минусов — очень ограниченной размер задачи: оптимизировать сотню параметров (вполне адекватное число для движка) ей не под силу, по крайней мере за адекватное время.

Texel's tuning


Решает проблему предыдущего метода. Берем большое количество позиций (автор предлагал 9 миллионов позиций из 64000 игр, я брал 8 миллионов из почти 200000), для каждой сохраняем результат партии (победа белых 1, ничья 0.5, поражение 0). Теперь минимизируем ошибку, которая находится сумма квадратов разности результата и сигмоида оценки. Метод эффективный и популярный, но работает не на всех движках.

Stockfish tuning


Еще одна методика от лидера. Берем параметр равный x, и сравниваем (в нескольких десятках тысяч партий) движок с параметром равным x-sigma и x+sigma. Если победил движок с большим параметром, сдвигаем немного вверх, иначе — немного вниз, и повторяем.

Соревнования движков


Из всех проводимых тестирований соревнований хотелось бы отдельно выделить TCEC. От всех остальных он отличается мощным железом, тщательным подбором дебютов и длинным контролем. В последнем финале было сыграно 100 партий на 2 x Intel Xeon E5-2690v3 с 256 гигабайтами RAM с контролем 180'+30". В таких условиях количество ничей огромно, и результативными было всего 11 партий.

Заключение


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

Только зарегистрированные пользователи могут участвовать в опросе. Войдите, пожалуйста.

Метки:
Поделиться публикацией
Похожие публикации
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама
Комментарии 55
  • +1
    Компьютер уже давно обыграл человека в шахматы, сейчас сильнейшие шахматисты не способны выиграть даже у старенького ноутбука.
    По-подробнее можно? Кто играл, когда, какая программа и кто выиграл?
    • +6
      Подробности — на википедии. В частности Крамник — Deep Fritz и участие Pocket Fritz в турнирах. Конкретно с ноутбуком никто вроде не играл, так что это можете считать моей оценкой.
      • –13
        Достаточно ли вы компетентны в данной области, чтобы давать такую оценку?
        • +9
          Да. Чемпион мира признавался, что затрудняется в игре с мобильным приложением.
          Для тех, кто в теме, это очевидно. Возможно оценка дана несколько расплывчатая, но идея верна. Ни один факт не указывает на противоположное.
      • +7
        Если компьютер(ноутбук) старенький и глупенький, то он подключается к сети, ищет компьютерного соперника для шахмат использующего более мощные ресурсы и начинает параллельно вести игру с ним. В игре с более мощным компьютером он производит те ходы, которые делает человек:)
        • 0
          Человек тоже подключается к параллельной игре с сильным компьютером и играет не хуже.
      • +2
        а что слышно про идею когда в соревнования принимают участие пары человек (сам опытный шахматист) и компьютер. будет ли человек тут только придатком к компьютеру? есть ли такие соревнования?
        • +2
          Есть.Называется advanced chess или просто адванс по русски. Федерация шахмат по переписке (ICCF) разрешает использование компьютерного анализа в играх.

          Влияют ли адвансеры на анализ? Они считают что да. Я склонен им верить, человек пока еще может направлять компьютер и подсказывать ему идеи, но с каждым годом это все сложнее и сложнее. Несколько лет назад сильные адвансеры на домашнем компьютере обыгрывали кластер на котором был запущен движок.

          С контролем же меньше часа-двух на ход, человек вряд ли что-то может улучшить.
          • +2
            Такие дисциплины уже достаточно давно существуют и даже успели потерять популярность — соревнования в таком формате с участием топовых гроссмейстеров проводятся крайне редко.
            Вероятно «продвинутые» шахматы имели смысл, когда человеческое «интуитивное» понимание позиции могло помочь оценке компьютера (в 2005-ом fritz по загадочным обстоятельствам просто просчитался в партии с Пономаревым). Сейчас скореее всего человек уже просто придаток и грубых просчетов программы уже не допускают.
            • +1
              Зайдите на сайт ICCF, посмотрите сколько людей играют в адванс.

              Конечно партии в реальном времени с классическим или более коротким контролем в адванс уже не играют. В этом и правда смысла нет, как я уже сказал.
          • –12
            Например ИИ не умет спец. поддаваться что бы в некоторых местах(ходах) что бы выигрывать. Так скажем блефавать. Это минус в сов. играх. ИИ думает или сделать что бы просто побеждать.
            • +2
              Можете привести пример из шахмат? Или даже любой другой игры.
              • –4
                Читал книгу где человек играет с ИИ шахмат по сети и ему кажется что тут что то не так. Так как ИИ не может спец. поддаваться. В конце он выяснил что играл с человеком. (No Game No Life)
                • +2
                  Кажется я понимаю, о чем вы. Компьютер всегда ожидает сильнейший с его точки зрения ход. Он не ставит некорректные ловушки, в расчете на то, что противник не заметит комбинацию или атаку. Люди делают это постоянно.

                  Взамен, у движков есть параметр "презрение" — число, которое добавляется к оценке (или вычитается из нее), чтобы он оценивал позицию в свою пользу. В целом, это несколько ослабляет игру движка, но помогает ему играть на победу с более слабым соперником.
                  • 0
                    Спасибо что правильно донесли то что я хотел сказать.
                    • +1
                      не думаю, что возникают проблемы «ловушек» у компьютеров, т.к. это лишь типичная проблема выбора между «локальным» и «глобальным» оптимумом, а т.к. до глобального оптимума все равно не добраться (пока не включились «эндшпильные таблицы»), то горизонт поиска оптимумов у компьютера гораздо шире и скорей это будет «ловушка» для человека.

                      Человек вообще по-другому играет, тренируя «ощущения», какая позиция хорошая, а какая плохая (как описанный тут пример Giraffe) + таблицы дебютов и рассчеты в эндшпилях. Правда, чем больше контроль времени тем больше рассчетов и меньше интуиции.
                      • +1
                        Под ловушкой подразумеваю ход, гораздо худший если найти опровержение, который человек делает, ожидая, что соперник опровержение не заметит или, чаще, сам его не замечая.

                        Например, я подставляю слона так, что сделав очевидный ход, соперник проиграет ферзя. Но сделав правильный ход, он выиграет пешку. Компьютер так не сыграет, а человек — может
                • 0
                  Вероятно, этого он действительно не умеет. Но кто сказал, что это слабость?
                  • 0
                    Это не слабость, скорее минус.
                    • 0
                      Для сильного движка, который может смять голой математикой, психологические трюки просто не нужны.
                      Зачем эти ужимки, если он всё равно тебя растопчет?
                      • +1
                        Из-за того, что в шахматах сильные ничейные тенденции, иногда надо делать более слабый, но более агрессивный ход, чтобы выиграть у более слабого игрока. Для этого и существует "презрение"
                • +1
                  тяжело «на глазок» оценить фору в 1-2 пешки — я бы сказал, что это «200-400» пунктов ЭЛО. Это значит что в «человеческом рейтинге» программы за 3000 уже выбрались.
                  • +1
                    Я сначала привел почти такую же цифру, но потом убрал, ибо оценки одной пешки сильно колеблются у разных исследователей. Тем более она зависит и от силы игроков — новичкам зевающим фигуры лишняя пешка мало чем поможет, для гроссмейстеров это серьезное подспорье.

                    Но да, программы явно выбрались за 3000
                    • +1
                      да, спасибо, очень правильное замечание, что перевод фиксированной форы в очки рейтинга ЭЛО будет сильно зависеть от силы игрока и от времени на игру. Видимо мы уже не узнаем (точно) насколько они сильны. Чтобы измерять силу программ нужно много игр с людьми, причем программ разных уровней (включая сопоставимых по уровню) и игр программ разных уровней самими с собой.
                    • 0
                      Не сочтите за придирку, но всё-таки «рейтинг Эло», а не «рейтинг ЭЛО» (эта ошибка в статье тоже наличествует). Арпад Эло — это дяденька такой был.
                    • +3
                      Мне кажется, эта статью стоит и в хабр скопировать, она вполне там будет к месту. ИМХО.
                      • +1
                        Дублировать вроде нельзя. Тематика пограничная, выбрал гиктаймс по совокупности причин (на самом деле просто хотел карму))))
                        • +2
                          Не нашел явного запрета дублирования, кроме того что копипаст с других ресурсов не желателен. Но никто не мешает чуть-чуть дополнить часть про алгоритмы и получится вполне себе интересная статья для хабра, уверен достаточно плюсов она бы там набрала.
                      • +1
                        Кстати было б очень интересно почитать также и про шашки, если у когонибудь есть похожый материал, буду рад почитать.
                        По словам знакомого мастера спорта шашки намного тяжелее поддаються компьютерному анализу, хотя вродиб клеток меньше возможностей хода тоже меньше. В подтверждение он говорит что компьютер однозначно победил человека в шашки на 2 года позже чем в шахматы (хотя может и проблема в том что шашки не так популярны как шахматы в целом мире). Было б тоже интерестно подтвердить или опровергнуть ситуацию с компьютерным анализом шашек VS шахмат.
                        Также у человека досих пор есть возможность выиграть в шашки у компьютера, при условии что компьютер не использует ендшпильные таблицы и время на партию 1минута.
                        • –1
                          У шашек в отличие от шахмат найдено слабое решение, после чего мне кажется интерес к ним практически полностью испарился.

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

                            Ну не путайте, не для шашек, а для чекерсов
                          • 0
                            Если мне не изменяет память, выигрышные алгоритмы для шашек существовали ещё в 80-е и были реализованы на «домашних» компьютерах типа Commodore или ZX Spectrum в виде коммерческих игр.
                            • +3
                              Программирование шашек почти всегда шло примерно в фарватере развития шахматного программирования (исключая только самые ранние годы в англо/американских шашках). К шахматам было приковано внимание ведущих программистов, в разработку программ нередко вливались значительные денежные средства. В свою очередь, шашечные программы были редки, интерес программистов небольшой. Такой порядок вещей, в принципе, сохранился и до наших дней. В международных шашках (10х10) активны в основном голландские программисты, в русских шашках — российские и белорусские. В начале-середине "нулевых", и в тех, и в других шашках ведущие программы достигли уровня лучших шашистов-людей, после чего по сути уперлись в ничейный барьер. Количество ничьих зашкаливает за 90%.

                              результаты матчей с сильнейшими шашистами
                              Международные шашки:
                              2001 Buggy vs. N'Diaga Samb, GMI +0 –2 =11
                              2002 Flits vs. Johan Krajenbrink, GMI +3 –0 = 7
                              2003 Buggy vs. N'Diaga Samb, GMI +3 –0 = 3
                              2003 Flits vs. Guntis Valneris, GMI +0 –0 = 7

                              Русские шашки:
                              2003 Кандауров — Магистр +1 -0 =9
                              2003 Кандауров — Тундра +1 -0 =9
                              2007 Королев — Каллисто +1, -2, =9 (игра с нестандартных позиций)


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

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

                              NS » 22.02.2009, 18:03
                              Чтоб прилично играл шашечный движок нужно совсем немного

                              Перебор — Альфа-бета либо PVS, рассмотрение всех взятий за горизонтом.

                              Для сортировки — Хеш, киллеры, история, взятия сортировать по взятому материалу.

                              В переборных алгоритмах LMR, MultiCut, отсечения на малой глубине (Футилити/ProbCut/Рыбья схема)

                              В оценке достаточно PST. Накрутки (мобильность, центр, баланс флангов и т.д.) что-то прибавляют, но для силы Каллисто3 они совершенно необязательны.


                              Кстати, Сергей хоть и не слишком хорошо играет в шашки, но тем не менее создал свою программу всего за несколько месяцев, используя стандартные алгоритмы. Если кому интересно — исходный код Скифи открыт. Его можно найти в архиве программы Каллисто 4.

                              Теперь про международные шашки.
                              Здесь ситуация немного получше. Программы медленно, но всё же прогрессируют. Сейчас они набирают примерно 65% очков против программ начала "нулевых". Что довольно много, учитывая большую ничейность игры. В настоящее время лучшая программа — Scan 2.0, авторства небезызвестного Фабьена Летузи. Писать он её начал совсем недавно — где-то в начале прошлого года. Не особо напрягался, использовал известные методики, но как ни странно программа сразу же заиграла сильно, и намного опередила все другие известные программы. Как и Скифи, Scan 2.0 тоже open source, т.е. движок с открытым исходным кодом. Скачать код можно здесь. Краткое описание алгоритмов здесь. Пожалуй стоит особо отметить, что для оценки позиции Scan использует также и набор локальных паттернов заимствованных из игры Отелло.
                              • Если в международных шашках ещё есть некоторый прогресс (об этом ниже), то в русских шашках из года в год на звание лучших претендует один и тот же десяток программ, из которых признаки жизни подают только 3-4. Остальные как-то подзаброшены своими программистами.

                                В обоих т.н. чемпионатах мира среди шашечных программ в ТОП-3 была одни и те же программы. Из которых как минимум одна (собственно, чемпион, Торнадо 3), похоже заброшена окончательно.

                                По-видимому, это следствие низкого общественного интереса и высокой ничейности игры.

                                Мне кажется, что больше на них просто не заработать. А улучшать всё сложнее и сложнее. Трудно найти в таком случае мотивацию.
                              • 0
                                Шашки вроде бы решены: была статья "checkers solved."
                                • +1
                                  Только англо/американские. Так называемые "чекерс". И только для начальной позиции. Все другие виды шашек не решены.
                              • 0
                                Спасибо за статью.
                                В FIDO рассылку о программировании шахмат, вел Сергей Марков, разрабатывающий фpиваpный отечественный шахматный движок SmarThink. Прилагаю часть одного письма:
                                ─ FIDO EchoMail (2:5064/10.6) ──────── SU.CHESS ─
                                Сооб: 115 из 116
                                От: Sergei Markoff 2:5027/16.13 04 Окт 01 20:01:41
                                Кому: All 19 Окт 01 02:37:30
                                Тема: Русскоязычные сайты по компьютеpным шахматам:
                                — Доминиpующим подвидом альфа-бета поиска (или метода Бpудно — по имени
                                советского математика, котоpый откpыл этот метод) является т.н. NegaScout.
                                Считается, что NegaScout и SSS* пpимеpно pавны по эффективности. В pазных
                                случаях выигpывает pазный алгоpитм. Однако SSS* весьма сложен в pеализации, это
                                pаз, а во-втоpых большинство эвpистик, используемых в пеpебоpной схеме (SEE,
                                history heuristic, killer moves и т.д.) «заточены» под альфа-бету и ее
                                pазновидности.
                                MTD(f) это, насколько я помню, попытка пpименять на пpактике теоpию т.н.
                                «conspiracy numbers» (pазделение min и max стpатегий в пеpебоpе). Тезисы
                                докладов есть на http://www.cs.ualberta.ca.
                                Для всех интеpесующихся шахматным пpогpаммиpованием pекомендую наш pесуpс:
                                *http://www.aigroup.narod.ru*
                                Там же совpеменный фpиваpный отечественный шахматный движок SmarThink (ELO
                                поpядка 2400).
                                • 0
                                  В отличии от движков, где свободный Stockfish уверенно борется за первую строчку рейтинга с платным Komodo.
                                  И это при том, что разработчики закрытых движков часто воруют код из опенсорса.
                                  • 0
                                    Это не доказано.
                                    Более того, архитектура этих движков должна настолько отличаться, а код быть настолько запутанным, что воровать код было бы просто нелогично. Все равно что винде воровать код у линукса.

                                    Можно воровать идеи, но опять таки, на таком уровне многие улучшения для одного движка будут ухудшениями для другого.
                                  • +1
                                    Хм, и что, платные шахматные GUI — это денежный рынок?
                                    Заняться что ли… :)
                                    • 0
                                      Ну стоит тот же Chessbase прилично… И им пользуется большое количество шахматистов.
                                      • 0
                                        И все они спортсмены или обычные любители тоже готовы тратить 300 евро на такой софт?
                                        • 0
                                          Ну я статистику не веду, но бесплатных альтернатив в принципе нет.
                                          • +1
                                            Насколько я понял, это не просто графическая морда для игры, это что-то более многофункциональное и комплексное.
                                            • 0
                                              Ну да, там всякие фишки для анализа игр, сортировки партий, работы с базами. С ними готовиться к соревнованиям или играть в адванс гораздо проще. Просто фигуры двигать в любой программе можно.
                                          • 0
                                            Для профи — ChessBase, для любителей — более дешевый Fritz.
                                            Я свой Fritz 12 покупал рублей за триста.
                                      • 0
                                        Вместе с тем, слабый гроссмейстер достаточно уверенно выиграл с форой в 2 пешки.
                                        По ссылке ничья с вечным шахом…
                                        • 0
                                          По ссылке — матч из 6 партий с результатом +3=2-1 в пользу человека.
                                          • 0
                                            Да, действительно. Сперва пустой чекбокс даже не заметил...

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

                                          1. Дело в том, что большинство позиций, который можно выставить на доске полным перебором — не валидны с точки зрения правил игры. Или крайне низковероятны. Например: три чернопольных слона с любой из сторон.

                                          2. Между соседними ходами очень небольшое изменение. Т.е. если озадачится именно проблемой ХРАНЕНИЯ позиций то можно сделать так, что совокупность позиций опирается на базовую, храня только дельту изменения к ней.

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

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

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

                                          Зато можно хранить таблицу для 9 а то и 10 фигур на одном обычном компьютере! Отдельный вопрос: как быстро будет посчитана такая таблица, но это уже отдельная история.
                                          • 0
                                            Получив такое компактное хранение можно их пронумеровать и результат оценки для 9 фигур по принципу, схожему с Syzygy. Игра в эндшпиле для компьютера будет сводиться к довольно сложному получению порядкового номера всех полу-ходовых позиции и проверка их в базе на результат.

                                            Syzygy хранит позиции очень, очень компактно.
                                            Безпешечные 9фигурки одного типа (например король, ладья и 3 легких фигуры против короля, двух ладей и легкой фигуры) состоят из 10 (симметрия)6362616059585756=1,56*10^15. Прикиньте, сколько места займет весь набор (5720 типов).
                                            • 0
                                              Парсер съел умножение, а я и не заметил.
                                              10х64х63х62х61х60х59х58х57х56 позиций.
                                              Если есть пешки, то еще раза в 2 больше, потому что симметрии для первой фигуры меньше
                                          • 0
                                            Итерационный п… што? Я всегда это называл поиском в ширину, где глубиной является кол-во шагов.

                                            А вообще хороший вышел чек-лист для любого ИИ. Почерпнул для себя «Quiescence Search», «Историческое отсечение», «Razoring» и «Эндшпильные таблицы». Большая часть вкусностей, к сожалению, не годится для игр несопернических, и где хочется найти решение лучшее, кратчайшее и т.п.
                                            • 0
                                              Отсечения значительно ослабляют игру при фиксированной глубине и значительно усиляют её при фиксированном времени: тест Komodo с включёнными и отключёнными отсечениями. Именно поэтому правильная сортировка ходов и хорошие отсечения гораздо важнее всего остального.

                                            Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.