Instituto Polit�cnico Nacional
Instituto Politécnico Nacional
"La Técnica al Servicio de la Patria"

Boletín No. 67
1o. de julio de 2018




MAQUINA PASIVA QUE JUEGA AL TRES EN LÍNEA A PARTIR DE PROBABILIDAD CONDICIONAL

 

Román Galarza Madrigal
Esta dirección de correo electrónico está siendo protegida contra los robots de spam. Necesita tener JavaScript habilitado para poder verlo.
Álvaro Anzueto Ríos
Esta dirección de correo electrónico está siendo protegida contra los robots de spam. Necesita tener JavaScript habilitado para poder verlo.

 

Resumen

En este trabajo se realiza la metodología para resolver el juego de tres en línea a partir de probabilidad condicional; colocando de forma vectorial la resolución del juego por probabilidades, se presenta una maquina pasiva que es capaz de jugar al tres en línea.

 

I. Introducción

Tres en línea o juego de gato

El juego de tres en línea, tres en raya o gato, que nace en oriente, es un juego que consiste de un tablero matricial de 3*3 obteniendo así 9 casillas diferentes. Se necesitan de dos jugadores para poder jugar, a cada jugador se le otorgan 3 fichas en la modalidad de juego donde las fichas son movibles. [1]

 

Figura 1. Tablero de tres en línea.

 

Para este trabajo se utilizara la variante de fichas no móviles, en la cual consiste en que el tablero, de 9 casillas, sea llenado por completo con fichas, O ó X, siendo ganador el primero que logre colocar 3 fichas en línea, ya sea horizontal, vertical o diagonalmente.

Las reglas para este jugo son sencillas:

  • Los turnos de los jugadores son alternados siempre.
  • Los jugadores deben colocar una ficha siempre que sea su turno.
  • No se debe colocar una ficha en el mismo sitio donde hay otra.
  • Gana el primero en colocar tres fichas en línea.

El resultado más óptimo es que alguien gane, sin embargo cuando dos personas que conocen bien el juego se enfrentan el resultado terminara en empate o tablas.

Probabilidad condicional

“Se refiere a la probabilidad de que un evento C ocurra cuando se sabe que ya ocurrió algún evento A y se le denota con P(B|A) que se puede leer como probabilidad de que suceda un evento B dado que ya sucedió un evento A.”[2]

Su cálculo es a través de la fórmula:

Donde:

P(AɅB) Es la intersección de la probabilidad de que ocurra A y la probabilidad de que ocurra B.

P(A) Es la probabilidad de que ocurra el evento A.

Maquina sin conocimiento: Búsqueda sin contar con información

“No existe información acerca de la cantidad de pasos necesarios o sobre el costo de ruta para pasar del estado de un momento dado a la meta: lo único que permiten hacer es diferenciar entre un estado meta del otro que no lo es, también llamado búsqueda ciega”. [3]

Se trata de un tipo de máquina que no guarda ni evalúa casos, solo se deja ir por la opción más lógica, ya sea más grande o más pequeña, o es 1 o es 0. Este tipo de máquinas no aprende y solo realiza las acciones según su algoritmo.

II. Desarrollo

El tablero del juego de tres en línea, con su acomode matricial, se le puede dar a cada casilla un nombre, en este trabajo se manejará cada casilla con un número del 1 al 9 que nos permita ubicarla, dicha numeración será dada comenzando en la esquina superior izquierda y terminará en la esquina inferior derecha, como se observa en la figura 2.

 

Figura 2. Tablero matricial del juego de tres en línea con asignación numérica a sus casillas.

 

Para poder ver las posibles rutas y casos convenientes, casos ganadores, lo más sencillo seria realizar un diagrama de árbol, como se ve en la Tabla 1, esto nos permitirá deducir que casos son convenientes y que casos no.

 

Tabla 1. Diagrama de árbol de decisión de las posibles tiradas mostrando un caso ganador, un caso de empate y un caso perdedor.

 

