Dominos !

Hello,

ça en est où par ici ?
Pour ma part, j'ai commencé à travailler un petit peu dessus, bon pour la moment rien qui ne concerne vraiment le jeu, je me suis occupé à trouver une librairie qui me convenait pour les WebSocket en java (ça n'a pas été aisé mais j'ai trouvé).

Ce que j'ai déjà fais ce trouve ici.

Concernant le programme maître tu en es ou ? Est-ce qu'on pourra bientôt avoir une version utilisable pour testé ? (Et ce qu'il faudra rajouter selon moi quand on reçoit une réponse du programme c'est de pouvoir identifier la fonction, car on n'est pas certain que tout arrive dans l'ordre).

• get, renvoie une liste de tous les dominos du joueur sous la forme a-b a-b a-b
• get-all, renvoie une liste de tous les dominos sur le plateau, de gauche à droite, sous la même forme que get

Il est impossible d'identifier si le retour appartient à la fonction get ou get-all. Donc il faudrait avoir dans la réponse quelque chose comme get a-b a-b et get-all a-b a-b

Je suis surpris de voir que la communauté scientifique ne s'est pas trop intéressée au sujet. Des gens ont trouvé des articles sur le jeu des dominos ? D'ailleurs peut-être que je me trompais dans ma remarque car apparemment, le jeu n'a pas encore été résolu…

Ce n'est pas un jeu à information totale (c'est bien le terme ?) donc ce n'est pas forcément surprenant qu'il ne soit pas résolu.

Dans le jeu à 2 joueurs, il y a pas mal de façons de choisir 7 dominos pour le joueur 1, pas mal pour le joueur 2, et encore plus pour répartir/ordonner les 14 dominos restants dans la pioche.

Et ça nous emmène à 1e22 distributions possibles…

Le jeu de dominos n'a pas une exposition extraordinaire ; ce n'est donc pas surprenant s'il n'a jamais fais l'objet de recherches poussées. Parmi les jeux où le hasard est prépondérant, le jeu de Backgammon est plus exposé, et il a fait l'objet de recherches. Pour les dominos, on trouve quand même un ""championnat du monde"" : http://www.dominoes-stars.fr/strategie-domino.html

La règle du jeu qui est exposée ici est différente de celle proposée pour notre challenge. Ici, à chaque fois que la somme des points aux extrémités du parcours donne un multiple de 5, vous marquez ce nombre de points ; le parcours a 4 branches, et pas seulement 2 ; et en plus, plus classique, quand vous posez votre dernier domino, vous marquez les points des dominos restants dans les mains des adversaires.

Oui mais si je ne me trompe pas, tu as une vidéo récente de sciences étonnantes dans laquelle il parle qu'une version du poker a été résolue. Je rejoins plus l'argument d'elegance et c'est certainement le fait que le jeu des dominos n'est pas un jeu très réputé.

Je n'ai pas dit que c'est impossible, c'est juste que le jeu n'est pas impartial et en plus tu n'as aucune information sur la main des adversaires donc je ne sais pas si c'est possible. Et comme pour ton exemple du poker ça serait certainement une strategie pour gagner "sur le long terme" (en esperance) plutôt que toutes les parties.
Pour le poker je ne me rappelle plus des détails mais il me semble que la technique utilisée était de faire jouer leur IA contre elle même pour constituer une base de donnée de positions pour savoir quoi faire. Aussi ils ont fait ça sur une variante très restreinte avec un seul adversaire.

Salut !

Je vais probablement proposer un client OCaml, ça me permettra de voir comment je m'en sors sur un programme un peu plus évolué que ce que je fais actuellement

Au poker, La technique se base sur des bêtes calculs de probabilités (statistiquement, avec une paire , j'ai un jeu supérieur à la moyenne, mais si les 2 premiers joueurs ont choisi de miser, j'ai probablement intérêt à passer, même si j'ai une paire de 3…).

Mais l'aspect gestion-du-bluff est très important. La gestion du capital est également importante (on ne joue pas de la même façon quand on est cheap-leader que quand on a un tapis quasi-vide).

Il faut savoir dire : tel joueur mise très souvent, statistiquement, il mise trop souvent, ça doit être un bluffer.

Le jeu de poker ne peut pas être résolu, à cause de cet aspect bluff.

Si on revient aux dominos, le jeu est peu réputé, et en plus, il existe différentes variantes qui se cannibalisent. Au poker, le Hold-em a pris le pas sur les autres variantes ; cette variante peut faire l'objet d'études.

Et au backgammon, il y a une seule variante, ça en fait un jeu universel, avec là aussi pas mal d'études sur le sujet.

Le nombre de tirages possibles pour le domino est $137680171200$ soit de l'ordre de $10^{11}$ bien loin des $10^{22}$ annonce. Mais cela n'est pas important du tout pour etablir une strategie. Connaissant ses pieces, le nombre de partitions entre le joueur adverse et le talon, avant de poser la premiere piece est de 116280 voire 38760 si l'adversaire commence.

La encore, en plus de ne pas etre tres utile, c'est ridiculement bas.

Le jeu de poker est resolu pour une version simple. Le bluff n'intervient pas la dedans.

En soi, ce n'est pas vraiment important ici. Cet atelier a pour but de faire/tester un petite IA. Personnellement, ce sera la première que je fais ça si j'arrive à participer¹. De fait, que ce soit 10¹¹ ou 10²², c'est beaucoup. Ça me parait suffisamment compliqué pour avoir de l'intérêt, au moins vis-à-vis d'un certain public (dont tu ne fais peut-être pas parti, si tu trouves ça trop simple – pour moi c'est déjà non négligeable, comme difficulté).

