Будет ли обрезание альфа-бета удалять случайность в моем решении с минимаксным?

Question

Существующая реализация:
В моей реализации Tic-Tac-Toe с минимаксным я ищу все коробки, в которых я могу получить лучший результат, и выбрал 1 из них случайным образом, чтобы одно и то же решение не отображалось каждый раз ,

Для примера. если возвращенный список будет [1, 0, 1, -1], в какой-то момент я буду случайным образом выбирать между двумя самыми высокими значениями.

Вопрос о Альфа-бета отсечение:
Основываясь на том, что я понял, когда алгоритм не находит, что он выигрывает от одного пути, было бы больше не нужно искать другие пути, которые могли бы/не могли бы привести к выигрышный случай.

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

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

Заранее спасибо. Если есть литература по этому поводу, я был бы рад прочитать ее. Если кто-то может опубликовать хорошую ссылку на обрезку aplha-beta, это будет отлично, поскольку мне было трудно понять, как ее применять.

Answer 1

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

Например, если истинная функция оценки для состояния игры может возвращать только значения -1, 0 и 1, вы можете добавить случайно сгенерированное число в диапазоне [0.0, 0.01] к оценке каждого игрового состояния.

Без этого альфа-бета-обрезка не обязательно найдет только одно решение. Рассмотрим this example from wikipedia. В середине вы видите, что найдено два решения с оценкой 6, поэтому он может найти более одного. Я действительно думаю, что он все равно найдет все движения, ведущие к оптимальным решениям в корневом узле, но фактически не найдет все решения в глубине дерева. Предположим, в примере изображение, что обрезанный узел со счетом 9 в середине фактически имел оценку 6. Он все равно будет обрезаться там, так что конкретное решение не будет найдено, но переход от корневого узла, ведущего к нему (средний ход у корня), все равно будет найден. Итак, в конце концов, вы сможете достичь этого.

Некоторые интересные заметки:

• Эта реализация также будет работать в минимакса, и избежать необходимости хранить список несколько (одинаково хорошо) решения
• В более сложных играх, чем Tic Tac Toe, где вы не можете искать полное пространство состояний, добавляя небольшое случайное число для максимального игрока и вычитая небольшое случайное число для такого минимального игрока, как это может немного улучшить вашу эвристическую функцию оценки. Причина этого заключается в следующем.Предположим, что в состоянии А у вас есть 5 ходов, а в состоянии В - 10 доступных ходов, что приводит к одному и тому же эвристическому оценочному счету. Интуитивно, преемники государства В могут быть немного лучше, потому что у вас было больше доступных ходов; во многих играх, наличие большего количества доступных движений означает, что вы находитесь в лучшем положении. Поскольку вы сгенерировали 10 случайных чисел для 10 преемников состояния B, также более вероятно, что наивысшее генерируемое случайное число относится к числу 10 (вместо 5 чисел, сгенерированных для преемников A)