Ayuda ajedrez

[danfox1d]

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

[Vicente]

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

[Prompt]

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!

[Vicente]

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

[Prompt]

Si en su caso es verdad, lo tiene facil.

[Pogacha]

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!

[danfox1d]

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

[Buffon]

es un MINIMAX de toda la vida con poda.

[Prompt]

Ahí le has dado Buffon!

http://es.wikipedia.org/wiki/Minimax

[Buffon]

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

[Pogacha]

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.

[Vicente]

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

[Pogacha]

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.

[Buffon]

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.

[Vicente]

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