Какой будет лучший алгоритм для использования, если я создаю 5x5 tictactoe ai, используя 4 в строке. Первоначальный алгоритм, который мы должны использовать, был минимаксным, но нам дают всего 10 секунд за ход.Лучший алгоритм для 5x5 tictactoe ai с использованием 4 в строке
Если вы хотите построить высокого качества игрока есть много важных улучшений можно реализовать.
Во-первых, это, конечно, alpha-beta pruning, но есть несколько других методов, которые сделают более эффективную обрезку альфа-бета.
Во-вторых, поскольку срок имеет важное значение, вы должны добавить итерационное углубление. То есть вы выполняете поиск сначала до глубины 1, затем до глубины 2 и т. Д. Когда у вас заканчивается время, вы берете лучший ход с ранее завершенной итерации. Поскольку дерево растет экспоненциально, вы фактически ничего не теряете от своих предыдущих итераций. (При коэффициенте разветвления 2 накладные расходы составляют 2, но по мере увеличения коэффициента ветвления эти накладные расходы не теряются.)
В-третьих, используйте history heuristic, чтобы заказать поиск. На небольших итерациях вы узнаете лучший порядок состояний, чтобы приблизиться к оптимальному порядку (для обрезки альфа-бета) на последующих итерациях.
В-четвертых, используйте transposition table, чтобы избежать дублирования состояний. При поиске дерева происходит много транспозиций, и их раннее обнаружение приведет к значительной экономии. (Это, вероятно, будет иметь большее влияние, чем эвристика истории.)
Наконец, постройте наилучшую возможную функцию оценки. Чем лучше вы оцениваете состояния, тем лучше вы играете. (В пределе идеальная оценка потребует только 1-слойного поиска, чтобы играть отлично.)
Конечно, если вы можете просто решить игру, сделайте это. Есть только 3^25 (847,288,609,443) возможных состояний в 5x5 tic-tac-toe, поэтому с прилично-силовой машиной вы можете решить игру, давая вам идеальную функцию оценки.
Поскольку вы упомянули о минимаксном алгоритме, я хочу предложить вам несколько сложный вариант minimax, который называется alpha-beta pruning. Обрезка альфа-бета позволяет избежать части пространства поиска, которое называется обрезкой. Я рекомендую вам прочитать это article.
Вы можете пройтись по дереву поиска до глубины 5 или независимо от вашего времени. Пожалуйста, не так, я не говорю, что обрезание альфа-бета является лучшим, но я предполагаю, что техника обрезки может дать вам преимущество перед минимаксным с точки зрения сложности времени.
Дополнительные ресурсы:
Используйте альфа-бета и функцию оценки. Остановите дерево поиска на глубине 5 или все, что можно достичь за это время. – trincot
, который открывает игру, имеет выигрышную стратегию. –