1.5 Recherche contr e conna issances
7
1.5 Recherche contre connaissances
Lorsqu'on écrit un programme de jeu il est tentant d'écrire une fonction d'évaluation
élaborée comportant de nombreuses connaissances de façon à bien diriger la recherche
du meilleur coup. Toutefois la complexification de la fonction d'évaluation rend souvent
le programme plus lent pour faire des évaluations et ralentit donc la recherche. Il peut
donc arriver qu'un programme avec une fonction d'évaluation plus élaborée soit moins
bon qu'un programme avec une fonction d'évaluation simple qui fait plus de recherche. Il
devient donc naturel de se poser la question de la pertinence d'ajouter des connaissances
dans la fonction d'évaluation en fonction du ralentissement de la recherche qu'elles induisent.
La figure 1.7 donne les courbes de niveau auxquelles on peut s'attendre en fonction
des connaissances et de l'effort de recherche qu'on donne à un programme de jeu [6 1, 8].
Une courbe représente un niveau du programme constant. On peut remarquer qu'ajouter
des connaissances lorsqu'il y a peu de recherche ou ajouter de la recherche lorsqu'il y a
peu de connaissances améliore peu le programme. La conclusion est qu'il faut garder un
bon équilibre entre recherche et connaissances.
Un étude empirique des courbes recherche versus connaissances a été faite aux Échecs,
à Othello et au Checkers [4 7] mais aussi sur des finales d'Échecs [7 2] et sur le jeu Lines of
Action [10]. Les courbes sont assez proches des courbes théoriques de la figure 1.7. Toutefois, pour les abscisses de l'effort de recherche proches de zéro, les courbes associées
ne montent pas aussi haut que sur la courbe théorique.
1.6 Corrigés des exercices
1.6.1 Coups gagnants à Nim
Dans cette position :
I
III
III!
III II II
1
3
4
7
0001
0011
0100
0111
0001
Les coups gagnants sont de retirer une allumette soit dans le tas à une allumette, soit
dans le tas à trois allumettes soit dans le tas à sept allumettes.
7
1.5 Recherche contre connaissances
Lorsqu'on écrit un programme de jeu il est tentant d'écrire une fonction d'évaluation
élaborée comportant de nombreuses connaissances de façon à bien diriger la recherche
du meilleur coup. Toutefois la complexification de la fonction d'évaluation rend souvent
le programme plus lent pour faire des évaluations et ralentit donc la recherche. Il peut
donc arriver qu'un programme avec une fonction d'évaluation plus élaborée soit moins
bon qu'un programme avec une fonction d'évaluation simple qui fait plus de recherche. Il
devient donc naturel de se poser la question de la pertinence d'ajouter des connaissances
dans la fonction d'évaluation en fonction du ralentissement de la recherche qu'elles induisent.
La figure 1.7 donne les courbes de niveau auxquelles on peut s'attendre en fonction
des connaissances et de l'effort de recherche qu'on donne à un programme de jeu [6 1, 8].
Une courbe représente un niveau du programme constant. On peut remarquer qu'ajouter
des connaissances lorsqu'il y a peu de recherche ou ajouter de la recherche lorsqu'il y a
peu de connaissances améliore peu le programme. La conclusion est qu'il faut garder un
bon équilibre entre recherche et connaissances.
Un étude empirique des courbes recherche versus connaissances a été faite aux Échecs,
à Othello et au Checkers [4 7] mais aussi sur des finales d'Échecs [7 2] et sur le jeu Lines of
Action [10]. Les courbes sont assez proches des courbes théoriques de la figure 1.7. Toutefois, pour les abscisses de l'effort de recherche proches de zéro, les courbes associées
ne montent pas aussi haut que sur la courbe théorique.
1.6 Corrigés des exercices
1.6.1 Coups gagnants à Nim
Dans cette position :
I
III
III!
III II II
1
3
4
7
0001
0011
0100
0111
0001
Les coups gagnants sont de retirer une allumette soit dans le tas à une allumette, soit
dans le tas à trois allumettes soit dans le tas à sept allumettes.