Зачем нужна обрезка игрового дерева на ленивом языке
Итак, я читал книгу Грэма Хаттона «Программирование на Haskell». В 11 главе реализована игра крестики-нолики. Мой вопрос касается AI-части игры, где используется минимакс. Меня немного смутила функция обрезки:
prune :: Int -> Tree a -> Tree a
prune 0 (Node x _) = Node x []
prune n (Node x ts) = Node x [prune (n-1) t | t <- ts]
Зачем нам нужна такая функция сокращения в Haskell (у которой есть ленивые вычисления)? Почему мы не можем просто создать одно бесконечное игровое дерево и запустить на нем фитнес-функцию до определенной глубины, не создавая при этом нового конечного дерева путем обрезки? Затем мы можем повторно использовать одно и то же дерево, срезая его сверху после каждого хода и как бы расширяя (то же самое) дерево вниз. Разве это тоже не должно работать?
Затем я увидел, что одно из упражнений этой главы было: генерировать дерево игры один раз, а не для каждого хода
Решение для этого упражнения предоставлено кем-то на Github. Однако мне кажется, что здесь после каждого хода генерируется новое дерево, и поэтому дерево не используется в течение всей игры.
Ответы 1
Зачем нам нужна такая функция сокращения в Haskell (у которой есть ленивые вычисления)?
По сути, это вспомогательная функция, которую можно использовать для поиска только на ограниченном количестве уровней. Она может брать лениво сгенерированное дерево и лениво его обрезать. Итак, если у вас есть функция, которая, например, определяет максимальную оценку всех узлов игрового дерева, то она может перейти в бесконечный цикл, поскольку дерево имеет бесконечную глубину. Мы можем специализировать функцию, определяющую оценку, для проверки только до заданной глубины, но, таким образом, функцию prune можно использовать в качестве препроцессора для обеспечения этого.
Решение для этого упражнения предоставлено кем-то на Github. Однако мне кажется, что здесь после каждого хода генерируется новое дерево, и поэтому дерево не используется в течение всей игры.
В решении действительно кажется, что каждый раз генерируется новое дерево, вы можете использовать подузел дерева, если сделаете ход, и, таким образом, повторно использовать уже построенное игровое дерево.
Вы пробовали реализовать это так, как вы предлагаете? Возможно, вы захотите включить в вопрос фитнес-функцию, возможно, из-за того, что она написана, трудно заставить ее остановиться на определенной глубине.