3.2.3 Alternativas

Next: 3.3 Alpha-Beta Up: 3.2 MiniMax Previous: 3.2.2 Algoritmo Minimax

No tenemos que generar todos los sucesores y guardar sus valores hasta que todos sean evaluados. Podemos usar un algoritmo depth-first (ver tabla 3.2).

Tabla 3.2: Algoritmo Minimax con backtracking.
$\begin{table} \begin{tabbing} Algoritmo \emph{minimax} (\emph{backtracking}) ... ...in[VA(J), V(J_k)]$ \\ regresa $V(J) \leftarrow VA(J)$ \end{tabbing}\end{table}$
No es necesario que evaluemos todos los nodos terminales (ver tabla 3.3).

Tabla 3.3: Algoritmo Minimax con pierde/gana.
$\begin{table} \begin{tabbing} Algortimo mejorado (ilustrado con \emph{gana-pier... ...} si todos \\ \> los sucesores de $J$ son \emph{gana} \end{tabbing}\end{table}$

**Tabla 3.2:** Algoritmo Minimax con *backtracking*.
$\begin{table} \begin{tabbing} Algoritmo \emph{minimax} (\emph{backtracking}) ... ...in[VA(J), V(J_k)]$ \\ regresa $V(J) \leftarrow VA(J)$ \end{tabbing}\end{table}$

**Tabla 3.3:** Algoritmo Minimax con *pierde/gana*.
$\begin{table} \begin{tabbing} Algortimo mejorado (ilustrado con \emph{gana-pier... ...} si todos \\ \> los sucesores de $J$ son \emph{gana} \end{tabbing}\end{table}$

Las mejoras dependen del orden en que los sucesores son evaluados.

Una de las razones de la eficiencia del último algoritmo es que se da cuenta que el estatus de algunos nodos no afecta la evaluación del nodo raíz.

Eduardo Morales Manzanares 2004-11-02