Nombre maximum de points atteignables pour un seul joueur dans une partie à deux joueurs de Carcassonne

Question

Commençons cette question en partant des hypothèses suivantes sur une partie de Carcassonne :

• C'est un jeu à deux joueurs.
• Le jeu utilise le set de règles/tuiles de base actuel. edit : pour être clair, j'utilise les règles de la 3ème édition qui attribuent 2 points à toutes les tuiles de ville et considèrent la même ville pour différentes fermes comme décrit ici.
• Le joueur que nous voulons maximiser a une chance parfaite et une compétence parfaite à la fois pour le tirage des tuiles et leur placement.
• L'adversaire a une chance et une compétence minimales.

Cela signifie que nous pouvons choisir quelles tuiles sont tirées par chaque joueur, comment elles sont placées et comment placer les meeples de chaque joueur.

Existe-t-il un moyen optimal de placer les tuiles afin de maximiser le score d'un joueur ? Si oui, ce moyen peut-il être déterminé ?

Answer 1

Comme le note Hackworth, tester tous les agencements possibles est clairement impossible. Cependant, il pourrait être possible d'obtenir une borne supérieure décente sur les points.

Je pense que nous pouvons raisonnablement supposer que les meeples ne seront pas une ressource rare en jouant de cette manière (puisque nous pouvons choisir de compléter la carte dans n'importe quel ordre, il ne devrait pas être difficile de s'assurer que nous avons toujours des meeples disponibles). Ainsi, le problème se réduit à trouver l'agencement de carte le plus rentable. Les bornes supérieures pour les routes, les villes et les cloîtres sont simples ; 9 pour chaque cloître, 2 pour chaque tuile de ville (et 2 pour chaque fanion) et 1 pour chaque tuile de route.

