El árbol de tecnologías

En resumen: Las tecnologías son nodos y los requisitos son flechas hacia ellas: un grafo dirigido sin ciclos. Una tecnología está libre cuando todos sus requisitos son conocidos; el orden topológico coloca todo de modo que cada una vaya después de sus requisitos, y un ciclo lo hace imposible.

Problema

Doce tecnologías hasta la Puerta Estelar

En Epic Cosmos la victoria por ciencia es la tecnología Puerta Estelar. No se investiga desde cero: necesita Acorazados y Rutas comerciales, los Acorazados necesitan Cañones de plasma y Nanoblindaje, y estos necesitan Fusión nuclear y más. El jugador se hace tres preguntas:

1. ¿Qué puedo investigar ahora? No todo: una tecnología está bloqueada hasta que todos sus requisitos son conocidos.
2. ¿En qué orden llego a la meta? Y cuánta ciencia costará el camino.
3. ¿Puede la tabla estar mal? Si dos tecnologías se esperan una a otra, nada puede empezar.

Esta es la pantalla tech del juego (de la partida con la que se comprueba el juego). + es conocida, > se investiga ahora, * se puede investigar, . está bloqueada; la última línea cuenta el camino hasta la Puerta Estelar:

Turno 24/150  Imperio Terrano (A)                      puntos 93
M25+16 G173+30 C0+16 U47+3  ciencia +10
Investiga: Fortalezas orbitales 13/42
Tecnologías (+ conocida, > ahora, * posible, . bloqueada)
+  1 drill    Perforación profunda    17  -
+  2 weapons1 Láseres                 21  -
+  3 hulls1   Blindaje ligero         21  -
+  4 lab2     Laboratorios cuánticos  35  drill
*  5 fusion   Fusión nuclear          49  lab2,weapons1
*  6 torpedo  Torpedos                31  weapons1
*  7 cruiser  Cascos de crucero       31  hulls1
*  8 trade    Rutas comerciales       35  drill
>  9 fortress Fortalezas orbitales    42  hulls1,drill
. 10 weapons2 Cañones de plasma       71  fusion,torpedo
. 11 hulls2   Nanoblindaje            71  fusion,cruiser
. 12 dread    Acorazados             107  weapons2,hulls2
. 13 stargate Puerta estelar         249  dread,trade
Hasta la Puerta Estelar: 8 tecnologías, 644 de ciencia, acumulad
Columnas: número, nombre, precio, requisitos.

La lección construye estas tres respuestas con programas pequeños sobre la misma tabla, y al final muestra lo mismo en el juego. Que los datos son una tabla de texto y no código se ve en la lección sobre las criaturas de Arcanum; aquí importa qué es la tabla como estructura.

La idea

Una tabla de requisitos

Una tecnología es una fila de una tabla: un número, un nombre, un precio en puntos de ciencia y requisitos, una lista de otros números. El juego guarda la tabla como texto y la lee al empezar, así que una tecnología nueva es una fila nueva, no código nuevo. Esta es la misma tabla tal como la cargan los programas de la lección (el juego tiene más columnas: los nombres en los otros idiomas, el efecto y su valor):

# id|nombre|precio|requisitos
drill|Perforación profunda|17|-
weapons1|Láseres|21|-
hulls1|Blindaje ligero|21|-
lab2|Laboratorios cuánticos|35|drill
fusion|Fusión nuclear|49|lab2,weapons1
torpedo|Torpedos|31|weapons1
cruiser|Cascos de crucero|31|hulls1
trade|Rutas comerciales|35|drill
fortress|Fortalezas orbitales|42|hulls1,drill
weapons2|Cañones de plasma|71|fusion,torpedo
hulls2|Nanoblindaje|71|fusion,cruiser
dread|Acorazados|107|weapons2,hulls2
stargate|Puerta estelar|249|dread,trade

Tres de las trece (drill, weapons1, hulls1) no tienen requisitos (-), y stargate necesita dos. Las filas con # son notas. Una fila se convierte en un objeto:

class Tech:
    def __init__(self, id, name, cost, prereqs):
        self.id = id
        self.name = name
        self.cost = cost
        self.prereqs = prereqs


