Algorithmique.pdf

(86 KB) Pobierz
Exploration d’espace d’état
Une classe particulière d’algorithmes,
utilisés dans de nombreuses situations, permettent de résoudre
les problèmes qui se ramènent à
l’exploration d’un espace d’états.
En particulier dans le cas des jeux à information ouverte
(i.e. des jeux où toute l’information nécessaire est constamment accessible),
les nœuds de l’arbres des états sont les différentes situations du jeu, associées
à l’indication du joueur dont c’est le tour de jouer
Par exemple, aux échecs, un état est la donnée d’une configuration
sur l’échiquier, associée à une information du type «c’est aux blancs de jouer».
Informatique II
Algorithmique
– 76 –
Exemple d’états pour le jeu d’échecs
• Si c’est aux blancs de jouer, ils gagnent
en 1 coup (Dame-H8)
• Si c’est aux noirs de jouer, ils
peuvent
gagner en 3 coups...
Informatique II
Algorithmique
– 77 –
Le jeu des allumettes (1)
Comme exemple d’illustration, nous allons
considérer un jeu très simple,
le jeu des allumettes.
6
Ce jeu se joue à deux.
La situation de départ est un nombre donné
d’allumettes (ce nombre sera appelé la dimension du jeu),
associé à l’indication du joueur qui doit commencer le jeu.
Chacun des joueurs retire alors à tour de rôle
1, 2 ou 3 allumettes parmi les allumettes encore disponibles.
Le joueur qui gagne est celui qui réussit
à retirer la (ou les) dernière(s) allumette(s).
6. Ce jeu, connu sous bien d’autres noms - par exemple «le dernier des mohicans», admet de nombreuses variantes.
Informatique II
Algorithmique
– 78 –
Le jeu des allumettes (2)
Exemple:
déroulement d’un jeu de dimension 11, le joueur 1 débute
Coup joué
11 allumettes disponibles
le joueur 1 retire 3 allumettes 8 allumettes disponibles
le joueur 2 retire 2 allumettes 6 allumettes disponibles
le joueur 1 retire 2 allumettes 4 allumettes disponibles
le joueur 2 retire 1 allumettes 3 allumettes disponibles
le joueur 1 retire 3 allumettes 0 allumettes disponibles
Etat
la main est au joueur 1
la main est au joueur 2
la main est au joueur 1
la main est au joueur 2
la main est au joueur 1
fin du jeu
le joueur 1 gagne...
Informatique II
Algorithmique
– 79 –
Le jeu des allumettes (3)
Représentation en graphe (en arbre) des étapes du jeu:
Chaque niveau de l’arbre correspond aux coups possibles d’un joueur, en alternance (cette
alternance est représentée ci-après par des sommets en forme de cercles ou de rectangles).
Un
sommet
représente le
nombre d’allumette encore disponible
pour le joueur associé à la profondeur du sommet (mis en évidence par sa forme)
Les fils d’un sommet sont alors les situations accessibles en un coup
à partir de la situation décrite par le nœud père.
Exemple:
à partir de l’état «11 allumettes disponibles, le joueur 1 doit jouer»,
les trois états accessibles sont:
11
-3
-2
-1
8
9
10
Informatique II
Algorithmique
– 80 –

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin