Stratégie gagnante ?

Avant de commencer à vous lancer dans le projet de conception d’un jeu, mettez vous à la place des joueurs.

L’unique préoccupation d’un joueur est de savoir quel est le meilleur coup à jouer dans une situation donnée. Prenons l’exemple d’un jeu où le gagnant est désigné parmi les joueurs ayant le plus de points.

Étapes à suivre:

» Représenter la situation :

Pour représenter les différentes situations possibles d’un jeu, on a souvent recours à un arbre d’états ou à un graphe d’états où chaque sommet représente une situation possible.

» Rechercher la ou les solutions :

Il n’existe pas de méthode générale de résolution de problèmes.

Malgré tout, comment essayez de résoudre un problème ? On a recours principalement à deux méthodes constructives:

  • avancer par étapes qui sera développer par la suite;

  • décomposer en sous-problèmes.

Ne restera plus qu’à les traduire en algorithme sans oublier de prouver la terminaison et la correction de celui-ci. (voir 3.3)

» Évaluer l’algorithme de recherche :

Les critères à prendre en compte:

  • complétude: si une solution existe, l’algorithme de recherche la trouve;

  • complexité en temps: temps nécessaire pour trouver la solution (voir 3.3);

  • complexité en espace: espace mémoire nécessaire pour l’usage de l’algorithme;

  • optimalité: la solution trouvée est-elle la meilleure.

Un peu de pratique …

Pour le jeu représenté par l’arbre précédent, proposez différentes méthodes de recherche afin d’obtenir une stratégie optimale (maximum de points en un minimum de coups joués).
Préciser le nombre d’arêtes empruntées lors de votre recherche pour aboutir à votre proposition.

Quelques méthodes parmi d’autres:

  • rechercher toutes les possibilités (parcours en largeur ou en profondeur au programme de Terminale).
    Avantage: on trouve toutes les solutions.
    Inconvénient: coûteux en temps et/ou en mémoire (irréaliste dans la plupart des situations).

  • rechercher au hasard.
    Avantage: on trouve une solution.
    Inconvénient: aucune garantie de l’optimalité de la solution et coût important en temps et en mémoire.

  • rechercher suivant une heuristique (recherche dans un arbre non complétement connu). Dans notre cas, la recherche sera guidée par le choix de maximiser le gain.
    Avantage: on trouve une solution approchée (optimale dans certains cas), rapidité.
    Inconvénient: suivant les cas, non optimalité de la proposition, et solution incomplète.
    Ce dernier algorithme est dit glouton (greedy en anglais).


Dans les exercices suivants, vous serez amener à proposer et programmer un algorithme glouton dans divers contexte pas uniquement dans des jeux quoiqu’on peut considérer un exercice de mathématiques comme tel !

Exercice 1: un peu de géométrie …

On dispose d’un rectangle de dimensions entières.
Question: combien de carrés de côté entier sont nécessaires au minimum pour le recouvrir ?

a) Soit un rectangle de dimensions 2 sur 3. Répondre à la question posée en y précisant les côtés des carrés utilisés et leurs effectifs respectifs.
b) Soit un rectangle de dimensions 11 sur 13. Même question que précédemment.
c) Proposer un algorithme glouton écrit en Python qui permettra d’approcher de la solution.
Vous nommerez la fonction recouvrir() ayant pour paramètres largeur et longueur. Elle retournera la solution sous la forme d’un dictionnaire dont les clés seront les dimensions des carrés utilisés et les valeurs associées seront leurs effectifs.
Vous y ajouterez des tests tirés des questions précédentes.

Cet algorithme glouton ne fournit pas de solution optimale dans tous les cas.


Exercice 2: rendu de monnaie

On dispose d’un système monétaire composé de pièces et de billets de valeurs différentes.
Question: combien de pièces et de billets sont nécessaires au minimum pour payer sur une somme entière donnée ?

a) Cas du système monétaire européen avec des pièces ou des billets de 50€, 20€, 10€, 5€, 2€ et 1€.
(i) Peut-on payer n’importe quelle somme enière avec ce système ?
(ii) Répondre à la question de l’énoncé avec une somme de 48€.
(iii) Peut-on payer d’une autre façon cette somme ?
(iv) Combien de manières différentes y a-t-il exactement ? Aide: vous pourrez faire usage d’une fonction en Python pour y répondre.

b) Cas de l’ancien système monétaire britanique avec des pièces ou des billets de 30€, 24€, 12€, 6€, 2€ et 1€.
(i) Peut-on payer n’importe quelle somme enière avec ce système ?
(ii) Répondre à la question de l’énoncé avec une somme de 48€.
(iii) Peut-on payer d’une autre façon cette somme ?
(iv) De combien de façons ?

c) Proposer un algorithme glouton écrit en Python qui permettra d’approcher de la solution.
Vous nommerez la fonction payer() ayant pour paramètres la somme entière à payer somme et le système monétaire représenté par la liste systeme. Elle retournera la solution sous la forme d’un dictionnaire dont les clés seront les montants du système monétaire et les valeurs associées seront leurs effectifs.
Vous y ajouterez des tests tirés des questions précédentes.

