Modélisation d'une pioche

[Alphasaft]

Bonjour,

J'aimerais étudier le jeu simplifié suivant :

On constitue un deck de N cartes au total, choisies comme le joueur le veut parmi (2m) types de cartes distinctes. Rien ne distingue deux cartes d'un même type. On mélange ensuite le deck. Le joueur n'a donc pas de contrôle sur l'ordre des cartes, uniquement sur la composition du deck.

La règle du jeu est la suivante : le joueur commence avec aucune carte en main. Il pioche à chaque tour une nouvelle carte du dessus du deck, qu'il ajoute à sa main ; il n'y a pas de limite au nombre de cartes pouvant être dans la main en même temps.
Il peut ensuite effectuer autant de fois l'action suivante : pour tout k entre 1 et m, il peut associer A(k) cartes de type 2k - 1 et B(k) cartes de types 2k (où A(k) et B(k) sont des entiers dépendant uniquement de k) pour valider une figure de valeur C(k), et placer ces cartes de coté. Au début de chaque tour, chaque figure validée par le joueur lui rapporte autant de points que sa valeur ; le joueur peut donc avoir intérêt à former rapidement des figures de valeur peut-être moindre, mais qui rapporteront plus de points sur la durée. Evidemment, le joueur pose ses figures dès qu'il le peut. Le jeu s'arrête quand le deck est épuisé.

La problématique est donc : comment composer le deck pour que l'espérance des points gagnés en fin de partie soit maximale en fonction de A, B et C ?

Je me demandais :
* si ce problème appartenait à un type de problème connu
* si l'on disposait d'outils permettant de le modéliser correctement (je me doute que composer un deck revient à choisir une loi pour une variable aléatoire X, et qu'on va calculer les points en fonction de A, B, C, et de X, mais je ne sais pas comment choisir une bonne représentation pour ce processus, sachant qu'il dispose d'une mémoire, donc pas de chaînes de Markov à priori, ou alors une très complexe) et d'en déduire des faits intéressants
* et le plus important, si vous pourriez m'orienter vers des ressources (articles de recherche, leçons, exercices, etc) qui me permettrait de répondre, au moins partiellement, à la problématique.

Un grand merci d'avance !
-----

[MissJenny]

Tu ne dis pas tout. Par exemple, il y a 2m types de cartes, mais combien de cartes d'un même type?

et autre chose : puisque c'est un jeu je suppose qu'il y a au moins 2 joueurs, mais tu n'en parles pas.

[Alphasaft]

On suppose qu'on dispose d'un nombre infini de cartes de chaque type pour composer le deck comme l'on veut.
Par contre il n'y a aucun second joueur ; j'ai appelé ça un 'jeu' mais la seule chose que l'unique joueur fait, c'est composer un deck (la phase de tirage pouvant dans les fait se faire automatiquement).
D'ailleurs le jeu de la vie demande de même un unique joueur et aucune intervention externe autre que la donnée de la configuration initiale.

[MissJenny]

ce que je ne comprends pas c'est que s'il n"y a qu'un seul joueur et s'il peut tirer autant de cartes qu'il veut, quel intérêt a-t-il à se débarrasser de cartes avant d'avoir épuisé le "deck"? Il me paraît préférable de piocher toutes les cartes. Et dans ce cas, l'ordre des cartes ne joue aucun rôle.

[A voir en vidéo sur Futura]

[Alphasaft]

Le but du jeu est d'attribuer des points en fonction d'à quel points les figures sont formées tôt.
Par exemple, si je dispose des types 1 2 3 4, avec pour figures 1+1+1+2 -> deux points, 3+3+4+4 -> trois points, et que je tire dans l'ordre:

1
2
1
3
1 --> première figure, 1+1+1+2, qui me rapportera 2 points à chaque tour
3 (+2 pts car figure 1+1+1+2)
2 (+2 pts)
3 (+2 pts)
4 (+2 pts)
1 (+2 pts)
2 (+2 pts)
4 --> deuxième figure, 3+3+4+4, qui me rapportera 3 points à chaque tour (+2 pts)
3 (+2 pts) (+3 pts car figure 3+3+4+4)
1 (+2 pts) (+3 pts)
Fin du deck


Ce deck m'a rapporté 2*9 + 3*2 = 24 points.
L'idée c'est : le joueur épuise certes son deck dans tous les cas mais puisqu'il tire les cartes une à une, et que chaque figure rapporte des points à chaque carte tirée, l'ordre importe.

Je précise aussi qu'il n'y aucun intérêt à garder des cartes dans sa main puisque les figures sont totalement indépendantes : dès qu'on a les cartes, il faut les poser (d'où l'idée que le joueur n'est pas nécessaire : simplement faire un programme qui tire une à une les cartes en décomptant les points conviendrait aussi)

[MissJenny]

je ne perçois pas tellement l'intérêt de ce jeu, mais pour répondre à ta question sur la composition du deck : n'y mettre que les cartes qui font partie de la ou des figures rapportant le plus de points.

[Alphasaft]

Je le perçois, c'est ça qui compte.
Ok, merci pour votre temps.

[Alphasaft]

Un petit doute néanmoins sur votre réponse (qui résulte peut être de moi qui m'exprime mal) : si il existe une figure 1+1+1+1+1+1+1+2 à 201 points, et une figure 3+3+3+3+4+4+4+4 à 200 points sur un grand deck, je ne suis pas convaincu que la figure 1 soit à preferer (ça ne me paraît effectivement pas aberrant, mais loin d'être trivial à montrer dans le cas où c'est bien la solution optimale) .