Rilevare conservazione, perdita o guadagno in un gioco di creazione con oggetti e ricette

Question

Supponiamo di progettare un gioco come Minecraft dove abbiamo molti articoli $i_1,i_2,...,i_n\in I$ e un sacco di ricette $r_1,r_2,...,r_m\in R$.Le ricette sono funzioni $r:(I\volte\mathbb{N})^n ightarrow I\volte\mathbb{N}$, ovvero prendono alcuni articoli con pesi interi non negativi e producono una quantità intera di un altro articolo.

Ad esempio, la ricetta della torta in Minecraft È:

3 latte + 3 grano + 2 zucchero + 1 uovo $\frecciadestra$ 1 torta

...e la ricetta delle torce è:

1 bastoncino + 1 carbone $\frecciadestra$ 4 torce

Alcune ricette potrebbero anche essere reversibili, ad esempio:9 diamanti $\frecciasinistradestra$ 1 blocco di diamanti

Se c'è una combinazione di ricette che possiamo applicare ripetutamente per ottenere più oggetti con cui abbiamo iniziato, il gioco è scarsamente bilanciato e questo può essere sfruttato dai giocatori.È più auspicabile progettare il gioco con ricette che conservino oggetti o possibilmente ne perdano alcuni (entropia termodinamica nel mondo reale: non puoi facilmente ricombustione del toast).

Esiste un algoritmo efficiente in grado di decidere se un insieme di ricette:

• conservare gli oggetti?
• perdere oggetti per inefficienza?
• ottenere oggetti?

Esiste un algoritmo efficiente in grado di trovare le ricette problematiche se un gioco è sbilanciato?

Il mio primo pensiero è che qui esiste un problema di struttura del grafico/flusso massimo, ma è molto complesso e assomiglia a un problema con lo zaino.O forse potrebbe essere formulato come un problema SAT: questo è ciò che sto pensando di codificarlo al momento, ma potrebbe esistere qualcosa di più efficiente.

Potremmo codificare le ricette in una matrice $\mathbf{R}^{m imes n}$ dove le righe corrispondono alle ricette e le colonne corrispondono agli articoli.Le voci di colonna sono negative se un articolo viene consumato da una ricetta, positive se è prodotto dalla ricetta e zero se non viene utilizzato.Similmente a un metodo a matrice ben noto per il rilevamento del ciclo del grafico, potremmo aumentare $\mathbf{R}$ a una certa potenza elevata e ottieni le somme di ogni riga per vedere se i totali degli elementi continuano a salire, rimangono in equilibrio o diventano negativi.Tuttavia, non sono sicuro che funzioni sempre.

Qualsiasi discussione, codice o lettura consigliata è molto apprezzata.

Answer 1

Questo dovrebbe essere risolvibile con la programmazione lineare.

Contesto e configurazione

Lascia che il vettore di stato sia un vettore del conteggio del numero di ciascun elemento che hai.Se gli oggetti possibili sono latte, grano, zucchero, uova, torta, diamanti, allora vale la regola

3 latte + 3 grano + 2 zucchero + 1 uovo $\frecciadestra$ 1 torta

influenza il vettore di stato aggiungendo $(-3,-3,-2,-1,1,0)$ ad esso.Quindi, lasciamo $a_i$ denotano il vettore di cambiamento per il $i$esima regola.

Guadagnare oggetti

Sostengo che esiste un modo per ottenere elementi senza limiti se e solo se esiste una soluzione fattibile al programma lineare

$$a_1 x_1 + \dots + a_n x_n \ge (0,0,\dots,0), ​​x_1 \ge 0, \dots, x_n \ge 0$$

tale che $a_1 x_1 + \punti + a_n x_n>(0,0,\punti,0)$.Qui $\ge$ è definito sui vettori puntualmente (cioè, $u \ge v$ eff $u_i\ge v_i$ vale per tutti $i$) e analogamente per $>$.Questo può essere espresso come un programma lineare:massimizzi la somma delle coordinate di $a_1 x_1 + \punti + a_n x_n$, fatte salve le disuguaglianze di cui sopra.Pertanto, puoi risolverlo in tempo polinomiale utilizzando un risolutore di programmazione lineare.Questo ti dice se esiste un modo per ottenere qualche oggetto senza limiti.

Perché l'affermazione è vera?Bene, se esiste una soluzione fattibile al programma lineare, allora fornisce un modo per aumentare il numero di alcuni elementi senza limiti.In particolare, se inizi con un numero molto elevato di ciascun articolo, applica la regola 1 $x_1$ volte, regola 2 $x_2$ volte, ecc., ti ritroverai con un nuovo vettore di stato che differisce da quello da cui hai iniziato $a_1 x_1 + \punti + a_n x_n$, che è almeno altrettanto grande in ciascuna componente ed è strettamente maggiore in almeno una componente.Inoltre, se si inizia con un numero sufficientemente elevato di elementi, non si “andrà mai in negativo” in nessun passaggio intermedio di applicazione delle regole.Nota che se c'è una soluzione a questo programma lineare, c'è una soluzione nei razionali, che produce una soluzione negli interi (moltiplica per la costante appropriata per eliminare i denominatori).

Al contrario, se esiste un metodo per aumentare il numero di alcuni elementi senza limiti, allora esiste una soluzione al programma lineare:lascialo e basta $x_i$ contare il numero di volte in cui regola $i$ viene applicato in quel metodo e vedrai che questo produce una soluzione valida per il programma lineare.

Perdere oggetti

Credo che esista un'equivalenza simile:esiste un modo per perdere elementi senza limiti se e solo se esiste una soluzione fattibile al programma lineare

$$a_1 x_1 + \dots + a_n x_n \le (0,0,\dots,0), ​​x_1 \ge 0, \dots, x_n \ge 0$$

tale che $a_1 x_1 + \punti + a_n x_n<(0,0,\punti,0)$.Dovresti controllare il mio ragionamento perché non l'ho controllato attentamente.

Conservazione

Infine, se non c'è modo di guadagnare oggetti senza limiti o di perdere oggetti senza limiti, allora penso che ne consegua che il valore viene conservato.

Answer 2

Il tuo problema equivale a chiedere se esiste una combinazione lineare di vettori di riga dal tuo $\mathbb R^{m\volte n}$ matrice che ha tutti i coefficienti positivi e la cui somma dà un vettore in cui (a) si trova ogni elemento $\ge 0$ e (b) almeno un elemento lo è $> 0$.

(Si noti che il ordine delle operazioni non ha importanza:Eseguirli in un certo ordine potrebbe far sì che la quantità di alcuni articoli scenda sotto lo zero, ma possiamo semplicemente cercare il limite minimo e supporre di avere almeno quel numero di ciascun articolo con cui iniziare.)

Penso che questo possa essere risolto con la programmazione lineare:Crea una variabile per ciascun coefficiente, aggiungi $\ge 0$ vincoli per ciascun elemento nel vettore di output (ogni elemento è un prodotto scalare di coefficienti variabili e coefficienti costanti delle ricette), più $\ge 0$ vincoli per ciascuna variabile di coefficiente e impostare la funzione da massimizzare in modo che sia la somma di tutti gli elementi.Per renderlo limitato, imposta la somma delle variabili dei coefficienti su una costante, ad es.1.Se e solo se il valore della soluzione è $> 0$, hai non conservazione!

Tieni presente che i valori frazionari non sono un problema:Devono essere razionali, quindi puoi sempre moltiplicare per tutti i denominatori per ottenere una soluzione intera pura.