Desafio : Tres en Raya

DeeR · #1 (**permalink**) 06/07/2007, 17:45

Que tal a todos foreros de PHP , Luego del buen recibimiento que tubo el Primero Desafio de PHP de nuestro Foro ( Desafio del Laberinto ) el cual nos sirvio para poner en practica nuestro ingenio , compartir conocimiento y analizar otras soluciones.
Tengo en mente de inicializar el Segundo Desafio de PHP, les cuento :

Desafio : Tres en Raya ( o Gato )
Consiste en Implementar un Script Optimo en PHP que permite Jugar Tres en Raya atravez de PHP. Lo ideal del Script es que permita.

1. - Player vs CPU ( PHP )
Clasico, donde jugamos encontra la Maquina.

2* - Player vs Player
Podamos Dos Usuarios puedan Jugar Simultaneamente

3* - CPU PHP vs CPU PHP
Donde podamos permitir que dos Scripts en PHP puedan jugar Tres en Raya y ver que algoritmo resulta Ganador.

El Punto Principal es el Numero 1 , lo importante es que el Script en PHP juege de forma inteligente y sea capaz de derrotar el Player. Utilizando alguna de las tantas tecnicas de Programacion.

La Segunda Opcion , por el momento es opcional, pero el Programador que quiera Implementarla , puede hacerlo , lo ideal es que dos jugadores puedan Jugar Tres en Raya atravez del Script. ( Podras Utilizar Base de Datos, Fichero de Texto, Cookies, Variables de Session , etc ..)

La Tercera Opcion , la tenemos que pensar entre todos , ya que debemos ofrecer e implementar una especia de API alojado en un Servidor , el cual permita ofrecer una batalla de tres en raya de dos Scripts en PHP, esto seria fenomenal para medir rendimiento y cual de los Scripts es mas inteligente (por supuesto en una serie de match ).

Asi que mis Amigos, animemonos a Participar en este Desafio y ver que resulta. Y Propongamos ideas para que podamos implementar el Tercer Punto para Medir Nuestras Soluciones.

Entonces, me imagino que todos conocen el Juego Tres en Raya o mas conocido como Gato en Chile ( http://es.wikipedia.org/wiki/Tres_en_raya )

El Tablero debe ser un Array 3x3

Código:

$tablero = array (


0 => array(

	0 => 0,
	1 => 0,
	2 => 0,
	),
	
1 => array(

	0 => 0,
	1 => 0,
	2 => 0,
	),
	
2 => array(

	0 => 0,
	1 => 0,
	2 => 0,
	)		
	


);

Saludos.

#2 (**permalink**) 06/07/2007, 18:11

Me parece un buen desafio

, ahora aclaremos algunos puntos:

Uso de javascript, AJAX, imagenes, etc...
Plazos
Calificacion
mmm... que es api?

Esperemos que esta idea prospere... Yo me apunto!

Un saludo,

DeeR · #3 (**permalink**) 06/07/2007, 20:10

Sobre
Player vs CPU
Basta con PHP , ya que al hacer click sobre una imagen que represente un espacio disponible, este es un enlace, e internamente el script tendra que responder con la peticion del script. Lo ideal es que tenga una bonita presentacion, yo creo que en este punto el Uso de Javscript o Ajax quedaria Fuera, pienso yo.

Sobre el segundo Punto , Players vs Player , es optativo, y este se podria implementar con AJAX para saber si el otro usuario ha respondido en el juego, o tambien se podria simular con un refresh cada 10 segundos para ver si se ha respondido digo yo algo asi.

Respecto al Tercer Punto, sobre CPU vs CPU para comparar script. Un API es como un conjunto de utilidades, mas que nada es hacer un Script regulador, es decir, que este comienze un Juego y le pida una jugada a tal script, este responde y el script Principal guarda su jugada y se la comunica al otro script en otro servidor, y asi sucesivamente.

Cuando llege de la noxe voy a ver eso mas a fondo :)

Saludos

derkenuke · #4 (**permalink**) 06/07/2007, 20:53

No lo veo dificil, hice uno en javascript. Mi opción sería esta:

Varios casos posibles que había que detectar al momento del turno de la CPU, y luego manejar bien para el correcto funcionamiento de la IA:

