Прогулка по огромному игровому дереву

Question

У меня есть игровое дерево, которое слишком велико, чтобы ходить целиком.

Как я могу написать функцию, которая будет оценивать дерево до тех пор, пока не будет достигнут предел времени или предел глубины?

Answer 1

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

• Ограничение по времени : Это явно невозможно без использования IO, для начала.Предполагая, что ваша функция обхода дерева игр в значительной степени чистая, вы, вероятно, предпочли бы не переплетать ее с кучей отслеживания времени, которая определяет поток управления.Я думаю, что самая простая вещь здесь, вероятно, состоит в том, чтобы обход производил поток прогрессивно лучших результатов, помещал каждый «лучший результат на данный момент» в MVar или около того и запускал его в отдельном потоке.Если ограничение по времени достигнуто, просто убейте нить и возьмите текущее значение из MVar.

• Предел глубины : самый тщательный способ сделать этобыло бы просто выполнить поиск в ширину, не так ли?Если по какой-либо причине это невозможно, я не думаю, что есть какое-то лучшее решение, чем очевидное решение: просто держать счетчик, чтобы указать текущую глубину, и не продолжать глубже, когда достигается максимум.Обратите внимание, что это тот случай, когда код потенциально может быть приведен в порядок с помощью монады в стиле Reader, где каждый рекурсивный вызов заключен в нечто вроде local (subtract 1).

Answer 2

Функция timeout в базовом пакете позволяет вам завершить вычисления после определенного периода. Чередование timeout с потоком все более глубоких результатов, так что самый последний результат сохраняется в MVar, является относительно распространенным приемом для проблем поиска в Haskell.

Answer 3

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