# Ricochet Robots

Ricochet Robots (Rasende Roboter pour la première édition en allemand) est un jeu de société créé par Alex Randolph et illustré par Franz Vohwinkel, édité en 1999 par Hans im Glück / Tilsit.
Le jeu est composé d'un plateau, de tuiles représentant chacune une des cases du plateau, et de pions appelés « robots ». La partie est décomposée en tours de jeu, un tour consistant à déplacer les robots sur un plateau afin d'en amener un sur l'une des cases du plateau. Les robots se déplacent en ligne droite et avancent toujours jusqu'au premier obstacle qu'ils rencontrent.
On peut aussi bien y jouer seul qu'à un grand nombre de participants.

## Matériel
### Première édition

En 1999, le jeu s'appelle Rasende Roboter et contient :
* 4 plateaux double-face à assembler ;
* 4 pions de couleurs différentes représentant les robots ;
* 4 tuiles robot de couleurs identiques à celles des robots ;
* 17 tuiles objectif distribuées en quatre groupes de quatre tuiles de couleur identique à celle d'un robot, et une tuile multicolore ;
* 1 sablier.
Le plateau de jeu représente un quadrillage sur lequel figurent certaines cases spéciales, les cases objectif, c'est-à-dire les cases où doivent être amenés les robots. Ce plateau de jeu est composé de quatre parties recto-verso, permettant ainsi d'obtenir 96 plateaux de jeu différents. Une version en anglais, titrée Ricochet Robot, est éditée par Abacus / Rio Grande Games.

### Deuxième édition

La deuxième édition sort en 2003 chez Abacus / Rio Grande Games, sous forme d’une boîte bleue titrée uniquement Ricochet Robots. Elle comprend un robot supplémentaire, de couleur noire. De plus certaines cases comportent des murs sur deux de leurs côtés, représentant les obstacles que rencontreront les robots.

### Troisième édition

La troisième édition est une réédition de la boîte d’origine sous le nom de Ricochet Robots, avec un robot supplémentaire, de couleur argent. Les plateaux sont différents et compatibles avec l'édition précédente.

## Objectif

L'objectif du jeu consiste à récupérer des tuiles objectif en amenant un des robots sur une case particulière du plateau.

## Règles du jeu

À chaque tour, un des joueurs retourne une tuile objectif. Le but est alors d'amener le robot de la couleur de la tuile sur la case objectif dont le symbole est identique à celui de la tuile. Si c'est la tuile multicolore qui est tirée, l'objectif est alors d'amener n'importe quel robot sur la case multicolore du plateau.
Les joueurs jouent simultanément, chacun réfléchissant sur le moyen d'amener le robot en utilisant les règles de déplacement. Lorsque l'un d'entre eux pense avoir trouvé une solution, il annonce en combien de mouvements il compte réaliser l'objectif puis il retourne le sablier. Les autres joueurs ont jusqu'à la fin du sablier pour proposer de meilleures solutions, utilisant moins de mouvements.
Après l'écoulement du sablier, le joueur qui a la solution comptant le moins de mouvement montre sa solution et remporte la tuile. S'il échoue dans sa démonstration, le joueur qui proposait le nombre de mouvements immédiatement supérieur montre sa solution, etc. jusqu'à ce qu'une solution soit valide.

### Règles de déplacement

Sur le plateau, les robots se déplacent en ligne droite et le plus loin possible avant de rencontrer un obstacle. Durant leur tour, les joueurs peuvent utiliser les quatre robots comme ils le souhaitent.
Une fois mis en mouvement, le robot ne peut s'arrêter ou repartir dans une autre direction que lorsqu'il rencontre un obstacle. Les obstacles peuvent être :
* les bords du plateau
* les murs symbolisés sur le plateau
* un autre robot
Chaque déplacement de robot compte pour un mouvement, quel que soit le nombre de cases parcourues.

### Cas particulier

