consejo sobre IA rival en juego "de tablero"

[kanc]

Buenas,

Estoy haciendo un juego para iOs con mecánica típica del columns, jewel, etc... pero en el que tienes que derrotar a un rival no humano. La idea es que cada combinación de piezas sea un golpe y se vaya reduciendo la vida del oponente. Mi duda es que no se si hacer un tablero (en memoria, en pantalla solo se verán los movimientos del jugador) para la CPU y simular los movimientos o directamente ir "pegando" al usuario de forma aleatoria. No seria del todo aleatorio, puesto que me gustaría que los rivales fueran aumentando de dificultad, amen que dada uno tendrá habilidades especiales que afectan al tablero del jugador y demás.

Que pensáis que puede ser mas interesante a la hora de jugar?? me decanto por la segunda opción porque me dará mas control a la hora de plantear el nivel de la partida, pero este es el primer juego que hago (de ahí que sea un simplón) y no se el tipo de practicas que suelen llevarse a cabo en estos casos.

Gracias!!

[Darago_malaga]

No te quedes con el chaval!!!

[blau]

jejeje... lo del mini-max con podas alfa-beta no es coña... ^_^' yo tengo el examen de IA en un mes y resulta que existe... ;)

otra cosa es implementarlo...

la idea es sencilla... es generar un árbol con todas las posibles jugadas, en la que empieza un jugador, y la siguiente jugada que implica bajar un nivel de profundidad en el árbol pertenece al otro jugador, y así sucesivamente hasta explorar un nivel de profundidad máximo que establezcas,

el quid de la cuestión está en valorar como de buena es la jugada... notese que lo que es muy bueno para uno es muy malo para el oponente... así que se van valorando los nodos... de forma que los de un jugador intentan maximizar la funcion (jugador MAX)... es decir... de todas las posibles jugadas del otro jugador (MIN)  tiene disponibles, escogerá la que devuelva un valor de la función más alto. (es la mejor jugada para él)... por el contrario el jugador MIN intentará minimizar el valor de su jugada... para ello de todas las posibles jugadas que puede realizar MAX elige la que devuelva un valor más pequeño... es decir, la peor jugada para MAX, pero a su vez la mejor para MIN.

Y respecto a la poda alfa-beta el concepto es relativamente simple..por lo menos haciendolo en boli -papel... aunque para mi no es tan fácil de explicar... pero lo voy a intentar...

Se basa en que si el jugador MAX está explorando jugadas de MIN... sabemos que MAX va a escoger la jugada con valor máximo... así que si explorando detectamos que una rama de MIN va a devolver un valor minimo que es menor que el valor más grande que MIN tenga que devolver a ese nodo... pues no hace falta seguir evaluando las jugadas MIN... porque mejorar la jugada para MIN equivaldría a buscar un valor más pequeño.. pero MAX que está encima ya va a escoger una jugada mejor para él... así que no tiene sentido seguir explorando...

Bueno... pues eso... no sé si os servirá pero a mi me ha servido para repasar...  8)

[julen26]

Se basa en que si el jugador MAX está explorando jugadas de MIN... sabemos que MAX va a escoger la jugada con valor máximo... así que si explorando detectamos que una rama de MIN va a devolver un valor minimo que es menor que el valor más grande que MIN tenga que devolver a ese nodo... pues no hace falta seguir evaluando las jugadas MIN... porque mejorar la jugada para MIN equivaldría a buscar un valor más pequeño.. pero MAX que está encima ya va a escoger una jugada mejor para él... así que no tiene sentido seguir explorando...

Amén!
Aunque no estaría de más un gráfico para que se entendiera mejor



Para entender e implementarlo por primera vez, como se hace en todo, tira por lo mas simple... Hazlo sobre un "tres en raya"

[kanc]

Hola chicos!! muchas gracias a todos por las respuestas. Efectivamente el minmax existe y lo conozco, pero creo que no es aplicable a mi caso jejeje. Puse "de tablero" entre comillas porque se juega en una grid, pero los movimientos que efectúe un jugador no tienen influencia en la partida del otro jugador.

Seguro que conocéis algún juego con esta mecánica, el típico de las joyitas de colores, que tienes que desplazarlas vertical u horizontalmente para formar combinaciones de mas de tres...

