Version User Scope of changes
Jan 27 2008, 10:56 PM EST (current) aespinalc 283 words added, 1 photo added
Jan 27 2008, 10:52 PM EST aespinalc

Changes

Key:  Additions   Deletions
ALGORITMO A*

Para juegos simples unipersonales puede usarse el algoritmo A* (Hart, 1968). Este algoritmo implementa una búsqueda primero el mejor.

Se utiliza una función de evaluación estática f formada por:
    f = g + h
  • La función g es una función de coste de llegar del estado inicial al estado evaluado.
  • La función h es una estimación del coste de llegar desde el estado evaluado al estado final u objetivo del juego.

En cada paso del algoritmo se selecciona el mejor nodo que no se ha expandido hasta el momento, es decir, aquel que tiene menor valor de función f. Este nodo se agrega a una lista de nodos explorados (NodosExplorados) y sus nodos sucesores se agregan a la lista de nodos pendientes de ser explorados (NodosNoExplorados).
El algoritmo A* es el siguiente: Estado_Inicial.g := 0;
Estado_Inicial.h := H(Estado_Inicial);
Estado_Inicial.f := Estado_Inicial.g + Estado_Inicial.h; NodosNoExplorados := Estado_Inicial;
NodosExplorados := Ø; Bool EncuentraEstadoFinal := FALSE; Mientras NOT EncuentraEstadoFinal AND NodosNoExplorados != Ø
    EstadoActual := SeleccionarMejorNodo(NodosNoExplorados);
    NodosExplorados := NodosExplorados + EstadoActual; Si EsEstadoFinal (EstadoActual) entonces
      EncuentraEstadoFinal := TRUE;
    Sino
      Sucesores := CalcularSucesores (EstadoActual);
      Para cada EstadoSucesor de Sucesores
        EstadoSucesor.padre := EstadoActual;
        EstadoSucesor.g: EstadoActual.g + Coste(EstadoActual,EstadoSucesor);
        Si Pertenece(EstadoSucesor, NodosNoExplorados) entonces
          EstadoViejo:=ExtraerNodo(EstadoSucesor, NodosNoExplorados);
          EstadoActual.sucesores := EstadoActual.sucesores + EstadoViejo;
          Si EstadoViejo.g > EstadoSucesor.g entonces
            EstadoViejo.padre := EstadoActual;
            EstadoViejo.g := EstadoActual.g;
            EstadoViejo.f := EstadoViejo.g + EstadoViejo.h;
          Fin si;
        Sino si Pertenece(EstadoSucesor, NodosExplorados) entonces
          EstadoViejo:=ExtraerNodo(EstadoSucesor, NodosNoExplorados);
          EstadoActual.sucesores := EstadoViejo;
          Si EstadoViejo.g > EstadoSucesor.g entonces
            EstadoViejo.padre := EstadoActual;
            EstadoViejo.g := EstadoActual.g;
            EstadoViejo.f := EstadoViejo.g + EstadoViejo.h;
            ActualizarSucesores(EstadoViejo);
          Fin si;
        Sino
          NodosNoExplorados := NodosNoExplorados + EstadoSucesor;
          EstadoActual.sucesores :=EstadoActual.sucesores + EstadoSucesor;
          EstadoSucesor.f := EstadoSucesor.g + EstadoSucesor.h;
        fin sino;
      Fin para;
    Fin sino;
Fin mientras;

Juegos SIN adversario - Inteligencia artificial en EAFIT

tomado de http://dmi.uib.es/~abasolo/intart/2-juegos.html
imagen tomada de http://ensino.univates.br/~chaet/algoritmos.jpg



Top Contributors