Dominos !

Chères agrumes, bonjour !

Il y a quelques temps (bon, deux ans en fait) Eskimon lançait la première édition de la ZestArena. Malheureusement, elle n'a jamais abouti.

Mais aujourd'hui, je vous propose de relancer cet atelier avec un nouveau défi : faire une IA capable de jouer aux dominos.

La ZestArena, keskesékoi ?

C'est un ensemble de défis/ateliers de programmation, dans lesquels les différents participants s'affrontent dans des combats acharnés !¹

Chaque participant devra donc créer une petite (ou grosse) IA dans le langage de son choix, capable de jouer à un jeu de société. Les différentes IA se battront ensuite dans des duels à mort, et un classement sera établi.

Deuxième arène : les dominos

La première arène était le puissance 4, celle-ci sera les dominos. Je pense que vous savez tous y jouer, mais comme les règles peuvent changer, voici celles qui sont utilisées :

• Il y 4 joueurs et 28 dominos dans une partie ;
• Au début de la partie, chaque joueur a donc 7 domino ;
• Le joueur qui a un double 6 commence ;
• Les autres joueurs connectent ensuite leurs dominos à droite ou à gauche de la file. Il faut bien sûr que deux dominos qui se touchent aient un nombre en commun ;
• Les joueurs peuvent passer leur tour ;
• La partie se termine quand les quatre joueurs passent à la suite (plus aucun ne peut jouer) ou quand les 28 dominos ont étés joués.
• Pour le décompte des points, c'est expliqué sur le Framagit.

Au niveau du code

Il y a un programme maître qui dit qui joue quand et qui donne les informations sur la partie en cours au programmes enfant. J'ai écrit ce programme maître, et vous, vous allez écrire les programmes enfants.

Ils communiquent entre eux via des messages, envoyés par WebSockets. Pour plus de détails, n'hésitez pas à aller lire ce fichier qui explique tout.

Si vous voulez participer, il faudra respecter ces conditions :

• Votre programme doit pouvoir être lancé via la ligne de commande ;
• Si il est compilé, merci de le faire sous Linux (Fedora de préférence), pour être sûr que je puisse le lancer. Sinon, il faudra me fournir les sources et me dire comment le compiler ;

Le programme maître générera aussi des GIFs animés des parties, pour que vous ayez droit à un replay.

Ce défi est une bonne occasion de vous entraîner dans un nouveau langage, d'en tester un, d'apprendre à utiliser les WebSockets, de faire une petite IA … ou tout ça à la fois ! Alors, n'hésitez pas à proposer quelque chose. Et si vous ne savez pas trop comment faire, n'hésitez pas à aller voir le code de l'IA de test (nommée « idiot », ça en dit long … D'ailleurs ce n'est même pas une vraie IA), ou à demander de l'aide.

Bonne chance à tous !

Et je ne l'ai pas dit, mais essayez de garder un esprit bon enfant. Si vous êtes le dernier du classement, profitez en pour voir ce qu'a fait le premier et voir comment vous pourriez améliorer votre programme.² Du coup, si vous partagez vos codes sources, c'est mieux, même si dans un premier temps, on peut garder son algorithme secret.

Salut, je pense participer. Par contre, comment on teste son IA ? Je n'ai rien vu sur comment lancer en local le programme maître.

merci

Ça a l'air bien fun !

Le seul truc qui me gène, c'est quand tu parles de websocket. Je ne sais pas ce que c'est, et quand je cherche un peu, je tombe sur des trucs tordus, super lourd ou bien en javascript. Est-ce que tu aurais un code d'IA qui ne fais rien : juste envoyer « A.N.Onyme » au début (tu veux un nom), puis « skip » à chaque tour.