Como decia en el post inicial, la partida esta planteada como un combate y cada vez que formas una combinacion de colores, digamos que das un golpe al contrario y gana el que deje sin vida antes al oponente, pero la "IA" no necesita construir un arbol con los posibles movimientos que realize el jugador y asi realizar la jugada optima.

En pantalla, dado que el juego es para movil, solo se vera el "tablero" del jugador y mi duda es... deberia tener un tablero para la IA en la que plantear una partida real o simplemente pegar golpes al jugador.

Un saludo!

[julen26]

La idea de no poner un tablero sería equivalente a jugar una partida en solitario con "tiempo", aunque no sabes realmente cuanto te queda ya que no sabrás cuando el adversario de "golpeará".

En mi opinión no solo sería más bonito mostrar el tablero del oponente, sino que en caso de no mostrarlo se rompería la esencia del juego que en un principio has diseñado.

Claro que, incluir dos tableros de juego en un dispositivo móvil podría acarrear problemas de espacio para la interfaz.

[kanc]

Exacto julen, por un lado me encuentro con que pierde un poco de encanto el no ver cuando la IA hace combinación y por lo tanto te golpea, pero por otro lado esta el tema que si dibujo dos tableros, las piezas deberían ser muy pequeñas y la jugabilidad se vería muy resentida, sobre todo para alguien con dedos grandes.

Por eso, lo de los dos tableros lo tengo descartado. Mi encrucijada es si hacer un tablero en memoria y hacer los movimientos de la cpu o no. Ten en cuenta que el juego tiene gran parte de agudeza visual y eso se perdería claro, la IA sabría inmediatamente que combinación hacer.

La otra opción es elaborar una rutina en la que el rival dependiendo de su nivel (la idea es que vayan aumentando de dificultad) "pegue" con mas o menos asiduidad. También entran en juego las habilidades especiales de cada oponente para putear el tablero del jugador.

[julen26]

No es una fácil elección, por simplicidad yo tiraría por la segunda opción.

De todos modos, también podrías hacer que los dos jugadores jugaran sobre el mismo tablero, sería mas interesante e incluso sería más fácil implementar el minimax, ya que en este caso cada movimiento sí afectaria al siguiente. Además se verían las acciones de la IA.

[blau]

los movimientos que efectúe un jugador no tienen influencia en la partida del otro jugador.

Como decia en el post inicial, la partida esta planteada como un combate y cada vez que formas una combinacion de colores, digamos que das un golpe al contrario y gana el que deje sin vida antes al oponente, pero la "IA" no necesita construir un arbol con los posibles movimientos que realize el jugador y asi realizar la jugada optima.

Estas dos afirmaciones son contradictorias... puedes planteartealo de muchas maneras... pero minimax es adaptable perfectamente... todo está en la función que uses para valorar la jugada.. y un ataque que quita "vida" a tu enemigo tiene muchos puntos para ser tenida en cuenta como valoración de una jugada... vamos... que está a huevo...

otra cosa es que quieras currarte los comportamientos de una forma más "smart" y no usar fuerza bruta,... pero desde luego no lo descartes por otro motivo... ;)

Un saludo...

[kanc]

Hola blau,

No descarto nada, por eso os pido consejo :D. La cosa es que mi conocimiento (que solo es teorico) del minmax es que tu construyes un arbol de posibles movimientos, teniendo en cuenta los que pudiera efectuar el contrario y eliges la mejor opcion. No termino de ver como aplicarlo... se me ocurre plantear un arbol con las posibles combinaciones y elegir la que mas daño haga al rival, pero eso es independiente de los movimientos que él pueda hacer no? total los tableros son independientes uno del otro.

Asi a bote pronto lo que se me ocurre es considerar todos los posibles movimientos de daño que tenga el jugador y plantear un arbol por cada uno de ellos viendo cual de las combinaciones de la CPU haria mas daño dependiendo de la combinacionq ue efectue el jugador. Ni siquiera se si me he explicado bien, pero suena enrevesado y me plantea el dilema de controlar el nivel de dificultad.

Como lo plantearias tu?? Esto no lo digo como reto, ante todo quiero aprender, que es mi primer juego.

Un saludo!

[blau]

Vamos a ver... yo tampoco soy el mas indicado para responderte con la verdad absoluta sobre IA.. no he hecho nunca nada similar y el minimax lo he conocido esta misma semana preparandome el examen de Introducción a la IA...  ^_^' , pero si fuese yo quien tuviera que hacer jugar a la cpu en tu juego haría lo siguiente...

1) Generas dos tableros, uno por cada jugador...
2) Con el mismo algoritmo generas todos los posibles movimientos hasta una determinada profundidad (p) tanto de la CPU como del HUMANO, al final un jewel tampoco admite tantas variantes y conforme vas avanzando cada vez hay menos movimientos posibles, puedes hacer un hilo de ejecución que solo se dedique a tener el árbol calculado hasta esa profundidad (p), de forma de que cuando cualquiera de los jugadores escoge una jugada... se empieza a calcular hasta el nivel de profundidad (p+1)...
3) En cada jugada yo no almacenaría todo el tablero... sino los cambios que se aplican para conseguir el nuevo estado del tablero... fichas que desaparecen y las que aparecen nuevas... aunque si el tablero es pequeño quizás no merezca la pena...
4) Hay que tener en cuenta que el algoritmo tiene que estar pensado para generar un nivel de jugada haciendo que en cada paso juegue un jugador... porque cuando se produzca un ataque... este afectará a los dos tableros o mejor dicho, a los dos estados de los jugadores... en el del jugador que lo ejecuta será una jugada normal... y en el del oponente habrá una alteración de fichas... o le quitas vida... o la ida de olla que se te ocurra...
5) Después tienes que valorar las jugadas en función del numero de movimientos válidos que tengas por debajo, de los ataques que generes y sobre todo valoraría mucho la vida que es lo que te hace ganar o perder la partida... sobre todo si tienes un ataque que quita toda la vida del oponente... o le deja una situación jodida de fichas... que no le permite atacarte... etc...  porque esa es otra, si se queda sin movimientos el jugador digo yo q tb pierde.... hay tienes materia para hacer una buena función de valoración de las jugadas ;)

PD: Ahora he caido en que quizás no quieras alterar el tablero del jugador contrario... simplemente quitarle vida... en cuyo caso se simplifica todo un poco.... porque sólo tienes que tener en cuenta los ataques, ,.... pero mola más joderle el tablero al oponente e imaginarte su cara de agobio.... xD....

[Manu343726]

si no he entendido mal, quieres que cada uno juegue su propia partida, y cada vez que uno hace un movimiento le quita vida al otro (proporcional al tipo de movimiento que haya hecho claro). pierde el que antes se quede sin vidas.

Y digo yo (como consejo, no para tocar las narices) no seria mas entretenido que ambos jugaran en el mismo tablero?

Así se darían situaciones del tipo: "Que cabrón, ese movimiento queria hacerlo yo!" o "Mejor no hago ésto, así el no puede hacer él tal movimiento después"

Si te fijas, requiere más estrategia, ya que ademas de pensar en los posibles movimientos futuros que puede generar tu movimiento actual, tienes que tener en cuenta que la ia te la puede liar usando alguno de ellos. Tienes que sopesar el beneficio riesgo de hacer un movimiento que pueda acarrear buenas jugadas en un futuro.

Además, es exactamente para lo que está diseñado minimax

[blau]

Hombre manu, los algoritmos de búsqueda de soluciones están para adaptarlos a lo que quieres hacer no al revés... ;P

aunque si es un juego para móviles yo abogaría tb por jugar en un mismo tablero para todos... pero simplemente porque mejora la experiencia de juego... y por todos esos motivos que dices...  ;)

[Manu343726]

ya ya, solo quería hacer notar que ese tipo de juego es perfecto para manejar con minimax, ya que se había propuesto en anteriores post

[kanc]

Pues joder Manu, no habia considerado esa opcion  8o ...

Me parece que es mejor solucion que la que estaba yo planteando. Voy a darle un par de vueltas pero creo que al final seguire tu consejo. Ademas como dices, no tendre que comerme el coco para adaptar el minmax  y elimino el problema de los dos tableros.

A veces las cosas mas simples las pasamos por alto jejeje.

Muchas a todos y un saludo!