Metodos Matematicos - Shanon.

...

El juego siempre termina después de un número finito de movimientos, y uno de los dos jugadores tiene que ganar. Ya sea corto, corte, o el jugador se mueve primero se garantiza la existencia de una estrategia ganadora en cualquier gráfico dado. [4]

Los cortos y corte son juegos que son una dualidad; es decir, el juego puede ser actualizado de forma que ambos jugadores tienen el mismo objetivo

-

El Numero de Shannon

En el área de las computadoras y de la inteligencia artificial, publicó en 1950 un trabajo que describía la programación de una computadora para jugar al ajedrez, convirtiéndose en la base de posteriores desarrollos. El número de Shannon, 10120, es una estimación de la complejidad del árbol de juego del ajedrez. Fue calculado por primera vez por Claude Shannon, el padre de la teoría de la información. Shannon lo calculó en su publicación "Programando un computador para jugar ajedrez".1 De acuerdo a su cálculo, se realizan una media de 40 movimientos en una partida de ajedrez, mientras que cada jugador escoge un único movimiento de unos 30 posibles (de hecho, puede ser que existan cero posibilidades como en los casos de jaque mate , o tantos como 218). Así, tenemos que son posibles (30×30)40, i.e., 90040 juegos de ajedrez diferentes. De manera aproximada se dice que es igual a 10120, valor que se obtiene de resolver la ecuación: 90040=10x. Despejando, tenemos que: x=40×log 900.

Actualmente la complejidad de árbol de juego del ajedrez se calcula en torno a 10123 (el número de posiciones legales en una partida de ajedrez se estima entre 1043 y 1050). Como comparación, el número de átomos que se estima que existen en el universo son entre unos 4×1078 a 6×1079.

Shannon propuso varias consideraciones que deben ser tomadas en cuenta en la función de evaluación de posiciones de un programa de ajedrez (aquella que determina un valor numérico para una posición):

- Ventaja Material

- Estructura de peones

- Peones Aislados y retrasados.

- Control relativo del centro.

- Peones en color opuesto al alfil propio.

- Peones pasados

- Posición de las piezas.

- Caballos avanzados, protegidos o atacados.

- Torres en columnas abiertas o semiabiertas.

- Torres en séptima fila.

- Torres dobladas.

- Posibilidades de ataque.

- Piezas que protegen a otras piezas.

- Ataques sobre otras piezas.

- Ataques sobre casillas adyacentes al rey enemigo.

- Clavadas.

- Movilidad, medida por el número de movimientos legales posibles.

Shannon describió dos tipos de estrategias para el juego de ajedrez por máquinas. La más primitiva, llamada "tipo-A", consistía en la búsqueda en profundidad con un límite a lo largo de cada "rama" del árbol de variantes, para luego utilizar el algoritmo "minimax". La estrategia "tipo-B" introdujo un método de búsqueda selectiva en el cual ciertas líneas eran más profundizadas que otras.

El mismo Shannon acotó que la estrategia "tipo-A`" presenta al menos tres desventajas. En una posición de medio juego hay cerca de 30 posibles movimientos. Después de una movida de cada bando las posibilidades crecen a 1000 nodos terminales los cuales deben ser evaluados. Luego de tres movimientos la proporción crece a 3#3 nodos terminales, lo cual implica que a una tasa de evaluación de 1 por cada microsegundo el programa tardaría al menos 16 minutos para cada movimiento.

Segundo, un jugador de ajedrez examina algunas variantes con profundidad de pocos niveles y otras con cerca de 20 niveles de profundidad. Esto es lo que se llamó "búsqueda selectiva" en la estrategia "tipo-B". La tercera desventaja es el problema derivado de las posiciones "inestables", aquellas en donde hay cambios de piezas o bien secuencias de jaques.

Referido a esto último, Shannon introdujo el concepto de "estabilidad", la cual aplicó a su segundo tipo de estrategia, proponiendo lo siguiente:

Examinar variantes forzadas lo más profundamente posible, evaluando sólo posiciones estables.

Seleccionar mediante un proceso externo las variantes importantes de ser analizadas, evitando perder tiempo analizando variantes inútiles.

Estos dos criterios son claramente utilizados por jugadores humanos, siendo el segundo nada más que el algoritmo alfa-beta, el cual fue utilizado en programas a partir de 1960.