Je n'y connais pas grand chose en web, et c'est un domaine qui ne m’intéresse pas du tout (alors que l'IA, si). Alors pour moi, ouvrir une websocket, c'est du chinois. Et les articles qui parlent de websocket aussi.

J'ai l'impression qu'au niveau du programme-maître, la commande get-all n'est pas suffisante. get-all va me dire la liste des pièces sur le plateau, mais elle ne va pas me dire quel joueur a posé quel domino. Elle ne va pas me dire non plus que tel joueur a passé à telle ou telle étape. Or ces informations sont essentielles pour une bonne stratégie. Par exemple, avec la version actuelle, je n'ai pas de moyen de connaître le nombre de dominos restants pour chaque joueur.

Je pense par ailleurs qu'une version Windows pourrait intéresser des participants.

Je me pose la question si la stratégie a vraiment une importance ici ? Car finalement le nombre de choix possible à chaque tour diminue grandement, et j'ai l'impression qu'il y a beaucoup de hasard dans ce jeu…

Du tout, le jeux de dominos est un jeux très stratégique !

Imagine un début de partie, le double 6 est sur la table, et dans les mains, tu as : (6.5) (6.4) (4.0) (4.1) (4.2) (4.3) (4.4), tu vas bien évidemment poser le 6.4 pour tenter de bloquer tes adversaires. Alors que poser le (6.5) n'a aucune chance de bloquer qui que ce soit.

Ici, c'est évident, mais les fins de partie sont plus difficiles, puisqu'il faut prendre en compte les actions des autres joueurs aux tours précédents. En fin de partie, s'il te reste 3 dominos alors que les 3 adversaires ont chacun un domino, tu vas probablement poser le domino qui a le plus de points, pour payer le moins cher possible (stratégie défensive). Mais si tu as encore un espoir de gagner, tu vas adopter une autre stratégie.

Je suis super intéressé de participer. Mais je n'ai jamais jouer au domino de ma vie .. (Bien triste n'est-ce pas ?)

Donc il faudra que j'aie faire un tour pour voir le fonctionnement du jeu.

Est-ce qu'à chaque fois qu'un joueur joue, tu envoies ce que le joueur à jouer à tout le monde ? ça serait util.

@Unknown : Tu peux le lancer comme ceci :

1

./domino port_joueur1 port_joueur2 port_joueur3 port_joueur4 id_de_la_partie

id_du_jeu sert à différencier le nom des images à chaque partie. Pour lancer l'IA par défaut, il faut utiliser ./main port nom.

@Gabbro : En général tu as des bibliothèques qui implémentent les Websockets dans la plupart des langages (en Rust par exemple), il suffit de rechercher websocket mon langage, tu devrais trouver ton bonheur si tu utilise quelque chose de pas trop exotique. En Vala par exemple, ça donnerai ceci :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

using Soup;

void main (string[] args) {
    MainLoop ml = new MainLoop ();
    try {

        Session sess = new Session ();
        Message req = new Message ("GET", "ws://localhost:8080");

        sess.websocket_connect_async.begin (req, null, null, null, (obj, res) => {
            try {
                var conn = sess.websocket_connect_async.end (res);
                conn.send_text ("A.N.Onyme");
                conn.message.connect ((type, message) => {
                    // ici on reçoit les messages du maitre et on les utilise
                });
            } catch (Error err) {
                print ("error : %s", err.message);
            }
        });

  } catch (Error e) {
      stdout.printf ("Error: %s\n", e.message);
  }
    ml.run ();
}

@elegance : je vais rajouter une commande pour connaître le nombre de domino des autres, et modifier get-all pour qu'elle indique qui a joué quoi. Si tu as d'autres idées de commandes qui pourraient utiles, dit moi, que je les ajoute.

Et pour la version Windows, qu'est-ce que tu veux dire ? Une version du programme maître pour Windows ? Si c'est le cas, je le ferai sûrement, il faut juste que je trouve le temps et le courage de rebooter pour compiler ça sous Windows.

@WinXaito : Je ne le fait pas, mais je peux rajouter ça aussi.

Ce qu'il veut dire c'est que la combinatoire est tellement raisonnable qu'on peut écrire très facilement des stratégies optimales de manière explicite et exacte.

Je doute que ce soit correct.

