Juego 4 en Linea o Conecta 4

[gandalf85]

Hola a todos he desarrollado el juego del “4 en Linea” o “Conecta 4” en Delphi, y funciona bien con 2 jugadores humanos.
Ahora me he puesto el reto de ponerle Inteligencia para que también se pueda jugar contra el ordenador.

He estado buscando información y he leído que hay que usar el Algoritmo MíniMax pero no tengo ni idea de cómo implementarlo

Se que hay que generar un árbol de búsqueda para ir buscando distintas combinaciones, dependiendo de los estados del tablero. (funcion min y funcion max) pero ni idea de por donde empezar.
También he leído que hay que valorar las casillas del tablero dependiendo de las fichas que estén colocadas alrededor, es decir una casilla en la que sea posible todavía hacer 4 en raya tiene que valer mas que una en la que ya no se pueda

Si alguien a programado alguna vez el algoritmo MíniMax y me puede echar un cable se lo agradezco, sino cualquier sugerencia será bien recibida.


Saludos

[Ñuño Martínez]

Te recomendaría dos libros del maestro Tim Hartnel, muy fáciles de leer y seguir, pero difíciles de encontrar: "El Libro Gigante de los Juegos de Ordenador" e "Inteligencia Artificial - Ejemplos y programas", ambos de Anaya Multimedia. Con suerte quizá encuentres alguna versión PDF en la lengua de Shakespeare. En castellano lo dudo, dada la agresiva política de la editora.