def load(text):
    techs = {}
    for line in text.split("\n"):
        if line.strip() == "" or line.startswith("#"):
            continue
        c = line.split("|")
        prereqs = [] if c[3] == "-" else c[3].split(",")
        techs[c[0]] = Tech(c[0], c[1], int(c[2]), prereqs)
    return techs

load recorre las líneas, salta las vacías y las notas, corta por | y guarda las tecnologías en el orden de la tabla. El orden importa: por eso la colección es ordenada (LinkedHashMap en Java, Dictionary en C#, dict en Python, Map en JavaScript), para que los programas de los cuatro lenguajes impriman lo mismo.

dict en Python conserva el orden de inserción por especificación desde la versión 3.7.

La idea

Un grafo sin ciclos

Dibuja cada tecnología como un nodo y cada requisito como una flecha del requisito a la tecnología: drill → lab2, lab2 → fusion. La tabla se convierte en un grafo dirigido: las flechas tienen sentido. El nuestro tiene 13 nodos y 16 flechas.

El grafo de tecnologías tiene otra propiedad: no tiene ciclos. Si sigues las flechas, nunca vuelves al punto de partida. Un grafo así se llama grafo dirigido sin ciclos (DAG, directed acyclic graph) y es justo la forma de «primero esto, luego aquello»: tareas con dependencias, los módulos de un proyecto, el árbol de habilidades de un RPG.

Un ciclo es esperarse unos a otros. Digamos que optics necesita lasers, lasers necesita radar, radar necesita optics:

# id|nombre|precio|requisitos
optics|Óptica|10|lasers
lasers|Láseres|10|radar
radar|Radar|10|optics

Ninguna de las tres puede ser la primera: cada una espera a otra. El juego no debe arrancar con una tabla así, por eso comprueba dos veces. Primero al cargar: cada requisito debe ser una tecnología que existe.

for tech in TECHS.values():
    for need in tech.prereqs:
        if need not in TECHS:
            raise RuntimeError('techs: unknown prerequisite ' + need)

Después en main, antes de que empiece el juego: si el orden topológico (las tarjetas siguientes) no sale, el árbol tiene un ciclo.

if topo_order() is None:
    raise RuntimeError('the tech tree has a cycle')

La idea

Qué se puede investigar ahora

El jugador conoce algunas tecnologías. Una tecnología está libre si aún no es conocida y todos sus requisitos son conocidos. El código dice lo mismo con un bucle y un retorno temprano:

def knows(known, tech_id):
    return tech_id in known


def can_research(known, tech):
    if knows(known, tech.id):
        return False
    for need in tech.prereqs:
        if not knows(known, need):
            return False
    return True


def available_techs(techs, known):
    result = []
    for tech in techs.values():
        if can_research(known, tech):
            result.append(tech)
    return result

canResearch devuelve false en cuanto ve un requisito desconocido, y si llega al final del bucle, true. Una tecnología sin requisitos tiene un bucle vacío, así que está libre desde el principio. availableTechs pregunta por cada tecnología de la tabla. El programa investiga drill, weapons1 y lab2 una por una y tras cada paso imprime qué se abre:

techs = load(TABLE)
known = []
for learn in ["", "drill", "weapons1", "lab2"]:
    if learn != "":
        known.append(learn)
    print("Conocidas: " + show(known))
    print("Se puede investigar: " + show(ids_of(available_techs(techs, known))))

Salida

Conocidas: -
Se puede investigar: drill, weapons1, hulls1
Conocidas: drill
Se puede investigar: weapons1, hulls1, lab2, trade
Conocidas: drill, weapons1
Se puede investigar: hulls1, lab2, torpedo, trade
Conocidas: drill, weapons1, lab2
Se puede investigar: hulls1, fusion, torpedo, trade

Fíjate en que fusion aparece solo al final: necesita lab2 y weapons1. Y drill desaparece de la lista en cuanto es conocida, porque canResearch empieza comprobando si ya la conoces.

def can_research(known, tech):
    if knows(known, tech.id):
        return False
    for need in tech.prereqs:
        if not knows(known, need):
            return 
    return True

Comprobar

Estas son las mismas funciones del juego. El conocimiento es la lista empire.techs, no un argumento aparte, y todo lo demás es igual:

# Las tecnologías son un grafo dirigido sin ciclos: una arista del requisito a la tecnología. El conocimiento del
# imperio es una lista de ids; "qué se puede investigar ahora" son las desconocidas cuyos requisitos
# ya son conocidos.
def knows(empire, tech_id):
    return tech_id in empire.techs


def can_research(empire, tech):
    if knows(empire, tech.id):
        return False
    for need in tech.prereqs:
        if not knows(empire, need):
            return False
    return True


def available_techs(empire):
    result = []
    for tech in TECHS.values():
        if can_research(empire, tech):
            result.append(tech)
    return result

Más precisamente, para curiosos

Las funciones listas de ahí trabajan en dos niveles: canResearch responde por una tecnología, availableTechs reúne las respuestas de todas. Así el mismo canResearch sirve a startResearch (si la investigación puede empezar) y a la inteligencia artificial que elige entre las libres (la lección sobre los rivales).

La idea

Orden topológico

¿Qué orden de investigación está permitido? Uno en el que cada tecnología va después de sus requisitos. Se llama orden topológico, y todo grafo sin ciclos tiene al menos uno. El algoritmo es simple: mientras queden sin colocar, toma la primera tecnología cuyos requisitos ya están todos colocados, dale el número siguiente y empieza de nuevo.

def topo_order(techs):
    placed = []
    done = set()
    while len(placed) < len(techs):
        pick = None
        for tech in techs.values():
            if tech.id in done:
                continue
            ready = True
            for need in tech.prereqs:
                if need not in done:
                    ready = False
            if ready:
                pick = tech
                break
        if pick is None:
            return None  # ciclo: ninguna tecnología lista
        placed.append(pick.id)
        done.add(pick.id)
    return placed

Si en algún paso no hay tal tecnología y aún quedan sin colocar, se esperan unas a otras: la función devuelve null. Así el mismo algoritmo es también una comprobación de ciclos.

El programa pone la tabla al revés (stargate va primero), para mostrar que el orden no viene de ella, y luego prueba la tabla con el ciclo:

techs = load(REVERSED)  # la tabla está al revés, pero el orden no depende de ella
order = topo_order(techs)
for i in range(len(order)):
    print(i + 1, order[i])

if topo_order(load(CYCLE)) is None:
    print("Ciclo: ninguna tecnología tiene listos todos sus requisitos.")

Salida

1 hulls1
2 cruiser
3 weapons1
4 torpedo
5 drill
6 fortress
7 trade
8 lab2
9 fusion
10 hulls2
11 weapons2
12 dread
13 stargate
Ciclo: ninguna tecnología tiene listos todos sus requisitos.

Primero sale hulls1: todas las de delante esperan algo. Después cruiser, porque hulls1 ya está colocada. Cada flecha del árbol apunta de un número menor a uno mayor, y la tabla con el ciclo devuelve null. Cuando hay varias listas, gana la primera de la tabla, así que el orden es el mismo en todas partes. Esa es también la regla del juego:

# Orden topológico (Kahn): una tecnología sale cuando sus requisitos ya han salido. Si hay
# varias listas, gana la de número menor en la tabla, por eso el orden es el mismo en todas partes.
def topo_order():
    placed = []
    done = set()
    total = len(TECHS)
    while len(placed) < total:
        pick = None
        for tech in TECHS.values():
            if tech.id in done:
                continue
            ready = True
            for need in tech.prereqs:
                if need not in done:
                    ready = False
            if ready:
                pick = tech
                break
        if pick is None:
            # Un ciclo: ninguna tecnología tiene sus requisitos listos.
            return None
        placed.append(pick.id)
        done.add(pick.id)
    return placed

La idea

Un plan hasta la meta

El jugador elige una meta, por ejemplo stargate, y quiere una lista: qué falta por investigar y en qué orden. Dos pasos.

1. Qué hace falta. Empezamos en la meta y vamos hacia atrás por las flechas con una pila: sacamos una tecnología, y si no es conocida, la anotamos en need y metemos sus requisitos en la pila. Las conocidas se saltan, así que la parte ya investigada no se paga otra vez.
2. En qué orden. need es un conjunto, sin orden. El orden viene del topológico: pasamos por topoOrder y nos quedamos solo con las necesarias.

def plan_to(techs, known, target_id):
    need = set()
    stack = [target_id]
    while len(stack) > 0:
        tech_id = stack.pop()
        if tech_id in need or knows(known, tech_id):
            continue
        need.add(tech_id)
        for pre in techs[tech_id].prereqs:
            stack.append(pre)
    plan = []
    for tech_id in topo_order(techs):
        if tech_id in need:
            plan.append(tech_id)
    return plan


def plan_cost(techs, plan):
    total = 0
    for tech_id in plan:
        total += techs[tech_id].cost
    return total

El programa planea el camino hasta la Puerta Estelar sin conocimientos y luego con drill, weapons1, hulls1 y lab2 conocidas:

techs = load(TABLE)
for known in [[], ["drill", "weapons1", "hulls1", "lab2"]]:
    plan = plan_to(techs, known, "stargate")
    print("Conocidas: " + show(known))
    print("Plan: " + show(plan))
    print(str(len(plan)) + " tecnologías, " + str(plan_cost(techs, plan)) + " de ciencia")

Salida

Conocidas: -
Plan: drill, weapons1, hulls1, lab2, fusion, torpedo, cruiser, trade, weapons2, hulls2, dread, stargate
12 tecnologías, 738 de ciencia
Conocidas: drill, weapons1, hulls1, lab2
Plan: fusion, torpedo, cruiser, trade, weapons2, hulls2, dread, stargate
8 tecnologías, 644 de ciencia

El plan sin conocimientos tiene 12 tecnologías, no 13: nadie en el camino necesita fortress. La suma 738 es lo que la pantalla del principio de la lección muestra como «Hasta la Puerta Estelar», y con cuatro conocidas quedan 8 tecnologías por 644. En el canon es igual:

# Lo que aún hay que investigar para llegar a la meta, en orden topológico.
def plan_to(empire, target_id):
    need = set()
    stack = [target_id]
    while len(stack) > 0:
        tech_id = stack.pop()
        if tech_id in need or knows(empire, tech_id):
            continue
        need.add(tech_id)
        for pre in TECHS[tech_id].prereqs:
            stack.append(pre)
    plan = []
    for tech_id in topo_order():
        if tech_id in need:
            plan.append(tech_id)
    return plan


def plan_cost(plan):
    total = 0
    for tech_id in plan:
        total += TECHS[tech_id].cost
    return total

Míralo

El árbol en movimiento

La escena recorre las tres respuestas: qué se abre tras cada tecnología investigada, el orden para la tabla al revés y el recorrido hacia atrás desde la Puerta Estelar. Sigue el color de los marcos (verde es libre, azul es conocida, naranja es necesaria) y los números de las insignias:

def plan_to(techs, known, target_id):
    need = set()
    stack = [target_id]
    while len(stack) > 0:
        tech_id = stack.pop()
        if tech_id in need or knows(known, tech_id):
            continue
        need.add(tech_id)
        for pre in techs[tech_id].prereqs:
            stack.append(pre)
    plan = []
    for tech_id in topo_order(techs):
        if tech_id in need:
            plan.append(tech_id)
    return plan

Paso a paso, en palabras

1. Trece tecnologías. Una flecha va del requisito a la tecnología: lab2 necesita drill, fusion necesita lab2 y weapons1. El número bajo el nombre es el precio.
2. Nada está investigado. drill, weapons1 y hulls1 no tienen requisitos: el bucle no encuentra ninguno desconocido y canResearch devuelve true. Solo ellas están libres (verde).
3. Investigas drill (azul). Ahora lab2 y trade necesitan solo drill y están libres. fortress necesita también hulls1, así que espera. drill ya no está en la lista: ya es conocida.
4. Investigas weapons1: torpedo se desbloquea. fusion necesita lab2 y weapons1: weapons1 ya es conocida, lab2 todavía no, así que el bucle devuelve false en lab2.
5. Investigas lab2: ahora fusion tiene los dos requisitos y está libre. Un requisito que falta mantiene bloqueada la tecnología; todos listos la abren.
6. Otra pregunta: ¿en qué orden investigamos todo? La tabla está al revés (stargate va primero), pero el orden no sale de ella. topoOrder recorre la tabla y toma la primera tecnología cuyos requisitos están todos colocados.
7. stargate, dread y las demás de delante esperan requisitos. La primera lista es hulls1 (sin requisitos): recibe el número 1.
8. Tras cada número la búsqueda empieza de nuevo: ahora cruiser está lista, porque hulls1 ya está colocada. Las colocadas se saltan.
9. La última es stargate, número 13: esperaba a dread y trade. Cada flecha apunta de un número menor a uno mayor: ese es el orden topológico. Si en algún paso no hay ninguna tecnología lista, hay un ciclo y la función devuelve null.
10. Un plan hasta stargate. Empezamos en la meta y vamos hacia atrás por las flechas con una pila: sacamos una tecnología y metemos sus requisitos. Todo lo alcanzado entra en need (naranja).
11. fortress nunca se alcanzó: ninguna tecnología en el camino hasta stargate la necesita. No entra en el plan. Las conocidas se saltan, así que lo ya investigado no se paga otra vez.
12. El recorrido solo dice qué hace falta. El orden viene del topológico: planTo pasa por topoOrder y se queda con las necesarias. Así el plan tiene 12 tecnologías en un orden en que cada una va después de sus requisitos.
13. 12 tecnologías, 738 de ciencia: la suma de los precios. fortress (42) no hace falta. El juego muestra el mismo número en la pantalla tech como «Hasta la Puerta Estelar».

El grafo es el mismo en las tres partes. Solo cambia la pregunta que se le hace: qué está libre (una mirada hacia delante desde las conocidas), en qué orden (colocar todo) y hasta dónde (una mirada hacia atrás desde la meta).

Pruébalo

Predice la salida

Una tabla pequeña: sensors no tiene requisitos, engines y shields necesitan sensors, warp necesita las dos, beacon necesita warp. Son conocidas sensors y engines. ¿Qué imprime el programa?

SMALL = """
# id|nombre|precio|requisitos
sensors|Sensores|10|-
engines|Motores|12|sensors
shields|Escudos|12|sensors
warp|Salto|20|engines,shields
beacon|Baliza|25|warp
"""

techs = load(SMALL)
known = ["sensors", "engines"]
print(show(ids_of(available_techs(techs, known))))

Respuesta

shields

shields, warp

engines, shields

Comprobar

Pruébalo

Encuentra el error

Un compañero copió canResearch y puso el nombre equivocado en la comprobación de los requisitos. Esto es lo que imprime el programa con solo drill conocida; si fuera correcto, aquí estarían también lab2 y trade:

def can_research(known, tech):
    if knows(known, tech.id):
        return False
    for need in tech.prereqs:
        if not knows(known, tech.id):
            return False
    return True


techs = load(TABLE)
known = ["drill"]
print("Conocidas: " + show(known))
print("Se puede investigar: " + show(ids_of(available_techs(techs, known))))

Salida

Conocidas: drill
Se puede investigar: weapons1, hulls1

¿Qué línea tiene la culpa?

Elige la línea con el error.

1def can_research(known, tech):2 if knows(known, tech.id):3 return False4 for need in tech.prereqs:5 if not knows(known, tech.id):6 return False7 return True8910techs = load(TABLE)11known = ["drill"]12print("Conocidas: " + show(known))13print("Se puede investigar: " + show(ids_of(available_techs(techs, known))))

Comprobar

Más precisamente

Lo que este sistema deja fuera

El árbol del juego tiene pocas reglas, y detrás de ellas hay decisiones.

Todos los requisitos, no «alguno de». canResearch devuelve false en el primer desconocido. Algunos juegos permiten «esto o aquello»: entonces un requisito es un grupo, y la tecnología se abre cuando se cumple uno de los grupos. Eso es otro grafo (con dos clases de flechas), no otra función.

El orden en un empate forma parte de la regla. Muchas tecnologías pueden estar listas a la vez, y cualquier disposición es correcta. El canon toma la primera de la tabla, para que salga el mismo orden en todos los lenguajes y en cada ejecución. Si el orden dependiera del orden de inserción de una tabla hash, los programas de dos lenguajes podrían diferir.

El algoritmo topológico de aquí es el más simple, no el más rápido. topoOrder recorre la tabla desde el principio para cada número: con n tecnologías son unas n² comprobaciones. Con trece no es nada. Con miles (dependencias de paquetes) se usa el algoritmo de Kahn, con un contador de requisitos pendientes por tecnología y una cola con las listas: O(V + E). Esa es la lección sobre la ordenación topológica, y recorrer un grafo con una pila está en la lección de DFS.

El efecto de una tecnología es otro trabajo. Aquí una tecnología es solo un nodo con un precio. Lo que da (más producción, ataque, una nave nueva) está en otras columnas de la tabla, y techMods suma los efectos de todas las conocidas; qué nave necesita qué está en la lección sobre las flotas.

El ciclo se detecta al empezar, no durante el juego. La tabla es parte del código del juego, no una entrada del jugador. Por eso la comprobación es una llamada a topoOrder en main. Si la tabla viniera de un usuario (un mod), la misma comprobación sería un mensaje de error para él, no una caída del juego.

Ejercicio

Un plan para una tabla dada

Resuélvelo en tu editor.

Un plan para una tabla dada. El programa lee tres cosas de la entrada: en la primera línea la meta, en la segunda las tecnologías conocidas separadas por comas (o - si no hay), y en cada línea siguiente una tecnología con la forma id precio requisitos (los requisitos separados por comas, - si no hay). La tabla está en orden topológico, pero el programa no debe apoyarse en eso. Imprime el plan (solo las tecnologías necesarias sin colocar, en orden topológico) y la suma de los precios.

Con la entrada warp | sensors | sensors 10 - | engines 12 sensors | shields 12 sensors | warp 20 engines,shields | beacon 25 warp (una por línea) la salida es:

Salida

Plan: engines, shields, warp
Precio: 44

Ojo: sensors es conocida, así que no está en el plan y no se paga; warp es la meta y va la última del plan.

Más ejercicios

• Un ciclo en la tabla. Da una tabla en la que a necesita b y b necesita a. ¿Qué hace planTo con un topoOrder que devuelve null? Haz que el programa diga que hay un ciclo en vez de caerse.
• Un requisito desconocido. Añade una fila con un requisito que no está en la tabla. Atrápalo al cargar, como lo hace loadData.
• ¿Qué desbloquea esta? Escribe unlocks(techs, id), que devuelve las tecnologías que necesitan id como requisito. Es un recorrido hacia delante por las flechas.
• La primera jugada más barata. Entre las tecnologías libres elige la de menor precio. ¿Qué pasa si dos cuestan lo mismo?

Test

Ponte a prueba

1. ¿Por qué la tabla de tecnologías no debe tener un ciclo, por ejemplo optics necesita lasers, lasers necesita radar, radar necesita optics?

Porque un ciclo hace la tabla más lenta de leerPorque una tecnología puede necesitar como máximo un requisitoCada una de las tres espera a otra de ellas, así que ninguna puede ser la primera y ninguna llega nunca a estar «libre». El juego lo comprueba al empezar y no arranca con una tabla así

2. fusion necesita lab2 y weapons1. Son conocidas drill y weapons1. ¿Se puede investigar fusion?

No: lab2 aún no es conocida, y hacen falta todos los requisitosSí: weapons1 es conocida, y un requisito bastaSí: drill lleva a lab2

3. En el programa topo la tabla está al revés (stargate va primero). ¿Por qué topoOrder da igualmente un orden correcto?

No sigue el orden de la tabla, sino que toma la primera tecnología cuyos requisitos ya están todos colocados, y empieza de nuevo. La tabla solo decide cuál gana cuando hay varias listasPrimero ordena la tabla por precioNo lo da: solo hay un orden correcto si la tabla ya está ordenada

4. ¿Por qué fortress no entra en el plan hasta stargate?

Porque tiene dos requisitosNinguna tecnología en los caminos hacia atrás desde stargate la necesita: es una hoja a la que el recorrido nunca llegaPorque es la tecnología más barata

5. topoOrder devolvió null. ¿Qué significa para la tabla?

Alguna tecnología necesita un requisito que no existeLa tabla está vacíaHay un ciclo: en algún paso ninguna tecnología sin colocar tiene todos sus requisitos colocados

Comprobar

Empezar la lección de nuevo

Lecciones relacionadas

• Se basa en: Lo que comparten todos los objetos: atributos de clase · Cadenas · Listas: append, remove y sort · dict y set
• Ejercicios sobre el tema: Epic Cosmos: el imperio