Using \emph{coalgebraic methods}, we extend Conway's theory of games to possibly \emph{non-terminating}, \emph{i.e.} \emph{non-wellfounded games} (\emph{hypergames}). We take the view that a play which goes on forever is a \emph{draw}, and hence rather than focussing on winning strategies, we focus on \emph{non-losing strategies}. Hypergames are a fruitful metaphor for non-terminating processes, \emph{Conway's sum} being similar to \emph{shuffling}. We develop a theory of hypergames, which extends in a non-trivial way Conway's theory; in particular, we generalize Conway's results on game \emph{determinacy} and \emph{characterization} of strategies. Hypergames have a rather interesting theory, already in the case of \emph{impartial hypergames}, for which we give a \emph{compositional semantics}, in terms of a \emph{generalized Grundy-Sprague function} and a system of generalized \emph{Nim games}. \emph{Equivalences} and \emph{congruences} on games and hypergames are discussed. We indicate a number of intriguing directions for future work. We briefly compare hypergames with other notions of games used in computer science.

Conway's Games, algebraically and coalgebraically

HONSELL, Furio;LENISA, Marina
2011-01-01

Abstract

Using \emph{coalgebraic methods}, we extend Conway's theory of games to possibly \emph{non-terminating}, \emph{i.e.} \emph{non-wellfounded games} (\emph{hypergames}). We take the view that a play which goes on forever is a \emph{draw}, and hence rather than focussing on winning strategies, we focus on \emph{non-losing strategies}. Hypergames are a fruitful metaphor for non-terminating processes, \emph{Conway's sum} being similar to \emph{shuffling}. We develop a theory of hypergames, which extends in a non-trivial way Conway's theory; in particular, we generalize Conway's results on game \emph{determinacy} and \emph{characterization} of strategies. Hypergames have a rather interesting theory, already in the case of \emph{impartial hypergames}, for which we give a \emph{compositional semantics}, in terms of a \emph{generalized Grundy-Sprague function} and a system of generalized \emph{Nim games}. \emph{Equivalences} and \emph{congruences} on games and hypergames are discussed. We indicate a number of intriguing directions for future work. We briefly compare hypergames with other notions of games used in computer science.
File in 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/11390/1039358
 Attenzione

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

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