Buenas, mi problema consiste en lo siguiente: Distribuyo aleatoriamente en el tablero de ajedrez un rey negro, una reina, alfil, torre y caballo blancos. La idea es saber cuantos son los turnos necesarios para dejar al rey en jaque mate. El rey, en su turno, se moveria a cualquier casilla, entre sus limites, sin importarle que la casilla a la que se mueve este en jaque o jaque mate. De antemano les agradezco las sugerencia para la implementacion de este programa
Generas todos los posibles movimientos de un bando, para cada uno de esos, generas todos los posibles movimientos del otro, etc etc. Ten cuidado que con tanta ficha blanca es posible que lo ahogues si colocas las piezas al azar.
Suena a trabajo de clase que no veas por cierto :p
Un saludo,
Vicente
Funcion para simular movimientos, una base de datos con los movimientos a seguir según los movimientos del otro.
En el caso de quien saca, tiene un tipo extra, q base de datos de movimiento inicial.
Hay sitios por internet que tienen estas bases de datos y librerias Open Source que creo que las utilizan y tal. Date una vuelta por google buscando "base de datos ajedrez" quizas en español encuentres poco :)
Un saludo!
Mmm, lo de la base de datos es útil en dos casos:
- aperturas (donde ya está más o menos establecido que jugadas son buenas y que jugadas son malas).
- finales: lo que danfox1d tiene es parecido a un final, pero no es un final de base de datos en sí. No hay peones, las blancas no tienen rey y además tienen material de sobra para dar mate de mil maneras diferentes. Y el rey negro ni siquiera se tiene que mover de forma inteligente parece.
Con generar todos los movimientos le sobra creo yo. Un saludo,
Vicente
Si en su caso es verdad, lo tiene facil.
Es una clasica busqueda en profundidad. Aun que no especifica, lo que debe estar buscando es la cantidad minima de movimientos por lo que el objetivo es hacer el jaque mate.
OJO con no entablar y hace movimientos repetitivos :P
Lo ultimo se soluciona facilmente haciendo que el orden de los movimientos se sette por seudo azar antes de meterlos en la cola o pila (dependiendo si haces una busqueda en ancho o en profundidad)
Saludos!
Muchas gracias a todos, la verdad nunca habia visto un foro tan colaborador, espero algun dia poderles retribuir.
Efectivamente mi intencion es hallar la cantidad minima de movimientos para hacer jaque mate, lo que pasa es que no se como hacer para que el programa ponga las fichas blancas de tal forma que dejen en jaque al rey. Mi idea es ir mostrando cada movimiento hasta que el rey quede en jaque mate. Una vez mas gracias
es un MINIMAX de toda la vida con poda.
Ahí le has dado Buffon!
http://es.wikipedia.org/wiki/Minimax
Cita de: "Prompt"Ahí le has dado Buffon!
http://es.wikipedia.org/wiki/Minimax
si no estubiera en el trabajo te habría buscado un PDF q tengo, pero la wiki que ha puesto prompt lo supera con creces jeje
Cita de: "Buffon"es un MINIMAX de toda la vida con poda.
No necesariamente, pues el rey tambien quiere ser jaqueado. Ambos bandos juegan para el mismo equipo.
Cita de: "Buffon"es un MINIMAX de toda la vida con poda.
No es exactamente un MINIMAX de toda la vida ;) El algoritmo en sí lo es, pero dado que normalmente se usa la cantidad de material en el tablero (entre otras cosas) para evaluar lo buena que es una posición y que en este caso el material es constante (vale, las negras se pueden comer alguna cosa, pero en la inmensa mayoría de movimientos va a ser constante y ciertamente no va a afectar para dar mate demasiado) se debería buscar otra forma de evaluar lo buena que es una posición (lo cerca que está el rey negro de un borde del tablero y similares) que es un problema bastante más complicado...
Vamos, dado que no parece que danfox1d sepa mucho del tema, pedirle que calcule el valor para una poda alfa-beta haciendo un análisis posicional me parece bastante pedir :p
Un saludo,
Vicente
OK,
El rey queire ser jaqueado, hay reina y torre, o sea mate en menos de 10 movimientos asegurados y lo que se busca es saber cual es el numero minimo de movimientos para realizar esto, solucion: una busqueda en profundidad con tope en 10.
... para que el minimax ?
Bueno, tal ves lo tomo demasiado pragmaticamente.
Edit:
Incluso creo que una busqueda en ancho resultaria mas fructifera, seguramente habra mate en 3 o 4 movimientos.
la forma de calcular el heurístico no interfiere en que sea o no un "MINIMAX de toda la vida".
Perdonad si no he entendido bien vuestro mensaje pero estoy en el curro y leo a prisas jeje.
Además se pueden definir dos heurísticos distintos, uno para jugadorA y otro para jugadorB.
Claro que no infiere, pero sí que hay que puntualizarlo. En este ejemplo decirle que haga un mini-max es un consejo muy poco práctico dado que la heurística es bastante jodida. A eso me refería.
Normalmente cuando la gente comienza a cacharrear con mini-max y la poda alfa-beta (porque un mini-max sin poda tampoco es que sea demasiado útil) suele usar problemas donde la heurística es más o menos trivial, pero en este caso no lo es.
Así que sí, generalmente el algoritmo a usar es un mini-max con poda (y otras cuantas cosas), pero antes de decir, usa esto, hay que ver si realmente es tan fácil de usar como de decir. De nada le sirve implementarse el mini-max (que al final para expandir los movimientos va a usar una búsqueda en anchura) para luego ver que se es incapaz de calcular el valor de la posición.
Además, como ha dicho pogacha, dado el material que hay en el tablero casi seguro que se puede conseguir mate en 8 jugadas o menos en la peor de las posiciones (con el rey negro en el centro, necesitas 4 jugadas para llevarle a un lateral y otras 2-3 para colocar tus piezas, así que puede que incluso sea menos). Una simple búsqueda en anchura o en profundidad iterativa funcionará bastante bien y no hace falta complicarse la vida.
Un saludo,
Vicente
Una vez mas quiero agradecer a todos por su colaboracion.
Debido a mi gran inexperiencia con este tema, pero ya entendiendo que debo utilizar alguna heuristica como por ejemplo la busqueda en profundidad iterativa, me veo en la necesidad de preguntar: que debo guardar en los nodos del arbol que genere?.
Al ser un problema de informacion completa:
Situacion actual del tablero + Jugador al que le toca + (numero de jugadas que llevas, en tu caso) [esto es si haces la busqueda usando recursividad].
Si generas una estructura de arbol fisicamente en disco te basta con situacion actual del tablero, ya que los otros dos los puedes deducir de los padres/abuelos/.../raiz.
Ni que decir tiene que lo mas recomendable es la primera opcion...
Cita de: "Lord Destiny"Al ser un problema de informacion completa:
Situacion actual del tablero + Jugador al que le toca + (numero de jugadas que llevas, en tu caso) [esto es si haces la busqueda usando recursividad].
Si generas una estructura de arbol fisicamente en disco te basta con situacion actual del tablero, ya que los otros dos los puedes deducir de los padres/abuelos/.../raiz.
Ni que decir tiene que lo mas recomendable es la primera opcion...
en este caso no creo que haga falta la situación actual del tablero, quizá le saldría a cuenta guardar punteros a los padres y guardar sólo el movimiento actual.
El resto se calcula en tiempo real por así decirlo cuando estás tratando el nodo para expandirlo o desecharlo.
TEN EN CUENTACuando hagas el algorismo puedes obtener este resultado.
NODONIVEL1.1
NODONIVEL2.1 NODONIVEL2.2 NODONIVEL2.3
....
NODONIVELN.1 = casualmente la situación en tablero es la misma que en algún nodo superior, pues aquí desechamos el árbol por que hay una posibilidad de encontrar el mismo resultado con menor cantidad de movimientos.
Esto significa que has de guardar la situación del tablero?No realmente, pero si un indicador de la misma, tipo hash o por ejemplo, empezando por A1 hasta la última casilla guardar un número que indique que pieza contiene.
NADA=0
PEON=1
TORRE=2
CABALLO=3
ALFIL=4
REINA=5
REI=6
Sabiendo que hay 64 casillas tendrías siempre un identificador de mínimo 192 bits = 12 bytes, con máscaras es muy rápido, además tu problema es más sencillo dado que sólo usas unas piezas concretas.
Además de tener dos listas.
situacionVisitada
situacionPorVisitarsi buscas en anchura:
do {
situacion = situacionPorVisitar.pop();
...... lógica del juego ......
porcada nueva situación expandida
if(!situacionVisitada.contains(situacionExpandida))
situacionPorVisitar.push_back(situacionExpandida);
}while(!situacionPorVisitar.empty());
---
Al final me retracto de lo que le he dicho a Lord Destiny, si que hay que guardar la situación de tablero, utilizando la mínima memoria posible tipo hash, lo que hace pensar un poco eh ^^
En ajedrez se suelen usar este tipo de hashes:
http://en.wikipedia.org/wiki/Zobrist_hashing
Un saludo,
Vicente