Reprenons, puisqu'il y a contestation.

Il y a 1184040 façons de choisir 7 dominos parmi 28 (les 7 dominos du joueur 1)

Il y a 116280 façons de choisir 7 dominos parmi les 21 restants (les 7 dominos du joueur 2).

En multipliant ces 2 nombres, on arrive à 137680171200.

Ensuite, comme déjà expliqué, les joueurs auront l'obligation de piocher. Le premier joueur qui pioche un domino a 14 possibilités (je dis bien possibilités, je ne dis pas choix volontairement), le 2ème joueur qui pioche un domino a 13 possibilités, etc … etc… On a 14! de répartir/ordonner les 14 dominos dans la pioche.

On arrive bien aux 1e22 distributions possibles.

Ce n'est pas comme ca que cela marche. On est d'accord sur le premier calcul. Une fois que l'on a distribue les dominos entre les deux joueurs, la partie commence. On s'en tamponne de la maniere dont on va tirer les dominos dans le talon. (EDIT: Pour completer, est-ce que connaitre le nombre de parties possibles du jeu d'echec aide a etablir une strategie ? Pas du tout. Pire, il y a des jeux de cartes ou l'on peut determiner des strategies optimales qui se calculent de maniere polynomiale alors que le nombre de parties est de l'ordre de 52! soit de l'ordre de $10^{66}$)

La seule information pertinente qu'il manque pour etablir une strategie optimale deterministe d'entree de jeu c'est quels sont les dominos dans le talon, quels sont ceux de mon adversaire. D'ou l'importance cette fois du nombre de partitions des 21 dominos qui ne sont pas les miens en debut de partie. Cela permet, une fois toute l'information disponible integree et les regles strategiques appliquees, de ponderer chaque coup possible en fonction de la probabilite de la main de l'adversaire, de ce qu'il va piocher ou de ce que je vais piocher.

Et la encore, le nombre de partitions se reduit drastiquement a chaque coup. Le plus dur c'est donc presque de commencer.

Pour repondre a Gabbro, le probleme n'est pas de savoir si 10^{11 ou 10}22, c'est beaucoup ou non, mais bien de savoir si cette mesure a une quelconque relation avec l'etablissement ou le calcul d'une strategie optimale ou sous-optimale. La reponse est pas directement ou en tout cas de maniere beaucoup moins spectaculaire que la maniere dont grandit ce nombre en fonction du nombre de dominos.

Bon maintenant vous avez titille ma curiosite de matheux, alors ayant 5h de train demain, j'essayerai peut-etre de formaliser cela. Peut-etre parce qu'a 4h du matin je risque de plus roupiller qu'autre chose.

Je viens d'améliorer le programme maître :

• La WebSocket est maintenant fermée à la fin de la partie ;
• On sait qui a joué quoi, avec cette syntaxe : other (Nom de l'adversaire) : commande jouée.
• On sait quelle « fonction » a renvoyé le message, avec la syntaxe proposée par WinXaito.

Maintenant, je vais essayer de faire en sorte qu'on puisse retourner les dominos, ça serait quand même mieux.

Cool ! Fais nous signe dès que tu as une version disponible que l'on puisse testé.

Par contre j'ai quand même une petite interrogation, pourquoi passer par des WebSockets ? Je trouve que ça aurait été plus simple avec des simples Socket, du moins il me semble.

Car par exemple, moi qui fais mon programme en Java, je dois passer par une librairie externe et c'est pas toujours évident.

Le problème des Sockets normales c'est qu'elles sont à sens unique. On reçoit ou on envoie. Et donc parce que j'avais la flemme de gérer deux Sockets par joueur (surtout qu'en Vala la gestion des Sockets est assez bas-niveau et gaère ), je me suis dit que les WebSockets, c'était quand même mieux.

Edit : Et du coup, je galère pas, mais toi oui !

Websocket c'est la vie. Il serait temps de massivement les utiliser. Du coup, je felicite l'auteur de les imposer, cela forcera les gens a les decouvrir.

Bonsoir.

Je ne sais pas si j'aurais le temps d'inscrire une IA au concours, probablement pas, même si en fait j'en ai déjà écrit une de mon côté dans le cadre d'un projet que je mène depuis 6 ans, mais que je participe ou non au final, j'ai quand même envie d'apporter mon petit grain de sel.