Si desarrollamos todo el diagrama de árbol para ver las probabilidades de ganar, perder o de empatar nos daremos cuenta que existen los casos ganadores posibles mostrados en la Tabla 2, tomando en cuenta que no importa el orden en el que se colocan las fichas.

 

Tabla 2. Casos ganadores donde no importa el orden en el que se tiran las fichas y donde el Humano no bloquea una secuencia ganadora.

 

Debido a que el orden no importa nos permite hacer la tirada que queramos en el turno que deseemos. Suponiendo que el contrincante no tirará en una casilla que interrumpa la ganadora, como se ve en la Tabla 2, se obtienen 8 posibles casos ganadores en los que se puede ganar en 5 turnos, 3 para la máquina y 2 para el humano.

Desarrollemos un posible juego con esta suposición; En el turno 1 la maquina elige tirar en la casilla 3, en el turno 2 el humano tira en la casilla 6, en el turno 3 la máquina tira en la casilla 1, en el turno 4 el humano tira en la casilla 4, por último en el sexto turno la máquina tira en la casilla 2 y el juego se termina, cediéndole la victoria a la máquina, ver Tabla 3.

 

Tabla 3. Se muestra un juego de gato con la suposición de la Tabla 2.

 

Si seguimos suponiendo que el contrincante nunca bloqueará una secuencia ganadora, tal como lo hicimos antes, pero ahora importándonos el orden en el que se tira, se obtiene la Tabla 4.

 

Tabla 4. Casos donde solo importa la primera tirada, sin tomar en cuenta donde coloca su ficha el contrincante.

 

Como se observa en la tabla 4, existen 24 casos ganadores a partir de elegir la primera casilla donde se coloca la ficha sin importar el orden de las otras dos. De estas 24 posibilidades, la casilla 5 se repite un mayor número de veces, siendo 4 veces las que se repite si se empieza primero en la casilla 5 y siendo 12 veces de las 24 que se utiliza la casilla 5 para poder ganar el juego.

Podemos decir que la casilla número 5 tiene un mayor peso probabilístico para la victoria, pues el primer jugador que se apodere de la casilla tendrá 4 rutas posibles para ganar y bloqueará 12 casos posibles al contrincante.

Para poder trabajar de una manera más cómoda en el lenguaje máquina pasaremos el tablero del juego de gato, de forma matricial, a una forma vectorial.

 

Figura 3. Transformación del tablero matricial a una forma vectorial.

 

Si le damos ponderación probabilística a cada casilla en el primer turno nos queda la Tabla 5 desarrollada a partir de la Tabla 4:

 

Tabla 5. Probabilidad de las casillas para obtener un caso ganador.

 

Si le diéramos a escoger a una persona en que casilla tirar, lo más probable es que tire en la casilla 5 como primer turno sabiendo la probabilidad anterior, así pues, si pusiéramos a una maquina a elegir en cual casilla tirar basados en la ponderación probabilística y haciendo que se escoja la máxima probabilidad tendríamos que:

Max (Probabilidad)=Casilla 5

Quitando las 12 probabilidades que bloqueamos al tirar en la casilla 5 obtenemos nuevos casos, 12, con probabilidades distintas siendo que el 5 ya ha sido escogido, al desarrollar la tabla nos daremos cuenta que las esquinas, casillas 1, 3, 7 y 9, ahora son las que tienen mayores posibilidades para ganar, 2/12, es decir tenemos un probabilidad condicionada.

 

Tabla 6. Probabilidades dado que ya fue escogida la casilla 5.

 

En la Tabla 6 están depositados los valores probabilísticos una vez escogida la casilla 5, nuevamente, siendo lógico, alguien elegiría una casilla con más probabilidad de los demás, en esta ocasión escogemos la casilla 1, por ser la primer casilla que encontramos y que tiene mayor probabilidad ahora.

 

Tabla 7. Probabilidades dado que ya fue escogida la casilla 5 y la casilla 1.

 

