Discussion :

[Alasea]

Bonsoir,

Je tiens à m'excuser dans un premier temps si le sujet a déjà été plus ou moins posé.
Je souhaiterais connaitre dans un premier temps le nom d'algorithme/technique d'IAs que l'on pourrait mettre en place dans un jeu de tour à tour comme Othello.
Je connais l'algorithme Minmax avec ses optimisations : Negamax et Alpha-Beta. Mais je souhaiterais savoir s'ils y en a d'autres adaptés pour ce jeu?

Je ne sais pas si je me trompe, mais il me semble que l'algorithme minmax repose sur un arbre comportant toutes les configurations possibles du jeu. Or il existe beaucoup de configurations pour un jeu pareil. Du coup, je me demande si l'algo Minmax est bien conseillé pour un jeu de la sorte.

Merci beaucoup,
Alasea

[ToTo13]

Bonjour,

l'avantage pour des des jeux comme Otello, les dames, puissance 4, ... c'est que les règles et la stratégie sont tellement simple qu'une simple recherche exhaustive des coups possibles suffit à battre les meilleurs joueurs.
De plus la puissance des ordinateurs actuels permet de faire tourner ce genre d'IA sur un ordinateur personnel.

[Alp]

En plus de ça, tu peux personnaliser ton algo de recherche exhaustive suivant le jeu.
Pour Othello (ce n'est pas un jeu que j'apprécie particulièrement et que je connais très bien, hein) il doit bien y avoir des bonnes petites stratégies lors du début ou quand on tombe dans un type précis de situation. Tu peux intégrer ces "bons coups" dans ton algo !

[Alasea]

Bonsoir,

c'est que les règles et la stratégie sont tellement simple qu'une simple recherche exhaustive des coups possibles suffit à battre les meilleurs joueurs.

j'ai du mal coder cette partie alors :s Quand j'essaye de demander une profondeur de 5/6 dans l'arbre des configurations possibles, Java m'engueule .... -_-

Enfin, là je travaille surtout sur une étude des IAs que l'on pourrait proposer sur un jeu tel qu'Othello... quels algos/approches pourraient sembler pertinents pour un tel jeu.
Quand on recherche sur le net, on tombe souvent sur l'algo-minmax plus ou moins optimisé... mais j'ai cru voir la théorie des Neurones ou encore des théories probabilistes. Je me demande si elles pourraient s'appliquer ou non à Othello. Ou au contraire si c'est complétement aberrant.

il doit bien y avoir des bonnes petites stratégies lors du début ou quand on tombe dans un type précis de situation

Je suis bien d'accord... je pensais aussi du coup à l'approche, je ne connais pas le nom, où l'on donne au programme des parties d'Othello pour qu'il les analyse. Un peu comme pour les programmes des jeux de Go (d'après ce que j'ai pu lire).

[Alp]

Je penche nettement pour une recherche +- exhaustive... Parce que si tu fais un RdN pour l'Othello à mon avis t'es pas encore sorti de l'auberge... La fonction à approcher doit être drôlement complexe

[Rumpel]

Oui, j'ai lu que les meilleurs programmes d'othello pouvaient avoir une profondeur de recherche de 25/30 coups. Donne nous ton algo codé, pour voir si tu n'as pas fait de grosses erreurs...

Sinon lis ça :
http://www.ffothello.org/info/algos.php

[Alasea]

analyser sur une profondeur de 25/30 coups 0_0

Sinon mon but n'est pas de coder à proprement parler Othello mais d'analyser les différentes approches pour développer l'intelligence artificielle, les comparer du point de vue complexité et autre...

Merci pour le lien, je l'avais déjà lu néanmoins ^^
Je recherchais voir s'il pouvait y avoir d'autres approches que les recherches exhaustives (je viens de découvrir grâce à Alp que MinMax, Alpha-beta étaient considérés comme des algos de recherches exhaustives)

[ToTo13]

Bonjour,

bien sûr qu'il y a d'autres approches, il y a même toutes les approches de recherche possible.

Mais lorsque sur ce genre de jeu on peut faire de l'exhaustif dans un temps raisonnable, on sait que l'on a la meilleure solution.
Les autres approches (réseaux de neurones, méta-heuristiques, etc.) fonctionnent mais je garantiront pas l'optimalité de la solution.