No hay posible victoria en esta tirada -> No hay posible victoria de mi oponente -> tirada aleatoria
No hay posible victoria en esta tirada -> Sí hay posible victoria de mi oponente -> impedir la victoria del oponente
Sí hay posible victoria en esta tirada -> Conseguir la victoria mediante esta tirada.

La verdad es que era eficiente, aunque tenía los típicos truquillos que se le podía ganar haciendo siempre lo mismo, quizás habría que corregirlos, pero bueno, era bastante básico.

PD: El laberinto me parece mucho más complicado...

Un saludo.

#5 (**permalink**) 06/07/2007, 20:56

Cita:

Iniciado por DeeR

Sobre
Player vs CPU
Basta con PHP , ya que al hacer click sobre una imagen que represente un espacio disponible, este es un enlace, e internamente el script tendra que responder con la peticion del script. Lo ideal es que tenga una bonita presentacion, yo creo que en este punto el Uso de Javscript o Ajax quedaria Fuera, pienso yo.

Si juegas con la PC, AJAX puede hacer que tus jugadas se procesen sin tener que estar recargandola pagina... Solo tendria esa funcion que ayudaria a al presentacion, no crees?... Bueno en fin, ya tengo la version 0.1 del script, aunque aun no hay plazos

... Pero hasta ahorita no me gana ni una XD

Un saludo,

Krunoslav · #6 (**permalink**) 06/07/2007, 22:43

Qué interesante!
Voy a participar, aunque no sepa mucho, pero me imagino que de esta forma se aprende.
Hay varias cosas que debo estar programando poco eficientemente

DeeR · #7 (**permalink**) 07/07/2007, 02:51

Cita:

PD: El laberinto me parece mucho más complicado...

Sips el Laberinto nos motivo mucho, y respecto a ese Desafio me gusto mucho los que pudieron implementar el Camino mas Corto al Queso en todo el Laberinto.

Cita:

Iniciado por okram

Si juegas con la PC, AJAX puede hacer que tus jugadas se procesen sin tener que estar recargandola pagina... Solo tendria esa funcion que ayudaria a al presentacion, no crees?... Bueno en fin, ya tengo la version 0.1 del script, aunque aun no hay plazos

... Pero hasta ahorita no me gana ni una XD

Un saludo,

lo interesante es aplicarle inteligencia al Script, que sea capaz de determinar que de todas las posibles jugadas, cual de todas tiene una mejor probabilidad de ganar, por eso lado me ire, talvez tenga que analizar muchos casos la CPU pero con el objetivo de responder una buena jugada.

Lo que tengo en Mente, es el Tercer Punto, es decir, poder hacer competir distintos Scripts, asi como los Concurso de Ajedrez donde Participan los distintos SuperComputadores, algo similar. (De todas formas a Futuro podemos inicializar un Desafio con Ajedrez, pero por eso primero quise que avancemos de poco y algo mas simple con tres en ralla).

Lo que tengo en Mente, para poder Lograr el Tercer Punto es lo siguiente.

1.- Que el Script reconosca un Identificador de Juego Momentario que Dure mientras dura la Partida y con un maximo de 5 min por decir. que esto lo reciba por GET
2.- Un Identificador donde le dice Que Objeto le Pertenece ( la X o la O )
3.- En una Variable obtenga el Tablero con las Posiciones del Juego(esta fue serielizada), y el Script analize el juego y responda su jugada.

Entonces va a existir un Script Maestro, el cual inicializa un Juego y Le da un Turno a un Tal Script en un Tal server, este le responde su jugada, y luego le manda el tablero al otro script, este le responde la jugada, asi sucesivamente hasta lograr un campeon :P

Lo veo bastante interesante el que los Scripts compitan uno contra uno :) :) , aunque por el momento lo primordial es el Primer Punto.

Saludos

PD: Hay bastante material bueno en Teoria de Juegos, Algoritmos Heutristicos, etc ..

jerkan · #8 (**permalink**) 07/07/2007, 04:36

Si no recuerdo mal, había una película llamada 'Juegos de Guerra' en la que, en la parte final, se ve un ordenador que juega contra sí mismo al tres en raya. El caso es que no podía ganar nunca. Y es que, si los dos participantes juegan bien ( y no es muy difícil hacerlo) no se puede ganar.
Un humano cometerá errores que le llevarán a perder la partida pero un ordenador nunca perderá con un buen algoritmo heurístico.

