De las cuatro piezas fundamentales de todo juego de tablero:
- El árbol de juego.
- El generador de jugadas.
- La función de evaluación.
- Y el procedimiento minimax.
- (El procedimiento de poda es opcional).
ya tenemos las dos primeras. Yo creo que con esto ya hemos alcanzado la cima del proyecto y a partir de ahora ya es todo un poco más cuesta abajo.
El siguiente paso, por tanto, es la función de evaluación. La función de evaluación es una rutina que recibe un tablero y devuelve cómo de bueno o malo es para ratón y gatos.
Criterios de evaluación:
Las funciones de evaluación, como ya comentamos, suelen tener en cuenta:
- Criterios materiales.
- Y criterios posicionales.
Los criterios materiales tienen que ver con las piezas que quedan sobre el tablero y las que ya se han "comido". Pero como en el juego del ratón y los gatos no hay capturas, no tiene sentido aplicar criterios materiales. Siempre habrá las mismas piezas sobre el tablero.
Y los criterios posicionales tienen que ver con la posición de las piezas: si tienen más movilidad, menos movilidad, si han llegado o están cerca del objetivo, si su posición es más ofensiva, más defensiva, etc. Todos los criterios que aplicaremos aquí serán posicionales.
Empezaremos haciendo una función de evaluación sencilla, con pocos criterios posicionales, y la iremos mejorando con sucesivas versiones.
Evaluación y procedimiento minimax:
En principio, la función de evaluación se aplica sólo sobre las hojas del árbol de juego, es decir, sobre los tableros de máxima profundidad. Y, a partir de ahí, las evaluaciones se van haciendo subir por el árbol de juego mediante el procedimiento minimax.
Sin embargo, debemos ir poco a poco. Así que en una primera versión haremos una función de evaluación sencilla y la aplicaremos sobre todos los nodos (tableros) del árbol de juego. Esto nos permitirá dos cosas:
- Probar bien la función de evaluación, ya que tendremos muchos tableros de ejemplo sobre los que probarla (todos los del árbol).
- Y preparar la base del procedimiento minimax, que sí tiene que trabajar sobre todos los tableros del árbol.
Valores de las evaluaciones:
El objetivo de la función de evaluación es devolver un número que diga cómo de bueno o malo es un tablero para el ratón y los gatos. El valor absoluto es lo de menos; lo importante es que, si se compara la evaluación de un tablero T1 con la de otro tablero T2, quede claro qué tablero es más favorable para el ratón (o los gatos) y qué tablero es más desfavorable.
Por ello, tenemos bastante libertad para elegir el rango de valores para las evaluaciones. Supongamos que decidimos usar un byte (256 valores distintos).
Puesto que el ratón se señaliza sobre el tablero con el valor $01 (positivo) y los gatos con el valor $ff = -1 (negativo), una primera opción intuitiva sería asignar valoraciones positivas para lo que favorece al ratón y perjudica a los gatos, y valoraciones negativas para lo que favorece a los gatos y perjudica al ratón.
Por ejemplo, algo así (recordemos que el objetivo del ratón es llegar a la fila cero, y el objetivo de los gatos es acorralar al ratón):
- Situaciones favorables al ratón:
- Ratón en fila 7 => +0 puntos
- Ratón en fila 6 => +1 puntos
- Ratón en fila 5 => +2 puntos
- Ratón en fila 4 => +3 puntos
- Ratón en fila 3 => +4 puntos
- Ratón en fila 2 => +5 puntos
- Ratón en fila 1 => +6 puntos
- Ratón en fila 0 (gana el ratón) => +32 puntos = $20
- Situaciones favorables a los gatos:
- Ratón con 4 movimientos => -0 puntos
- Ratón con 3 movimientos => -1 puntos = $ff
- Ratón con 2 movimientos => -2 puntos = $fe
- Ratón con 1 movimientos => -3 puntos = $fd
- Ratón con 0 movimientos (ganan los gatos) => -32 puntos = $e0
Sin embargo, manejar números negativos en ensamblador no es fácil. No es fácil compararlos, no es fácil calcular el máximo ni el mínimo (procedimiento minimax), al operar con ellos se puede producir desbordamiento, es decir, al sumar dos números positivos el resultado puede ser aparentemente negativo (situación señalizada con el flag V), etc.
Por todo ello, y dado que los valores absolutos de las evaluaciones son lo de menos, simplifica bastante la vida tomar un valor intermedio en el rango 0 – 256 como valor neutro y, a partir de ahí, tomar valores por debajo para situaciones que favorecen a los gatos y valores por encima para situaciones que favorecen al ratón. En nuestro caso en particular vamos a tomar $80 = 128 como ese valor neutro y, a partir de ahí, sumaremos o restaremos, pero siempre manejaremos números positivos.
Con todos estos comentarios previos ya estamos listos para abordar la primera versión de la función de evaluación, cosa que ya dejamos para la siguiente entrada.
No hay comentarios:
Publicar un comentario