el desarrollo humano

Análisis de la complejidad
Tras consultar a un profesor especializado en inteligencia artificial he
llegado a una serie de conclusiones.
La primera es, como ya sospechaba, que el problema de untres en raya en
3D para 3 jugadores es NP-Completo1.
Esto quiere decir básicamente que no es posible solucionarlo en un tiempo
aceptable. Es evidente que a un jugador no le parecería bien esperarel
movimiento del rival más que unos pocos segundos como máximo.
No es viable la implementación de árboles de búsqueda para si no se limita
muy estrictamente la profundidad umbral tras la que no sedeberían de
expandir nuevos nodos porque se dispararía el tiempo de cálculo.
¿Y a qué se debe principalmente este problema que los ordenadores más
potentes son incapaces de resolver?
El problemaestá en la incapacidad de barajar todas las posibles situaciones
del tablero (llamaremos a partir de ahora tablero al cubo de 27 casillas).
Un tres en raya convencional tiene 9 casillas e implementarun algoritmo
de búsqueda para este juego es perfectamente viable con búsqueda en
árboles. Lo es gracias a su pequeño orden de ramificación y su profundidad
máxima del árbol.
En este caso tenemos9 casillas y cada una de ellas puede tener 3 diferentes
estados: Vacía, con X y con O. Los posibles estados del tablero de juego
para el tres en raya convencional es:
39=19.693 posibilidades
Encomparación, este mismo juego con una dimensión más tendría 27
casillas y tres jugadores. Cada casilla tendría entonces 4 estados posibles:
Vacía-X-O-ı.
427=18014398509481984 posibilidades
Ladiferencia ya es llamativa en este aspecto pero lo es más en términos de
ramificación y profundidad en la búsqueda en árboles.
Si para el convencional tres en raya el explorar todas las posibilidades esdel orden O(n!) con n=9 fijo9!= 362880
Esta cifra no supone desafía alguno para un ordenador.
Pero ese mismo orden de complejidad aplicándose en 27 casillas posibles.
Nos supone, tratándose de...