Les fermes sont les parties délicates. Tout d'abord, nous devrions déterminer le nombre maximal de villes que nous pouvons créer, et deuxièmement, nous devons déterminer le nombre maximal de fermes qui peuvent approvisionner chaque ville, avec une limite de 7 champs au total. Ce n'est certainement pas facile, mais cela devrait être beaucoup plus simple que le problème original (il y a un nombre limité de façons qu'une ville pourrait être approvisionnée par plusieurs fermes, etc).

Vous pourriez probablement obtenir une approximation décente en jouant simplement avec les tuiles pendant quelques heures...

Answer 2

342

Pour les règles de la troisième édition

Voici une façon de faire: Les numéros montrent quand les tuiles sont placées. Le joueur noir est le premier à jouer et place toujours un meeple à l'endroit du numéro. Le bleu joue en deuxième et ne place jamais de meeple.

Preuve de l'optimalité

Optimalité de l'utilisation des meeples:

Le premier joueur aura 36 tours et donc seulement 36 opportunités de placer des meeples pour des points. La meilleure utilisation de ces 36 est la suivante :

• 7 pour les champs
• 6 pour les cloîtres
• 16 pour les villes
• 7 pour les routes

On ne peut pas en mettre plus sur les champs car on ne les récupère pas. Le nombre sur les villes et les cloîtres est suffisant pour compter tous les points possibles des villes/cloîtres (sauf la tuile de ville impaire, voir l'optimalité des villes). La seule modification utile possible serait donc d'avoir plus de routes, ce qui ajouterait au maximum 2 points car toutes les routes sans extrémités sont déjà marquées. Mais 2 points est moins que ce que nous perdrons en ayant moins de villes (chaque ville supplémentaire ajoute 3 points de champ à chaque grand champ), cloîtres (9 chacun) ou petit champ (6 chacun).

Optimalité des villes:

Il y a 44 tuiles de ville et 10 boucliers. 5 des tuiles de ville ont deux villes distinctes dessus et donc si vous les placez sur des villes différentes, elles peuvent être comptées deux fois. Cela vaudrait 59 points au total et les villes complètes valent double, soit 118. Cependant, toutes les villes complètes doivent avoir un périmètre vertical pair et un périmètre horizontal pair car elles doivent être complètes à la fois de gauche à droite et de haut en bas (une tuile de ville diagonale a 1 périmètre horizontal et 1 périmètre vertical, pas 1 périmètre total). Par exemple, disons qu'une ville fait 5 tuiles de haut, alors son périmètre vertical doit être de 10 si elle est complète, oui vous pourriez avoir de la concavité mais les mêmes règles s'appliquent à cela. Et puisque le périmètre horizontal+vertical total de toutes les tuiles disponibles est impair, vous ne pouvez pas compléter toutes les tuiles de ville, le mieux que vous puissiez faire est de laisser une tuile de côté. Cela signifie que le score maximum de la ville est (59-1)*2=116.

Optimalité des champs:

Nous devons maximiser le nombre de villes complètes car nous pouvons construire de grands champs qui touchent toutes les villes. Une ville complète doit avoir au moins 4 tuiles avec un coin qui n'a pas sa propre ville qui les touche. Les tuiles de ville diagonale (par exemple la ville noire #29) ont 1 coin de ce type et les tuiles de ville simples avec des côtés (par exemple la tuile de départ) ont 2 coins de ce type (toutes les autres tuiles de ville n'en ont pas). Il y a 10 tuiles de ville diagonale et 28 tuiles de ville simples avec des côtés (les tuiles avec 2 villes simples avec des côtés comptent comme 2). Cela donne 10+28*2=66 coins ce qui permet un maximum de 16 villes.

Maintenant pour maximiser le nombre de champs qui touchent ces 16 villes. J'essaierai d'expliquer cela intuitivement mais l'utilisateur 1873 est arrivé à la même conclusion et le prouve en utilisant la théorie des graphes (voir leur réponse - qui est la même en d'autres aspects sauf qu'elle a seulement 15 villes). Au maximum nous pouvons avoir 2 grands champs touchant toutes les villes. Un troisième champ doit rester à l'intérieur de ces grands champs et ne toucher que 2 villes. Pour toucher une troisième ville, il devrait traverser un des grands champs, mais cela diviserait ce grand champ en deux petits champs.

Nous avons donc 2 grands champs touchant 16 villes et 5 petits champs touchant 2 villes. 2*16*3+5*2*3=126

Optimalité des routes:

Chaque route complète a 2 points d'extrémité. Il y a 32 tuiles de route sans extrémité qui peuvent s'insérer dans n'importe quelle route complète. Donc le maximum de points que vous pouvez obtenir des routes est 2 * #routes + 32. Comme nous avons seulement le temps de placer des meeples sur 7 routes cela donne 2*7+32=46.

Optimalité des cloîtres:

Chacun des 6 cloîtres peut marquer un maximum de 9 points pour 6*9=54.

Somme des caractéristiques optimales 116+126+46+54 = 342

Je dois dire que c'est une belle question car non seulement la preuve est multifacette avec une pensée hors du commun requise, mais aussi parce que trouver réellement une configuration qui l'atteint était vraiment non trivial et amusant. Tellement que même 6 ans plus tard, je me souviens de la joie de trouver comment placer ce vide dans la ville pour lui permettre de se compléter et de la tuile manquante pour empêcher les deux grands champs de se joindre. Cette beauté est la raison pour laquelle j'ai revisité ceci et réécrit cette réponse pour la rendre plus claire et aussi pour la décomposer en un exemple avec tous les mouvements et une preuve séparée.

Une question ouverte serait de savoir quel est le score maximum possible dans un jeu à un joueur. Vous auriez 31 tours de plus pour placer des meeples mais les seuls points possibles à obtenir seraient de compléter davantage de routes. Il y a 12 extrémités de route inutilisées dans mon exemple mais comment diable les réarrangeriez-vous pour les connecter les unes aux autres sans casser d'autres choses ? Une autre question ouverte est quel est le score total collaboratif pour des parties de 2 à 5 joueurs. Cela serait difficile car partager des villes, des champs et même des routes devrait être fait autant que possible mais il ne sera sûrement pas possible de tout partager. Ces questions seront un ordre de grandeur plus difficile à résoudre et à prouver de manière optimale.

Answer 3

Existe-t-il un moyen optimal de placer les tuiles afin de maximiser le score d'un joueur?

Oui

Avec un nombre fini de tuiles, un nombre fini de placements légaux pour n'importe quelle tuile à n'importe quel moment dans le jeu, et un nombre fini de placements de meeple après avoir placé une tuile, il est évident qu'il existe un nombre fini de jeux possibles. Chaque jeu a un résultat définitif en termes de score, il doit donc clairement y avoir au moins un jeu qui produit le score le plus élevé possible.

Si tel est le cas, ce moyen peut-il être déterminé?

Oui

De toute évidence, en théorie, vous pourriez simplement faire passer tous les coups possibles par un ordinateur et trouver le meilleur.

En pratique, mon intuition de programmeur me dit qu'une recherche exhaustive de tous les coups serait, sur le matériel actuel, rapidement inutile en raison d'une explosion combinatoire, simplement parce que l'arbre de recherche devient trop large pour être géré incroyablement rapidement.

Juste pour avoir une idée approximative, un calcul simplifié :

L'ensemble de base contient 72 tuiles. Après avoir placé la tuile de départ, vous en avez 71 à votre disposition.

• La tuile de départ est conçue pour permettre à chaque une de ces 71 tuiles d'être placée de 1 à 6 manières distinctes, sans tenir compte des rotations graphiques simplement graphiques.

• En supposant une moyenne de 3 manières par tuile, pour le premier coup seul, vous avez environ 200 cartes possibles après que la 2ème tuile ait été placée.

• Le tour suivant, vous avez seulement 1 tuile de moins, mais beaucoup plus de façons possibles de placer la tuile moyenne, car le nombre de bords simples a augmenté de 2, ou augmenté de 50% dans ce cas. Vous regardez probablement environ 300 mouvements possibles maintenant.

• Même si la somme des placements possibles de tuiles pour toutes les tuiles restantes stagne à 200 par coup en moyenne (ce qui est probablement une estimation bien trop basse), après 10+1 coups de 71+1, vous avez déjà 200^10 = 10^23 cartes différentes.

• Calculer 10^12 cartes par seconde (probablement hors de portée du matériel de bureau classique), il faudrait plus de 3000 ans pour calculer toutes les cartes possibles après 11 coups. . Ajoutez un million de PC de bureau, et il vous faudra une journée entière pour calculer les 11 premiers coups. Au coup suivant, multipliez par 200, et ainsi de suite.

• Et tout cela en supposant que personne ne place de meeple pendant ces tours, ce qui augmente encore énormément l'espace de recherche!

• En conclusion, il est hautement improbable que quelqu'un ait jamais calculé quelque chose qui ressemble de près ou de loin à un ensemble exhaustif de cartes possibles de Carcassonne, sans parler du score élevé définitif que quiconque peut théoriquement atteindre.

Je comprends que aucune de ces réponses n'est particulièrement utile, mais je crois que c'est à peu près tout ce que l'on peut dire sur le problème sans rédiger un article scientifique.

Answer 4

Le score théorique maximum est de 338. J'ai déjà répondu à la question pour les règles de la 1ère édition (les villes ne sont marquées qu'une seule fois par les fermiers), donc voici ma seconde tentative pour répondre à cette question. Il devrait être assez clair pour tout le monde que puisqu'il n'y a que 72 tuiles et que l'une d'entre elles est la tuile de départ, le nombre maximum d'opportunités de marquer est de 36 si vous commencez. Vous ne pouvez marquer qu'en plaçant un partisan lors de votre tour, que ce soit vous ou votre adversaire qui pose la tuile qui marque ce partisan. Il devrait également être clair que le score optimal consiste à marquer le plus de points possible pour chaque partisan que vous pouvez marquer. Voici les possibilités de marquage maximum.

---

• 1x Longue Route : Une longue route marquera 32 pts. + 2 pts. = 34 pts.
• 2x Grande Ferme : Une grande ferme marquera 3 pts. x 15 villes = 45 pts.
• 6x Monastère : Un monastère marquera 9 pts.
• 15x Villes : Marquer toutes les 15 villes vaut 2x (10 pts (fanion) + 48 pts (tuiles de ville)) = 116 pts
• 5x Petite Ferme : Une petite ferme marquera 3 pts. x 2 villes = 6 pts.
• 7x Petite Route : Une petite route marquera 1 pts. x 2 tuiles de route = 2 pts.
• Score Total = 34 + 2x45 + 6x9 + 116 + 5x6 + 7x2 = 338 points

Notes concernant le score moyen par Partisan.

Une grande ferme nécessite que vous ayez complété 15 villes. Le nombre maximum de grandes fermes est de deux. Imaginez les deux fermes comme à l'intérieur/dehors, gauche/droite, haut/bas, etc. Dans le graphique ci-dessous, les grandes fermes seraient A et B et il y aurait 15 nœuds entre elles. Cela peut être démontré comme étant vrai en utilisant le Théorème d'Euler, concernant le problème de Graphique d'Utilité K(3,3). Points moyens ~10,72. Ce calcul provient du total des points de ville (116) + (90) 2 Grandes Fermes + (30) 5 Petites Fermes = (236 pts/(15 Chevalier+7 Fermier=22 Partisans))

