Yahtzee a été faiblement résolu * pour un joueur unique, et utilise en moyenne le même nombre de dés. Le jeu est probablement à peine plus complexe que le Yahtzee.
Une stratégie optimale pour Roll Through the Ages pour deux joueurs peut-elle être mise en œuvre sur du matériel moderne ?
Deux choses m'inquiètent à propos du jeu à deux joueurs. Le jeu à deux joueurs pourrait techniquement ne jamais se terminer, car aucun des deux joueurs n'est obligé de construire des monuments ou d'acheter des développements. Je ne suis pas certain que cela soit un problème pour la découverte d'une stratégie optimale, mais cela pourrait l'être. Un autre point problématique est que dans RTtA, même si vous ne lancez que 3 dés au départ, vous pouvez lancer jusqu'à 7 dés par tour (dès le tour 3) au lieu des 5 dés de Yahtzee. Cela a déjà triplé le nombre de résultats (en utilisant la méthode de modèle de sac décrit ci-dessous) pour le premier jet d'un tour.
( *Note : Compte tenu de n'importe quel jet de dés, peut-on calculer une stratégie optimale pour "relancer quel dé/construire quel monument/acheter quelle technologie" qui maximisera vos points tout en minimisant vos pertes de manière à ce que vous ayez le plus de chances possible de gagner une partie ? (sur le matériel actuel))
Plus je réfléchis à ce problème, moins je pense que cette communauté possède l'expertise nécessaire pour y répondre. Il conviendrait probablement mieux à Math.SE ou à StackOverflow.
Rouler à travers les âges - (Solitaire Play)
1) Lancer X dés (x = villes, x = 3-7)
1a) Choisissez les dés à conserver ou à relancer (les crânes doivent être conservés dans le jeu multijoueur).
1b) Choisir les dés à conserver ou à relancer (les crânes doivent être conservés dans les parties multijoueurs).
2) Nourrir les villes et résoudre les catastrophes.
3) Construire des villes et/ou des monuments.
4) Vous pouvez acheter jusqu'à 1 développement.
5) Jeter les marchandises excédant 6.
La partie se termine à la fin du tour lorsqu'un joueur a 5 développements ou que tous les monuments ont été complétés par au moins un joueur. (le jeu en solitaire se termine seulement au 10ème tour).
Complexité du jeu
On peut considérer la complexité d'un jeu de deux manières différentes.
Tous les jeux possibles (taille de l'arbre de jeu) ou tous les états de jeu possibles (complexité de l'espace d'état).
D'après ce document Optimisation du Solitaire Yahtzee des scores. Vous pouvez voir l'une des généralisations concernant l'arbre de jeu. L'arbre de jeu complètement spécifié est très complexe.
-
(taille de l'arbre de jeu) = (permutations en lançant 5 dés à six faces) (façons de relancer)^(2 fois) (façons de choisir la ligne de score)
-
(taille de l'arbre de jeu) = (6^5) * (7^5)^(2) * (13 !)
-
(taille de l'arbre du jeu) = (environ) 1,725 10^170
Essayer de résoudre le jeu Yahtzee en utilisant ce modèle n'est pas faisable avec du matériel de bureau moderne. Ce n'est pas un problème, car le modèle précédent reposait sur des hypothèses qui ne sont pas vraies. Tout d'abord, il suppose que vous pouvez faire la distinction entre les différents dés. Ce n'est évidemment pas le cas. Un lancer de { 1, 1, 1, 1, 2} est exactement le même que { 2, 1, 1, 1, 1} (ainsi que 3 autres lancers).
|Value |Lists|Bag|Lists|
+---------+-----+---+-----+
|a,a,a,a,a| 1| 6| 6|
|a,a,a,a,b| 5| 30| 150|
|a,a,a,b,b| 10| 30| 300|
|a,a,a,b,c| 20| 60| 1200|
|a,a,b,b,c| 30| 60| 1800|
|a,a,b,c,d| 60| 60| 3600|
|a,b,c,d,e| 120| 6| 720|
+---------+-----+---+-----+
Total |252| 7776|
+---+-----+Le modèle du sac par rapport au modèle de la liste nous permet de réduire le nombre d'états possibles des dés (de 7776 à 252) ( Note : Pour la RTtA, si vous lancez 7 dés, le modèle du sac n'a que 792 (au lieu de 279936) résultats initiaux au premier lancer). L'utilisation de ce modèle rend plus difficile le calcul de toutes les possibilités de relance. Je n'entrerai pas dans les détails (lisez le livre blanc si vous êtes intéressé), mais cela réduit la taille de l'arbre de jeu à 2,806*10^119 (51 fois moins). Il s'agit d'un modèle de l'ensemble de l'arbre de jeu, qui pourrait être utilisé pour déterminer la stratégie optimale à n'importe quel moment de la partie. Un modèle similaire modèle de sac déterministe peut être utilisé pour la RTtA afin de réduire la complexité, mais ce n'est pas vraiment ce que nous essayons de résoudre. Ce qui nous intéresse vraiment, c'est la complexité de l'espace d'état. Jakub Pawlewicz L'article de l'auteur de l'article a procédé à une optimisation encore plus poussée pour supprimer le nombre d'arêtes (transitions) d'un état (nœud) à un autre, et mentionne que ce qui aurait pris 10 minutes sans l'optimisation des arêtes ne prend plus que 30 secondes sur du matériel moderne.
Plus d'informations recherche .
