Discussion :

[pekka77]

Bonjour,

Je cherche comment programmer l'intelligence artificielle d'un jeu othello pour pouvoir jouer contre l'ordi.
Le pb c'est que je ne vois pas comment commencer... on m'a dit d'utiliser un arbre en listant à chaque noeuds les coups possibles (sachant que le nb de coups est tout à fait variable)
Avez - vous une idée ?

Merci

[Laurent Gomila]

Effectivement, c'est le principe. Il te faudra un algo de type minmax (ou alpha-beta si tu veux un truc performant) qui consiste à construire l'arbre de tous les coups possibles et de choisir le meilleur.

Descriptions des méthodes ici :

https://intelligence-artificielle.developpez.com

Pour plus de détails sur les méthodes de base (alpha-beta) je te laisse voir avec Google.

Le plus dur sera ensuite de trouver une fonction qui pourra évaluer efficacement une situation donnée. Plus ta fonction sera pertinente, plus ton IA sera efficace. Il me semble qu'il existe des règles précises pour Othello (genre attribuer beaucoup de points aux pions "imprennables", sur les bords, etc...). Pour démarrer tu peux simplement prendre une fonction qui compte le nombre de pions du joueur, ça te fera une base qui marche.

[pekka77]

Je veux bien contruire un arbre des coups possibles mais comment choisir le meilleur coup sachant qu'il dépend de ce que va jouer l'adversaire...
je suis pas très fort à ce jeu donc j'ai du mal à imaginer quel coup sera le meilleur... aurais tu d'autres pites ?

[sanna]

Bonsoir,

Je sais pas si tu connais ce lien... je pense que ca pourra bcp t'aider.

http://www.ffothello.org/info/algos.htm

[Laurent Gomila]

Je veux bien contruire un arbre des coups possibles mais comment choisir le meilleur coup sachant qu'il dépend de ce que va jouer l'adversaire...
je suis pas très fort à ce jeu donc j'ai du mal à imaginer quel coup sera le meilleur... aurais tu d'autres pites ?

Commence par lire les liens qu'on te donne... Après ça te paraitra plus clair

[pekka77]

bah en fait ton lien est en anglais
par contre j'ai lu celui qui se trouve sur le site officiel d'othello.

[Harlem]

La référence par excellence si tu veux faire un programme vraiment performant :
http://www.cs.ualberta.ca/~mburo/publications.html
Il s'agit de l'essemble des thèses de Michael Buro, créateur de Logistello, le meilleur programme d'Othello (ou l'ancien meilleur depuis qu'il ne le met plus à jour, mais bon).
Il ne faut pas commencer par là, une solide connaissance des divers algorithme de base (minimax, alpha-beta) est nécessaire, mais il y a vraiment matière à réflexion.
Le gros problème est que c'est anglais, désolé. Mais bon, ç'est vraiment la mine d'or pour IA d'othello, donc je me permets de les mentionner tout de même.
Je recommande personellement :
Toward Opening Book Learning : Construction d'un livre d'ouverture et mise en place d'un mécanisme d'apprentissage ingénieux.
Statistical Feature Combination for the Evaluation of Game Positions : Comment construire sa fonction d'évaluation
ProbCut: An Effective Selective Extension of the Alpha-Beta Algorithm :
Améliorarion de l'alpha-beta sur base de probabilité d'une branche de donner un résultat intéressant, très ingénieux et efficace.

[gangsoleil]

Salut,

Pour othello, Bruno Bouzy (Université de Paris 5) s'y est intéressé : http://perso.wanadoo.fr/brunodlb/

Egalement le rapport que j'ai écrit sur l'IA du programme que nous avons réalisé :
http://frenchippy.free.fr/projets/rapport_ia.ps
(attention, le fichier est en postscript, pas en PDF. Pour l'ouvrir sous Windows, il est nécessaire d'installer Ghostview http://frenchippy.free.fr/prog/gsv43w32.exe ET ghostscript http://frenchippy.free.fr/prog/gs704w32.exe )

Bonne lecture,
Gangsoleil