Le nombre maximum de petites fermes est de 5, puisque vous n'avez que 7 Partisans et que 2 seront indisponibles en tant que Grandes Fermes. Ces petites fermes seront situées comme nœud C, entre deux villes seulement.

La Longue Route nécessite l'utilisation de toutes les tuiles de route non terminales (32), et deux tuiles de route qui se terminent dans une ville/monastère. Construire une seule route la plus longue n'est pas nécessaire pour trouver une carte ayant le score le plus élevé, tant que des tuiles de route non terminales sont incluses dans les Petites Routes que vous marquez.

Le nombre maximum de villes est de 15 (avec un bord inutilisé). Points moyens ~7,73.

Le nombre maximum de Monastères est de 6. Points moyens 9.

Le nombre maximum de Petites Routes est tous les Partisans moins ceux utilisés précédemment avec des scores moyens plus élevés (36 - (1+2+6+15+5)) = 7 Partisans. Comme mentionné précédemment, ces petites routes peuvent utiliser des segments non terminaux qui n'ont pas été utilisés dans le marquage de la Longue Route. Le seul élément nécessaire pour obtenir le score le plus élevé possible est que les 32 tuiles de route non terminales soient utilisées parmi les 8 Partisans de Longue/Petite Route. Score moyen pour les 8 Partisans de route = 48 / 8 = 6 pts.

Answer 5

285

Pour la première édition (et 272 pour la 2ème édition qui est également optimale pour cette édition). Cette question était pour la 3ème édition, mais les anciennes éditions mènent à des idées différentes et intéressantes donc j'ai pensé y répondre aussi.

Un jeu avec le plus de points théoriques possible en 1ère édition serait :

• Avoir tous les chemins marqués et tous les points d'extrémité sur des tuiles séparées (vous ne pouvez pas compter chaque point d'extrémité sur la même tuile comme un point distinct s'ils sont sur le même chemin).
• Avoir autant de villes complétées et marquées que possible et pas de petites villes (dans la 1ère/2ème édition les villes complétées avec seulement 2 tuiles valent seulement 2 points). Et comme pour les chemins, les tuiles avec plusieurs villes doivent se retrouver dans des villes séparées.
• Toutes les tuiles de ville incomplètes marquées.
• Tous les cloîtres complétés et marqués.
• Toutes les villes marquées par au moins un champ (les villes ne peuvent pas être comptées par plusieurs champs comme dans la 3ème édition).

Sur le nombre maximal de villes tout en minimisant les petites villes

