In the video game “7 Billion Humans”, the player is requested to direct a group of workers to various destinations by writing a program that is executed simultaneously on each worker. While the game is quite rich and, indeed, it is considered one of the best games for beginners to learn the basics of programming, we show that even extremely simple versions are already NP-Hard or PSPACE-Hard.

Coordinating "7 Billion Humans" is hard / Panconesi, Alessandro; Posta, PIETRO MARIA; Giacchini, Mirko. - (2024). (Intervento presentato al convegno Conference on Fun with Algorithms tenutosi a Island of La Maddalena, Sardinia, Italy).

Coordinating "7 Billion Humans" is hard

Alessandro Panconesi;Pietro Maria Posta;Mirko Giacchini
2024

Abstract

In the video game “7 Billion Humans”, the player is requested to direct a group of workers to various destinations by writing a program that is executed simultaneously on each worker. While the game is quite rich and, indeed, it is considered one of the best games for beginners to learn the basics of programming, we show that even extremely simple versions are already NP-Hard or PSPACE-Hard.
2024
Conference on Fun with Algorithms
video games; computational complexity; np; pspace
04 Pubblicazione in atti di convegno::04b Atto di convegno in volume
Coordinating "7 Billion Humans" is hard / Panconesi, Alessandro; Posta, PIETRO MARIA; Giacchini, Mirko. - (2024). (Intervento presentato al convegno Conference on Fun with Algorithms tenutosi a Island of La Maddalena, Sardinia, Italy).
File allegati a questo prodotto
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/1725418
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact