domingo, mayo 04, 2014

Complejidad de FisFus

Según la teoría de juegos (combinatorial game theory) hay varias maneras de medir la complejidad de un juego: complejidad del espacio de estados, tamaño del árbol de juego, complejidad de decisión, complejidad computacional, etc.

Trataré de establecer algunos de éstos valores para el juego FisFus, que ya expliqué en otro post. Se toma como base el juego "clásico" de FisFus, con tamaño de tablero de 9x9 y 3 piedras por casilla en la primera fila.

Para tratar de determinar el tamaño del árbol de juego, primero se tiene que hacer una aproximación a el factor de ramificación (branching factor), que es el número de hijos en cada nodo del árbol. En FisFus como en cualqier juego de tablero de estrategia, como el Ajedrez o el Go, el factor de ramificación es variable en cada jugada.

FisFus es un juego con alto factor de ramificación, por lo que es complicado de tratar computacionalmente. Un factor de ramificación alto necesitan algoritmos que sigan cada ramificación en cada nodo, tales como búsquedas de fuerza bruta, que son computacionalmente más caras debido al número de nodos que crece exponencialmente, derivando en una explosión combinatoria.

El alto factor de ramificación de FisFus se debe al gran número de combinaciones que puede haber en el movimiento de un grupo de piedras. En condiciones ideales (sin piedras propias o rivales que estorben el movimiento y en un tablero suficientemente grande) las casillas libres a las que puede ir un número de piedras está dado por la fórmula:

c=2n+1

Es decir, una piedra sola puede moverse a 3 casillas, 2 piedras a 5 casillas, 3 piedras a 7 casillas... En cada uno de estos destinos posibles se pueden depositar desde cero, hasta todas las piedras. Para calcular el número de combinaciones se toma como base la conocida fórmula:


Donde n representaría el número de casillas y k el número de piedras. Sin embargo hay que tomar en cuenta que para nuestro propósito, una casilla puede alojar varias piedras, por tanto hay que modificar la fórmula para tomar n=(casillas+piedras-1). Sustituyendo y renombrando variables quedaría entonces así:


Por ejemplo para calcular el número de jugadas posibles de una celda con 3 piedras, hay que calcular las combinaciones de 3 elementos en (7+3-1) espacios, o sea, las combinaciones de 3 en 9. Esto sería 84 posibilidades.

En la siguiente tabla se muestra, para un número determinado de piedras, el número máximo de destinos y las combinaciones para estos.

piedras
destinos óptimos
combinaciones
1
3
3
2
5
15
3
7
84
4
9
495
5
11
3,003
6
13
18,564
7
15
116,280
8
17
735,471
9
19
4,686,825

El factor de ramificación entonces está dado por la suma de las posibilidades de cada conjunto de piedras.

Para hacer honor a la verdad, en un juego real de PerSiVic las piedras comienzan muy limitadas de movimiento, pegadas en el límite del tablero, y muy frecuentemente se estorban entre si y con las piedras del rival. Esto reduce las combinaciones posibles, pero de cualquier manera yo puedo escoger mi jugada inicial entre 235 diferentes. Esto es mucho mas que las 20 del ajedrez. Ciertamente es menos que los 361 comienzos a escojer en go, pero tomemos en cuenta que a partir de ese número, en las jugadas sucesivas, se reduce constantemente, mientras que en PerSiVic no es raro encontrar posiciones con 1000 o más posibilidades. Jugando con ply 3, el software de PerSiVic encuentra alrededor de 1,090,000 jugadas diferentes. Obteniéndo la raíz cúbica de éste número nos da 103, que es un buen aproximado para el factor de ramificación, al menos para la fase inicial del juego.

Los juegos de FisFus son más breves que los de ajedrez. Supongamos que sean 20 jugadas en promedio, por tanto es un ply de 40. Esto nos daría un tamaño del árbol de juego de 103 elevado a la 40. El resultado aproximado es 10^80. Este es un valor conservador; un límite superior podría calcularse tomando un factor de ramificación de 200 (como ya se mencionó no es infrecuente encontrar posiciones con factor de 1000) y un ply de 80. Esto es 200^80, igual a 10^184. Como comparación, el Ajedrez tiene un tamaño de árbol de 10^123. Esto es, el árbol de FisFus sería 61 órdenes de magnitud más grande. Basado en algunos juegos rales (humano vs. software PerSiVic) se ha encontrado que un promedio más realista de factor de ramificación es 134. Con un ply de 30, se obtendría un tamaño de árbol de 10^64.






sábado, mayo 03, 2014

FisFus

FisFus es un juego de tablero clásico de estrategia, partisano, con información perfecta. Bajo la sombrilla de FisFus se pueden definir un número indeterminado de juegos con las mismas características y reglas consistentes, en forma semejante al juego oriental Go, que se puede jugar en tableros de diversos tamaños: 9x9, 13x13 y 19x19.

FisFus fue desarrollado por Ernesto Amezcua Montes, de México, a partir de 2001. En sus inicios usaba el nombre PerSiVic.

Las diferentes versiones de FisFus se pueden determinar por tres parámetros, cada uno representable por un número natural: el tamaño del tablero (número de filas o columnas), el número inicial de piedras en cada casilla de la primera fila, y el número de piedras en la última fila para cumplir la condición ganadora. La única limitante para estos parámetros es por consideraciones prácticas: un tablero demasiado pequeño sería trivial, o bien sería imposible realizar jugadas. Un tablero demasiado grande ocasionaría juegos demasiado largos o complicados.

Consideraremos el juego "clásico" de FisFus, con un tablero de 9x9, 3 piedras en cada casilla de la primera fila (cada jugador sus piedras en su primera fila correspondiente), y 5 piedras para ganar.



Movimiento: depende del número inicial de piedras en la casilla. Las piedras se moverán a una celda vacía, por una ruta vacía, un número de casillas ya sea a la izquierda, derecha o arriba. Cada piedra podrá terminar en una celda diferente, siempre y cuando la celda final esté a una distancia ortogonal igual al número de piedras iniciales.


Captura: Todas las piedras de una celda inicial se mueven y sustituyen a las piedras rivales, a través de una ruta vacía. Igual que con el movimiento, las piedras solo pueden moverse en una distancia ortogonal igual al número de piedras que se mueven.


Condición ganadora: 5 piedras llegan a la última fila.



Condición de empate: Si ambos jugadores llegan a tener menos de 5 piedras, o si no hay movimientos válidos, o si se repite la misma posición tres veces, o de común acuerdo.

Persivic en Boardgamegeek

Persivic, reglas en inglés, por Sam Tremholme

Persivic (y FisFus) en rec.games.abstract

FisFus en Google Play