Ricochet Robots

Données clés
Auteur	Alex Randolph
Éditeur	Hans im Glück
Date de 1re édition	1999
Autre éditeur	Tilsit
Joueur(s)	1 à 99
Âge	À partir de 10 ans
Durée annoncée	30 minutes

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 mur 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^[1], 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^[2].

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^[3].

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^[4].

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

Le plateau du jeu de Ricochet Robots est conçu de manière à ce 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. 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)$ .

$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 à PSPACE-complete^[5].

Le problème d'optimisation associé au problème de décision

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 consiste à maximiser la taille de l'ensemble K où K est le nombre total de tuiles couvertes par des robots de la couleur correspondante.

Trouver une solution au problème de $MR(n,1,m,1)$ consiste à résoudre le problème de Ricochet Robots. Il existe une $S$ -reduction du problème de Maximal independent set qui est Poly-APX-complete^[6] vers $MR(n,1,m,1)$ donc le problème d'optimisation de Ricochet Robots est Poly-APX-hard^[5] cela implique que le Ricochet Robots est non seulement difficile à résoudre exactement mais aussi à approximer efficacement.