💻 computer science

An ASP-based approach to Solving General Stochastic Two-Player Games

Questo articolo introduce la Programmazione per Insiemi di Risposte Stocastica (SQASP) come il primo approccio basato su ASP per risolvere giochi a due giocatori con turni alternati descritti nel Linguaggio di Descrizione Generale dei Giochi (GDL) con incertezza, dimostrandone la competitività rispetto alla ricerca in avanti su piccoli giochi stocastici e il potenziale per la valutazione delle fasi finali.

Autori originali: Yifan He, Michael Thielscher

Pubblicato 2026-05-25

📖 6 min di lettura🧠 Approfondimento

CC BY 4.0

Autori originali: Yifan He, Michael Thielscher

Articolo originale sotto licenza CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Questa è una spiegazione generata dall'IA dell'articolo qui sotto. Non è stata scritta né approvata dagli autori. Per precisione tecnica, consulta l'articolo originale. Leggi il disclaimer completo

Immagina di dover insegnare a un computer come giocare a un gioco da tavolo. Di solito, questi giochi sono come gli scacchi: fai una mossa, il tuo avversario ne fa una e la scacchiera cambia in modo prevedibile. Ma cosa succederebbe se il gioco includesse anche una "jolly"? Cosa succederebbe se, dopo la tua mossa, un lancio di dado magico decidesse se la tua mossa funziona, o se un terzo giocatore invisibile (chiamiamolo "Casuale") gettasse un cuneo negli ingranaggi?

Questo articolo tratta dell'insegnamento ai computer di come risolvere questi giochi complicati e imprevedibili. Gli autori, Yifan He e Michael Thielscher, hanno costruito un nuovo kit matematico per determinare la strategia migliore possibile quando è coinvolta la fortuna.

Ecco la spiegazione del loro approccio utilizzando semplici analogie:

1. Il Problema: Il Giocatore "Casuale"

Nella teoria dei giochi standard, i computer sono eccellenti nel calcolare la mossa perfetta contro un avversario intelligente. Ma quando si aggiunge la casualità (come lanciare dadi o pescare carte), la matematica diventa complicata.

Il Vecchio Metodo: I precedenti programmi informatici potevano gestire giochi con due giocatori intelligenti (come gli scacchi) o giochi con un solo giocatore e un elemento casuale (come il Solitario). Non potevano gestire un gioco con due giocatori intelligenti E un elemento casuale contemporaneamente.
L'Obiettivo: Gli autori volevano risolvere i "Giochi Stocastici Generali a Due Giocatori". Immaginalo come un gioco del Tris in cui, ogni volta che cerchi di posizionare una X, c'è il 30% di probabilità che la casella diventi una O invece, o il 50% di probabilità che la mossa venga bloccata completamente.

2. Il Nuovo Strumento: SQASP (La "Mappa Magica")

Gli autori hanno inventato un nuovo linguaggio chiamato Stochastic Answer Set Programming (SQASP).

L'Analogia: Immagina di essere un architetto che progetta una casa. Hai una pianta (le regole del gioco). In passato, potevi progettare case solo per due tipi specifici di costruttori: uno che è un genio strategico (l'avversario) e uno che è un robot che segue regole rigide.
L'Innovazione: SQASP è come un nuovo tipo di pianta che può descrivere un cantiere in cui hai un Genio Strategico, un Robot e un Giocatore d'Azzardo che lavorano tutti insieme.
- Il Genio (Giocatore X) vuole vincere.
- L'Avversario (Giocatore O) vuole fermare il Giocatore X.
- Il Giocatore d'Azzardo (Casuale) lancia una moneta per decidere cosa succede dopo.
SQASP permette al computer di chiedere: "Qual è la massima probabilità possibile che ho di vincere, assumendo che il mio avversario giochi perfettamente per fermarmi e che il Giocatore d'Azzardo faccia ciò che vuole?"

3. Il Traduttore: Trasformare le Pianta in un Enigma

I computer non parlano "Pianta". Parlano "Enigmi Logici".

