3.2.1 Tamaño de Búsqueda

Una de las motivaciones principales de investigación en juegos es que son difíciles de resolver.

Ajedrez: branching factor $\approx 35$, número de jugadas por jugador $\approx$ 50, por lo que hay $\approx 35^{100}$ o $10^{120}$ hojas o nodos terminales (aunque sólo hay $10^{40}$ posiciones diferentes legales).

En en caso de Damas Chinas es: $10^{40}$

Como no se puede evaluar/explorar todo el árbol, exploramos hasta cierta profundidad y usamos heurísticas (una función de evaluación estática).

Suposición: evaluando después de cierta exploración es mejor que evaluar sin exploración, bajo el supuesto que el mérito de una situación se clarifica al ir explorando.

La calidad del programa depende fundamentalmente de la función de evaluación. Tiene que ser (i) congruente con la función de utilidad de los nodos terminales, (ii) rápida y (iii) reflejar las posibilidades actuales de ganar.

Una valor de la función de evaluación en realidad cubre muchas posibles posiciones.

Si fuera perfecta, no tendríamos que hacer búsqueda.

El algoritmo minimax usa dos heurísticas: (i) cálculo de la función de evaluación y (ii) propagar valores hacia atrás asumiendo que los valores en los nodos de frontera son correctos.

Si las estimaciones son burdas, también son los resultados.

Muchas de las funciones de evaluación asumen independencia entre los factores y las expresan como funciones lineales con pesos ( $w_1 f_1 + w_2 f_2 + \ldots + w_n f_n$).

Para ésto, hay que encontrar los pesos y decidir qué factores a considerar.

Algunas estrategias de evaluación (tomadas de Deep-Blue antes Deep-Thought):

• Material: peón = 1, caballos y alfiles = 3, torre = 5, y reina = 9. Puede variar dependiendo de la situación (e.g., el mantener un par de alfiles al final del juego).
• Posición: Al principio se pensó que el control del centro era lo primordial. Aunque si es muy importante no es lo único. Una forma fácil de imaginarse ``posición'' es contanto el número de cuadros que se pueden atacar en forma segura. Entre más cuadros se tengan, se tiene más control.
• Defensa: Los aspectos defensivos de la posición tienen que ver con la seguridad del rey.
• Tempo: define la ``carrera'' por el control del tablero.