Итеративное углубление в минимаксе - сортировка всех допустимых ходов или просто поиск PV-хода с использованием MVV-LVA? - PullRequest
Новая
       111

Итеративное углубление в минимаксе - сортировка всех допустимых ходов или просто поиск PV-хода с использованием MVV-LVA?

0 голосов
/ 06 января 2020

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

Он состоял из минимаксного поиска, выполненного на глубине = 1, глубине = 2 и т. Д. c. до достижения желаемой глубины. После минимаксного поиска каждой глубины, сортируйте root -узел перемещений в соответствии с результатами этого поиска, чтобы обеспечить оптимальный порядок перемещения при следующем поиске с глубиной + 1, поэтому при следующем более глубоком поиске PV-перемещение выполняется поиск, затем следующий лучший ход, затем следующий лучший ход после этого и т. д.

Это правильно? Сомнения возникли, когда я прочитал об упорядочивании MVV-LVA, в частности об упорядочении захватов и, кроме того, об использовании таблиц ha sh и подобных. Например, на этой странице рекомендует порядок перемещения:

  1. PV-перемещение основного варианта из предыдущей итерации итеративной структуры углубления для самого левого пути, часто неявно выполняемой на 2.
  2. Ха sh ход от ха sh столов
  3. Победные захваты / продвижения
  4. Равные захваты / продвижения
  5. Убийственные ходы (не захват), часто сначала с убийцами помощников Точка сортировки минимакса по каждой глубине, если нужен только PV-ход? С другой стороны, если вся точка ID - это PV-перемещение, не будет ли бесполезно искать от каждой минимальной глубины до желаемой глубины только для вычисления PV-перемещения каждой глубины?

    Какова конкретная цель идентификатора и сколько вычислений он экономит?

1 Ответ

0 голосов
/ 13 января 2020

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

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

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

Надеюсь, это поможет, и я правильно понял ваш вопрос.

...