rédaction

salut, voila un début de rédaction de quelques points qui vont sans doute avoir leur place dans le rapport....dites moi ce que vous en pensez:bounce:



Avertissement : ceci est un
1^er jet écrit sur le tas !





Algorithme de jeu :
stratégie de déplacement du point de vue de l’ordinateur





Tout d’abord
on peut remarquer que toute partie de Dames Chinoises se décompose en trois
grandes phases d’encombrement du plateau de jeu:





-la
sortie des pions : le plateau reste relativement dégagé, chaque joueur
cherchant en général à faire sortir un maximum de pions, tout en les laissant
groupés pour pouvoir faire des sauts assez grands,





-« l’embouteillage » :
c’est une phase importante de la partie, où la majorité des pions est arrivée
dans l’hexagone centrale, et l’encombrement est désormais assez important. Les
déplacements deviennent de plus en plus difficiles à trouver,





-le
désengorgement : vers la fin de la partie, la situation se débloque assez
vite, car la majorité des pions commence à être près de son arrivée. Il est
donc important de ne pas avoir laissé de pions à la traîne.





L’ordinateur
va donc chercher à avancer ses pions en privilégiant ceux qui sont le plus en
retrait. Pour cela, chaque fois que ce sera à lui de jouer, il va parcourir la
matrice du plateau en commençant par le bas, et il regardera les déplacements
potentiels des trois pions les plus éloignés de la destination finale. Le choix
de trois pions à étudier à chaque coup est arbitraire, mais il nous a paru
important de limiter ce nombre pour que le temps de recherche soit raisonnable.


Lorsque l’on
tient compte de la réaction de l’adversaire, on conservera les mêmes trois
pions à déplacer pour limiter la taille de l’arbre d’exploration des chemins
possibles plusieurs coups à l’avance.


On ne
favorisera pas les déplacements qui amènent les pions les plus au centre du
plateau car en milieu de partie, c’est la zone la plus encombrée, et il est
parfois plus facile alors de passer sur le côté. (On pourrait envisager une
fonction qui évalue à chaque coup la densité du plateau de jeu, et qui décide
en fonction si elle privilégie les déplacements centraux ou pas.)(Commentaire
qui irait dans une ouverture dans le rapport.)





Commentaires sur des
subtilités de programmation





-la fonction ListeDeplacementSaut :


Lors de la
récursivité après le premier saut, afin de déterminer si d’autres sont
possibles, on prend pour référence l’état de jeu enregistré dans la matrice
Plateau, qui n’a donc pas été modifiée (les déplacements calculés sont
enregistrés dans les matrices Deplacement et Saut) simplement en modifiant les
coordonnées du pion, compte tenu du coup précédent. Comme on a un contrôle qui
évite au pion de tourner en rond, on ne risque pas de revenir sur nos pas. De
plus cela évite d’avoir à modifier constamment la matrice Plateau, qui sert à
l’affichage.

-choix
de la représentation de l’arbre :


On veut représenter l’ensemble des chemins
possibles pour l’ordinateur en fonction de la réaction sur un coup de
l’adversaire. La stratégie consiste à déterminer, pour un état de plateau donné
(c’est à l’ordinateur de jouer), les trois pions de l’ordinateur les plus en
retrait sur le plateau. Pour chacun de ces pions on évalue les trois meilleurs
déplacements possibles sur ce coup (étage 1 de l’arbre).


Ces valeurs
vont être stockées, puis, pour chacune d’entre elles, on va évaluer les
réponses potentielles de l’adversaire.


Pour chaque
pion de l’ordinateur de l’étage 1, on évalue les trois pions les plus en
retrait de l’adversaire (on suppose qu’il applique la même méthode que
l’ordinateur et qu’il cherche à déplacer ses pions de façon groupée) et on
calcule les trois meilleurs déplacements qu’ils peuvent faire (étage 2 de
l’arbre).


Pour chaque
pion de l’étage 1 on a maintenant 9 réactions possibles de la part de
l’adversaire.


C’est de
nouveau à l’ordinateur de jouer, et on évalue de la même façon les déplacements
possibles pour trois pions de l’ordinateur. On se retrouve donc avec trois
arbres en parallèle (issus des trois pions initialement choisis par
l’ordinateur à l’étage 1) ayant 27 feuilles chacun.


Concernant la
représentation des trois arbres, il était possible d’utiliser soit des listes
indiquant les frères de chaque pions, soit des tableaux où il est peut-être plus facile de
retrouver le déplacement et le pion qui ont engendré la situation de plateau.(l’explication
est en chantier)





-choix de la profondeur de l’arbre et du nombre de déplacements
potentiels retenus :


Deux
schémas ont été envisagés : soit l’ordinateur calcule l’ensemble des
possibilités de déplacement jusqu’à la rentrée de l’un de ses pions dans la
partie adverse pour décider du meilleur coup à jouer, soit il effectue le
calcul sur un nombre limité de coups.


A
priori la première méthode semble plus efficace, mais elle est également
beaucoup plus lourde à gérer pour l’ordinateur. Un moyen de limiter
l’arborescence dans la recherche des différents chemins possibles est de
n’envisager que le meilleur déplacement pour chacun des pions mis en jeu. Par
exemple, on choisit à l’étage 1 les trois pions A, B, C les plus en retrait de
l’ordinateur, et on leur affecte uniquement le meilleur déplacement (au
lieu des trois meilleurs). A l’étage suivant, pour le pion A, on regarde les
trois pions a, b et c les plus en retrait de l’adversaire, et on leur affecte le
meilleur déplacement possible. Ainsi, à l’étage 2 on se retrouve avec trois
feuilles au lieu de neuf, et ainsi de suite. Si l’on veut encore plus simplifier,
on peut également limiter le nombre de pions à déplacer. L’inconvénient de
cette méthode « à long terme » est que, en la simplifiant, on ne
tient pas compte du fait que l’adversaire (qui est humain, rappelons-le) risque
de changer de tactique en cours de route. En effet, rien ne prouve qu’il va
chercher pendant toute la partie à ne faire avancer que ses pions les plus en
retrait. De plus, plus on élabore des stratégies à long terme, et plus elles
ont de chances d’être contrariées, par exemple par un coup
« imprévisible » de la part de l’adversaire.


La
deuxième méthode permet de se dédouaner de ce facteur
« imprévisible ». En ne regardant les coups possibles que sur un
petit nombre d’alternances ordinateur/adversaire, on a moins de chances de se
tromper sur les réactions possibles de l’adversaire, et on peut étudier un plus
large éventail de réactions possibles. (C'est-à-dire que pour chaque pion
déplacé au coup i-1, on choisit trois pions chez l’adversaire, et on attribue à
chacun trois déplacements possibles.)

la mise en page de word y connait pas...pour indic ca fait seulement 2 pages de texte

voila la suite, un peu plus structurée.


Introduction


·
Rappel du sujet : contexte et objectif
recherché (1)


·
Présentation « large » du domaine dans
lequel le projet s’intègre (2)


·
Annonce du plan (3)


Rapport


·
Introduction au sujet


o Intitulé du projet (4)


o Présenter le jeu de dames (5)


o
Intérêt du point de vue de l’application :
gestion d’arbres, graphes… (6)


o
Fixer le vocabulaire (7)


