Approccio Automatico per la Risoluzione di Giochi di Raggiungibilità Polinomiali a Stato Infinito

Un nuovo articolo su arXiv presenta un metodo automatico per risolvere giochi di raggiungibilità polinomiali a stato infinito. I giochi di raggiungibilità coinvolgono due giocatori, REACH e SAFE, dove REACH mira a raggiungere un insieme target mentre SAFE cerca di evitarlo. Questi giochi hanno applicazioni nell'IA e nella sintesi reattiva, spesso coinvolgendo grafi a stato infinito. Lo studio si concentra su giochi a turni su valutazioni di variabili reali. Gli autori propongono certificati di ranking come regola di prova corretta e completa per determinare se REACH ha una strategia vincente. Considerano anche giochi di raggiungibilità polinomiali con transizioni e obiettivi definiti da polinomi. L'articolo introduce un approccio automatico per risolvere tali giochi, contribuendo alla teoria dei giochi a stato infinito.