Comme quelques avis précédents, je pense que si les dominos n'ont pas été vraiment étudiés, c'est principalement parce qu'il y a énormément de variantes dans les règles, parce qu'il n'existe pas un seul jeu de dominos, et parce qu'aucune combinaison de jeu et variante ne s'est spécialement imposée. Le double-six à 28 pièces et 2 à 4 joueurs est la plus simple, mais on peut jouer avec des double-neuf et des double-douze; permettre ou non de dédoubler les chaînes quand on joue un double; obliger à jouer si on le peut; jouer avec des tas de variantes plus compliquées mais ô combien plus intéressantes comme le train mexicain, ou les dominos 2D ou en triangle…

L'avantage d'avoir choisi ce jeu c'est quand même qu'il n'y a pas déjà de route toute tracée pour coder une bonne IA. Comme autre jeu intéressant à essayer, j'aurais bien proposé le tarot.

Sur la forme par contre: vouloir faire du websocket, c'est cool, c'est moderne ! Par contre ça ferme la porte à beaucoup plus de monde que ce que vous croyez.

Ce serait quand même beaucoup plus simple pour tout les participants si le programme maître faisait du classique stdin/stdout; ça a l'énorme avantage d'être universel, pour tous niveaux, tous langages, et accessoirement ça pourrait éviter qu'un petit malin essaie de pirater le serveur (on ne sait jamais, je sais pas vous mais moi personnellement je suis méfiant). Bref ça ouvre le challenge à plus de monde, d'autant plus que sur un projet comme ça, on n'a pas envie de se prendre la tête avec de l'I/O ou une bibliothèque qu'on ne maîtrise pas bien, donc le protocole le plus simple sera le meilleur.

Ah, et, à part ça, évidemment qu'on doit pouvoir tourner les dominos. Sinon le jeu n'a absolument aucun intérêt.

Rajouts:

Le problème des Sockets normales c'est qu'elles sont à sens unique. On reçoit ou on envoie.

C'est faux, les sockets TCP sont en full duplex.

Edit : Et du coup, je galère pas, mais toi oui !

Normalement dans un challenge comme ça, ce n'est pas aux participant de se faire ch### avec la communication, mais bien au programme maître. Être gêné par des problèmes d'I/O à la con en tant que participant ne donne pas envie d'aller jusqu'au bout. Je suis certain que les websockets en rebutent plus d'un, et même les sockets TCP normaux. Après à vous de voir quel public et quels buts vous visez mais à mon avis il est important de garder à l'esprit que c'est un challenge pour coder une IA, pas pour apprendre à faire du websocket.

@QuentinC Tu aurais dû découper ton message en 4 ou 5 messages, un message par idée ; ça m'aurait permis de te mettre 4 ou 5 fois +1.

Tu parles de coder une IA sur le tarot. J'en profite pour rappeler ce tutoriel que j'ai proposé, et qui est toujours en attente de validation

Tu proposes un challenge 'une IA de tarot' … je ne pense pas que ce soit raisonnable. Développer une IA de tarot à temps perdu le soir en sortant de la fac ou du boulot … Si quelqu'un sait faire ça, alors chapeau !

Sinon, il y a quand même une idée à tirer de tout ça, c'est le jeu en duplicate. Dans les compétitions de tarot ou de bridge, ou même de scrabble, les joueurs jouent en duplicate : en gros : la même distribution est jouée une fois par l'équipe A contre l'équipe B, et plus tard, par l'équipe B contre l'équipe A.

Au niveau du programme 'MASTER' de dominos, cela peut être mis en place. Et au final, visualiser les 2 parties, en parallèle ; montrer à quel moment l'IA n°1 ne fait pas le même choix que l'IA n°2, etc etc …

C'est faux, les sockets TCP sont en full duplex.

Ah ben l'implémentation Vala doit être mal faite (c'est surtout que la doc est un peu pourrie en fait) parce que je n'ai pas trouvé comment faire.

Yep, je sais mais malheureusement Vala est très limité à ce niveau là, donc je n'ai pas trop eu le choix. Mais bon, généralement les bibliothèques pour faire des WebSockets facilitent la tâche : on se connecte à l'adresse, on reçoit les messages dans un callback et on en envoie grâce à une méthode. Dans la plupart des langages je pense que ça tient en même pas 100 lignes, et si la bibliothèque a une doc un minimum bien faite, ça peut être fait vraiment vite, même si on n'y comprends pas grand chose.

Je précise aussi qu'on a le droit de faire équipe, ce qui peut permettre par exemple de travailler avec quelqu'un qui s'y connaît en WebSockets si on y comprends rien.

Je précise aussi qu'on a le droit de faire équipe, ce qui peut permettre par exemple de travailler avec quelqu'un qui s'y connaît en WebSockets si on y comprends rien.

Chouette, du coup si quelqu'un veut faire avec moi car la pour le coup je pense m'en sortir pour les websocket mais moins pour l'IA

Edit: Pour ma part j'ai déjà commencer en Java, mais je suis ouvert à d'autre langage. (C++, Python, etc.)