Abalone, un jeu où l’homme bat (encore) la machine

Voici un article du journal Le-Monde-Logo qui retiendra probablement l’attention de ceux qui s’intéresse à la question des intelligences artificielles (communément abrégés IA) et de leur développement :

Les jeux où l’homme bat (encore) la machine.

Même si l’article ne le mentionne pas, Abalone semble (encore) faire partie du lot : bien qu’il ne soit pas évident à battre, Aba-Pro comporte des failles assez facilement exploitables ; Nacre s’est révélé moins fort qu’Aba-Pro en 2003 ; ULA, qui dans ses niveaux élevés utilise apparemment beaucoup de ressources, n’est pas assez rapide et perdrait au temps ; je ne peux me prononcer sur MLA, qui sur MiGs n’était disponible qu’en version d’entraînement (bridée) – mogwai seul peut-être connaît sa véritable capacité ; quant au replayer d’Eob, j’avoue que pour le moment je n’ai pas réussi à le faire fonctionner en mode IA.

Il existe enfin de nombreuses autres IA jouant à Abalone, mais elles n’ont ni le niveau ni la notoriété des IA mentionnées plus haut. Bref, à Abalone aussi, l’élite humaine conserve une longueur d’avance sur l’élite artificielle.

FightClub

 

 

27 réflexions sur “Abalone, un jeu où l’homme bat (encore) la machine

  1. Après, c’est une question de temps….
    Abalone est quand même moins complexe pour une IA que le Go, je pense…
    Au fur et à mesure que les anciens très bons joueurs deviendront séniles 😉 et au vu de la probable faible apparition de nouveaux talents et, enfin, considérant que la puissance des ordinateurs ne pourra que progresser, un jour ou l’autre les IA auront (malheureusement) gagné.
    Cela dit, restera-t-il des IA et fonctionneront-elles sur les machines du futur ?

  2. MLA reste vincible, bien que difficilement 🙂
    Quant à mon replayer, pour faire jouer un coup par l’IA, il faut taper la commande « ai x », où x est la profondeur de recherche. Avec une profondeur de 1, ça marche bien mais il n’est pas très bon. Au-delà, je ne garantis rien, car je crois qu’il y a un bug dans le parcours de l’arbre de recherche, donc il n’est pas certain que ce soit meilleur qu’en profondeur 1, ni qu’il arrive à calculer quelque chose… 😉
    De toute façon, c’est une sorte d’Aba-Pro, en plus lent et avec des paramètres plus pourris…

    Concernant Aba-Pro, je ne trouve pas que ses failles soient faciles à exploiter, dans le cas général. En particulier, en Marguerite il est plutôt fort.

  3. Rappelons qu’il a déjà été question (succintement) d’intelligences artificielles ici : https://onlineabalone.wordpress.com/abalone-cest-aussi/des-intelligences-artificielles/

    Cet article du journal Le Monde me laisse perplexe. Selon la manière de voir les choses, je dirais soit qu’il mélange tout, soit qu’il est intéressant parce qu’il envisage le sujet de manière assez large. En tout cas, je le trouve un peu superficiel.

    Je ne suis pas informaticien, ni programmateur ou quoi que ce soit d’analogue, je ne peux donc pas donner un avis de ce point de vue, mais la question de l’intelligence – ou plutôt des intelligences – m’intéresse, et quand on aborde la question des intelligences artificielles, c’est aussi la question de l’intelligence – ou des intelligences – tout court qui est en jeu. Vaste sujet, sujet inépuisable.

    Le grand tort de cet article me semble venir de ce qu’il ne fait pas la distinction entre les différents jeux dont il parle ; jeux à information complète, jeux intégrant une part de hasard, jeux de connaissance et de culture générale, jeux sportifs, etc.

    Je m’en tiendrai aux jeux à information complète de type échecs ou abalone pour exprimer un avis qui, je le répète, n’est pas celui d’un technicien ni d’un scientifique.

    Il me semble assez évident que dans ce type de jeux qui reposent entièrement sur le calcul, tôt ou tard le cerveau humain sera (et parfois est déjà) supplanté par les capacités de calcul de l’ordinateur. Pour autant que je sache, la question n’est pas tout à fait réglée pour les échecs (quoique…), elle l’est déjà pour Othello, jeu fortement résolu, elle ne l’est pas encore pour abalone simplement parce que pour l’instant les grands moyens n’ont pas encore été employés, quelles que soient par ailleurs les qualités éminentes de ceux qui ont travaillé à la programmation d’abalone.

  4. Je suis bien d’accord avec toi. En revanche, je ne crois pas qu’Othello soit résolu. À ma connaissance, il l’est en plateau 6×6, mais pas en 8×8 et encore moins en 10×10. Mais, ce qui est peut-être ce que tu voulais dire, les IA sont meilleures que les humains…

  5. Si je peu me permettre de réagir sur certains points…
    La méthode classique et simple pour coder l’AI est de scorer tous les coups possibles, puis tous les coups suivants, etc. On en sort un arbre de décision et on va prendre le chemin qui mène au meilleur score. Il y a donc 2 paramètres qui vont impacter la force de l’AI : la puissance de calcul (combien de coups on peut prévoir, sachant que ce nombre explose assez vite) et la qualité de la fonction de score. Ce qui fait que les AI d’échecs battent les humains repose surtout sur la première condition. Il y a peu de coup à jouer en comparaison à pas mal de jeux (sans parler des ouvertures classiques, forçant le début de partie), et donc au bout d’un moment, on a pu battre l’humain. Abalone et le Go sont des jeux où il y a trop de coups possibles pour prévoir pertinemment un bon coup. Je vous réfère à cet article qui en parle d’ailleurs : http://www.cs.cornell.edu/~hn57/pdf/AbaloneFinalReport.pdf. La valeur de branching factor est assez claire… Pour Othello du coup, je sais pas.

    Cependant, il y a de nouvelles approches, basées sur du machine learning pour le Go. L’AI apprend sur des parties de pros (ou en faisant des parties contre des pros) et optimise sa fonction de score. Ca donnait visiblement de très bons résultats récemment, même si ça ne bat pas encore un humain (les temps de calcul sont bien réduits).

    • C’est assez inexact dans l’ensemble. Dans l’arbre de décision on ne peut pas explorer tous les chemins … donc les mécanismes de coupe sont la clef. Ce qui est difficile avec abalone est qu’il n’y a pas de coup vraiment + improbable par nature qu’un autre (par exemple aux échecs sacrifier une dame sur un pion n’est pas forcément le premier coup à essayer pour trouver une suite intéressante ….). A abalone, à part essayer les éjections en premier, les poussées en second il n’est pas facile d’écarter un coup « a priori ». Et c’est pour ça que MLA ne peut pas aller aussi loin dans le nombre de coups « à l’avance ». Je passe les détails mais en plus on souffre d’un fort « effet d’horizon », certaines coupes habituelles aux échecs dans l’arbre de décision (razoring par exemple) ne fonctionnent pas.

      La génération des coups possibles est également + lente. Pas de répertoire des ouvertures, pas de tables de fin de partie ….

  6. Othello est justement un jeu dans lequel il y a assez peu de coups possible à chaque tour, d’où la force des IA… À Abalone il y en a beaucoup, mais à mon avis nombre d’entre eux sont assez inutiles et pourraient être passés à la trappe.

  7. En disant qu’Othello était « fortement » résolu, je disais implicitement (mais peut-être pas très clairement, vu la tournure de ma phrase) qu’il ne l’était pas « totalement ». En tout cas c’est un jeu où la machine est très forte, sans doute plus que l’homme, pour les raisons que vous avez exposées.

  8. La confusion vient du fait que « fortement résolu » a un sens précis : on sait jouer parfaitement à partir de n’importe quelle configuration valide. Le jeu est « faiblement résolu » si l’on sait jouer parfaitement au moins à partir de la configuration initiale.

  9. La méthode probabiliste est la même, sauf qu’on réduit l’espace de recherche dans l’arbre pour réduire la complexité algorithmique. Le concept derrière est le même finalement… On peut très certainement l’appliquer pour Abalone oui.

    @Eob : tu as raison pour le nombre de coup à Abalone, mais il y a une subtilité je pense. Il y a pas mal de coups inutiles qui devraient passer à la trappe, le problème est d’évaluer leur inutilité. Il me semble assez difficile de trouver un coup inutile. Je veux dire, le formaliser sous la forme de règle. Il y a au final pas mal de paramètres qui rendent le coup inutile. Alors même si beaucoup sont inutiles, il reste encore difficile de les connaitre rapidement. Au contraire, un peu comme au Go, on peut envisager des approches comme « tel coup implique une réponse directe » et réduire l’espace de recherche…

  10. Pas forcément faciles à repérer, en effet. Mais pour un humain, pas trop dur 🙂
    Ce qui fait, d’ailleurs, qu’invoquer le nombre de coups moyen disponible pour montrer la complexité du jeu d’Abalone pour les humains n’est pas bien avisé…

  11. Effectivement, pas trop dur pour un humain, grâce à une qualité fondamentale du joueur que la machine ne possède pas (pas encore) : l’intuition. Nous sommes capables d’éliminer un certain nombre (et souvent beaucoup) de coups inutiles sans vraiment avoir à y réfléchir. Notre cerveau fait le tri à l’insu de notre plein gré. 😉 La machine doit calculer l’inutilité, alors que nous la pressentons (pas de manière parfaite, bien sûr, il y a toujours des coups dans une zone un peu grise) . Sans doute les machines finiront-elle par acquérir une puissance de calcul qui se rira de notre intuition, mais pour l’instant, nous gardons cet avantage.

    Notons que ce que j’appelle l’intuition n’a rien à voir avec une quelconque bénédiction qui nous tomberait du ciel ou de je ne sais où : l’intuition est plutôt une sorte de « talent » qui se forge avec l’expérience et le travail. Un joueur totalement novice n’a pratiquement aucune intuition (si ce n’est celle qu’il a acquise au travers d’autres jeux, ou d’autres situations d’apprentissage cognitif). Il doit évaluer laborieusement chaque coup possible, un peu comme le ferait une IA.

  12. Une fois qu’un « bon » joueur(et il y en a sur ce forum) a éliminé d’un rapide aperçu les coups ‘inutiles’, parmi combien de ‘bons’ coups va-t-il faire son choix définitif ?
    Dit autrement,, il en envisage combien ? deux , trois ?

  13. @lolo : c’est une question à laquelle on ne peut pas répondre, car elle dépend en premier lieu de la configuration, qui offre plus ou moins de mouvements possibles, parmi lesquels plus ou moins de mouvements éligibles. Pour partir de configurations identifiables, je prends l’exemple de deux positions de départ : « Damier », qui est une position éclatée, offre un large choix de premier coup possible pour Noir, là où « Pyramide » n’en offre que 2, dont l’un est le symétrique de l’autre. Et le premier coup de Blanc en Damier, n’est pas obligé d’être une réponse immédiate à ce que l’adversaire vient de jouer, mais s’inscrira plutôt dans une démarche d’ensemble sur plusieurs coups prenant en compte ce qu’il pourrait être intéressant pour l’adversaire de jouer à partir du coup qu’il vient d’effectuer. Il est impossible de savoir à quel moment la première bille qui vient d’être déplacée va à nouveau servir. Ca peut être au coup suivant comme n’importe quand.
    En revanche, en Pyramide (et en bloc en général), on joue quasiment à vue, avec la plupart du temps au mieux le choix entre deux coups (le plus souvent un seul), et le jeu se limite à jouer très vite en guettant l’erreur fatale de l’adversaire (ce qui n’arrive pas avec une IA).

    Contre un joueur humain, d’autres éléments entrent aussi en considération, en particulier la connaissance que l’on a de son adversaire : son niveau, son style de jeu, ses mouvements de prédilection, ses erreurs récurrentes, le caractère offensif ou défensif de son jeu, etc., toutes choses qui permettent d’anticiper ses réactions et ses coups à venir. Il y a certains joueurs avec lesquels on peut se permettre de jouer freestyle ou de bluffer, d’autres non. C’est vivement déconseillé contre une IA 😉

  14. Effectivement, la réponse à la question de Lolo dépend de la situation. Et puis entre les coups manifestement inutiles et les « bons » coups, il peut y avoir toute une gradation (ce que j’appelais la zone grise dans mon post plus haut). Ainsi le choix du coup à jouer se fait par tout un va-et-vient entre notre intuition et notre imagination.

    Par « imagination », j’entends notre capacité à nous représenter mentalement les positions futures. On pourrait aussi dire, au lieu d’imagination, notre capacité de calcul. Sauf que sur un jeu de plateau, nous raisonnons en images et non en calcul mathématique. Pour moi, l’imagination est une des trois qualités fondamentales du joueur, au même titre que l’intuition.

    Maintenant, pour répondre très simplement à la question de Lolo, il me semble que le choix définitif se fait effectivement parmi deux ou trois coups en moyenne (sachant que parfois on n’a pas le choix du tout).

    Ceci dit, je ne fais probablement pas partie des « bons joueurs » auxquels il pense. 😀 Je ne me considère moi-même que comme un joueur de force respectable.

    • Vu de mon niveau, tout le monde est bon joueur ;-).
      Mais toi, Gramgroum, je te considère comme intrinsèquement un bon joueur.
      Et cela sans flagornerie.
      (que de pédanterie dans ce commentaire…)

      • lol Pas de fausse modestie en ce qui me concerne, je me considère comme un bon joueur. Mais pas vraiment le haut du panier. Je n’ai pas la capacité d’analyse ni la force de jeu d’Eobllor, de Johy ou de quelques autres. Donc mes avis valent ce qu’ils valent, ni plus ni moins. 😉

  15. J’aime beaucoup l’idée de l’intuition, c’est exactement ça. Un coup qui ne mène à rien, on le voit instantanément en effet.
    Eob, tu parlais de qui/quoi quand tu disais que « invoquer le nombre de coups moyen disponible pour montrer la complexité du jeu d’Abalone pour les humains n’est pas bien avisé » ? Je te rejoins totalement, mais pour l’heure les seuls que j’ai vu en parler sont ceux qui développaient une AI. Il est évident que le nombre de coup jouable pour un humain est largement en dessous du nombre théorique. Ca se vérifie moins au Go (car il y a plus de choix et la suite peut être intéressante à long terme) mais on retrouve ça aussi je pense.

    • Je n’avais personne de particulier en tête, mais j’ai déjà lu des arguments de ce type pour vanter les mérites d’Abalone, histoire de dire que le jeu soutient la comparaison avec d’autres classiques de la réflexion tels que les échecs. Mais comme tu le dis, l’argument n’est valable que tant qu’on parle d’une IA et que l’on ne connaît pas de moyen simple de faire un élagage brutal de l’arbre des possibilités 🙂
      Au go comme à Abalone ou tout autre jeu de réflexion, plus le joueur est fort, moins il a le choix 😉 Concernant le go, j’ai vu de nombreuses situations commentées par « the only move », quand bien même ça ne me paraissait absolument pas évident… Enfin, on peut nuancer un peu en ajoutant qu’en étant plus fort on peut avoir des idées inaccessibles à d’autres ; mais globalement, je pense qu’en progressant on élimine dans sa tête plus de faux bons coups qu’on en trouve d’insoupçonnés bons.

  16. Comme le decrit gramgroum, les IA, du fait de leur capacite de calcul au cp par cp, auraient une grande imagination mais pas ou peu d’intuition.

    Je n’y connais rien en programmation, et je n’ai aucune idee de la maniere de calcul d’une IA mais si l’intuition vient de la capacite d’avoir une vision globale du jeu, de quelques brefs calculs et de la memoire des situations auxquelles on a deja etait confronte et qui nous servent de repere, alors il suffirait que les IA gardent en memoire les situations utiles qu’elles ont rencontre pour les comparer, ce qui leur eviterait de passer trop de tps a recalculer une position deja rencontree et leur donnerait un genre d’intuition.
    C’est peut-etre ce que Nicolas appelle le machine learning.

    Comme on l’avait dit dans un autre article, le nombre de positions differentes est vraiment tres grand et semble impossible a garder en memoire. Mais il me semble que le nombre de positions qui reviennent dans les parties est relativement faible. On se retrouve souvent dans des situations similaires, donc si les IA peuvent les memoriser et les analyser, ca apporterai peut-etre un plus, non?
    Si oui, ya plus qu’a ! 😀

  17. Pour simplifier , on peut dire que l’humain a plus une vision stratégique de la partie et une IA n’a qu’une force tactique.
    En gros, un humain joue avec une vision à long terme tandis qu’une IA joue à court terme.
    Ou bien , dit d’une autre manière (militaire),l’humain est un général qui gère un conflit étendu géographiquement, en prenant son temps,et sans trop craindre les pertes tandis que l’IA essaye de gagner des batailles assez localisées en parant au plus pressé. Et elle est assez efficace dans ce rôle.
    La question étant de savoir si beaucoup de coups à court terme font une vision à long terme.
    Selon moi, non.
    Une citation sur ce sujet (à méditer):
    « La tactique consiste à savoir ce qu’il faut faire quand il y a quelque chose à faire. La stratégie consiste à savoir ce qu’il faut faire quand il n’y a rien à faire.  » ( Xavier Tartakover ).

  18. @ lolo : hé ! Tu viens de me griller une citation que je gardais en réserve pour dans quelques semaines ! (lol) :
    The tactician must know what to do whenever something needs doing; the strategist must know what to do when nothing needs doing.
    J’avais l’intention de la traduire comme ça :
    Le tacticien, c’est celui qui sait quoi faire quand il y a quelque chose à faire ; le stratège , c’est celui qui sait quoi faire quand il n’y a rien à faire.

    @ propos de la différence entre la vision du joueur humain et celle de l’IA : ce que je crois comprendre, c’est que l’humain a une vision discriminante qui relègue à l’arrière-plan ce qui ne l’intéresse pas, contrairement à l’IA qui capte tout ce qu’elle voit sans discrimination et fait un gros travail de tri après coup. L’humain peut se tromper et ne pas voir ce qu’il est intéressant de voir, mais plus il est expérimenté, plus son intuition est développée et il vise souvent juste. Quant à l’IA, son travail d’analyse est très souvent efficace, mais il est parfois des situations où ses critères s’avèrent inopérants, bien qu’ils soient pertinent en général et dans la plupart des cas.

Répondre

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l’aide de votre compte WordPress.com. Déconnexion /  Changer )

Photo Google

Vous commentez à l’aide de votre compte Google. Déconnexion /  Changer )

Image Twitter

Vous commentez à l’aide de votre compte Twitter. Déconnexion /  Changer )

Photo Facebook

Vous commentez à l’aide de votre compte Facebook. Déconnexion /  Changer )

Connexion à %s

Ce site utilise Akismet pour réduire les indésirables. En savoir plus sur la façon dont les données de vos commentaires sont traitées.