El ajedrez y el factor de ramificacion

Cuando uno estudia o es aficionado al ajedrez por computadora se debe de conocer el concepto de factor de ramificación (branching factor) en palabras simples si tenemos la posición inicial y cada movimiento siguiente tiene X posibilidades, entonces el factor de ramificación es X, por ejemplo un juego ya resuelto por las computadoras es el famoso gato(tic tac toe en ingles) tiene factor de ramificación de 4.

El ajedrez tiene factor de ramificación 35 es un factor mucho mayor pero no se compara al factor de ramificación del go que es 250, por supuesto que también influye el tamaño del tablero y la cantidad de jugadas máximas posibles. 

Como se podrán imaginar a mayor tamaño de tablero y mayor cantidad de jugadas posibles mas “dificil” de resolver se vuelve el juego.

Solo para evitar confusiones, tener un factor de ramificación alto solamente no implica que un juego sea mas difícil, digamos que tenemos un juego donde su factor de ramificación es 1000 pero la cantidad total de jugadas es 2, al tener solo 2 jugadas existen muchas menos opciones que por ejemplo un juego de factor de ramificación 30 pero que se puedan jugar hasta 200 jugadas.

Pero manteniendo todos los demás valores constantes el factor de ramificación si es muy importante, un juego muy similar al ajedrez en tamaño de tablero y que ya esta resuelto son las damas(checkers en ingles) su factor de ramificacion es 8, mientras un juego muy similar llamado arimaa tiene factor de ramificacion de 17000 y de las cuales las computadoras aun no tienen mucha idea.

También hay que darse cuenta que el factor de ramificación no es constante, si no mas bien un promedio puede verse claramente que en esta jugada:

Se tienen muchas mas posibles movidas que en esta otra

Pero lo que nos importa es la cantidad promedio de ramificación promedio entre los juegos empezando desde el inicio.

Aclaro que todos los números mencionados son aproximados si quieren saberlo con exactitud les dejo unas referencias.

Referencias:

http://www.cs.cmu.edu/~adamchik/15-121/lectures/Game%20Trees/Game%20Trees.html

http://es.wikipedia.org/wiki/Factor_de_ramificación

http://www.gamedev.net/page/resources/_/technical/artificial-intelligence/chess-programming-part-iv-basic-search-r1171

http://arimaa.janzert.com/bf_study/

Comments

comments

2 comentarios en “El ajedrez y el factor de ramificacion”

Los comentarios están cerrados.