Cet algorithme glouton fournit une solution optimale avec le système monétaire européen. Dans ce cas, on dit que ce système monétaire est canonique.


Exercice 3: du travail … encore du travail !

Cet exercice provient d’un puzzle présent sur la plateforme CodinGame [^1].

Le bon vieux maître Mason veut construire un mur. Il dispose d’un nombre de briques gisant sur le sol, chacune avec des poids différents . La hauteur des briques est de \(6,5 , cm\). Le mur est construit par le bas; dans chaque rangée ne peut pas être plus de briques que dans la rangée en dessous. Les briques peuvent être placées juste au-dessus, si la condition précédente est remplie. Dans chaque rangée, il y a une place pour le maximum donné de briques.

Maître Mason veut minimiser son travail. Se souvenant de la vieille école et des cours de physique, il calcule le travail comme suit. Si une brique est construite dans la rangée L à partir du sol, le travail nécessaire pour placer cette brique est:

\(W = d \times g \times m\) , où \(m\) est la masse de la brique mesurée en kilogrammes et \(g = 10 , m/s^2\) est la valeur approximative de l’accélération gravitationnelle, enfin \(d = ((L-1) \times 6,5 / 100\) mesure la distance à laquelle la brique doit être levée en mètres.

Notez que la rangée la plus basse est la première rangée de briques montées.

Question: calculer le travail minimal que Master Mason peut construire toutes les briques dans un mur (pas nécessairement rectangulaire).

Implémenter une fonction en Python mur() de paramètres lg, le nombre total de briques par rangée, et masses, la liste des masses de chacune des briques. Elle retournera w, l’effort répondant à la question centrale de l’exercice.

Jeu de tests:

>>> mur(2, [100, 10, 150])
6.5
>>> masses = [21, 15, 5, 9, 5, 7, 9, 11, 11, 11, 20, 3, 8, 21, 8, 10, 19, 15, 6,
5, 18, 6, 8, 17, 18, 12, 1, 10, 19, 5, 14, 16, 9, 15, 3, 5, 4, 5, 3, 6, 19, 1]
>>> mur(7, masses)
436.15

Cet algorithme glouton retourne la solution optimale dans tous les cas.

Exercice 4: … c’est cadeau !

Cet exercice provient d’un autre puzzle présent sur la plateforme CodinGame. Il fait référence à des personnages présents dans la série britanique Docteur Who.

Énoncé :

Les Oods veulent offrir un cadeau à l’un d’entre eux. Seulement, tous ont un budget différent à investir dans ce cadeau, et bien sûr, leur unique souhait est de parvenir à déterminer le partage qui soit le plus équitable possible tout en restant dans les limites des budgets de chacun. Les Oods réfléchissent à la méthode optimale depuis des jours et n’ont toujours pas réussi à s’accorder sur une solution satisfaisante.

Objectif : Le Docteur décide donc de leur donner un coup de main en créant un programme. Son idée est de s’assurer que les Oods ont assez d’argent pour acheter le cadeau et si oui, de déterminer la somme dont chaque Ood devra s’acquitter dans la limite de son budget.

Le Docteur a en main la liste des budgets maximum de chaque Ood. Pour respecter les aspirations démocratiques des Oods et pour départager les différentes solutions, le Docteur décide que :

  • aucun Ood ne peut mettre plus que son budget maximal,

  • la solution optimale est celle pour laquelle la plus grande contribution est minimale,

  • s’il y a plusieurs solutions optimales, on prend la solution pour laquelle la deuxième plus grande contribution d’un participant est minimale et ainsi de suite…

De plus pour faciliter les comptes, le Docteur souhaite que la participation de chacun soit un nombre entier de la monnaie locale (personne ne doit donner de centimes).

Exemple 1:

On souhaite acheter un cadeau qui coûte 100. Le premier Ood dispose d’un budget de 3, le deuxième d’un budget de 45 et le troisième d’un budget de 100. Dans ce cas,

Budget Solution
3 3
45 45
100 52

Exemple 2:

On souhaite toujours acheter un cadeau qui coûte 100, mais le deuxième Ood dispose cette fois d’un budget de 100. Dans ce cas:

Budget Solution
3 3
100 45
100 49

Implémenter une fonction en Python partage() de paramètres prix, le prix du cadeau, et budgets, la liste des budgets dans l’ordre croissant de chacun des Oods . Elle retournera repartition, la liste donnant la contribution de chaque des Oods en respectant les consignes de l’énoncé.

Jeu de tests:

>>> partage(100, [10, 100, 100])
[10, 45, 45]
>>> partage(100, [20, 20, 40])
'Impossible'
>>> partage(10, [5, 5, 10])
[3, 3, 4]
>>> partage(420, [10, 23, 24, 45, 91, 94, 94, 113, 120, 169, 181, 196])
[10, 23, 24, 40, 40, 40, 40, 40, 40, 41, 41, 41]

Cet algorithme glouton retourne une des solutions optimales répondant aux exigences de l’énoncé.


##### Notes de bas de page: [^1]: C'est un site fondé par une startup française. Il est consacré à la programmation via des casses-têtes. Quelques entreprises l'utilisent afin de recruter leurs futurs collaborateurs.