El juego
Tic-tac-toe es un juego muy popular para dos jugadores, X y O, que se turnan marcando los espacios en una cuadrícula de 3×3. El jugador que logra colocar tres de sus marcas en una fila vertical, horizontal o diagonal gana el juego.,
propiedades matemáticas
desde un punto de vista matemático el juego tiene dos propiedades muy importantes:
Propiedad 1:
el juego admite que el jugador que utiliza esta estrategia óptima ganará o empatará pero no perderá.
propiedad 2:
el número de posibles coincidencias diferentes es relativamente pequeño.
al inicio, el primer jugador puede marcar cualquiera de los 9 espacios. En el turno siguiente el segundo jugador puede marcar uno de los 8 espacios restantes y así sucesivamente., El juego continúa hasta que todos los espacios estén marcados o uno de los jugadores gane.
entonces es fácil entender que el número total de diferentes coincidencias es menor que:
987….1 = 9! = 362880
es un número razonablemente pequeño para una computadora.
el algoritmo
de las propiedades 1 y 2 se deduce que un algoritmo práctico y general para ganar / dibujar el juego es usar la búsqueda Alfa Beta.,
en cada turno el algoritmo evalúa todas las posibles consecuencias de cada movimiento (posible debido a la propiedad 2) y elige la que asegurará una victoria o un empate (posible debido a la propiedad 1).
Un jugador AI que elige cada movimiento con la alfa-beta algoritmo de búsqueda nunca va a perder. Para hacer el juego más realista, es bueno introducir un factor estocástico para que cada vez con una probabilidad predefinida, el jugador de IA se mueva aleatoriamente en lugar de seguir el algoritmo alfa beta., Esto hará que el juego sea más realista, ya que el jugador de AI más humano y a veces se pierde.