o
Les limites (


·
Analyse du problème


o
Expliquer la méthode retenue pour résoudre le
problème, et dire pourquoi d’autres ont été abandonnées (9)


o
Décrire un algorithme intéressant (10)


o
Etude de la complexité des algorithmes (11)





Intitulé du projet (4)





Le projet a consisté à programmer
un jeu de Dames Chinoises, permettant à un joueur humain de jouer contre un
adversaire de la même espèce, ou bien contre l’ordinateur. C’est ce deuxième
aspect qui va être développé.





Présentation du jeu de Dames Chinoises (5)





Le jeu de
Dames Chinoises aurait été inventé par un américain dans les années 1880, et
n’aurait de chinois que le nom, mais le jeu a tout de même eu un franc succès
en Chine. Il peut y avoir de deux à six joueurs. Le jeu se pratique sur un
plateau en forme d’étoile à six branches (photo), dont les extrémités sont
occupées par les dix pions des six joueurs potentiels. Les pions ont la
possibilité de se déplacer car le plateau est troué régulièrement.


L’objectif de chaque joueur est d’amener le
premier l’ensemble de ses pions dans la branche située en face de lui.


L’un des
intérêts de ce jeu est qu’il n’y a pas suppression des pions au fur et à
mesure. Il faut donc apprécier le jeu en prenant en compte l’ensemble des
pions.


A chaque coup,
le joueur à la possibilité de déplacer l’un de ses pions. Il peut soit lui
faire faire un déplacement simple de sa case vers une case adjacente, ou bien
il peut sauter par-dessus un pion adjacent, si la case derrière celui-ci est
vide. Dans le cas d’un saut par-dessus un autre pion, on peut en effectuer
plusieurs d’affilée, tant qu’ils ne nécessitent pas de déplacement simple au
cours de l’enchaînement. (Mettre des illustrations)





Intérêt du point de vue de l’application : gestion
d’arbres, graphes… (6)





Il
nous a semblé intéressant de s’attaquer à ce jeu, car il nous permettait
d’élaborer pour l’intelligence artificielle différentes stratégies de choix de
déplacement en fonction ou pas de la réaction de l’adversaire. Nous avons donc
pu introduire une fonction Min-Max, et gérer la construction et le parcours
d’arbres, ce qui s’. (En chantier j’ai pô d’idée.)





Fixer le vocabulaire (6)

ouh là là, y'en a beaucoup! j'essaie de tt lire et tt comprendre mais pour l'instant ce que j'ai lu me semble très bien

il faudrait vraiment faire une séance pour se partager la rédaction en tt cas, parce que je préfère bosser sur word, c plus pratique.

en attendant samedi voila un peu de lecture:


Intérêt du point de vue de l’application : gestion d’arbres,
graphes… (6)





Il
nous a semblé intéressant de s’attaquer à ce jeu, car il nous permettait
d’élaborer pour l’intelligence artificielle différentes stratégies de choix de
déplacement en fonction ou pas de la réaction de l’adversaire. Nous avons donc
pu introduire l’algorithme minimax, et gérer la construction et le parcours
d’arbres, servant à évaluer quels déplacements seraient les plus judicieux. (En
chantier j’ai pô d’idée.)





Fixer le vocabulaire (6)





Pour plus de commodité, on fixe
les dénominations suivantes :


-un déplacement simple
consiste à se déplacer depuis une case vers une autre qui lui est
directement adjacente. Ceci exclue donc tout saut par-dessus un autre pion.


-un saut, comme son
nom l’indique, désigne un déplacement effectué par-dessus un autre pion.


-on regroupe désormais sous le
terme de déplacement soit un déplacement simple, soit une suite
de sauts consécutifs. Cela revient à désigner la réaction d’un joueur sur un
seul coup.


-un chemin désigne
une suite de déplacements en plusieurs coups, pour un joueur.


-lorsque l’on a effectué un coup,
cela veut dire que chacun des joueurs a joué en faisant un déplacement (ici, le
joueur humain et l’ordinateur).


-un demi-coup a lieu lorsque un
seul des deux joueurs a effectué son déplacement.


(photos)





Limites (





L’objectif
de ce projet est de présenter une intelligence artificielle capable de choisir
le déplacement le plus avantageux pour lui, en tenant compte des différentes
réactions possibles de l’adversaire.


Pour des
raisons de simplicité nous avons dû poser quelques limites :


-le programme a été conçu pour
deux joueurs ayant chacun dix pions,


-seules deux branches
diagonalement opposées sont donc utilisées. Les autres sont considérées comme
« interdites » aux pions.


-pour choisir son déplacement le
plus optimal, l’ordinateur n’évalue qu’un nombre limité de ses pions,


-autre chose ?