Texto y documentos
Números y cálculo
Datos y formatos
Seguridad
Desarrollo y DevOps
Inteligencia Artificial
Finanzas
Salud y bienestar
Productividad
Juegos y entretenimiento
Multimedia y diseño
Empresa
Guía de uso
Cómo se usa

Pulsa Play y mira cómo busca el algoritmo: en azul claro lo que ya ha mirado (expandido), en amarillo lo que tiene pendiente (la frontera) y, al final, en azul el camino. Pinta paredes o barro arrastrando sobre la cuadrícula, y mueve el inicio y la meta.

En qué se diferencian

Todos hacen lo mismo: sacan una casilla de la frontera, la expanden y meten sus vecinas. Solo cambia CUÁL sacan. Anchura, la más antigua (menos pasos). Profundidad, la más nueva (encuentra algo, rara vez lo mejor). Coste uniforme, la más barata hasta ahora (el camino más barato). Voraz, la que parece más cerca de la meta (rápido, pero se deja engañar). A*, la que suma lo gastado y lo que parece faltar: el más barato mirando menos.

Palillos y Nim: juegos resueltos enteros

En la pestaña Juego, los palillos y el Nim son tan pequeños que la máquina los resuelve enteros: sabe desde el principio quién gana con juego perfecto. El árbol muestra, para cada posición, quién gana desde ella; y la búsqueda acaba encontrando la misma regla que un humano puede aprender (los múltiplos de 4 en los palillos, la suma nim en el Nim). Fíjate en la diferencia entre los nodos del árbol (millones) y las posiciones distintas (unas pocas): recordar lo ya resuelto, una tabla de transposición, es lo que hace que todo vaya al instante.

Damas y ajedrez: cómo miran menos los motores de verdad

En las damas, cada jugada de la máquina se mide cinco veces a la misma profundidad: sin poda, con poda, ordenando las jugadas, con tabla de transposición y con las tres. El valor sale igual; las posiciones miradas, no. En el ajedrez pequeño, la lección es el efecto horizonte: si la búsqueda se para a mitad de un cambio de piezas, la máquina cree que gana lo que acaba de comer. La búsqueda de quietud sigue mirando capturas hasta que la posición está tranquila; puedes quitarla y comparar lo que habría jugado.

Hex y Monte Carlo Tree Search

Hex no cabe en minimax: hay demasiadas posiciones y una buena heurística es difícil de escribir. MCTS no la necesita: para valorar una jugada, juega muchas partidas al azar desde ella y cuenta cuántas gana. UCT decide a qué jugada dedicar la siguiente partida, equilibrando las que van ganando con las poco probadas. Con más partidas juega mejor, y es la base de los programas que ganan al Go (AlphaGo y AlphaZero añadieron una red neuronal que guía la búsqueda).

Portales y dirección única

Un portal te lleva a su pareja (se emparejan por orden). Con portales, la distancia Manhattan ya no es una cota de lo que falta: puede haber un atajo «mágico». A* deja de garantizar el camino más barato, porque su heurística ya no es admisible, y en el ejemplo da 19 cuando hay uno de 10. Una casilla de dirección única solo deja salir hacia su flecha: el mapa pasa a ser un grafo dirigido, y poder ir de A a B no significa poder volver.

El peso de A*

Con peso 1, A* da siempre el camino más barato, porque la distancia en línea (Manhattan) nunca se pasa de lo que falta de verdad. Al subirlo, confía más en esa estimación: mira menos casillas, pero puede dejar de dar el mejor camino. Con un peso muy alto se comporta como el voraz.

Búsqueda: caminos y juegosCómo busca una IA: anchura, A* y minimax, paso a paso
Búsqueda: caminos y juegosCómo busca una IA: anchura, A* y minimax, paso a paso

Saca la que menos suma entre lo gastado y lo que parece faltar (g + peso·h). Con peso 1, el camino más barato mirando menos casillas.

Pasar con el mismo pincel por encima de lo pintado lo borra.

0 expandidos · 1 en la frontera

Pulsa Play para ver la búsqueda, o «Hasta el final» para el resultado de golpe.

Los cinco sobre esta misma cuadrícula
AlgoritmoExpandidasPasosCoste
10318 18
2120 20
10318 18
3120 20
6218 18