Conway games, algebraically and coalgebraically
Using coalgebraic methods, we extend Conway's theory of games to possibly non-terminating, i.e. non-wellfounded games (hypergames). We take the view that a play which goes on forever is a draw, and hence rather than focussing on winning strategies, we focus on non-losing strategies. Hypergames...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Logical Methods in Computer Science e.V.
2011-09-01
|
| Series: | Logical Methods in Computer Science |
| Subjects: | |
| Online Access: | https://lmcs.episciences.org/703/pdf |
| _version_ | 1797268695056121856 |
|---|---|
| author | Furio Honsell Marina Lenisa |
| author_facet | Furio Honsell Marina Lenisa |
| author_sort | Furio Honsell |
| collection | DOAJ |
| description | Using coalgebraic methods, we extend Conway's theory of games to possibly
non-terminating, i.e. non-wellfounded games (hypergames). We take the view that
a play which goes on forever is a draw, and hence rather than focussing on
winning strategies, we focus on non-losing strategies. Hypergames are a
fruitful metaphor for non-terminating processes, Conway's sum being similar to
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
determinacy and characterization of strategies. Hypergames have a rather
interesting theory, already in the case of impartial hypergames, for which we
give a compositional semantics, in terms of a generalized Grundy-Sprague
function and a system of generalized Nim games. Equivalences and 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. |
| first_indexed | 2024-04-25T01:36:34Z |
| format | Article |
| id | doaj.art-5e770556121642b58320d5d89b20ab46 |
| institution | Directory Open Access Journal |
| issn | 1860-5974 |
| language | English |
| last_indexed | 2024-04-25T01:36:34Z |
| publishDate | 2011-09-01 |
| publisher | Logical Methods in Computer Science e.V. |
| record_format | Article |
| series | Logical Methods in Computer Science |
| spelling | doaj.art-5e770556121642b58320d5d89b20ab462024-03-08T09:17:23ZengLogical Methods in Computer Science e.V.Logical Methods in Computer Science1860-59742011-09-01Volume 7, Issue 310.2168/LMCS-7(3:8)2011703Conway games, algebraically and coalgebraicallyFurio HonsellMarina LenisaUsing coalgebraic methods, we extend Conway's theory of games to possibly non-terminating, i.e. non-wellfounded games (hypergames). We take the view that a play which goes on forever is a draw, and hence rather than focussing on winning strategies, we focus on non-losing strategies. Hypergames are a fruitful metaphor for non-terminating processes, Conway's sum being similar to 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 determinacy and characterization of strategies. Hypergames have a rather interesting theory, already in the case of impartial hypergames, for which we give a compositional semantics, in terms of a generalized Grundy-Sprague function and a system of generalized Nim games. Equivalences and 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.https://lmcs.episciences.org/703/pdfcomputer science - logic in computer sciencef.3.2, f.4.1 |
| spellingShingle | Furio Honsell Marina Lenisa Conway games, algebraically and coalgebraically Logical Methods in Computer Science computer science - logic in computer science f.3.2, f.4.1 |
| title | Conway games, algebraically and coalgebraically |
| title_full | Conway games, algebraically and coalgebraically |
| title_fullStr | Conway games, algebraically and coalgebraically |
| title_full_unstemmed | Conway games, algebraically and coalgebraically |
| title_short | Conway games, algebraically and coalgebraically |
| title_sort | conway games algebraically and coalgebraically |
| topic | computer science - logic in computer science f.3.2, f.4.1 |
| url | https://lmcs.episciences.org/703/pdf |
| work_keys_str_mv | AT furiohonsell conwaygamesalgebraicallyandcoalgebraically AT marinalenisa conwaygamesalgebraicallyandcoalgebraically |