Arimaa: The Game of Real Intelligence

[Sébastien Nadeau]

Désolé pour le titre en anglais, j'ai simplement copié-collé le titre de la page Web de ce jeu.

Voici un jeu (un lointain, mais récent, cousin des échecs) dans lequel l'être humain moyen est encore plus fort que les meilleurs ordinateurs.

Je trouve le jeu très intéressant et les possibilités sont beaucoup plus grandes qu'aux échecs (par plusieurs ordres de magnitude). Constatez-le par vous-même: http://arimaa.com/

Sébastien

[Serge Champetier]

Eh bien Sébastien...voilà qui est très intéressant, en effet!
Je me demande seulement comment me fabriquer un jeu. Peut-être acheter des petits animaux en plastique et les peinturer?...
Quoiqu'il en soit, faut que je montre ça à ma fille. Elle pourra peut-être enfin battre son père
* * *
Parlant de battre des plus forts que soi, voici une petite anecdote qui m'est arrivée ce midi.
Un de mes collègues, avec qui j'avais déjà convenu de lui donner une leçon d'échecs un bon jour, passe la tête dans le cadre de porte de la salle à dîner, et me lance un "En tout cas, quand tu seras prêt à me laver, tu n'as qu'à venir me voir".
Je me suis empressé de préciser le contexte à mes autres collègues de travail, qui auraient pu s'imaginer toutes sortes de choses...

[Ummite]

Salut Sebastien

J'ai lu les règles, et effectivement ca semble être un killer pour un ordinateur. Ce qui rendra un ordinateur fort à ce jeu sera de bien travailler les tables de transpositions pour minimiser le facteur de branchement.

De plus, je ne sais pas si c'est facile de comparer deux positions, ce qui rend la chose plus facile aux ordinateurs aux échecs. Ca me semble plus difficile qu'aux échecs, mais n'ayant jamais joué je ne peux pas vraiment me prononcer à ce niveau.

Ca me donne le goût de participer au tournoi ordinateur 2006

[Sébastien Nadeau]

Je me demande seulement comment me fabriquer un jeu. Peut-être acheter des petits animaux en plastique et les peinturer?...

Tu peux utiliser un jeu d'échecs normal: roi => éléphant, dame => chameau, cavaliers => chevaux (évidemment...), tours => chiens, fous => chats et les pions sont les lapins. Pour les trappes des cases c3, f3, c6 et f6, tu pourrais dessiner un X avec un crayon feutre pour enfants sur un échiquier en vinyle (ça s'efface avec de l'eau).

Quoiqu'il en soit, faut que je montre ça à ma fille. Elle pourra peut-être enfin battre son père

Si ma plus grande ne me bats pas aux échecs, elle me bat en racontage d'histoires! Je pourrais passer la nuit à lui raconter des histoires et elle les écouterait toutes! Je vais éviter de lui présenter les candidats à chefferie du PQ...



Sébastien

[benoitstpierre]

Le jeu a l'air fascinant ! Le tutoriel est simple et très efficace.

Ceci dit, l'argument de vente n'est pas fort. On a déjà surestimé nos capacités humaines à jouer aux échecs. Me semble qu'on faire mieux que de faire le même coup avec un jeu dont on ignore à peu près tout, non ?

Je ne vois pas pourquoi les machines n'excelleront pas bientôt à ce jeu tout autant qu'aux échecs. À vue de nez la fonction d'évaluation pour arimaa devrait accorder une grande importance au matériel. La seule limitation actuelle des joueurs artificiels se trouve dans des jeux où les considérations matérielles sont secondaires, comme au go. Et encore, la taille de l'espace de solution y est pour beaucoup. L'espace de solution du shogi, plus complexe que les échecs mais moins que le go, est fort probablement plus grand que ce jeu. En fait, a-t-on une démonstration que c'est un jeu plus complexe que les échecs ?

[Sébastien Nadeau]

Salut Sebastien

J'ai lu les règles, et effectivement ca semble être un killer pour un ordinateur. Ce qui rendra un ordinateur fort à ce jeu sera de bien travailler les tables de transpositions pour minimiser le facteur de branchement.