Il Processo: Gli autori hanno costruito un traduttore (uno strumento chiamato sqasp2xssat). Prende la loro sofisticata pianta SQASP e la converte in un enorme enigma logico chiamato Soddisfacimento Stocastico Esteso (XSSAT).
La Metafora: Pensa a SQASP come a una ricetta complessa per una torta. Il traduttore è una macchina che trasforma quella ricetta in un gigantesco Sudoku a più livelli. Una volta risolto l'enigma, la risposta ti dice la probabilità esatta di vincere il gioco.
Il Risolutore: Hanno utilizzato un risolutore esistente (SharpSSAT) per risolvere questo Sudoku. Se il risolutore dice "Sì, questo enigma può essere risolto", significa che il giocatore ha una strategia vincente. Se calcola una probabilità del 67%, quello è il miglior risultato possibile.

4. Il Trucco dello "Spostamento dei Quantificatori"

L'articolo ha anche testato una specifica tecnica di ottimizzazione chiamata Spostamento dei Quantificatori.

L'Analogia: Immagina di organizzare un torneo.
- Metodo A (Baseline): Elenchi ogni singola mossa di ogni giocatore, poi controlli se le mosse sono legali, poi controlli se il gioco è finito.
- Metodo B (Spostamento): Controlli se le mosse sono legali prima ancora di elencare le mosse. Questo sembra più veloce perché non perdi tempo a pianificare mosse illegali.
Il Risultato: Nei giochi con due giocatori intelligenti (giochi deterministici), questo trucco dello "Spostamento" è un enorme aumento di velocità. Tuttavia, gli autori hanno scoperto che nei giochi con il "Giocatore d'Azzardo" (giochi stocastici), questo trucco non ha fatto molta differenza.
Perché? Il risolutore che hanno utilizzato (SharpSSAT) è molto intelligente. Ha un "detective" integrato (chiamato propagazione delle unità) che individua le mosse illegali da solo, indipendentemente dall'ordine in cui hai dato le istruzioni. Quindi, il riordinamento sofisticato non era necessario per questo specifico risolutore.

5. I Risultati: Come Ha Performato?

Il team ha testato il loro sistema su varianti di giochi classici come Tris, Connect-4 e Nim, ma con l'aggiunta del giocatore "Casuale".

Prestazioni: Il loro nuovo metodo è stato competitivo rispetto ai metodi standard di "ricerca in avanti" (che sono come un computer che gioca il gioco milioni di volte nella sua testa per vedere cosa succede).
Il Rovescio della Medaglia: Ha funzionato benissimo su piccole scacchiere (come 3x3 o 4x4). Tuttavia, quando il gioco diventava troppo grande (come un mucchio di 100 pezzi in Nim), l'enigma logico diventava troppo enorme perché il computer potesse risolverlo in un tempo ragionevole.
La Conclusione: Il metodo è eccellente per la valutazione del finale di partita. Se una partita è quasi finita, questo sistema può dire a un'intelligenza artificiale generale per i giochi: "Ehi, se fai questa mossa, hai il 99% di probabilità di vincere", aiutandola a prendere la decisione finale.

Riassunto

Gli autori hanno creato un nuovo modo per descrivere matematicamente i giochi in cui fortuna e strategia si scontrano. Hanno trasformato queste descrizioni in enigmi logici che un computer può risolvere per trovare le "migliori probabilità possibili" di vincere. Sebbene non sia una soluzione magica per ogni dimensione di gioco, dimostra che possiamo utilizzare la programmazione logica per risolvere giochi complessi e incerti, offrendo ai computer un modo migliore per pensare al futuro in un mondo caotico.

Cosa NON hanno affermato:

Non hanno affermato che questo funziona per giochi in cui non puoi vedere l'intera scacchiera (come il Poker o il Tris-Krieg). Affermano esplicitamente che il loro metodo è per giochi in cui tutti vedono l'intera scacchiera (informazione perfetta).
Non hanno affermato che questo sostituirà immediatamente tutti gli altri metodi di IA; hanno notato che è un'alternativa per scenari specifici, in particolare i finali di partita.

Riepilogo Tecnico: Un Approccio basato su ASP per la Risoluzione di Giochi Stocastici Generali a Due Giocatori

Enunciato del Problema

I sistemi di Gioco Generale (GGP) mirano a giocare a giochi strategici basandosi su descrizioni a runtime senza conoscenze preliminari delle regole. Il Linguaggio di Descrizione dei Giochi (GDL) e la sua estensione GDL-II sono i formalismi standard per specificare tali giochi, con GDL-II che supporta la casualità (stocasticità) e l'osservabilità parziale. Sebbene la Programmazione per Risposte di Insiemi (ASP) sia stata applicata con successo alla risoluzione di giochi GDL deterministici a uno e due giocatori, gli attuali framework ASP mancano della capacità di esprimere simultaneamente comportamenti avversariali (minimax) e stocastici. Di conseguenza, esiste un vuoto nell'uso di metodi basati su ASP per risolvere giochi GDL a due giocatori con turni che coinvolgono incertezza.

Metodologia

Gli autori propongono un approccio innovativo per risolvere giochi GDL stocastici a due giocatori introducendo un nuovo linguaggio e un solver basato sulla traduzione.

1. Programmazione per Risposte di Insiemi Quantificata Stocastica (SQASP)

Per colmare il divario tra ASP e la risoluzione di giochi stocastici, il documento introduce SQASP, un linguaggio che estende QASP (ASP Quantificata) con quantificatori di probabilità.

Sintassi: Un programma SQASP assume la forma $Q_1.x_1 \dots Q_n.x_n \ P$ , dove $P$ è un programma logico normale e i quantificatori $Q_i$ possono essere esistenziali ( $\exists$ ), universali ( $\forall$ ) o di probabilità ( $\mathcal{R}_{p}$ ).
Semantica: La probabilità massima di soddisfare un programma SQASP è definita ricorsivamente. Il quantificatore di probabilità $\mathcal{R}_{p}$ assegna una probabilità $p$ a una variabile di essere vera, calcolando il valore atteso basato sulle probabilità delle sotto-formule.
Traduzione: Gli autori implementano uno strumento, sqasp2xssat, che traduce programmi SQASP in formule di Soddisfacibilità Stocastica Estesa (XSSAT). XSSAT estende le Formule Booleane Quantificate (QBF) con quantificatori di probabilità. La traduzione sfrutta strumenti esistenti (come lp2sat) per convertire il programma logico $P$ in una formula CNF $\psi$ i cui modelli corrispondono ai modelli stabili di $P$ .

2. Codifica dei Giochi GDL in SQASP

Il contributo principale è la costruzione di un programma SQASP $\Psi$ tale che la sua probabilità massima di soddisfacibilità sia uguale alla probabilità massima di vittoria di un giocatore $x$ entro $n$ passi ( $P_x^w(S_0, n)$ ). La codifica procede in due fasi principali:

