Como parte de una tarea, tengo que programar un simple juego de ajedrez en Java. Estaba pensando en aprovechar la oportunidad de experimentar con la recursión, y me preguntaba si hay un candidato obvio en el ajedrez para el código recursivo.¿Buen uso de recursión en la programación de ajedrez?
El candidato más obvio para mí sería una rutina recursiva Minimax para la búsqueda de los mejores movimientos. Esto también entra en gran parte de la teoría detrás de los algoritmos de búsqueda y sería genial implementarlo.
Ejemplo:
http://www.devshed.com/c/a/Practices/Solving-Problems-with-Recursion/6/
Incluso creo que no hay alternativa al minimax recursivo (si la idea es desarrollar un KI) –
También es útil este enlace que explica alfa-beta http://www.fierz.ch/strategy1.htm –
Guau, esto es un gran artículo. Parece que este es un método que se usaría de manera diferente en diferentes etapas. Tal vez haya una versión para mate y una para algún otro objetivo (por ejemplo, capturar una pieza), cada una con diferente profundidad. Hmmm ... Diversión. – JDelage
No ajedrez, pero un rompecabezas clásico con Figueres ajedrez: http://en.wikipedia.org/wiki/Eight_queens_puzzle
Usted está pensando en backtracking
búsqueda en profundidad es un candidato ideal para la recursividad. así que si estás programando una IA para la tarea, entonces el algoritmo de la mirada de la IA para tratar de encontrar el mejor próximo movimiento sería un buen candidato.
Sin embargo, tenga cuidado: puede quedarse sin memoria rápidamente. Probablemente quieras limitar la cantidad de movimientos profundos que puede tener la inteligencia artificial.
Sí, sí. Si tiene alguna función que evalúe "fuerza" de alguna posición para decir jugador blanco. Puede mover una pieza y llamarla recursivamente para evaluar el valor de un movimiento y elegir el mejor movimiento.
Debe llamar a la misma función para jugador negro, intercambiando roles para blancos y negros, evaluando así el "peligro" de un movimiento oponente.
luego de nuevo para los blancos, etc.
Sólo ten en cuenta que no debe ir demasiado profundo en los niveles de recursividad o que va a tener para siempre.
Gracias. Solo necesito encontrar una buena lógica para el valor de cada movimiento. – JDelage
mente dynamic programming, ya que tiene varias combinaciones que conducen a la misma tabla, usted debe recordar para almacenar en caché los movimientos con el fin de evitar la repetición de cálculos
Si detecta una recursión sólo te lleva a un lugar donde se tiene estado, acaba de romper esa llamada. Esto se conoce como backtracking
Todo lo relacionado con los árboles. –
Uno de mis primeros programas Java (en 1998) fue un programa de ajedrez, usando un algoritmo recursivo minimax que Laplace menciona a continuación. Definitivamente es un proyecto interesante para aprender Java y recursión con. – Jesper
www.m-w.com dice que la recursividad no es una palabra válida en inglés. Título editado. –