Почему Minimax с отсечкой альфа-бета расширяет число узлов во втором повороте Connect Four?

Question

У меня есть программа, которая проигрывает Connect Four против оппонента-человека, используя либо стандартный минимаксный алгоритм, либо минимаксный с отсечкой альфа-бета. Оба алгоритма имеют ограничение по глубине, после чего они применяют функцию оценки. В рамках проекта мне пришлось создать кривые производительности, показывающие количество узлов дерева поиска, расширяемых алгоритмами, за оборот компьютера. Кривые показывают тенденцию к снижению, как и ожидалось, так как число возможных состояний уменьшается по ходу игры. Тем не менее, я не могу объяснить, почему количество узлов увеличивается во втором повороте компьютера, что особенно заметно в случае альфа-бета, как можно видеть на изображениях ниже:

Эти кривые были построены на основе тестовой игры, в которой человек играл первым, а предел глубины составлял 8 слоев. Кто-нибудь знает, почему кривые не строго уменьшаются?

Answer 1

Минимакс может видеть увеличение количества узлов в зависимости от того, как игра разветвляется на разных слоях. Рассмотрим глупую игру, в которой на первых 8 уровнях оба игрока вынуждены «ничего не делать», а на 9-м уровне они получают гораздо больше вариантов. Если ваша глубина составляет 8 слоев, вы наверняка увидите, как больше узлов будет расширено, как только минимакс достигнет 9-го слоя.

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