Ok, à un instant t, j'ai le choix entre 3 ou 4 mouvements en général, mais pour évaluer quel mouvement est le meilleur, c'est complexe. Dans des jeux comme les échecs ou les dames ou le go, ou a beaucoup plus de mouvements, mais on joue à cartes ouvertes, on connaît exactement les forces en jeu. Au jeu de dominos (comme dans les jeux de cartes), on ne connaît pas les forces en présence. On peut faire des hypothèses : si tel joueur avait eu telle pièce, il l'aurait certainement posée à telle occasion, ou alors il joue très mal, ou alors il a cherché à me tromper.

Explorer toutes les branches de l'arbre, et prendre en compte ce type de raisonnement, ça devient très complexe. La taille de l'arbre est élevée, à cause de l'incertitude sur les forces en présence.

L'autre possibilité, c'est d'étendre le nombre de pièces. Traditionnellement, on joue avec 28 pièces, c'est la norme pour des humains. Passer à 36 ou 45 ou 55 pièces, ça peut rendre jeu plus adapté à une variante sur ordinateur.

Non, c'est pas complexe. La combinatoire est ridicule pour des petites valeurs de $n$ ou $n$ est le nombre maximal qui peut apparaitre sur un domino. Or, 6 c'est ridicule. L'incertitude ne change pas grand chose a cela, c'est juste une partition fini et relativement petite (i.e. un facteur multiplicatif). Rajouter des joueurs ne change pas enormement la donne.

Les raisonnements que tu evoques n'ont rien de complexe a integrer et n'ont probablement meme pas a etre integres (il faudrait etudier la gueule des strategies optimales pour savoir si elles sont independantes de celle des autres joueurs).

Ça peut être intéressant je tente ma chance.

Est-ce que la commande skip est répercutée sur les autres joueurs ? Je veux dire, est-ce qu'on peut savoir si un joueur a skip?

Non, mais ça peut être fait si besoin.

Les points qu'ont a fait à la partie d'avant restent. Faut voir comment on fait le classement, mais on peut soit faire en X parties celui qui a le plus de points, ou le premier à X points

On peut aussi le faire comme ça si besoin, mais normalement les IAs n'auront pas de trop grosses différences de niveau, donc je ne sais pas si ça vaut le coup.

Est-il autorisé d'avoir une communication externe ? (Http)

Pour par exemple créer une stratégie selon les précédentes partie ?

Pourrais-tu aussi faire une liste nous indiquant tous les mots que nous pourrons recontrer dans le jeu et leur utilité ?

Exemple:

1
2
3

skip: Passer son tour
play: Lancement de départ
end: fin du tour

Et pour la fin du programme comment est-elle indiqué ? (Exit, stop ?)

Et il y a quelque chose que je n'ai pas bien compris, mais comme je l'ai compris c'est qu'on ne peut pas choisir le sens de nos dominos ?

Est-il autorisé d'avoir une communication externe ? (Http)

Pour par exemple créer une stratégie selon les précédentes partie ?

Oui, je n'y vois pas d'inconvénient.

Pourrais-tu aussi faire une liste nous indiquant tous les mots que nous pourrons recontrer dans le jeu et leur utilité ?

Exemple:

1 2 3

skip: Passer son tour play: Lancement de départ end: fin du tour

Il y a aussi get pour obtenir ces dominos et get-all pour voir ceux qui ont été joués. Mais d'autres vont être rajoutés.

Et pour la fin du programme comment est-elle indiqué ? (Exit, stop ?)

Euh… Il faudrait que je ferme la WebSocket.

Oui, j'avais essayé de faire en sorte qu'on puisse, mais le programme maître buggait dans tous les sens sans que je trouve pourquoi. Il faudrait quand même que j'essaie de mettre ça en place, parce que les possibilités sont limités du coup …

Et concernantoi le programme maître, tu peux le mettre sur github ? Car sa peut être plus simple de gérer la communication si on voit le code. De plus on pourra t'aider si tu as des soucis.

Bon peut être pas pour moi car je ne connais pas du tout le vala :pour

Si je ne me trompe pas, il y a déjà le code du programme maître sur le framagit.

(par contre c'est vrai qu'un exemple de websocket en C m'aiderait pas mal, mais bon je suppose que google est mon ami !)