Pour commencer, un petit préambule.
Je cherchais à initier mes enfants à la programmation, et on m'a parlé d' un site absolument génial, créé par le M.I.T. Mes gamins s'y sont donc essayés mais pris au jeu (et oui, on n'est pas là pour parler d'informatique), j'ai aussi mis les mains dans le cambouis. Après quelques essais (un SNAFU à la sauce Intellivision pour les nostalgiques), j'ai regardé ma ludothèque en cherchant un jeu à adapter et mon choix s'est porté sur Love Letter. La première étape du projet, que je viens de terminer, était de reproduire les mécanismes d'un jeu à 2 joueurs, l'ordinateur jouant aléatoirement les coups de l'adversaire. La deuxième étape est de le faire jouer le mieux possible !
Ne connaissant rien en adversaire virtuel (appelons le pompeusement IA), j'imagine qu'on peut créer des IA qui valorisent des situations, et projettent leur force brute pour trouver le meilleur coup, et d'autres IA qui analysent objectivement une situation pour déterminer le "seul" coup possible à partir de règles absolues. A priori, c'est cette approche qui conviendrait à Love Letter.
Le préambule étant terminé, j'arrête de parler informatique et je vous demande quels sont les règles permettant de gagner une partie de Love Letter ?
On commence par la plus évidente : ne pas jouer la Princesse (il faut le dire, car pour le moment mon adversaire le fait !)
En deux, par exemple, pondérer la carte visée par le garde selon les cartes dans les défausses et celle en main, mais déjà ce n'est pas suffisant car certaines cibles sont plus importantes ...
Et après, je suis un peu perdu, car en fait je joue un peu à Love Letter comme mon ordinateur, au pif !
Des idées ?
PS : J'utilise cette version
#1 Garde *5 (perdu si carte désignée dans main)
#2 Prêtre *2 (regarder carte adversaire)
#3 Baron *2 (compare les cartes, le moins élevé perd)
#4 Servante *2 (protège des effets)
#5 Prince *2 (un joueur défausse sa carte et pioche)
#6 Roi *1 (échanger main avec adversaire)
#7 Comtesse *1 (perdu si dans la main avec 5, 6 ou 8 )
#8 Princesse *1 (perdu si défaussé)
PS2 : je n'ai pas codé depuis mon Commodore 64, donc des conseils sur des points clés peuvent aussi m'être utiles, mais ce n'est pas le but premier de ce sujet.
PS3 : Si vous pensez que je devrais arrêter de fumer la moquette, vous pouvez aussi me le dire.
Faire une IA pour un jeu à information incomplète, c'est assez coton.
La modification la plus simple, plutôt que de jouer toujours au hasard, serait de gérer ce que l'IA sait avec certitude sur la main de joueur, après qu'elle ait joué une carte donnant cette information. Avec une valeur spéciale pour dire qu'il n' a pas d'information (ex : mainConnue==8, pour dire qu'on est sûr que l'adversaire a la princesse; alors que mainConnue==-1 indique qu'on ne sait pas ce que l'adversaire a en main)
Avec ça, tu peux établir une stratégie simple :
- si l'IA n'a pas une information sûre (mainConnue<0) et qu'elle a une carte permettant d'obtenir cette information sans risque (voir la main adverse, ou échanger les cartes sans risquer de donner un garde), elle la joue
- si mainConnue>0 et que l'adversaire joue la carte connue, tu remets mainConnue à -1
- si l'IA a une information sûre (mainConnue>0) et une carte qui permet de gagner, elle joue ce qu'il faut (ex : mainConnue=2 et elle a un garde, elle joue le garde pour désigner le prêtre)
En version avancée, si tu n'a qu'une seule carte pour cette stratégie en deux coups (ex : garde et servante), tu joues si possible ta carte "inutile" (servante) en espérant piocher la carte manquante (pretre).
En version encore plus avancée, tu vérifies dans la défausse que tu as encore une chance de piocher la carte convoitée.
Tout ça est très basique, on ne joue que deux coups à l'avance avec une seule tactique, mais pour faire une IA qui joues vraiment bien à ce type de jeu, il faudrait faire beaucoup plus compliqué :
- conserver une trace de ce que l'adversaire sait de ta propre main, pour déjouer la stratégie ci-dessus
- tenir à jour la liste des cartes que l'IA a vues ou non, pour connaitre les probabilités que l'adversaire ait chaque carte possible en main (par exemple pour jouer un garde au pif, mais pas complètement au pif)
- jouer récursivement plusieurs coup à l'avance (algorithme type minmax), avec la difficulté supplémentaire qu'il y a une part d'aléa dans le jeu alors que ce type d'algorithme est fait à l'origine pour les jeux type echecs, go, dames..
- retenir l'historique des parties jouées, pour déterminer le comportement habituel de l'adversaire (ex : joue-t-il plutôt ses gardes au début, ou les conserve-t-il pour la suite?)
En fait, ce n'est plus un problème de programmation, ça devient un vrai problème d'algorithmique et de prise de décision. (c'est le genre de choses que je pourrais poser en projet à mes élèves ingénieurs.. 
)
Pas mieux que Roswell ici au dessus. Ce n'est un projet que je ne donnerais même pas à mes étudiants de DUT Info… La dernière fois je leur avais demandé de me faire un solveur pour Ricochet Robots, un truc relativement facile d'un point de vue conceptuel (même si trouver une heuristique pour un A* ne me parait pas trivial), et ça n'avait pas marché… Ça me parait plus un truc pour un master (à la limite une licence 3) avec une coloration Algo/IA assez marquée.
Tout d'abord, merci d'avoir répondu.
Je note quelques idées, notamment la possibilité de préparer des séquences de coups, et je vais essayer d'en tirer partie avec mes petits moyens. Concernant les informations, l'I.A. a effectivement accès aux défausses et à la carte éventuellement connue de son adversaire.
Je vais aussi préciser mon ambition : je ne cherche pas à réaliser une I.A. très complexe, juste à rentrer quelques règles pour améliorer le hasard. On va d'ailleurs la renommer I.A. (pour Intteligence Attroffiée). Ainsi, à la différence de Ricochet Robot, on ne cherche pas la perfection, juste à jouer un coup, si possible meilleure que celui déterminé au hasard.
Depuis hier j'ai rentré la première règle, et dorénavant I.A. ne défausse plus la Princesse, ce qui représente un bond gigantesque dans son évolution. J'ai aussi réfléchi à d'autres règles et à une priorité à leur accorder :
Règle - Priorité
- Ne pas jouer Princesse - 100%
- Ne pas se cibler avec Prince si Princesse en main - 100%
- Garde choisir cible selon cartes visibles et/ou connues - ?
- Jouer Baron si probabilité >50% selon cartes visibles et/ou connues - ?
- Jouer Prêtre - 80%
- Jouer Prêtre si Garde en main, sauf dernier tour - 95%
- Jouer Garde si carte en main connu (sauf si Garde) - 100%
- Jouer Servante sauf si fin partie approche et carte plus faible en main - 90%
- Jouer Garde si couplé avec Roi - 100%
- Garder Roi sauf vers la fin si séquence positive - ?
- Jouer la Comtesse dans les premiers tours, la garder à la fin sauf si ...
Je me rends compte que la fin de partie est susceptible d'être plus facilement scriptée mais cela me semble tout de même assez lourd.
Je cherche donc à enrichir cette liste de règles/conseils, voire de tactique (coups d'attente comme expliqué par Roswell).
Des idées ?
PS : je pense à l'instant qu'il est peut être possible de recréer l'ensemble des couples de cartes possibles et d'établir certaines règles, je vais voir ce que cela donne ...
Salut SansDétour!
Ce projet est bien cool !
Un pote avait commencer à faire un programme Love Letter, il n'avait fait que la partie mélange des cartes distribution...
Du coup je tag le sujet !
juste un petit point :
Sansdétour dit:
#7 Comtesse *1 (perdu si dans la main avec 5, 6 ou 8 )
Le joueur ne perd pas si il a Comtesse plus prince/roi/princesse, il est juste obligé de jouer la Comtesse. J'ai vu ce point et je me suis dis que ce serai dommage de commencer a coder avec des règles erronées
bon courage !
boubou
Il existe 2 versions de Love Letter, la version originale japonaise et la réédition américaine avec des dessins plus consensuels et un changement de règles.
J'utilise cette superbe version thématisée. J'ai cependant modifié certains textes mal écrit, à mon sens, et surtout rétabli la version initiale de la Comtesse. Dans la version américaine, celle-ci ne respecte pas le principe : "plus la carte rapporte de point plus elle est dangereuse / moins son effet est puissant". La version initiale est beaucoup plus cohérente. Il y a un autre changement, moins important, concernant la Servante. La version japonaise permet de cibler un joueur protégé par la Servante, même si l'effet est annulé.
Voici la version japonaise :
Minister (Ministre) – Rang 7 (1 carte)
Passif : Si votre main s'élève à un total de 12 ou plus vous êtes éliminé de la partie. Le Minister est aussi puissant que la Princesse, mais le garder peut s'avérer être un pari dangereux. Si vous attirez l'attention d'un autre puissant personnage (si vous piochez une carte de rang élevé), cela signifie qu'il vient de demander conseil à ce personnage (cela peut être la princesse elle même), il vient aussi d'arriver à la conclusion que ce mariage est prématuré, et il déchire donc la lettre. Donc le fait de le jouer est un moyen de s'en débarrasser. Note : Il est techniquement possible de tricher avec ce personnage, mais si vous le faîtes la princesse ne vous aimera jamais. Note : Vous êtes aussi éliminé de la partie si vous piochez cette carte alors que vous possédez déjà un personnage puissant en main.
Priest (Prêtresse) – Rang 4 (2 cartes)
Effet : Jusqu'à votre prochain tour, ignorez les effets des autres cartes dont vous êtes la cible. Ce prêtre silencieux garde tous les secrets, il vous protégera vous et vos alliés. C'est un des personnages les plus utile du jeu. Note : vous pouvez toujours être la cible de l'effet d'une carte, par contre l'effet n'est pas appliqué.
Plusieurs personnes ont déjà répondu sur le sujet et effectivement je suis assez d'accord avec eux sur le fait que de faire une intelligence artificielle n'est pas si triviale, malgré le fait que le jeu semble extrêmement simple.
Du coup, si c'était moi, je partirai non pas sur une liste de règles à appliquer de manière générale, mais carrément sur quelle carte jouer dans chacune des possibilités.
En gros, tu fais une liste de toutes les possibilités de cartes que tu as en main, c'est-à-dire toutes les paires possibles de cartes que tu peux avoir à ton tour de jeu (il y en a 33) et tu indiques laquelle jouer dans chaque cas.
Comme l'indique ce thread sur BBG http://boardgamegeek.com/thread/1258953/which-your-two-cards-should-you-play-analysis-all, il n'y a finalement pas tant de possibilités que cela.
En fait, il y a 19 cas à gérer. Car 14 cas sur les 33 sont triviaux.
Dans un premier temps, tu peux essayer de gérer ces cas sans se préoccuper de l'historique de ce qui a été joué et/ou du nombre de cartes qu'il reste à jouer.
Après, pour faire plus évolué on peut commencer à s'intéresser à l'historique de ce qui a été joué (par exemple, quand on joue un garde, on n'accuse pas quelqu'un d'être un prince si les 2 princes sont déjà tombés).
Maintenant, si tu veux le faire jouer le mieux possible, une idée typique est la suivante. Pour les cas à gérer qui ne sont pas triviaux (donc les 19 cas restants), tu fais jouer ton programme contre lui-même un très grand nombre de fois (plusieurs millions si possible). Et tu enregistres le ratio de victoires par paire.
Exemple: pour trouver comment jouer avec la situation "garde" + "prince". Tu règles ton programme pour que les 18 autres situations non triviales soient jouées à 50-50. Tu fais une première variante du programme où il joue systématiquement "garde". Une autre où il joue "garde" dans 10% des cas. Une troisième variante où il joue "garde" 20% des cas. Etc. Puis tu fais jouer les programmes entre eux, un très grand nombre de fois et tu analyses si l'un gagne plus souvent.
Mais là ça devient déjà du haut niveau. Et d'après ton post, je ne sais pas si tu as vraiment l'occasion de faire jouer le programme contre lui-même un très grand nombre de fois.
Mais sinon, ce n'est pas grave. Tu lui fais jouer les 19 situations non-triviales à 50-50. Mais il enregistre le %-age de victoires pour chaque cas. Par exemple, il enregistre en mémoire que dans la situation "garde" + "prince", il gagne 67% des fois où il joue "garde". Etc.
Ensuite, il faut savoir que même si "l'expérience" montre que dans la situation "garde" + "prince", le fait de jouer "garde" fait gagner 80% des parties (j'invente), cela ne signifie pas qu'il faut toujours jouer "garde". Il convient d'ajouter un peu d'aléatoire et de faire en sorte que, au hasard, il joue "prince" malgré tout peut-être une fois sur 10, pour rendre le programme moins prédictible.
Joli projet! J'avais la mauvaise impression en lisant le titre que tu voulais imaginer une variante solo (encore que c'est un peu l'idée).
Love Letter est un jeu qui contient du bluff, je ne crois pas que ce soit le jeu le plus pertinent pour développer une IA. Jouer contre un ordinateur, même s'il peut donner l'illusion de bluffer, ne permettra jamais de retranscrire cet aspect du jeu.
artless dit:Love Letter est un jeu qui contient du bluff, je ne crois pas que ce soit le jeu le plus pertinent pour développer une IA. Jouer contre un ordinateur, même s'il peut donner l'illusion de bluffer, ne permettra jamais de retranscrire cet aspect du jeu.
Ben, ça peut quand même être programmé, mais ce n'est pas facile du tout. Il y a des labos de recherche qui planchent là dessus depuis plusieurs années sur le Poker (qui est conceptuellement un jeu assez simple, surtout en variante Limit et à deux joueurs, où finalement il n'y a que trois choix à chaque coup − se coucher, checker ou relancer) avec un peu de succès.
En gros, tu fais une liste de toutes les possibilités de cartes que tu as en main, c'est-à-dire toutes les paires possibles de cartes que tu peux avoir à ton tour de jeu (il y en a 33) et tu indiques laquelle jouer dans chaque cas.
C'est effectivement ce à quoi j'avais pensé à la fin de mon avant dernier message. J'ai isolé les 19 paires mais en prenant les premières, j'ai eu du mal à trouver des solutions pertinentes, car on ne prend pas en compte les autres variables (défausses, protection de la Servante, carte adversaire connue ...). J'ai donc mis de coté cette approche et je suis revenu à mes règles. Je pensais cependant l'utiliser pour peaufiner le résultat obtenu par les règles. Par contre j'avais complètement oublié cette approche par la force brute statistique. Elle serait parfaite dans ce cas mais me semble très lourde à mettre en place et pas forcément adapté à l'outil de développement que j'utilise.
J'ai donc avancé sur mon petit programme : il semble supporter les règles sans erreur, je vais donc le mettre en ligne. Si des bonnes âmes veulent le tester ...
J'ai rentré dans l'IA la plupart des consignes évidentes. Au vu de l'amélioration de son niveau, elle est dorénavant promue Intelligence Amenuisée.
Tout d'abord elle tire au hasard une des deux cartes de sa main (oui, je sais, ça commence fort !) puis elle applique les consignes suivantes :
R6Jouer Baron si joueur pas protégé et carte connue inférieure à autre carte
R5Jouer Baron si joueur pas protégé et probabilité X%>50% selon cartes visibles et/ou connues
R9Choisir cible de Garde selon probabilité au vu des cartes visibles et/ou connues
R8Imposer cible si carte en main connue (sauf si Garde)
R7Jouer Garde si carte en main connue (sauf si Garde) et joueur non protégé par Servante
R1Ne pas jouer Princesse
R3Jouer Garde si couplé avec Roi
R4Ne pas se cibler avec Prince si Princesse en main
Si je rentre d'autres règles, il va me falloir faire attention à l'ordre dans lequel les appliquer ...
Règles envisagées :
Jouer Prêtre - 80%
Jouer Prêtre si Garde en main, sauf dernier tour - 95%
Jouer Servante sauf si fin partie approche et carte plus faible en main - 90%
Garder Roi sauf vers la fin si séquence positive - ?
Jouer la Comtesse dans les premiers tours, la garder à la fin sauf si ...
Défausser une carte connue de l'adversaire -
Décisions spécifiques selon couples de carte
Donner un poids négatif à des mauvaises décisions
...
Cela se passe ici pour les courageux :
Le cadre bleu à gauche aggrandit la fenêtre
Le drapeau vert lance le programme
Pour jouer, il suffit de cliquez sur carte choisie / Barre espace pour faire jouer l'IA
Voir à l'intérieur amène au code
Au milieu, cliquez sur Données en orange et en cochant sur les listes en bas vous avez accès aux données, notamment MainIA pour pour juger les décisions de l'IA
J'ai "terminé" mon petit programme et l'IA réalise, en gros, ce que j'espérais.
Vous pouvez la tester ici et pourquoi pas poster vos résultats !
Si vous avez des remarques quant à son comportement, je suis preneur.