¿Cuáles son algunos de los mejores algoritmos de IA para juegos de 2 jugadores como Ultimate Tic Tac Toe?

Esto dependerá mucho de lo que permita como AI.

Algo así como Tic Tac Toe tiene un pequeño espacio de estado y, por lo tanto, es muy fácil escribir un programa que, en el peor de los casos, dibujará. También es fácil escribir un programa de IA que evalúe muchos juegos basados ​​en este juego pero con reglas diferentes. No he analizado ultimate pero dudo que sea más difícil que la versión directa.

Otros juegos dependerán de su tamaño y de las habilidades del programador, pero la mayoría estará sujeta a un tratamiento de IA, búsqueda eficiente, seguido de heurística.

La poda alfa-beta es el mejor algoritmo de propósito general que conozco, pero si quisiera un programa mundial, escribiría el mío basado en una búsqueda eficiente, buenas heurísticas y algo de aprendizaje jugando tanto contra sí mismo como contra muchos humanos de diferentes capacidades.

Los juegos de IA

  1. Tic Tac Toe tiene solo 19683 variaciones de tablero. Después de aplicar la simetría, este número se reduce varias veces. Entonces, al escribir su juego Tic Tac Toe, escriba un programa separado que repita en todos los tableros posibles y recuerde el camino más rápido hacia la victoria desde cada tablero. Esto generará un archivo de datos sorprendentemente pequeño. Empaquete este archivo con su juego en lugar de AI, y ya está.
  2. Tic Tac Toe no puede perderse por un jugador perfecto, por lo que no hay competencia entre algoritmos. O su algoritmo funciona (nunca pierde) o no funciona.

Poda alfabeta: que es una versión optimizada de minimax que elimina las ramas que no pueden ser parte de la solución.

Otra opción es la búsqueda del árbol de Monte Carlo para juegos no deterministas o un gran árbol de juegos.