Othello fait partie de la classe des jeux de stratégie à deux joueurs, à information complète (les joueurs connaissent à chaque instant la totalité des informations sur la position qu’ils ont à jouer) et à somme nulle (à la fin de la partie, l’ensemble de la mise, c’est-à-dire les 64 pions, est distribuée intégralement entre les joueurs).
De nombreuses recherches dans le domaine de l’intelligence artificielle, mais qui en fait empruntent des techniques à bien d’autres branches de l’informatique, ont depuis une cinquantaine d’années perfectionné les algorithmes des programmes jouant à cette classe de jeux, en particulier aux échecs. Nous allons essayer dans les lignes qui suivent de présenter quelques techniques sophistiquées communément utilisées par les meilleurs programmes. Nous distinguerons les algorithmes génériques de recherche dans les arbres de jeu (partie I), des méthodes plus spécifiques à Othello : méthodes de tri des coups, fabrication de fonctions d’évaluation dédiées, bibliothèques d’ouvertures (partie II).
Partie I : Algorithmes de recherche dans les arbres de jeu
Le Minimax
L’idée fondamentale, appliquée dans tous les bons logiciels d’échecs, de dames, de go, d’awale, d’Othello, etc. est qu’il faut faire parcourir par le programme un espace de recherche constitué des positions futures potentiellement atteintes par les joueurs pour anticiper la meilleure séquence à jouer. On modélise cet espace de recherche avec des techniques issues de la théorie des graphes (arbres, graphes sans cycles, etc.) et on utilise des systèmes de production pour générer leurs états (les positions) et les transitions entre les états (les coups permettant de passer d’une position à l’autre).
La méthode générale est la suivante : à partir d’une position (racine de l’arbre) on génère tous les coups possibles pour le programme. Puis à partir de ces nouvelles positions (niveau 1) on génère toutes les réponses possibles pour l’adversaire (niveau 2). On peut alors recommencer l’opération aussi longtemps que le permet la puissance de calcul de l’ordinateur et générer les niveaux 3, 4, …, n.
Le facteur de branchement dans une partie d’Othello équilibrée étant d’environ 10 et le nombre de coups environ 60, on ne peut générer, dans un temps limité, la totalité de l’arbre. On doit donc limiter la profondeur de la procédure. Une fois atteinte cette profondeur, les feuilles (par opposition à la racine) de l’arbre ainsi construit sont évaluées par une fonction d’évaluation. Le programme peut, à partir de la racine, jouer le coup de niveau 1 qui lui garantit le gain maximal contre toute défense de son adversaire, en supposant que celui-ci utilise également une stratégie optimale, c’est-à-dire qu’il joue lui-même à chaque coup le gain qui lui garantit le gain maximal contre toute défense. Ce mécanisme est appelé principe Minimax.
Par convention :
Un coup entre la racine et une feuille est appelé nœud (interne).
Les nœuds où le programme a le trait sont de type MAX car le programme doit maximiser sa valeur.
Les nœuds où l’adversaire a le trait sont de type MIN car l’adversaire doit minimiser la valeur du programme.
Fig. 1 : l'algorithme Minimax
int fonction minimax (int depth)
{
if (game over or depth = 0)
return winning score or eval();
int bestScore;
move bestMove;
if (nœud == MAX) { //=Programme
bestScore = -INFINITY;
for (each possible move m) {
make move m;
int score = minimax (depth - 1)
unmake move m;
if (score > bestScore) {
bestScore = score;
bestMove = m ;
}
}
}
else { //type MIN = adversaire
bestScore = +INFINITY;
for (each possible move m) {
make move m;
int score = minimax (depth - 1)
unmake move m;
if (score < bestScore) {
bestScore = score;
bestMove = m ;
}
}
}
return bestscore ;
}
Il est important de noter que pour déterminer la valeur de la racine (qui est celle du meilleur coup, ou devrais-je dire le moins mauvais) toutes les branches sont générées par la procédure ci-dessus, et chaque feuille évaluée.
Les coupures alpha-bêta
Est-il absolument nécessaire de générer la totalité de l’arbre pour déterminer la valeur de sa racine ? La réponse, négative, à cette question n’est pas évidente (elle a mis plus de 20 ans à être découverte et connue parmi les pionniers des programmeurs d’échecs dans les année 50 et 60), mais fondamentale puisque l’algorithme alpha-bêta constitue la grande découverte qui explique la force des programmes de jeux de stratégie actuels. Dans le minimax l’information ne fait que redescendre l’arbre (de la feuille vers la racine), on peut la faire remonter pour en informer les autres branches.
Soit alpha, pour un nœud MIN n,la plus grand valeur connue pour un nœud MAX ancêtre de n.
Soit bêta, pour un nœud MAX n’,la plus petite valeur connue pour un nœud MIN ancêtre de n’.
Alors pour MIN si la valeur de n est inférieur à alpha, ou pour MAX si la valeur de n’est supérieur à bêta, la poursuite de exploration est inutile, parce que la valeur du nœud « père » ne sera pas modifiée.
En d’autres termes, l’algorithme alpha-bêta utilise l’histoire de la recherche déjà effectuée lors du début de la recherche minimax pour borner les variations possibles de la notation de la racine, ce qui permet d’élaguer de façon non risquée des sous-arbres entiers de l’espace de recherche (on parle de coupures alpha-bêta).
Fig. 2 : l'algorithme alpha-beta
int alphabêta(int depth, int alpha, int bêta)
{
if (game over or depth <= 0)
return winning score or eval();
move bestMove;
if(nœud == MAX) { //Programme
for (each possible move m) {
make move m;
int score = alphabêta(depth - 1, alpha, bêta)
unmake move m;
if (score > alpha) {
alpha = score;
bestMove = m ;
if (alpha >= bêta)
break;
}
}
return alpha ;
}
else { //type MIN = adversaire
for (each possible move m) {
make move m;
int score = alphabêta(depth - 1, alpha, bêta)
unmake move m;
if (score < bêta) {
bêta = score;
bestMove = m ;
if (alpha >= bêta)
break;
}
}
return bêta;
}
}
Les valeurs initiales des bornes de la fenêtre [alpha,bêta] à la racine de l’arbre sont alpha = -INFINI et bêta = +INFINI.
Mais est-il possible de faire encore mieux ?
La convention NegaMax
Avant de poursuivre, nous allons présenter une convention simplificatrice (du moins pour le programmeur) qui consiste à considérer qu’on évalue une position non pas du point de vue d’un joueur fixe (par exemple joueur MAX = programme) mais du point de vue du joueur qui a le trait sur cette position.
Fig. 3 : l'algorithme alpha-beta, en convention NegaMax
int alphabêta(int depth, int alpha, int bêta)
{
if (game over or depth <= 0)
return winning score or eval();
move bestmove ;
for (each possible move m) {
make move m;
int score = -alphabêta(depth - 1, -bêta, -alpha)
unmake move m;
if (score >= alpha){
alpha = score ;
bestMove = m ;
if (alpha >= bêta)
break;
}
}
return alpha;
}
Pour conserver alpha et bêta pour chaque niveau il suffit de les intervertir entre les appels de procédures et d’inverser leur valeurs. En d’autres termes, on utilise encore, implicitement, la condition de symétrie des jeux à somme nulle : Position.eval(Programme) = -Position.eval(Adversaire).
Le fail-soft alpha bêta
En modifiant encore légèrement notre pseudo-code il est encore possible de ramener un supplément d’information de notre recherche, la valeur qui a provoqué la coupure.
Fig. 4 : fail-soft alpha-beta
int alphabêta(int depth, int alpha, int bêta)
{
if (game over or depth <= 0)
return winning score or eval();
move bestMove ;
int current = -INFINITY;
for (each possible move m) {
make move m;
int score = -alphabêta(depth - 1, -bêta, -alpha)
unmake move m;
if (score >= current) {
current = score;
bestmove = m;
if (score >= alpha){
alpha = score;
bestmove = m ;
if (score >= bêta)
break;
}
}
}
return current;
}
Il a été démontré (non, pas par moi) que
- si alpha < current < bêta, alors current est la valeur minimax
- si current <= alpha, alors la vraie valeur minimax m vérifie :
m <= current <= alpha - si bêta <= current alors la vraie valeur minimax m vérifie :
bêta <= current <= m
Mais à quoi cela sert-il ?
Si on lance un recherche avec [alpha,bêta] = [v, v+1] (ou plutôt [-(v+1), -v] mais là vous ne suivez pas), seul les cas de figure 2 et 3 sont possibles et nous obtenons une fonction très rapide (car il y a alors de nombreux élagages alpha-bêta, et donc peu de nœuds générés) qui nous informe que la valeur minimax est « supérieure ou égale » ou « inférieure ou égale » à un pivot v.
Mais à quoi cela sert-il ?
Tester les inégalités : le Negascout/PVS
Plutôt que lancer aveuglement une nouvelle recherche alpha-bêta coûteuse en temps pour explorer les branches sœurs, une recherche rapide avec une fenêtre nulle (bêta = alpha+1) nous informerait de l’utilité de celle-ci.
Fig. 5 : l'algorithme Principal Variation Search
int alphabêta(int depth, int alpha, int bêta)
{
if (game over or depth <= 0)
return winning score or eval();
move bestMove = first move;
make move bestMove;
int current = -alphabêta(depth - 1, -bêta, -alpha);
unmake move bestMove;
if (current >= alpha)
alpha = current;
if (current < bêta) {
for (each remaining move m) {
make move m;
int score = -alphabêta(depth - 1, -(alpha+1), -alpha)
if (score > alpha && score < bêta)
score = -alphabêta(depth - 1, -bêta, -alpha)
unmake move m;
if (score >= current) {
current = score;
bestmove = m;
if (score >= alpha){
alpha = score;
if (score >= bêta)
break;
}
}
}
return current;
}
Mais est-il possible de faire mieux ?
Le mtd(f) : un algorithme multipasses
Une autre approche est possible ! En effet, puisque l’exploration de l’arbre avec une fenêtre nulle est si rapide, pourquoi ne pas faire la totalité de la recherche avec cette méthode ? Bien sûr, plusieurs recherches consécutives seront nécessaires pour trouver la valeur minimax de la racine, mais on espère gagner du temps au total.
Plusieurs algorithmes se sont développés autour de cette idée et le mtd(f) semble le meilleur.
Fig. 6 : l'algorithme Memory Test Driver (MTD(f))
int MTDF(depth, init_g)
{
int g = init_g , bêta;
int upperbound = +INFINITY;
int lowerbound = -INFINITY;
do {
if (g == lowerbound)
bêta = g + 1 ;
else
bêta = g;
g = AlphaBêtaWithMemory(depth, bêta - 1, bêta);
if (g < bêta)
upperbound = g
else
lowerbound = g;
}
while (lowerbound != upperbound);
return g ;
}
Plus la valeur init_g sera proche de la valeur minimax plus la recherche sera rapide. En générale, sans idée de la valeur minimax, init_g = 0.
Bien sûr, puisque la recherche doit être lancée plusieurs fois, il est judicieux de conserver pour chaque nœud les informations des précédentes recherches. C’est la technique connue sous le nom de table de transposition, que l’on implémente en général avec une table de hachage.
Fig. 7 : alpha-beta avec mémoire
int AlphaBêtaWithMemory (int depth, int alpha, int bêta)
{
if (retrieve(Position) == true) {
if (position.lowerbound >= bêta)
return position.lowerbound;
if (position.upperbound <= alpha)
return position.upperbound;
alpha = max(alpha, position.lowerbound);
bêta = min(bêta, position.upperbound);
}
if (game over or depth <= 0)
return winning score or eval();
int a = alpha ;
move bestmove ;
int current = -INFINITY;
for (each possible move m) {
make move m;
int score = -alphabêta(depth - 1, -bêta, -a)
unmake move m;
if (score >= current) {
current = score;
bestmove = m;
if (score >= a){
a = score;
if (score >= bêta)
break;
}
}
}
if (g <= alpha) {
position.upperbound = current;
store position.upperbound;
}
if (g > alpha && g < bêta){ //impossible dans le cas du mtd(f)
position.lowerbound = current;
position.upperbound = current;
store position.lowerbound, position.upperbound;
}
if (g >= bêta) {
position.lowerbound = current;
store position.lowerbound;
}
return current;
}
Quel est le meilleur choix, le mtd(f) ou le negascout, pour lequel on sait qu’une table de transposition est également bénéfique ?
Je n’ai pas de réponse définitive a cette question.
Mais est-il possible de faire mieux ?
Quelque raffinements sont encore possibles, comme la recherche par aspiration et l’approfondissement itératif. Mais c’est surtout dans le tri des coups, c’est-à-dire l’ordonnancement des branches lors de la génération de l’arbre de jeu, qu’il faut concentrer les efforts. Nous entrons ici dans le domaine des techniques ad hoc, dépendant du jeu considéré.
Partie II : Techniques particulières à Othello
Trier les coups
On peut démontrer que, sous certaines hypothèses raisonnables de régularité dans la structure de l’arbre (coefficients de branchement régulier, en particulier), le cas optimal de l’algorithme alpha-bêta se rencontre lorsque l’on explore toujours le meilleur nœud en premier. Cas utopique, mais plus on s’en rapproche, plus la recherche est rapide : le tri des coups avant exploration est vraiment l’une des clefs d’un programme de jeu efficace !
Dans cette perspective, plusieurs critères de tri des coups sont généralement utilisés à Othello:
- En fonction du type de case. On joue d’abord les coins et en dernier les cases C et X.
- Tri du plus rapide d’abord. On joue en premier les coups qui minimisent la mobilité (le nombre de coups) de l’adversaire. En procédant ainsi, on aura un plus petit nombre de coups à examiner en premier lieu et cela ira donc plus vite. Cette technique est très efficace, particulièrement vers la fin de la partie.
- Tri par recherche courte. Avant de ce lancer dans une recherche longue, on évalue le score de chaque coup par une recherche à quelques coups de profondeur (généralement 1 ou 2,
parfois plus si la recherche à effectuer est très profonde). Les coups sont ensuite triés depuis le meilleur score jusqu’au plus mauvais. - Coup meurtrier. On essaie en premier une réponse habituelle au coup précédent. Pour cela on maintient un tableau des fréquences des réponses à chaque coup et l’on jouera la réponse la plus fréquente. Par exemple après g2, la réponse la plus fréquente est h1, on essaiera donc ce coup en premier.
- Coup mémorisé. On regarde dans la table de transposition si cette position a déjà été joué et, en cas de réponse positive, on recommence avec le meilleur coup trouvé précédemment. Couplé avec l’approfondissement itératif ou une succession de recherche de moins en moins sélective, cette technique est très efficace. La question subsidiaire est de savoir quels tris effectuer et quand.
Effectuer tous les tris dans l’ordre indiqué ci-dessus est une possibilité, mais certaines techniques sont coûteuses en temps (tri par recherche courte, tri du plus rapide d’abord, …) et l’on a intérêt à les réserver au positions proche de la racine. L’utilisation optimale de ces techniques est un problème de réglage qui dépend de chaque programme, de ses qualités intrinsèques et des ressources disponibles.
Recherche sélective
Depuis quelques années, les meilleurs programmes (Logistello, Hannibal, Brutus, Zebra, Cassio, Turtle, Ntest, Edax, Caesar, …) effectuent une sélection des coups à analyser. L’idée de base est simple et proche du mode de pensée des joueurs humains : concentrer l’effort de recherche sur les meilleurs coups et laisser tomber les coups évidemment mauvais. La technique qui a la actuellement la faveur des programmeurs d’Othello est le multi-probcut (MPC), introduit par Michael Buro [1]. Avant d’analyser une position à, par exemple, une profondeur de 12 coups on regarde à une profondeur réduite à 4 coup si cette position ne va pas conduire à un élagage évident. Lors de l’appel de la fonction alpha-béta avec une fenêtre [alpha, bêta] on anticipera la coupure dans les conditions suivantes :
E(v) <= alpha – T * sigma ou E(v) >= bêta + T * sigma
Où:
- E(v) est le score attendu pour la recherche profonde et déduit de la recherche courte.
- sigma est une estimation de l’erreur entre les scores obtenus par une recherche profonde et une recherche courte. Elle est obtenu par analyse statistique d’un grand nombre de positions et de couple de profondeurs.
- T est un facteur multiplicatif permettant de régler la sélectivité. Il est d’usage d’en faire la réalisation d’une fonction de Gauss et d’afficher la probabilité associée sous forme de pourcentage (Si vous vous demandiez ce que signifie le 95% de win@95% qu’affiche Zebra, c’est ça). Néanmoins cette probabilité n’a qu’une signification locale et n’est pas un taux d’erreur global, la manière dont se propage les erreurs dans un arbre étant difficile à décrire de manière formelle.
Cette technique d’élagage heuristique est évidement risquée, dans la mesure où l’on utilise une recherche à faible profondeur pour estimer la valeur d’une recherche à grande profondeur, ce qui peut dans certains cas (que l’on espère très rares, et d’autant plus rares que la qualité de notre fonction d’évaluation est bonne) amener à passer à côté de pièges stratégiques profonds que la recherche courte ne révèle pas.
C’est pourquoi il est, en pratique, impératif d’avoir une fonction d’évaluation très performante et dont la signification est constante au cours de la partie. L’efficacité de la recherche sélective est alors indéniable. Une recherche classique dépassera rarement les 15 coups en milieu de partie, tandis que qu’une recherche avec MPC atteint facilement de 20 à 30 coups en milieu de partie. Son utilisation en fin de partie (appelé endcut) permet une analyse très sure d’une position (sans toutefois rejoindre la perfection d’une résolution). Un peu à l’image de l’approfondissement itératif, une succession de recherches de moins en moins sélectives permet de gérer convenablement le temps disponible, tout en améliorant progressivement la qualité de l’analyse. Certains programmes peuvent, dans des conditions de tournoi, commencer une recherche finale sélective alors que l’othellier est encore parsemé de plus de 30 cases vides.
Table de transpositions
Une transposition (ou interversion) est une position qui peut être obtenue par plusieurs suites de coups différents. La table de transposition (TT) est une structure de stockage, généralement sous forme de table de hachage, des positions rencontrées lors de l’analyse. En récupérant les résultats d’une recherche précédente, on évite ainsi une nouvelle et fastidieuse analyse. Quoique moins fréquentes à Othello que pour d’autres jeux de réflexions (échecs, go, …), les transpositions sont suffisamment nombreuses pour rendre l’usage de la TT indispensable. Du fait des limitations actuelles des mémoires informatiques, il n’est guère possible d’enregistrer toutes les positions rencontrées et certains choix doivent être faits. Comme compromis, les meilleures techniques [2] s’arrangent pour conserver à la fois les positions les plus rentables (les plus coûteuses si on devait rechercher le sous-arbre) et les plus récentes.
La table de transposition apporte un tel gain de performance qu’il est bon d’en abuser. L’algorithme Enhanced Transposition Table (ETC), par exemple, propose, avant d’analyser chaque coup d’une position, de regarder, pour chacun des coups, s’il n’y aurait pas une coupure possible dans la table de transposition [3]. Curieusement, l’ETC a pour résultat d’augmenter le nombre de positions analysées, mais une implémentation judicieuse permet quand même de diminuer le temps d’analyse. C’est donc une excellente méthode pour obtenir un nombre de nœuds/seconde spectaculaire.
Fonction d’évaluation
Quand le programme atteint un nœud terminal de son algorithme de recherche, il a besoin de savoir s’il est dans une position favorable ou non. Si, à cette position, la partie est terminée, le score exact est trivialement obtenu en dénombrant les pions sur l’othellier. Ni les ordinateurs actuels, ni les algorithmes de recherche ne sont néanmoins assez puissants pour résoudre systématiquement la position de départ, et les nœuds terminaux de l’espace de racherche sont souvent des positions de milieu de partie. C’est la fonction d’évaluation qui est alors chargée d’estimer la qualité de la position. La fonction d’évaluation est la partie la plus importante du programme et, pour le programmeur, la plus intéressante à concevoir. Il s’agit vraiment du cerveau du programme et de sa conception dépendra le style de jeu du programme. Les fonctions d’évaluations reflètent souvent les connaissances du programmeur sur le jeu d’Othello et l’on peut ainsi distinguer trois niveaux d’approches :
- Les fonctions d’évaluation débutantes
Comme nombre de joueurs débutants, certaines fonctions d’évaluation se contentent de dénombrer les pions sur l’Othellier. A éviter absolument.
Un peu plus ingénieux, certains utilisent un tableau attribuant un score à chaque case selon son occupation : pion blanc, pion noir ou case vide. Ainsi les coins on généralement une bonne note, les cases adjacentes une mauvaise notes, et ainsi de suite. Une sophistication de ce procédé utilise parfois plusieurs tables en fonction du cours de la partie. Le niveau reste faible. - Les fonctions d’évaluations expertes
Ce second type d’approche tente d’incorporer les connaissances humaines du jeu à la fonction d’évaluation : mobilités réelles et potentielles, influence, stabilité des pions, et, pour les plus sophistiquées, structure des bords et des coins. Les programmes utilisant cette approche offrent généralement un bon niveau de jeu tout en restant raisonnable au niveau de leur besoin en mémoire. D’un autre côté les mesures de mobilités ou de stabilités sont difficile à implémenter efficacement. Le niveau de jeu est bon, mais on peut faire mieux.
- Les fonctions d’évaluations utilisant les structures de pions.
Les meilleurs programmes (Logistello, Hannibal, Zebra, Cassio, Turtle, Ntest, Edax, …) utilisent cette approche, dont l’initiative revient aux programmes Compoth (François Aguillon) et Bill (Lee) dans les années 1980, tandis que Michael Buro et son programme Logistello en ont généralisé l’usage en perfectionnant les méthodes de calcul [1]. L’othellier est divisé en zones, généralement toutes les lignes verticales/horizontales/diagonales, avec des zones un peu plus grosse pour les bords (bord + case x) ou les coins (carré 3×3, rectangle 5×2, triangle, …). A chaque zone on attribue une note en fonction de la configuration des pions qui s’y trouvent. L’ensemble des notes est ensuite sommé pour produire le score global de la position. Les notes ne sont pas attribuées arbitrairement, mais après une période d’apprentissage. Plusieurs méthodes d’apprentissage existent, chaque programmeur ayant un peu sa recette. La plupart reposent sur une analyse statistiques d’une base de plusieurs millions de positions.Il est certain que les futurs programmes vont raffiner cette méthode. L’approche statistique présente des similitudes avec les techniques de réseaux de neurones et la plupart des programmes utilisent donc un unique neurone comme fonction d’évaluation. Les (très) nombreux travaux dans le domaine des réseaux de neurones offrent donc de vaste perspective à explorer. Déjà Hannibal utilise un réseau multi-couche avec un certain succès. Les bases d’apprentissages s’améliorent. D’autres s’essaient aux algorithmes génétiques pour améliorer l’apprentissage (Darwersi, …).
Bibliothèque d’ouvertures
Les meilleurs programmes disposent d’une bibliothèque et peuvent la mettre à jour après chaque partie jouée. Généralement [4][5], la bibliothèque se résume à un réservoir de positions d’Othello pré-analysées. La plupart des positions sont issues de parties déjà jouées (auto-jeu, GGS, IOS, bibliothèque de Logistello, WThor, …) et pour chaque position, la meilleure alternative « non encore jouée » est aussi calculée, ce qui permet de réfuter les mauvais coups. Les scores sont ensuite rétro propagées à la manière du minimax ce qui permet au programme de jouer les meilleurs lignes.
La construction d’une bibliothèque est un processus long et fastidieux. Certains programmes fonctionnent continuellement jour et nuit depuis plusieurs années pour améliorer leur bibliothèque. D’autres maintiennent leur programme secret afin de ne pas révéler d’éventuelles réfutations et ne les exhibent que les jours de tournoi.
Enfin, il semble que les parties standards deviennent particulièrement ennuyeuses, beaucoup de programmes reproduisant sans cesse les mêmes parties nulles. Les bibliothèques d’ouvertures sont certainement l’un des endroits où de nouvelles approches doivent être développées, par exemple fondées sur la modélisation du style de jeu des adversaires ou la recherche de pièges cachés difficiles à anticiper par les fonctions habituelles.
Notons enfin que d’autres approches sont proposées afin de fuir cette monotonie, par exemple changer légèrement le format des tournois informatiques d’Othello : Othello 10×10 ou tournoi de parties synchro-aléatoires sur GGS.
Pour aller plus loin…
Vous trouverez de nombreuses informations complémentaires les pages perso suivantes : celles de Bruno Causse, de Richard Delorme, de Gunnar Andersson, des publications de Michael Buro, de Machine Learning in Game, de Jean-Marc Alliot. D’autre part, depuis quelques années les étudiants de l’Université Standford ont un projet d’Othello (ou plus exactement d’une variante d’Othello) dans leur module d’informatique : voici la page remarquablement complète que l’un de ces brillants étudiants, Luke Swartz, a consacrée à son projet et à ceux de ses camarades. Mais la meilleure source reste bien sûr les articles universitaires consacrés à l’intelligence artificielle (voir par exemple le moteur de recherche spécialisé http://citeseer.ist.psu.edu/) ou les publications de la FFO, en particulier les anciens numéros de Fforum et le numéro spécial informatique.
B. Causse, R. Delorme, S. Nicolet
Bibliographie
[1] Buro M. (1997). Experiments with Multi-Probcut and a new-high quality evaluation function for Othello. Workshop on Game-Tree Search, NEC Research Institute.
[2] Breuker D.M., Uiterwijk J.W.H.M. & van den Herik H.J. (1996) Replacement Schemes and Two-Level Tables. ICCA J 19-3 p 183-193.
[3] Plaat A, Schaeffer J., Wirn P. & de Bruin A.(1996) Exploiting Graph Properties of Game Trees.
[4] Delteil J. (1993) A propos des bibliothèques d’ouvertures. FFORUM n°29. p. 18-19
[5] Buro M. (1995) L’apprentissage chez Logistello. FFORUM n°37. p.18-20
