Ayuda ajedrez

[danfox1d]

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?.

[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...

[Buffon]

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 CUENTA

Cuando 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
situacionPorVisitar

si buscas en anchura:

Código [Seleccionar] Expand


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 ^^

[Vicente]

En ajedrez se suelen usar este tipo de hashes:

http://en.wikipedia.org/wiki/Zobrist_hashing

Un saludo,

Vicente