Si, après avoir retourné une tuile objectif, il s'avère que la solution est atteignable en un seul mouvement, les joueurs devront ignorer cette solution et s'efforcer d'en trouver une autre.

## Conditions de victoire

Le joueur qui possède le plus de tuiles objectif en fin de partie remporte la victoire.

## Complexité algorithmique du jeu

Trouver une solution au jeu de Ricochet Robots avec un nombre fixé de robots et une solution de taille fixée (la taille de la solution correspond au nombre de mouvements) appartient à la classe de problème FPT.

### Généralisation du problème de décision

Le plateau du jeu de Ricochet Robots est conçu de manière qu'il soit toujours possible pour un robot d'atteindre sa tuile objectif. Dans le cas on où on construit le plateau de manière arbitraire, il est possible de définir le problème de décision suivant: étant donné le plateau (construit arbitrairement), une position de départ des 4 robots et une tuile objectif de couleur. Existe t-il une solution pour amener le bon robot vers sa tuile objectif ?
De ce problème de décision peut être extrait un problème de décision généralisé nommé Generalized Reachability (GR) dans lequel on a un nombre arbitraire $n$ de robots colorés avec $c_{r}$ couleurs différentes et $m$ tuiles différentes avec $c_{t}$ couleurs différentes. On dénote ce problème $GR(n,c_{r},m,c_{t})$.
Le problème généralisé (GR) consiste donc à déterminer s'il existe une configuration où chaque tuile objectif est atteinte par un robot de la même couleur. Pour mieux comprendre, prenons par exemple $GR(4,2,2,2)$, n = 4 robots dont 2 rouges et 2 bleues (donc c_r = 2), m = 2 car il y a 2 tuiles objectifs et c_t = 2, soit 2 tuiles de couleurs distinctes une tuile rouge et une bleue. Trouver une solution de $GR(4,2,2,2)$ consiste à déterminer si oui ou non il existe une configuration tel qu'un robot rouge soit sur la tuile rouge et un robot bleu sur la tuile bleue.
Le jeu de plateau original de robot ricochet est une instance particulière du problème généralisé avec 4 robots différents et une tuile objectif coloré $GR(4,1,1,1)$ en effet dans Ricochet Robots il s'agit de ramener le bon robot sur la bonne tuile.
$GR(n,1,1,1)$ appartenant à PSPACE et possédant une réduction polynomiale vers le problème de Token Sliding, le problème qui consiste à déterminer si une instance de Ricochet Robots possède une solution appartient donc à PSPACE-complete.

### Un problème d'optimisation associé au problème de décision généralisé

Au problème de décision généralisé $GR(n,c_{r},m,c_{t})$ peut être associé un problème d'optimisation $MR(n,c_{r},m,c_{t})$ où comme pour le problème de décision: $n$ est le nombre de robots colorés avec $c_{r}$ couleurs différentes et $m$ le nombre de tuiles différentes avec $c_{t}$ couleurs différentes. Le problème $MR(n,c_{r},m,c_{t})$ consiste à maximiser la taille de l'ensemble K où K est le nombre total de tuiles couvertes par des robots de la couleur correspondante. Par exemple une instance de $MR(10,3,10,3)$ consisterait à déterminer le nombre maximum de tuiles (sur les 10 tuiles au total), combien peuvent être atteints par un robot de la bonne couleur parmi les 10 robots au total.
$MR(4,1,1,1)$ qui est une instance particulière de $MR(n,1,m,1)$ correspond au Ricochet Robots. Et trouver une solution au problème généralisé $MR(n,1,m,1)$ consiste à résoudre le problème de Ricochet Robots avec un nombre arbitraire de robots et de tuiles. Il existe une $S$-reduction du problème de Maximal independent set qui est Poly-APX-complete vers $MR(n,1,m,1)$ donc le problème d'optimisation de Ricochet Robots est Poly-APX-hard cela implique que le Ricochet Robots est non seulement difficile à résoudre exactement mais aussi difficile à approximer efficacement.