Je ne suis pas certain que ce genre d'optimisation est vraiment efficace. Même avec des bonnes tables de transposition, un fait demeure: aux échecs il y a une trentaine de possibilités en moyenne à chaque coup. À Arimaa, c'est plus de 20000 possibilités. Développer l'arbre de ces possibilités est une tâche colossale, même pour le plus puissant des ordinateurs.

Pour « voir » 4 plys (2 coups ou 16 steps, comme on les nomme à Arimaa), un ordinateur doit évaluer 1,6x10E17 possibilités différentes. On voit tout de suite qu'il faut chercher une solution ailleurs que dans la force brute.

Un autre facteur important à considérer: aux échecs, si vous ne faites rien ou jouez passivement, vous allez perdre rapidement, mais à Arimaa, le plus souvent, jouer passivement et ne rien faire est très fort! Les coups d'attaque doivent donc être bien préparés.

Ca me donne le goût de participer au tournoi ordinateur 2006

Je pense que c'est une très bonne idée si tu veux exploiter tes habiletés en informatique; Arimaa est une terre vierge qui reste à défricher.

Sébastien

[Sébastien Nadeau]

L'espace de solution du shogi, plus complexe que les échecs mais moins que le go, est fort probablement plus grand que ce jeu. En fait, a-t-on une démonstration que c'est un jeu plus complexe que les échecs ?

Non, j'ai vu une table de comparaison. Je vais essayer de retrouver la source. Aux échecs, l'espace solution est de l'ordre de 10E50, au shogi et au Go c'est beaucoup plus, mais Arimaa les bat tous avec un espace solution défiant toute comparaison pour un jeu se jouant sur un échiquier classique (8x8): 10E512

Sébastien

[Sébastien Nadeau]

Ok, oubliez mon dernier message, je vous ai raconté n'importe quoi. Voici la référence:

http://en.wikipedia.org/wiki/Board_game_complexity

Sébastien

[benoitstpierre]

Sébastien,

La complexité d'un espace de solution pour un problème ne relève pas juste de sa taille, i.e. le nombre de possibilités. C'est pas rien, mais c'est pas tout : ça prend l'algorithme ! En plus, jouer n'est pas résoudre. Si on a une fonction d'évaluation, on peut faire jouer des machines à des jeux de manière satisfaisante, même si ce sont des problèmes démontrés irrésolubles par tous les calculs possibles d'une machine telle qu'on la conçoit actuellement.

(C'est sûr que si on peut stocker une infinité d'information dans un seul électron et qu'on peut effectuer une infinité d'action simulatannément, c'est une autre paire de manche.)

Un exemple concret : des équipes de robots peuvent jouent au soccer avec les programmes assez simples, alors que le problème de jouer au soccer implique un espace de solution pas mal plus complexe que les échecs. On parle de plusieurs dimensions à calculer en temps réel, sur un espace continu !

En théorie de la complexité, les intuitions sont pas toujours fiables. (Entéka, pas les miennes ! ;) Compare par exemple les échecs classiques et les échecs Fischer dans le tableau de l'article que tu cites : les deux ont la même complexité algorithmique.

Voici quand même mon intuition de ce matin. J'ai l'impression que les pièces d'arimaa sont moins mobiles qu'aux échecs et au shogi. Jouer plusieurs petits coups reviendrait à peu près à jouer un gros coup. Ces petits coups permettraient d'obtenir un certain nombre de configurations à peu près équivalentes, i.e. des congruences. On n'a pas besoin de se demander en quoi la position A est différente de la position B, si A revient au même que B. Si en plus des immenses tables de transpositions comme le suggère Philippe, notre fonction d'évaluation nous permet de trouver des ensembles de congruences, alors on est en affaire.

Trève de spéculation, je retourne travailler !

[Sébastien Nadeau]

Je pense qu'avant de pousser plus loin notre analyse, une bonne session de jeu s'avère nécessaire afin de découvrir toutes les subtilités inhérentes à une position d'Arimaa. Il y a des concepts comme « freezing » et « blockading » qui à eux ceuls méritent des études poussées.

Sébastien

[Ummite]

Bon ben finalement, faut que je m'y mette en fin de semaine!

Mais j'ai vraiment trop de choses simonac... Je sais pas si j'ariverais à modifier mon jeu d'échecs en shogi en moins d'une journée...

a+