Una vez más, con las casillas ya escogidas, nos encontramos con nuevas probabilidades para elegir una casilla más, la cual definirá las posibles tiradas siguientes, cada jugador buscara la victoria dependiendo de las posibilidades que se generan en cada turno.

Cada turno las probabilidades van variando dependiendo de quien empezó y que casilla se eligió. Cada una de estas decisiones puede verse en el desarrollo del diagrama de árbol, presentado en la tabla 1, más todos los casos posibles de la Tabla 2.

Desarrollemos la casilla 9:

En el primer turno esta casilla tiene 3/24 probabilidades de ganar, siendo que se eligió la casilla 5 en el primer turno nos quedaría una probabilidad condicional dado que fue elegido el 5, desarrollando la fórmula 1 obtenemos 3/24*2/12, y una vez elegida la casilla 1 obtenemos 3/24*2/12*2/6 probabilidad ganadora, que a pesar de ser muy pequeña es mayor a cualquier otra. Como valor final de la casilla 9 dejaremos el valor probabilístico de la suma de todas sus probabilidades, es decir, la probabilidad independiente y las dos condicionales, quedando:

 

 

Continuando con cada caso, resultara un vector probabilístico para un juego general, en el que no se pueden escoger casos, que se muestra en resultados.

III. Resultados

Una vez realizados todos los casos, todos los tiros hasta que alguien gané escogiendo siempre la casilla con mayor probabilidad, nos encontramos con el siguiente vector de probabilidad condicional.

Vector de decisión basado en la probabilidad condicional sin permutaciones y tomando la ruta más probable para ganar:

 

Tabla 8. Vector de decisión, VD.

 

Dicho vector está basado en que en cada turno cada jugador siempre eligió la mayor probabilidad para ganar y tiro en la primer casilla con mayor valor, dándonos un vector de decisión que la maquina utilizará para poder jugar, sin embargo la maquina nunca busca ganar o empatar, solo elige la casilla con mayor probabilidad debido a que de esta forma es más posible ganar.

 

Tabla 9. Forma de ver las casillas del gato con los valores probabilísticos del VD.

 

Del vector de decisión basado en probabilidad condicional sin tomar en cuenta las permutaciones se elegirá cada turno el valor más alto y del cual se obtendrá la posición para después el sistema de juego de gato pasivo pueda tirar en la casilla teniendo en cuenta que no debe poner donde exista ya una ficha previa.

 

IV. Conclusiones

Esta secuencia de tiros en la posición simula a una persona que apenas está empezando a jugar gato, debido a que está sujeto a una secuencia definida, una vez se encuentra el patrón con que juega la maquina es bastante sencillo ganarle, sin embargo si se le subestima se puede llevar una sorpresa.

El ganar solo es algo empírico para la máquina que sigue el vector de probabilidad.

Teniendo en cuenta que la decisión pasiva del programa es tomar siempre el primer máximo valor que encuentre y que se encuentre disponible podemos decir que su orden de decisión es el siguiente:

 

Tabla 10. Forma de ver las casillas del gato con los valores probabilísticos del VD.

 

Una vez jugado contra la maquina es posible encontrar un patrón y ganarle de forma sencilla. La máquina, al no buscar ni guardar patrones, le es imposible aprender a jugar de una mejor manera.

Si la maquina pudiera guardar patrones y escoger un vector de decisión para cada tirada le sería posible aprender, como lo hacemos nosotros los humanos, a ganar o empatar.

 

Referencias

  1. Carla Martín Montero.(2010) Colección de juegos infantiles: los tres en raya. Museo del juego: museo del juego.

  2. Walpole, Myers,Myers,Ye. (2007) Probabilidad y Estadística para ingeniería y ciencia. México: Pearson Prentice Hall.

  3. Stuart Russell, Peter Norving. (1996) Inteligencia Artificial, un enfoque moderno.México: Prentice Hall Hispanoamericano S.A.