Échecs : celui qui perd gagne | Le jeu scientifique

Pour gagner dans la version linéaire de Nim (dans laquelle celui qui prend le dernier cure-dent perd), dont nous avons abordé les variantes la semaine dernière, il faut laisser à l’autre joueur 5 cure-dents, ce qui signifie que, quel que soit celui qu’il prend, il nous quittera le dernier. Et pour pouvoir lui laisser 5, il faut d’abord lui laisser 9, et avant ça 13, et avant ça 17… C’est-à-dire que celui qui se retrouve avec 4n + 1 bâtons perd c’est sûr (pourvu que l’autre fait les bons gestes, c’est entendu). Ainsi, si vous partez d’une rangée de 20 cure-dents, le premier joueur gagne en en retirant 3 et en en laissant 17.

Les variantes avec plusieurs rangées de cure-dents sont plus compliquées ; mais seulement en apparence, puisqu’il existe en réalité un moyen très simple de savoir si une position est gagnante ou perdante, découvert au début du siècle dernier par le mathématicien américain Charles L. Bouton (également responsable d’appeler le jeu Nim ), dont le pionnier de l’analyse est considéré comme à l’origine de la théorie combinatoire des jeux (CGTselon l’acronyme en anglais), dont l’objet d’étude est les jeux séquentiels avec une information parfaite (c’est-à-dire dans lesquels les joueurs connaissent à tout moment l’état du jeu et tous les mouvements possibles).

Bouton a montré que pour déterminer si une position était gagnante ou perdante, il suffisait d’écrire le nombre de bâtons dans chaque ligne en notation binaire : si toutes les colonnes totalisent 0 ou pair, la position est gagnante ; sinon non.

Supposons que nous partions de trois rangées avec respectivement 5, 4 et 3 cure-dents :

IIIIII

III

III

Mettre 5, 4 et 3 en nombres binaires :

101

100

11

212

La première colonne additionne 2, la deuxième 1 et la troisième 2, et comme il y a une somme impaire, la situation est perdante. En effet, le premier joueur atteint une position gagnante en retirant deux bâtons de la troisième rangée et, s’il joue correctement, il est assuré de la victoire, quoi que fasse l’autre joueur.

Nim est donc, quel que soit le nombre de rangées et le nombre de bâtons qu’il y a dans chaque rangée, un jeu de stratégie sûr. Tous les jeux séquentiels à information parfaite ne le sont pas (ou du moins on ne peut pas être sûr qu’ils le soient), car au-delà d’un certain degré de complexité ils échappent à nos possibilités de calcul. C’est le cas des échecs : sa combinatoire est si énorme (de l’ordre des septillions) que, même si certains spécialistes estiment que la « partie parfaite » se terminerait par un match nul, nous ne pouvons pas le garantir.

‘Antichesse’

Et en parlant des échecs et d’un autre jeu séquentiel à information parfaite – Nim – dans lequel, selon les variantes, ce qui chez l’un gagne (en prenant le dernier bâton) chez l’autre est perdant, on ne peut manquer de mentionner le antichesse ou les échecs perdant-gagnant, une modalité très populaire dans laquelle l’objectif est de perdre toutes les pièces ou de se noyer. Comme dans le célèbre roman de Graham Green, celui qui perd gagne. Les règles sont les mêmes que celles des échecs conventionnels, à quelques exceptions près :

*La capture est obligatoire (comme aux dames). S’il y a plusieurs captures possibles, le joueur peut choisir celle qui lui convient le mieux.

*Le roi n’est qu’une autre pièce qui peut être capturée comme n’importe quelle autre et, par conséquent, il n’y a pas d’échec, pas d’échec et de mat et pas de roque. Par conséquent, un pion qui couronne peut aussi devenir roi.

*Un joueur noyé, c’est-à-dire qui ne peut effectuer aucun mouvement légal, remporte la partie.

Inutile de dire que les jeux de antichesse Ils sont très différents de ceux des échecs conventionnels (quelles ouvertures vous semblent bonnes et lesquelles ne le sont pas ?). Et les problèmes aussi, comme vous le verrez si vous essayez de résoudre celui de la figure : Noir joue et gagne (c’est-à-dire perd). Il semble facile de perdre-gagner avec un seul pion, mais…