next up previous
Next: 3.6 Estrategias de Juego Up: 3. Juegos Previous: 3.4 SSS (Stockman 79)

3.5 SCOUT (Pearl 80)

La idea básica es que mucho esfuerzo computacional se puede evitar si se tiene una forma rápida de probar desigualdades.

Idea: probar si la desigualdad $V(J) > v$ es verdadero y evaluar $J$ sólo si es el caso, donde $v$ es algún valor escogido para la prueba (e.g., si $ev(t) > v$ entonces se declara ganadora la posición).


Tabla 3.5: Procedimiento de Prueba de SCOUT.
\begin{table}
\begin{tabbing}
123\= \kill
Procedimiento Prueba \\
Si $J$ es no...
...$ \\
\> y regresa {\bf T} si todos son mayores a $v$
\end{tabbing}\end{table}


Eval(J) calcula el valor minimax de posiciones MAX evaluando el sucesor de la izquieda y explora los sucesores siguientes de izquierda a derecha para determinar (llamando a Prueba) si se cumple que $V(J_k)
> V(J_1)$

Si la desigualdad se cumple, se evalua el valor exactamente y se continua.



Eduardo Morales Manzanares 2004-11-02