De todas formas, prueba primero a hacerlo "a lo bruto". Es decir, intenta "traducir" tu línea de pensamiento en un diagrama de flujo e intenta implementarlo. Yo lo hice con un juego de Reversi/Othello, y aunque no es difícil de batir, tampoco juega mal del todo, además me siento orgulloso de haberlo hecho solito. :) Puedes bajarte las fuentes de este programa desde esta página (http://www.burdjia.com/proyecto/?id=reversi).

[gandalf85]

Gracias por responder Ñuño

Va a estar difícil encontrar esos libros ya que no están en la biblioteca de mi ciudad pero “El libro gigante de los juegos para ordenador” tiene buena pinta haber si lo encuentro en alguna librería y le puedo echar un vistazo mas detalladamente.

Nunca he sabido jugar al Reversi; Ponía Fichas y luego la maquina siempre convertía mis fichas pero yo las suyas no. supongo que es cuestión de leer las instrucciones…

A lo bruto ya lo había intentado:
-->Primero lo hice que moviera Aleatoriamente a una columna (Obviamente no tiene Inteligencia)
-->Luego hice que antes de mover comprobara si hay ya 3 del usuario y si encuentra 3 le tapa la 4 posición, sino las encuentra mueve Aleatoriamente (Sigue sin tener Inteligencia pero no es tan tonto)

La Idea es Ponerle Inteligencia para que El Ordenador también vaya a ganar…
Para ello lo mejor es utilizar la estrategia MiniMax porque te adelantas a las posibles jugadas eligiendo la combinación óptima… Aunque también se que esto le puede llevar mucho tiempo y que habría que mezclarlo con el Algoritmo de Poda. Pero de momento lo que me interesa saber es como hacer el árbol de estados.

Seguiré buscando información sobre el Algoritmo haber si me aclaro, porque encuentro mucha paginas que hablan sobre el pero en todas pone lo mismo;
es un árbol de exploración donde a partir de un estado inicial del tablero, se busca aquellos valores mínimos que maximicen la posibilidad de ganar para ello hay que considerar que tras la realización de una jugada MAX, viene una jugada MIN y tras la misma viene otra MAX y así sucesivamente hasta llegar al objetivo

Pero no se como valorar el tablero para buscar dichos valores. En otros juegos como el Ajedrez valoran las casillas según la ficha que hay en el tablero por ejemplo donde hay un peón (vale 1), caballo (2), Alfil (3)… Así saben donde están las piezas con mayor valor…

Si alguien sabe donde puede encontrar el algoritmo explicado paso a paso que lo diga; ya que informacion interesante si que he encontrado por google pero no una explicacion detallada.

[cocute]

Aqui tienes el codigo de un Conecta4 ya hecho con Inteligencia artificial, y muy chulo hasta con grágficos 3D
http://members.fortunecity.com/schutzenberger/download/ConnectFour3DSrc.zip
(ademas compila sin problemas en cualquier delphi sin componentes de terceros)

aqui tienes un PDF con la explicacion del funcionamiento del conecta4, en ingles, pero......
http://www.farfarfar.com/games/connect_four/connect4.pdf


puedes mirar el codigo
pero vamos si es para algun trabajo mejor que lo intentes por tus medios aunque no quede tan sofisticado,
nadie se va a creer que ese juego lo has hecho tu.

aqui hablan de lo mismo y dan ideas de como hacerlo:
http://foro.hardlimit.com/programacion/t-juego-conecta-4-11456.html

aqui tienes un ejemplo en delphi pero solo la base como ya tienes, pero quizas te de alguna idea nueva para la interface
source
http://delphi.about.com/library/code/fdac_connect4_src.zip
ejecutable
http://delphi.about.com/library/code/fdac_connect4_exe.zip

[Delphius]

Hola gandalf85,

Al parecer, creo que estás confundiendo y mezclando lo que es el algoritmo MiniMax o Min-Max con la heurística.

El algoritmo Min-Max sólo se limita a obtener los mínimos y los máximos, tal como lo has descrito, explorando sus ramas y alternando Mínimos y Maximos. La heurística es cosa aparte. La heurística es quien te dá el valor, que luego el algoritmo Min-Max captura y los evalúa.

No es que el algoritmo Min-Max debe ajustarse al juego, mas bien es que debe definirse una heurística apropiada al juego.
El algoritmo es fijo, no cambia. Y si, es como dicen: se explora el árbol buscando máximos y/o mínimos. La poda alfa-beta ayuda a evitar recorrer ramas innecesarias.

No está demás limitar la profundidad. Prueba con 5 ramas, cuanto mucho, para empezar.

A ese juego la verdad es que nunca lo he entendido, por lo que no te sabría decir como podrías definir la heurística. Quizá puedas hacer una especie de ponderación entre la cantidad de piezas y espacios libres disponibles. Prueba con diferentes heurísticas y a ver que sale.

Las heurísticas del Ajedrez no son tan simples como piensas. No es una simple cuestión de la posición o valoración de las piezas. Son más de 40 o 50 variables (ya no recuerdo bien). Es más, ¡algunos diseñan sus algoritmos para ser capaces de cambiar de heurística sobre la marcha!

Saludos,

[gandalf85]

Gracias cocute y Delphius por ayudar

cocute he estado mirando los enlaces que has puesto y te comento:
- El pdf ese ya lo tenia y estaba en proceso de traducirlo haber si me daba alguna idea. De todas formas se agradece.
- Con respecto al último como bien dices eso ya lo tengo ya que es la base para dos jugadores humanos. El mío no es tan sofisticado ya que no se ven caer las fichas; Sino que encima de cada columna tengo un botón que al darle se pinta la casilla donde debería caer la ficha (digo se pinta porque yo lo desarrolle utilizando el componente shape y poniéndole estilo redondo en vez de utilizar imágenes)
- Ahora compilare el primero haber si lo entiendo…
pero vamos si es para algun trabajo mejor que lo intentes por tus medios aunque no quede tan sofisticado, nadie se va a creer que ese juego lo has hecho tu. No, no es para ningún trabajo, sino que estoy estudiando Pascal y fue una sugerencia que nos hizo el profesor para que hiciéramos en Navidad… lo único que ahora me dijo que lo ideal seria que también pudiera jugar el ordenador contra el usuario. Por eso es por lo que quiero ponerle inteligencia.

Delphius seguramente este confundido y este mezclando Algoritmos y heurística ya que nunca he visto ninguna materia de Algoritmos para Juegos sino que lo que se, es por información que he buscado por Internet.

Como en todos los sitios donde explican el algoritmo MINIMAX lo hacen con el 3 en Raya esta tarde lo he implementado en delphi y lo tengo terminado para dos jugadores pero tampoco he sabido configurarlo para que juegue el ordenador…
Por ejemplo: en este PDF en la pagina 9 veo que cuando ganan los círculos el estado terminal es (-1), si hay empate (0) y si ganan las X (+1) pero en la pagina 18 de donde se saca los números para hacer las operaciones (supongo que será lo que dice Delphius de la heurística)

*Ni aun siendo el tablero mas pequeño he logrado entender lo que hay que hacer para aplicar el algoritmo

Gracias de Nuevo a los dos, seguiré intentándolo.

Pd.: Un poco mas y escribo un libro xD.

Saludos

[gandalf85]

Olvide poner la direccion del PDF:
ii.uam.es/~fdiez/docencia/material/juegos.pdf

Nota: ponerlo a continuacion de las www ya que todabia no me deja poner enlaces ni imagenes

[cocute]

- Ahora compilare el primero haber si lo entiendo…


creo que no debe de ser nada facil de entender, aun para expertos,
ya que usa lenguaje ASM en algunas partes y el codigo es bastante largo y confuso.

[Delphius]

Hola de nuevo,
Yo tengo una pregunta (bueno... en realidad son varias, pero el punto al que voy es uno sólo): ¿Si no es para un trabajo, para que es? ¿Si no es para un trabajo para qué te estás complicando la vida?
¿Estás cursando, o cursaste alguna cátedra como Sistemas Expertos y/o Inteligencia Artificial? ¿Es de esta cátedra el dichoso profesor?

Si no viste el tema, y no es para presentar, yo creo que te estás complicando las cosas al vicio. Mi consejo, en este caso, es que te olvides de min-max, poda alfa-beta, heurísticas y demas conceptos que se ven en dicha cátedra.
Mantenlo simple y no te compliques buscando que sea perfecto. Si puedes simplificar el modelo y simular en cierto grado la inteligencia es mejor que estar rompiendose la cabeza con algo que no se vió (y por tanto no se comprende) todavía.

Exactamente a eso me refiero con las heurística. Vendría a ser una especie de fórmula que da un "puntaje" a una jugada. Luego Min-Max toma estos puntajes y va buscando los máximo y mínimos de éstos.
Muchos libros exponen el tema siguiendo el ejemplo del tateti (o Tic-Tac-Toe, o "Tres en Raya" como se lo denominan en otros lados). Una de las posibles heurística (pueden aplicarse e inventarse muchas) busca el sombolizar como bien describes un escenario simple de (1, 0 y -1). Otra opción es la de regresar los movimientos libres que quedan... se puede combinar ambas, etc.

Por ello te digo que pruebes "inventando" y/o poniendo en práctica (si aún estás en la idea de seguir dandote contra la pared:D) varias heurísticas y comparar los resultados.

Repito nuevamente, a ese juego nunca no lo entendí. Por tanto no puedo serte de ayuda en este aspecto. Tu si sabes jugarlo por tanto sabes y puedes intuir posibles heurísticas. ¿Digo no;)?

Si no es el problema ese entonces... ¿cual es?:confused:

Saludos,