Baseline Cooperativa: In primo luogo, viene costruito un programma logico $P_c$ assumendo che tutti i giocatori (incluso l'avversario $o$ e il giocatore casuale $r$ ) cooperino per raggiungere uno stato terminale in cui $x$ vince. Ciò garantisce una progressione valida del gioco, la terminazione entro $n$ passi e il raggiungimento dello stato obiettivo.
Modellazione Avversariale e Stocastica: Il programma viene quindi esteso per catturare i comportamenti specifici dell'avversario e dell'ambiente:
- Giocatore Avversario ( $o$ ): Modellato utilizzando la quantificazione universale ( $\forall$ ) sulle variabili decisionali (dec_o). Ciò costringe il solver a considerare lo scenario peggiore in cui l'avversario minimizza la probabilità di vittoria di $x$ . La codifica utilizza una rappresentazione logaritmica delle azioni per ridurre il numero di regole.
- Giocatore Stocastico ( $r$ ): Modellato utilizzando quantificatori di probabilità ( $\mathcal{R}_{1/i}$ ). La codifica garantisce che, se il gioco non è terminato, il giocatore casuale selezioni esattamente un'azione legale uniformemente tra le mosse legali disponibili. Ciò è ottenuto contando le azioni legali e applicando vincoli di probabilità alle variabili decisionali (dec_r).

3. Strategie di Quantificazione

Il documento esamina due strategie di quantificazione per la formula XSSAT risultante:

Metodo Baseline ( $Q_b$ ): Tutti gli atomi non di scelta (ad esempio legal, terminal) sono collocati nel blocco esistenziale più interno, seguendo un ordine temporale rigoroso degli atomi di scelta.
Metodo Basato sulle Dipendenze ( $Q_d$ ): Ispirato a tecniche per giochi deterministici, questo metodo sposta gli atomi non di scelta per apparire il prima possibile nel prefisso dei quantificatori, immediatamente dopo gli atomi di scelta da cui dipendono. Ciò mira a ridurre lo spazio di ricerca fissando valori come legal prima di diramarsi su does.

Contributi Chiave

Primo Solver basato su ASP per GDL Stocastico: Il documento presenta il primo approccio per risolvere giochi GDL a due giocatori, stocastici e a turni utilizzando ASP.
Linguaggio SQASP: L'introduzione della Programmazione per Risposte di Insiemi Quantificata Stocastica, che unifica il ragionamento avversariale e stocastico all'interno di un framework di programmazione logica.
Solver basato sulla Traduzione: Lo sviluppo di sqasp2xssat, che converte programmi SQASP in formule XSSAT, consentendo l'uso di solver XSSAT esistenti (in particolare SharpSSAT) per la risoluzione di giochi.
Correttezza Teorica: Gli autori forniscono prove formali (Teoremi 2 e 3) che stabiliscono l'equivalenza tra la probabilità massima di vittoria nel gioco GDL e la probabilità massima di soddisfacibilità della formula SQASP/XSSAT generata.

Risultati Sperimentali

Gli autori hanno valutato il loro approccio su varianti stocastiche di Tris, Connect-4 e Nim, confrontando il metodo basato su SQASP (utilizzando sia la quantificazione $Q_b$ che $Q_d$ ) con un solver Expected Minimax (EMM) a ricerca in avanti.

Prestazioni: L'approccio basato su ASP è competitivo con la ricerca in avanti su piccoli giochi stocastici. In molti casi (ad esempio Tris, Connect-3), il solver ASP calcola probabilità di vittoria comparabili a quelle di EMM, spesso entro tempi simili.
Spostamento dei Quantificatori: Sorprendentemente, la quantificazione basata sulle dipendenze ( $Q_d$ ) non ha prodotto miglioramenti significativi delle prestazioni rispetto alla baseline ( $Q_b$ ) quando si utilizza il solver SharpSSAT. Gli autori attribuiscono ciò al meccanismo interno di propagazione delle unità di SharpSSAT, che può derivare valori di atomi (come legal) indipendentemente dall'ordine dei quantificatori, mitigando efficacemente la necessità di uno spostamento esplicito.
Limiti di Scalabilità: L'approccio fatica con spazi di stato più grandi, come Nim Stocastico con dimensioni di mucchi elevate. Le formule XSSAT risultanti diventano troppo grandi (oltre un milione di clausole) per essere gestite efficientemente dai solver attuali, mentre EMM scala bene grazie alla programmazione dinamica e alle tabelle di trasposizione.

Significato e Affermazioni

Il documento afferma che l'approccio proposto basato su ASP fornisce un'alternativa praticabile per la valutazione della fase finale nei sistemi di Gioco Generale. Estendendo l'applicazione di successo dell'ASP ai giochi deterministici al dominio stocastico, il lavoro dimostra che la programmazione logica può gestire efficacemente incertezza e ragionamento avversariale.

Gli autori notano con modestia che, sebbene l'approccio non domini la ricerca in avanti in tutti i casi (in particolare per giochi con spazi di stato molto grandi o strutture specifiche come Nim), generalizza con successo i risultati precedenti per giochi deterministici a quelli stocastici. Identificano l'estensione all'osservabilità parziale (ad esempio Poker, Krieg-Tris) come una direzione critica per il lavoro futuro, riconoscendo che il metodo attuale è limitato a giochi a informazione perfetta.