Un saludo

EDITADO: Aquí un enlace por si lo queréis ver.

nicolaspar · #9 (**permalink**) 07/07/2007, 08:18

Como me gustan estas cosas!. Actualmente estoy bastante cortado de tiempos, no prometo participar, pero lo intentare!.

Por otro lado, si queremos usar ajax no me parece mal si se define de entrada, el tema sería si se permite tambien algun framewrok para dicha tarea.

En fin, sigan definiendo que se pone bueno!!!

PD, que tres en rayas ni tres en rayas, como se les ocurre llamarlo Gato!!!, es un ta-te-ti :) :P

PostIt???

#10 (**permalink**) 07/07/2007, 10:09

Cita:

Iniciado por derkenuke

[...]

No hay posible victoria en esta tirada -> No hay posible victoria de mi oponente -> tirada aleatoria

[...]

La inteligencia del script se basa principalmente en este punto, mas especificamente en que este punto no sea tan aleatorio

Un saludo,

#11 (**permalink**) 07/07/2007, 10:13

Para competir scripts contra scripts se me ocurre esto:

los dos scripts en PCs remotas... Ambos tienen la opcion de inicializar el juego, y luego llama al otro script pasando el campo marcado por la url (algo como http://sitio.com/tresenraya.php?s=1,1). Luego, el segundo script analiza y llama al otro script de la misma forma...

Cada script interpretara, guardara los tableros con las jugadas, etc...

Es solo una idea, pero primero lo primero!

Un saludo,

#12 (**permalink**) 07/07/2007, 10:15

¡¡Quiero quiero!!
Coincido con nicolaspar, eso no es un gato, es un TA-TE-TI... (gatos son algunas de las chicas que aparecen en la tele

)

En fin, hace tiempo quería programar este juego, incluso me puse a analizar posibles jugadas, como por ejemplo, partiendo de x posición, qué jugadas hay que hacer (y no debe hacer el rival) para que la victoria esté asegurada. Les aseguro que son más que las que parecen ;)

DeeR, en el mensaje original, en el punto 2, creo que te quedó un poquito mal redactado

Si solo vamos a usar PHP, definitivamente la única opción para el punto 2 es alguna recarga automática cada x segundos. AJAX sería basicamente lo mismo, ya que también tendría que hacer peticiones cada x tiempo. Igual se podría usar un iframe que sea el que realmente recarga cada x tiempo y si se hizo la jugada que mande recargar el tablero también.

Con respecto al punto 3, creo que bastaría con que ambos programas lleven un registro del juego y con variables GET sería suficiente.
Por ejemplo: fila=1&columna=2&jugada=2 (el número de jugada sirve para que los programas se sincronicen).
Luego, ambos tienen que comprobar si alguien ganó, así que podríamos poner una variable más tipo "gane=1" para que un script indique al otro que le ganó, o que se declara vencido

Creo que eso sería suficiente.

Ahora hay que definir los plazos...

caricatos · #13 (**permalink**) 07/07/2007, 11:04

Hola:

Me gusta la idea del "Ta-Te-Ti"... aunque estamos pendiente de una competencia en javascript, intentaré meterme con esto.

Saludos

DeeR · #14 (**permalink**) 07/07/2007, 12:17

Concuerdo que en el Primer Punto, el que quiere utilizar JavaScript/AJAX para implementar la presentacion mas que nada, pero en ningun caso esto este involucrado en el Algoritmo del Juego. se entiende.

Respecto al Segundo Punto, aqui si podemos usar Javascript/AJAX aunque este punto es Opcional para el Desafio , aunque seria bonito implementarlo , y poder jugar tres en raya contra otra persona con solo PHP HTML Javascript.

El Tercer Punto, sobre la Competencia del Script. Lo mejor es que un Script Principal actue como Controlador del Match y este Informa a cada Script el estado del Tablero y pregunta la Movida de cada Script, las anota y determinar si ha ganado o perdido un Script, luego graba los Resultados.

Sobre el Tercer Punto Todos debemos llegar a un acuerdo como son los datos de entrada y salida para este tercer punto. Yo pienso lo siguiente.
* Todas las Variables se va a pasar via GET