Pour des raisons de concision, laisser 2C signifier une tuile avec une ville sur deux côtés, etc.

Ainsi, à partir de la réponse de la 3ème édition de 342, nous savons que 16 villes sont possibles et comment calculer le nombre de villes possibles. Par ce calcul (66 coins), nous avons 5 2C supplémentaires (3 en ligne et 2 en diagonal) qui peuvent être insérés dans une petite ville sans baisser le nombre total de villes. Cela nous laisse avec seulement 9 petites villes. À partir de là, nous pouvons réduire le nombre de petites villes mais pour le faire nécessite également de réduire le nombre total de villes. Chaque petite ville de moins rapporte 2 points, mais chaque ville de moins en perd 4 (chaque ville dans un champ vaut 4 points dans la première édition). Pour commencer, nous pouvons prendre 4 2C de plus et alors nous aurions 5 petites villes et 15 villes, un gain de 4 points. Nous ne pouvons pas refaire cela car alors il n'y a aucun moyen de compléter la ville avec les 3Cs et 4C en utilisant de nombreuses pièces 1C de manière inefficace. Mais nous pouvons prendre deux 3Cs et les entourer chacun de trois 1Cs. Ensuite, nous avons 2 petites villes et 14 villes, une amélioration de 2 points de plus. Enfin, nous pouvons prendre un seul 3C et l'entourer de la même manière, cela nous amène à 0 petites villes et 13 villes. Cela n'ajoute pas plus de points mais c'est quand même mieux car cela prendra moins de tours/meeples puisque chaque ville doit être marquée. Il existe de nombreuses configurations de ville qui peuvent atteindre cela mais aucune ne peut faire mieux.

Pour résumer nos options sont :

• 9 petites villes, 16 villes au total
• 5 petites villes, 15 villes au total (+4)
• 2 petites villes, 14 villes au total (+6)
• 0 petites villes, 13 villes au total (+6)

Combien de points cela donnerait-il?

• Chemin : 30 points d'extrémité et 32 points non d'extrémité, donc 62
• Villes : 44 tuiles de ville, 1 ne peut pas être complétée, 5 ont 2 villes, 10 blasons donc (44-1+5+10)*2+1 = 117
• Champs : 13 villes * 4 chacune = 52 (39 en 2ème édition car les champs passent à valoir 3)
• Cloîtres : 6 cloîtres * 9 chacun = 54

Total : 62 + 117 + 52 + 54 = 285 points

Combien de meeples (tours) cela prendrait-il?

Le nombre minimal de chemins possible est de 15 puisqu'il y a 30 points d'extrémité (il serait plus élevé si vous aviez des boucles pures). Le nombre minimal de champs qui peuvent toucher toutes les villes est de 1. Nous avons donc besoin d'au moins : 15 (chemins) + 13 (villes complétées) + 1 (villes incomplètes) + 1 (champs) + 6 (cloîtres) = 36 meeples.

Il se trouve justement que nous avons besoin exactement du nombre d'opportunités de placer des meeples qu'il y a de tours pour le premier joueur, c'est une coïncidence incroyable! Ce qui signifie qu'il est tout juste possible de saisir toutes les caractéristiques possibles dans une solution optimale. Cela signifie également qu'il est impossible de marquer plus de points même en jouant en solitaire.

Est-il possible de construire une carte qui respecte tous ces critères?

Avec beaucoup d'essais guidés et d'erreurs, j'ai trouvé une façon possible de construire ladite carte : Il ne serait pas difficile de trouver un ordre de pose des tuiles et de placement des meeples pour réaliser cela car vous n'aurez pas besoin de coordonner les 7 meeples étant dans les champs comme vous le feriez pour la solution de la troisième édition. À la fin, il vous suffira d'avoir 1 meeple dans le grand champ et 1 sur la tuile de ville incomplète.

C'était plus facile à construire que la solution de la 3ème édition en termes de champs mais beaucoup plus difficile en termes de chemins.