Est-il possible d'obtenir une impasse aux dames ?

Question

Duplicata possible :
Quel est le terme pour une impasse aux dames ?

J'allais poster ceci dans StackOverflow, quand j'ai réalisé que cela n'avait vraiment rien à voir avec la programmation. S'il y a un meilleur endroit, dites-le moi, pour que je puisse le déplacer.

Je suis en train de créer un jeu de dames basique, et j'étais en train de configurer le gestionnaire de jeu quand je suis arrivé à la méthode qui met fin au jeu de manière gracieuse. Cela aurait pris dans un boolean valeur, true signifiant que le joueur 1 a gagné, false signifiant que le joueur 2 a gagné. Cependant, j'ai réalisé que, dans la plupart des jeux, il y a la possibilité d'une impasse, donc je l'ai changé en un byte , donde x < 0 est le joueur 1, x == 0 est une impasse, et x > 0 est le joueur 2. Après cela, j'ai commencé à me demander si les dames peuvent même avoir une impasse. Cela semble possible, mais je n'arrive pas à imaginer un scénario où la partie se termine sans qu'aucun des deux joueurs ne gagne. Existe-t-il un scénario, dans le jeu de dames anglaises (dames nord-américaines), où aucun des deux joueurs ne gagne la partie, et pourtant la partie se termine ? Notez qu'un forfait de la part d'un joueur signifie que l'autre joueur gagne.

Answer 1

Si vous ne forcez pas la capture, il est très possible, voire trivial, de se retrouver dans une impasse.

Même sans cela :

De wikipedia :

Les dames anglaises (dames américaines 8×8) ont été le théâtre de plusieurs avancées notables en matière d'intelligence artificielle de jeu. Dans les années 1950, Arthur Samuel a créé l'un des premiers programmes de jeu de société, quel qu'il soit. Plus récemment, en 2007, des scientifiques de l'université d'Alberta[13] ont fait évoluer leur programme "Chinook" jusqu'au point où il est imbattable. Une approche par force brute, qui a nécessité le travail de centaines d'ordinateurs pendant près de vingt ans, a été utilisée pour résoudre le jeu[14], montrant qu'une partie de dames se termine toujours par une impasse si aucun des joueurs ne commet d'erreur[15][16]. La solution concerne la variante du jeu de dames appelée "go-as-you-please" (GAYP) et non la variante appelée "three-move restriction". En décembre 2007, cela fait des dames anglaises le jeu le plus complexe jamais résolu.