This repository has been archived by the owner on Feb 10, 2022. It is now read-only.
-
Notifications
You must be signed in to change notification settings - Fork 0
/
rapport_projet.tex
177 lines (125 loc) · 8.53 KB
/
rapport_projet.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
\documentclass[12pt]{article}
\usepackage[french]{babel}
\usepackage[utf8x]{inputenc}
\usepackage{amsmath, amsthm, amssymb, amsfonts}
\usepackage{graphicx}
\usepackage[colorinlistoftodos]{todonotes}
\usepackage{color}
\usepackage{pifont}
\usepackage{wrapfig}
\usepackage[Glenn]{fncychap} %Conny, Glenn, Bjarne, Bjornstrup, Rejne, Lenny
\frenchbsetup{StandardLists=true}
\usepackage[a4paper,pdftex]{geometry} % Use A4 paper margins
\usepackage[french]{babel}
\usepackage{multicol}
\usepackage[version=3]{mhchem}
\usepackage{hyperref}
\usepackage{tikz}
\usepackage{xcolor}
\usepackage{xcolor,rotating,epic,eepic}
\usepackage{tikz-qtree}
\usetikzlibrary{matrix}
\usepackage{fancyhdr}
\usepackage{xcolor,rotating,epic,eepic}
\usetikzlibrary{%
arrows,%
calc,%
shapes.geometric,%
shapes.misc,%
shapes.symbols,%
shapes.arrows,%
automata,%
through,%
positioning,%
scopes,%
decorations.shapes,%
decorations.text,%
decorations.pathmorphing,%
shadows}
\definecolor{orange}{cmyk}{0,0.5,1,0}
\definecolor{forestgreen}{rgb}{0.13,0.54,0.13}
\definecolor{carmine}{rgb}{0.59, 0.0, 0.09}
\definecolor{grey}{rgb}{0.5,0.5,0.5}
\definecolor{blue}{rgb}{0.2, 0.2, 0.6}
\begin{document}
\newcommand{\HRule}{\rule{\linewidth}{0.5mm}}
\begin{titlepage}
\renewcommand{\HRule}{\rule{\linewidth}{0.5mm}}
\center
\textsc{\LARGE Ecole Polytechnique de Louvain}\\[1cm]
\HRule \\[0.4cm]
{ \huge \bfseries Informatique II}
\HRule \\[1cm]
\vspace{3cm}
\fbox{
\begin{minipage}{10cm}
\begin{center}
\vspace{0.5cm}
\Huge{\textbf{Rapport de projet}}
\vspace{0.5cm}
\end{center}
\end{minipage}}
\vspace{4cm}
\begin{minipage}{6cm}
\begin{center}
Antoine Gennart
\end{center}
\end{minipage}
\begin{center}
Réalisé le \today.
\end{center}
\end{titlepage}
Dans le cadre de ce projet, il nous a été demandé de réaliser un jeu "Qui oz-ce" du même style que le célèbre jeu "Qui est-ce" . Notre jeu part d'une base de données sur les différents membre de l'équipe des Diables Rouges de la coupe du monde 2014, contenant des questions et des réponses permettant de les identifier. \\
Il nous a été demandé de réaliser avant tout une solution de base qui se diviserait en trois étapes.\\La première, \textbf{lire la base de donnée}, nous a été fournie. Les deux étapes qu'il nous restait à implémenter étaient \textbf{construire un arbre de décision pour guider la tache suivante} et \textbf{poser les questions au joueur humain pour trouver la personne choisie}.\\
\section{Construire un arbre de décision (BuildDecisionTree)}
Tout abord, nous avons implémenté la construction d'un arbre basique, qui prendrait en compte les questions dans leur ordre d'apparition. Cela nous a permis de comprendre la structure fondamentale que devait prendre cette fonction, et donc cet arbre.\\
La fonction prend la \textbf{database} en argument et une sous fonction crée immédiatement la liste des questions à poser selon leur apparition dans la base de données. Dans le cas simple, la liste des questions est crée dans l'ordre de d'apparition de celles-ci. Pour chacune d'entre elles, la fonction auxiliaire parcourt toute la database et construit une \textbf{ListFalse}, contenant les noms des joueurs dont la réponse à la question actuelle est \textbf{false}, ainsi qu'une \textbf{ListTrue}, contenant les noms des joueurs dont la réponse à la question est \textbf{true}.\\
La première question posée constitue le noeud principal à partir duquel l'arbre de décision va être construit.\\ Cet arbre sera ensuite construit par \textbf{appels récursifs} de la fonction\\ {\fontfamily{lmtt}\selectfont \{BuidDecisionTreeAcc ..\}} avec, à chaque appel, la question suivante. A \textbf{droite} de toute question (=noeud), la fonction sera appelée avec la \textbf{liste true} à la place de la \textbf{database}, alors qu'à \textbf{gauche} elle sera appelée avec la \textbf{liste false}.\\
Une fois que toutes les questions ont été posées, c'est à dire que la \textbf{"question" est nil}, la fonction \textbf{renvoie une liste} contenant tous les joueurs encore présents dans la \textbf{database actuellement prise en compte} par celle-ci, à savoir une liste false ou true.\\
ListOfQuestions = [Question1 Question2 Question3 ...]\\
\begin{figure}[h]
\centering
\begin{tikzpicture}[>=stealth,sloped]
\matrix (tree) [%
matrix of nodes,
minimum size=0.25cm,
column sep=0.25cm,
row sep=1.5cm,
]
{
& & &\fbox{\begin{minipage}[t]{0.2\textwidth}\begin{center}Question 1\end{center} \end{minipage}}& & & \\
& & \fbox{\begin{minipage}[t]{0.3\textwidth}\begin{center}ListTrue = [P1, P2,...]\end{center} \end{minipage}}
& & \fbox{\begin{minipage}[t]{0.3\textwidth}\begin{center}ListFalse = [P3, P4,...]\\\end{center} \end{minipage}} & & \\
& & \fbox{\begin{minipage}[t]{0.2\textwidth}\begin{center}Question2\end{center} \end{minipage}} &
& \fbox{\begin{minipage}[t]{0.2\textwidth}\begin{center}Question2\end{center} \end{minipage}} & &\\};
\draw[->] (tree-1-4) -- (tree-2-3) node [midway,above]{}; %{$P$};
\draw[->] (tree-1-4) -- (tree-2-5) node [midway,above]{}; %{$(1-p)$};
\draw[->] (tree-2-3) -- (tree-3-3) node [midway,below]{}; %{$(1-p)p$};
\draw[->] (tree-2-5) -- (tree-3-5) node [midway,below]{}; %{$(1-p)^2$};
\end{tikzpicture}
\caption{\textbf{\label {}Algorithme de la fonction de base}}
\end{figure}
Ensuite, nous avons implémenté différentes améliorations,... \\
Il nous a ensuite été demandé de faire en sorte que notre arbre soit le plus optimal possible. Nous sommes partis sur le principe que l'optimisation de l'arbre se ferait par la maintenance de son équilibre.\\
Nous avons donc implémenté une fonction {\fontfamily{lmtt}{\selectfont \{BestQuestion\}} qui prend en argument la base de données, la liste de question actuelle ainsi qu'une variable unbound, la nouvelle liste de question, qui sera modifée par la fonction. {\selectfont \{BestQuestion\}} renvoie la question qui engendrera la plus petite différence entre le nombre de personnes qui répondront true et celles qui répondront false, afin de maintenir l'arbre le plus équilibré possible.\\
Nous avons également du prendre en compte le nombre de personnes possédant une réponse à la question, non pas pour l'équilibre de l'arbre, mais pour minimiser le nombre de questions à poser pour trouver la bonne personne. En effet, l'extension "unknown" fait en sorte que les personne dont la réponse n'est pas connue se retrouvent dans la liste true et dans la liste false. Nous sommes arrivés au critère de précision suivant : \\
\begin{center}
Abs((\# true)-(\# false)) - (\# réponses)
\end{center}
Cela se fait en plusieurs étapes :
\begin{enumerate}
\item Calcul du critère de précision pour chaque question de la liste. La fonction {\selectfont \{DiffTrueFalseList DB ListOfQuestions\}} parcourt la base de données pour chaque question présente dans la liste de question actuelle et renvoie une liste contenant la valeur critère de précision de chaque question, dans le même ordre que l'apparition des questions dans la liste.
\item Trouver l'emplacement du plus petit élément de la liste des différences, au moyen de {\selectfont \{MinList L\}}
\item Extraire ce $N^{ieme}$ élément de la liste de questions.
C'est la question qui déséquilibrera le moins l'arbre, elle est renvoyée par la fonction {\selectfont \{Nth ListOfQuestion N\}} déjà présente dans Oz.
\item Modifier la "nouvelle liste de question", la variable unbound entrée en argument. La fonction {\selectfont \{RemoveList L Nth \}} retire de la liste de question la "question optimale" qui sera renvoyée afin d'être posée.
\end{enumerate}
Nous devons implémenter deux fonctions principales : \textbf{BuildDecisionTree} qui va créer un arbre de décision le plus optimal possible pour que l'ordinateur pose le moins de questions possibles pour tomber sur la bonne personne. Et \textbf{GameDriver}, qui va, à partir de l'arbre créer par le BuildDecisionTree, décider des questions à poser, et s'il n'y a plus de questions a poser, proposer une solution.
\section{GameDriver}
\section{Extensions}
\subsection{Incertitude dans la base de donnée}
\subsection{Questions non binaires}
\subsection{Incertitude du joueur (true, false, I don't know}
\subsection{Gérer les erreurs du joueur}
\subsection{Bouton "OUPS" (revenir à la décision précédente)}
\end{document}