Сохраняют ли шахматные движки все ранее проанализированные позиции между ходами

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

[Редактировать: я предполагаю, что причина, по которой анализ перемещений не кэшируется, связана с некоторыми ограничениями памяти компьютера, которые просто ускоряют перезапуск анализа]

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

Фон

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

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

Математический тангент

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

Рассмотрим стартовую позицию. Вершина дерева ( k=0) - это один узел. У белых двадцать возможных первых ходов, поэтому на глубине двадцать узлов k=1. Кроме того, у черных также есть двадцать доступных ходов для каждого из вариантов белых: таким образом k=2, есть 20 * 20 = 400возможные позиции! И это только ухудшается, поскольку игроки развивают свои части!

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

Ply |    Positions   |  Total Tree Size
----------------------------------------
 0  | 1              | 1
 1  | 20             | 21
 2  | 400            | 421
 3  | 8000           | 8421
 4  | 160000         | 168421
 5  | 3200000        | 3368421
 6  | 64000000       | 67368421
 7  | 1280000000     | 1347368421
 8  | 25600000000    | 26947368421
 9  | 512000000000   | 538947368421
10  | 10240000000000 | 10778947368421

Результатом того, что каждый уровень экспоненциально больше предыдущего уровня, является то, что размер всего дерева определяется нижним уровнем . Рассмотрим пример выше: последний уровень содержит десять триллионов узлов. Весь остаток дерева содержит только пятьсот миллиардов. Десятый слой содержит около 95% узлов во всем дереве (это действительно так на каждом уровне). На практике это означает, что все время поиска тратится на оценку «последнего» хода.

Ответ

Так как это связано с вашим вопросом? Ну, скажем, компьютер настроен на десять слоев, как указано выше, и далее он «запоминает» результаты своих оценок. Он рассчитывает ход, воспроизводит его, а затем вы делаете ход. Теперь были сделаны два хода, поэтому он удаляет все позиции из памяти, относящиеся к шагам, которые не произошли, и остается с деревом, которое опускается на оставшиеся восемь ходов, которые он уже рассчитал: 26,947,368,421 позиций!

Все в порядке! Таким образом, нам нужно только рассчитать два последних слоя! Используя нашу оценку 20 ходов на каждую глубину, общее количество ходов, которое нам нужно здесь рассчитать, все еще превышает десять триллионов. Позиции, которые мы уже рассчитали, составляют всего 2,5% возможностей! Таким образом, даже кэшируя результаты последнего хода, лучшее, на что мы можем надеяться, это увеличение скорости на 2,5%! По сути, именно поэтому, даже если ваша программа кеширует предыдущие результаты, вы обычно не видите значительного ускорения между ходами (за исключением случаев, когда компьютер находит принудительное сопряжение или что-то, конечно!).

Упрощение Отказ от ответственности

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

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

² Средний коэффициент ветвления в 20, вероятно, слишком низок .

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

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

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

Пример, свидетельствующий о памяти двигателя:

Рассмотрим позиции, где обнаруживаются глубокие теоретические новинки, в частности, игра Каруана против Топалова, в которую играли в этом году. Когда вы позволите двигателю анализировать положение после 12-го хода в течение более или менее короткого промежутка времени (скажем, 10-15 минут), вы можете проверить предложенные движения и увидеть, что TN ( 13.Re2!) не появляется среди них. Представьте движение самостоятельно, вернитесь назад и дайте двигателю снова проанализировать ту же позицию в течение более или менее того же времени. Удивительно, но после некоторых размышлений, теперь двигатель считает TN одним из лучших ходов и одобряет его.

РЕДАКТИРОВАТЬ: оригинальный ответ (хранится ниже) является неправильным, однако, он предоставляет полезный пример памяти двигателя, который был указан в верхней части.

Насколько я знаю, они этого не делают, то есть они начинают поиск дерева практически с нуля при каждом движении.

Однако у них должна быть какая-то функция, которая актуализирует значения для каждого хода, и эта функция, безусловно, имеет некоторую кратковременную память. Некоторые примеры - позиции, где обнаруживаются глубокие теоретические новшества, в частности игра Каруана против Топалова, в которую играли в этом году. Когда вы позволите двигателю анализировать положение после 12-го хода в течение более или менее короткого промежутка времени (скажем, 10-15 минут), вы можете проверить предложенные движения и увидеть, что TN ( 13.Re2!) не появляется среди них. Представьте движение самостоятельно, вернитесь назад и дайте двигателю снова проанализировать ту же позицию в течение более или менее того же времени. Удивительно, но после некоторых размышлений, теперь двигатель считает TN одним из лучших ходов и одобряет его.

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

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

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

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

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

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

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

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

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

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

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