Le problème des nnn -queens classiques demande, étant donné un entier positif nnn , s'il existe un tableau d'entiers satisfaisant aux conditions suivantes:Q[1..n]Q[1..n]Q[1..n] i1≤Q[i]≤n1≤Q[i]≤n1\le Q[i] \le n pour toutiii i ≠ jQ[i]≠Q[j]Q[i]≠Q[j]Q[i] \ne Q[j] pour touti≠ji≠ji\ne j...
Le problème suivant est-il NP-difficile? Étant donné une configuration de carte pour brouillons internationaux , trouvez un mouvement juridique unique.n×nn×nn\times n Le problème correspondant pour les vérificateurs américains (ou versions anglaises) est trivialement résoluble en temps polynomial....
J'ai pensé à une variante d' hex , où au lieu que les deux joueurs effectuent des mouvements alternativement, chaque tour un joueur choisi au hasard fait un mouvement. Est-il difficile de déterminer les chances de chaque joueur de gagner? Ce problème est évidemment dans PSPACE, mais ne peut pas...
Je cherche à obtenir une réponse définitive à la question du titre. Existe-t-il un ensemble de règles qui traduisent un programme en une configuration de pièces finies sur un plateau infini, de sorte que si le noir et blanc ne joue que des mouvements légaux, le jeu se termine en temps fini si le...
Contexte Cette question est motivée par un jeu de société appelé «Dracula». Dans ce jeu, il y a un vampire et quatre chasseurs, le but des chasseurs est d'attraper le vampire. Le jeu se déroule en Europe. Le jeu se présente comme suit: 1. Le joueur chasseur place tous les chasseurs dans les villes....
Considérez le jeu de cartes suivant (connu en Italie sous le nom de "Cavacamicia", qui peut être traduit par "stripshirt"): Deux joueurs partagent au hasard en deux jeux un jeu de cartes standard. Chaque joueur reçoit un deck. Les joueurs alternent en plaçant dans une pile la carte suivante de leur...
Il y a une très belle construction par Conway de nombres surréalistes. Ce sont des "nombres" qui contiennent à la fois des nombres réels et des ordinaux, sont totalement ordonnés et ont toutes les propriétés d'un champ (sauf qu'ils ne forment pas un ensemble mais une classe). Voir par exemple ce...
Considérez les jeux combinatoires à deux joueurs à informations complètes qui se terminent après un nombre polynomial de mouvements, et d'une manière alternée, les joueurs choisissent parmi un nombre fini de mouvements autorisés. La question habituelle est de savoir à quel point il est difficile de...
MCTS / UCT est une méthode de recherche d'arbre de jeu qui utilise un algorithme de bandit pour sélectionner les nœuds prometteurs à explorer. Les jeux sont joués de manière aléatoire et les nœuds menant à plus de victoires sont explorés plus en profondeur. L'algorithme de bandit maintient un...