Возможно ли применение Minimax с доской Tic Tac Toe 4 * 4 или требуется альфа-бета-обрезка?

Question

Я реализовал игру Tic Tac Toe 3 * 3 в java, применяя только алгоритм Minimax. Однако, когда я изменяю размер платы на 4 * 4, программа, кажется, зависает. Я хочу спросить, должен ли я применять Minimax с обрезкой альфа-бета, чтобы решить эту проблему, или это нормально для самого Minimax?

Answer 1

Если вы пытаетесь сделать полный поиск, вам нужно использовать альфа-бета. Наивное дерево поиска 4х4 имеет 16! или около 21 триллиона узлов. Многие из этих узлов не нужно искать, потому что другая сторона опровергает позицию предка, выигрывая на следующем ходу или создавая позицию, которая вынуждает выиграть на 2 слоя позже. Альфа-бета позволит вам вырезать некоторые из этих областей поиска, не проходя их.