Classic Nintendo games are (computationally) hard

We prove NP-hardness results for five of Nintendo's largest video game franchises: Mario, Donkey Kong, Legend of Zelda, Metroid, and Pokémon. Our results apply to generalized versions of Super Mario Bros.1-3, The Lost Levels, and Super Mario World; Donkey Kong Country 1-3; all Legend of Zelda games; all Metroid games; and all Pokémon role-playing games. In addition, we prove PSPACE-completeness of the Donkey Kong Country games and several Legend of Zelda games.

Cannibal Animal Games: A new variant of Tic-Tac-Toe

This paper presents a new partial two-player game, called the cannibal animal game, which is a variant of Tic-Tac-Toe. The game is played on the infinite grid, where in each round a player chooses and occupies free cells. The first player Alice can occupy a cell in each turn and wins if she occupies a set of cells, the union of a subset of which is a translated, reflected and/or rotated copy of a previously agreed upon polyomino P (called an animal). The objective of the second player Bob is to prevent Alice from creating her animal by occupying in each round a translated, reflected and/or rotated copy of P. An animal is a cannibal if Bob has a winning strategy, and a non-cannibal otherwise. This paper presents some new tools, such as the bounding strategy and the punching lemma, to classify animals into cannibals or non-cannibals. We also show that the pairing strategy works for this problem.

Efficient energy distribution in a smart grid using multi-player games

info:eu-repo/semantics/submittedForPublication

Idiotypic games within the immune network.

In this paper, we have considered the problem of selection of available repertoires. With Ab2 as immunogens, we have used the idiotypic cascade to explore potential repertoires. Our results suggest that potential idiotypic repertoires are more or less the same within a species or between different species. A given idiotype "à la Oudin" can become a recurrent one within the same outbred species or within different species. Similarly, an intrastrain crossreactive idiotype can be induced in other strains, even though there is a genetic disparity between these strains. The structural basis of this phenomenon has been explored. We next examined results showing the loss and gain of recurrent idiotypes without any intentional idiotypic manipulation. A recurrent idiotype can be lost in a syngeneic transfer and a private one can become recurrent by changing the genetic background. The change of available idiotypic repertoires at the B cell level has profound influences on the idiotypic repertoires of suppressor T cells. All these results imply that idiotypic games are played by the immune system itself, a strong suggestion that the immune system is a functional idiotypic network.