Variable op
Esta indica que opcion del juego vamos a jugar, es decir, una partida CPU vs CPU, en este caso siempre tendra el valor 3 , y el script debe ser capaz de reconocer que se trata de un juego CPU vs CPU.

Variable ob
En esta Variable le mandamos al Script el objeto que utiliza, es decir la X o O

Variable tablero
Se le manda al Script el Tablero del Juego serializado , el script debe ser capaz de unserializarlo y reconocer que jugadas ha echo en este.

Luego el Script debe entregar serializado el Tablero en simple texto, para el que el Script Maestro Analize dicho tablero, vea si solo se efecto un cambio, y realize la peticion al otro script.

Me imagino que con estos puntos, podemos lograr que los Scripts se puedan comunicar para establer duelos , usando un Script Maestro que va a ser como el Albitro en el Juego.

¿¿ Que les parece ??

Lo otro, no hay limite de Soluciones por Jugador, por si alguien quiere en un Script utilizar tal tecnica, y otra solucion utilizar otra. etc ...

Respecto a las Fechas Maxima, me imagino que dentro de 3 semanas mas (o un poco mas) para que podamos implementar bien esto.

Sobre como evaluar, creo que yo que la primera parte ( Player vs CPU ) igual como en el desafio anterior, los usuarios del foro, pongan una nota de acuerdo, como ellos piensen que el CPU Jugo de manera inteligente el Juego del Gato.

Y Respecto al Tercer Punto, el Script Maestro determinara en una Serie de Match (veremos como lo hacemos este torneo ) determinara quien es el Ganador :) , me imagino un todos contra todos. Propongamos ideas sobre el torneo.

Saludos

#15 (**permalink**) 07/07/2007, 18:09

De acuerdo Deer... tengo algunas dudas... Entiendo que en una partida CPU vs CPU habra tres scripts, dos participantes y un moderador... NO hay problema con lo de recibir la jugada del oponente por medio de las variables ($_GET) op, ob y tablero, pero como se envia el tablero al script moderador? y quien diseñara/programara ese script?...

Yo estaba pensando mas en solo los dos scripts comeptidores, algo asi:

Al inicio a ambos scripts se le da la url completa del otro script (el oponente) (terminada en .php), y se establece cual de los dos iniciara el juego... Así, el primer script (Script A) hace su jugada, y llama (mediante AJAX o con solo PHP) al otro script (Script B), enviandole todas las variables ya mencionadas. Luego B, al ser ejecutado, procesa los datos recibidos y envia a A una respuesta de la misma manera, y etc. etc.,,, osea sin la participacion de un tercer script moderador... Cada script se encargará de procesar y validar el tablero recibido, y en caso de error tambien habra que setear una 4ta variable (algo como fail) que sera enviada como respuesta junto con el tablero previo para que el script que se equivoco corrija su jugada...

Bueno, es solo una idea, aunque ya me estoy complicando muxo creo,...

Pero primero es lo primero, a programar el script! (el mio ya comenzo a mostrar sus primeras grande debilidades)

Un saludo,

Krunoslav · #16 (**permalink**) 07/07/2007, 18:26

Acá va mi "Gato"
http://www.udec.cl/~bkarelovic/gato/gato.php

Por ahora sólo piensa para el turno siguiente. Espero en unos días más hacerlo pensar por dos turnos más.
Viendo todas las jugadas posibles y analizando cada una de las respuesta a ver si deja al otro en "calzoncillo" (tener que defender dos posiciones) o si él queda en esa posición.

DeeR · #17 (**permalink**) 07/07/2007, 21:59

Cita:

Iniciado por okram

De acuerdo Deer... tengo algunas dudas... Entiendo que en una partida CPU vs CPU habra tres scripts, dos participantes y un moderador... NO hay problema con lo de recibir la jugada del oponente por medio de las variables ($_GET) op, ob y tablero, pero como se envia el tablero al script moderador? y quien diseñara/programara ese script?...

Yo estaba pensando mas en solo los dos scripts comeptidores, algo asi:

Al inicio a ambos scripts se le da la url completa del otro script (el oponente) (terminada en .php), y se establece cual de los dos iniciara el juego... Así, el primer script (Script A) hace su jugada, y llama (mediante AJAX o con solo PHP) al otro script (Script B), enviandole todas las variables ya mencionadas. Luego B, al ser ejecutado, procesa los datos recibidos y envia a A una respuesta de la misma manera, y etc. etc.,,, osea sin la participacion de un tercer script moderador... Cada script se encargará de procesar y validar el tablero recibido, y en caso de error tambien habra que setear una 4ta variable (algo como fail) que sera enviada como respuesta junto con el tablero previo para que el script que se equivoco corrija su jugada...

Bueno, es solo una idea, aunque ya me estoy complicando muxo creo,...

Pero primero es lo primero, a programar el script! (el mio ya comenzo a mostrar sus primeras grande debilidades)

Un saludo,

Sobre como enviar el Tablero, es decir la Respuesta del Script , que solamente imprima el tablero serializado ( utilizando la funcion http://es.php.net/serialize ) asi el script maestro recibe el tablero y se lo puede enviar al otro script.

Esque de esta manera, de inmediato podemos realizar los Torneos , y es mas transparente para los Competidores pienso yo.

Respecto a este Script ya lo tengo en mente como planificarlo y estructurarlo , pero todavia este punto es lejano. lo importante es que nuestro script respondan bastante bien.

Saludos

#18 (**permalink**) 07/07/2007, 22:23

Ya es muy tarde...

Ya tengo lista una version primaria del script (v0.3), aun no es muy inteligente pero ya es un poco mas complicado ganarle. Tiene aun algunas debilidades... Aqui esta:

http://www.okram.com.ar/fdw/threeinarow.class.php

Un saludo,

Krunoslav · #19 (**permalink**) 07/07/2007, 22:41

Juega muy bien, okram. Aún no logro encontrarle debilidades.

Sobre la compteción entre distintos programas, el juego al ser simple, tiene una estrategia no-perdedora fácil, al menos para un humano. Y ya habiéndosela entregado al programa todos los programas debieran empatar.

Aunque de todas formas lo interesante es hacer competir distintos algoritmos.

#20 (**permalink**) 09/07/2007, 05:25

BIen, corregi algunas debilidades encontradas, y aqui esta mi v0.4 [EDITO: VERSION 1.0]... Es fuerte cuando la maquina empieza, pero muestra una gran debilidad en caso de que el humano empieze [EDITO: Parece que ya es fuerte tambien cuando es el humano el que empieza]... Bueno, aqui esta:

http://www.okram.com.ar/fdw/threeinarow.class.php

Un saludo,

EDITO: Estuve trabajando un rato mas y tengo la version estable v1.0. Hice algunas pruebas y no le pude ganar

DeeR · #21 (**permalink**) 09/07/2007, 08:51

uy okram tu gato ta muy felino haha
ta weno , ayer le habia ganado en la noxe (la ver 0.3 ) , pero hoy la 1.0 no pierde nunca al parecer :P

Comenze con mi Script, primero me dedique a la parte visual , a que el sistema funcione y detecte cuando alguien gane o empate , y la posibilidad que parte el usuario o el cpu. mientras el CPU juega demanera aleatoria. (Esta solo funcionando el Opcion 1 es de decir Player vs CPU ).

Hoy en la Tarde cuando tenga tiempo, le voy a empezar a dar inteligencia a mi Clase CPU :P para que no juege aleatoriamente

http://deerme.org/gato/

naujgf · #22 (**permalink**) 09/07/2007, 09:10

Cita:

Iniciado por Krunoslav

Acá va mi "Gato"
http://www.udec.cl/~bkarelovic/gato/gato.php

Por ahora sólo piensa para el turno siguiente. Espero en unos días más hacerlo pensar por dos turnos más.
Viendo todas las jugadas posibles y analizando cada una de las respuesta a ver si deja al otro en "calzoncillo" (tener que defender dos posiciones) o si él queda en esa posición.

hola krunoslav... tu script tiene un error que logre percatar... si el juego lo comienza el humano y presionas la esquina superior derecha, luego la casilla del medio y luego la esquina superior izquierda, a pesar de que tu script quiera tamar mis jugadas es posible ganar presionando en el boton superior central, pero si presiono el script dice q gana la maquina... cosa q es errada xq el humano es el que ejecuta primero el movimiento... sería bueno que modificaras eso!...

DeeR · #23 (**permalink**) 09/07/2007, 11:46

Cita:

Iniciado por okram

BIen, corregi algunas debilidades encontradas, y aqui esta mi v0.4 [EDITO: VERSION 1.0]... Es fuerte cuando la maquina empieza, pero muestra una gran debilidad en caso de que el humano empieze [EDITO: Parece que ya es fuerte tambien cuando es el humano el que empieza]... Bueno, aqui esta:

http://www.okram.com.ar/fdw/threeinarow.class.php

Un saludo,

EDITO: Estuve trabajando un rato mas y tengo la version estable v1.0. Hice algunas pruebas y no le pude ganar

jejeje le gane a tu Maquina en la version 1.0

me costo pero la gen

Mientras la mia, poco a poco va aprendiendo ... aunque todavia se le gana muy facil hahaha

elquique · #24 (**permalink**) 09/07/2007, 12:37

No me queda claro luego de leer todos los post, si se puede usar Javascript y/o AJAX.

Igualmente al ser un desafío PHP seria mejor si solo se usa PHP, incluso para igualar a los que solo usan PHP y no saben javascript o AJAX, además de que creo seria un reto interesante si se hace en PHP puro :)

DeeR · #25 (**permalink**) 09/07/2007, 13:01

Cita:

Iniciado por elquique

No me queda claro luego de leer todos los post, si se puede usar Javascript y/o AJAX.

Igualmente al ser un desafío PHP seria mejor si solo se usa PHP, incluso para igualar a los que solo usan PHP y no saben javascript o AJAX, además de que creo seria un reto interesante si se hace en PHP puro :)

Sipos hay q utilizar solamente PHP, es posible utilizar Javascript/Ajax para la Presentacion, ejemplo yo utilizo una alerta javascript para dar el resultado final de un juego. te explico mejor los puntos que se van a evaluar

Para el Punto 1 (Player vs CPU)
- Los Scripts deben utilizar en el Algoritmo del Juego y su analisis, Solamente PHP.
- Pueden Utilizar Javascript/AJAX Para la Presentacion del Juego
(Ejemplo mi Script y el de Okram simplemente usamos Javascript para lanzar una Ventanita con el Resultado, esto es simplemente presentacion ).

Para el Punto 3 (CPU vs CPU )
- Los Scripts deben utilizar en el Algoritmo del Juego y su analisis, Solamente PHP.
- Aqui no existe presentacion, solamente el Script debe imprimir en pantalla el array tablero serializado, es decir debe haber un echo serialize($tablero), nada mas que eso, para que el Script Maestro pueda entendar tu Jugada dentro del Tablero.

Para el Punto 2(Player vs Player)
Este punto es Opcional (No va a interferir en la competencia), si alguien lo quiere implementar para poder Jugar Tres en Raya con un Amigo, lo puede hacer, aqui puede utilizar PHP , Base de Datos, Javascript , Ajax , etc .. libremente.

Saludos

elquique · #26 (**permalink**) 09/07/2007, 14:51

A ok, pense que era un juego de Php.

#27 (**permalink**) 09/07/2007, 15:46

Cita:

Iniciado por DeeR

jejeje le gane a tu Maquina en la version 1.0[...]

Anduve viendo el codigo, y le di al error... Imagino que tu jugada fue algo como:

En el 4to cuadro estaba el error, pero ya esta corregido... Gracias por comentar... El script va en su v1.1

Un saludo,

Krunoslav · #28 (**permalink**) 09/07/2007, 21:26

Es realmente invencible.
La única forma fue con trampa. Aunque «legítimo» programilmente, modificando la dirección. jeje

naujgf, Gracias, aunque no logro ver el error aún, me dice que gano yo, no la máquina.

naujgf · #29 (**permalink**) 10/07/2007, 07:41

Cita:

Iniciado por Krunoslav

naujgf, Gracias, aunque no logro ver el error aún, me dice que gano yo, no la máquina.

Mira la manera en que me funciona tu Script...

Fijate cada paso y el resultado final... por eso digo que es un error...

DeeR · #30 (**permalink**) 10/07/2007, 10:42

Ya mi Gato va en la Version 0.3

Ya esta pensando mucho mejor, es por mientras defensivo, pero pronto programare su ataque uyy, se defiende bien cuando el usuario parte, cuando parte la maquina, aveces cae en las clasicas trampas del usuario haha pero eso lo vere mas tarde

http://deerme.org/gato/