[Puerto Rico]
On appelle un jeu fini, un jeu pour lequel il existe une méthode qui permet à un joueur de gagner à coup sur. Par exemple, à Puissance 4, si le joueur 1 ne fait pas d'erreur, il est obligé de gagner (mais heureusement pour l'auteur de ce jeu, il faut une forte puissance de calcul pour y arriver). La question est pausée de savoir si les échecs sont un jeu fini, la réponse à cette question n'étant certainement pas pour bientôt.
J'ai testé PR à Cannes. Je n'ai pas fait de partie, car les deux fois, les joueurs ne voulaient que découvrir les mécanismes, et donc les parties se sont arrêtées au bout de
4 à 5 tours. Le mécanisme ma cependant enthousiasmé, même si je n'ai pas pu tester les limites de mes premières stratégies intuitives.
Or, surprise, Monsieur Bilbo nous propose une feuille excell pour jouer à ce jeu, et la feuille excell peut apprendre à jouer et s'améliore au fur et à mesure des parties. Du coup, j'ai peur que PR ne soit qu'un exercice d'optimisation. Il existe peut être une politique optimal à suivre par un joueur (qui pourrait être le joueur 3 d'après ce que j'ai pu lire dans le forum), et ce joueur gagnerait obligatoirement si il ne faisait pas d'erreur. Vous me direz, mais non, car les autres joueurs peuvent s'entendre sur une politique pour lui nuire. Mais, j'ai l'intuition que cette politique de nuisance pourrait avoir un effet suicidaire pour le joueur la mettant en œuvre (c'est-à-dire qu'elle permettrait seulement à un autre de gagner, mais pas à lui). L'intérêt du jeu pour le moment existe, car nous ne connaissons pas encore cette stratégie optimale (si elle existe) et cessera lorsque une stratégie optimal imbattable sera proposée (sauf si réaction suicidaire d'un ou d'autre joueurs).
Est-ce qu'un algorithmicien c'est déjà penché sur la question ? Quelles sont vos intuitions sur ce problème ?
dans Puerto Rico il reste une part de hasard qui peut pourrir le jeu (le tirage de tuiles de plantations)... même si on peut trouver des lois de proba pour limiter ce hasard, il peut faire mal les choses 
A Caylus par contre, il n'y a pas de hasard mais plus de mécanismes, peut-être que là...
Veux rien savoir moi, il est où le plaisir ??!!
Je dois dire que mon initiation à PR m'a enthousiasmé. C'est un jeu de gestion qui demande des choix qui me semble subtil (quoi que les sondages que l'on voit sur les stratégies sembleraient montrer que les degrés de liberté réelle ne sont pas si grand). Bref, j'ai aimé, et donc pris du plaisir.
Il est vrai que j'avais oublié l'aspect tirage aléatoire des plantations.
le poney dit:dans Puerto Rico il reste une part de hasard qui peut pourrir le jeu (le tirage de tuiles de plantations)... même si on peut trouver des lois de proba pour limiter ce hasard, il peut faire mal les choses
A Caylus par contre, il n'y a pas de hasard mais plus de mécanismes, peut-être que là...
Je plussoie Monsieur Poney. Cette part de hasard, même infime, empêche de mettre en place une stratégie imparable: on ne peut se contenter que de la stratégie qui a le plus de chances d'aboutir à une victoire, et encore.
La raison pour laquelle je pense que le jeu réel ne peut en aucun cas être "fini" dans le sens défini par Monsieur KrKa est que contrairement aux parties générées par l'I.A contre elle même sous excel, les parties avec des joueurs humains sortent du cadre de la théorie des jeux.
Pourquoi ? Parce que cette théorie repose sur un axiome qui ne se retrouve jamais dans la vraie vie: que tous les joueurs sont rationnels.
En gros, imaginons qu'il n'y ait pas de hasard dans PR (par exemple, si l'ordre dans lequel arrivent les tuiles était déterminé à l'avance), dans ce cas la stratégie optimale ne serait toujours pas certaine de fonctionner, dans la mesure où elle doit nécessairement s'appuyer sur l'hypothèse de rationalité parfaite des joueurs, c'est à dire que chaque joueur optimiserait systématiquement son coup de manière à maximiser ses chances de victoire.
Or ça ne se vérifie jamais en vrai; à un joueur contre un ordinateur, ça peut éventuellement fonctionner pour certains jeux à deux (échecs...) mais penser que dans une partie à 5 vos quatre adversaires seront purement rationnels jusqu'au bout relève de la folie !
L'I.A d'Excel ne peut s'améliorer justement que parce que dans ce cas l'hypothèse de rationalité est -presque !- vérifiée.
Pareil pour Caylus... ici, il n'y a même plus de hasard (à partir du moment où on connaît l'ordre des joueurs et la disposition des tuiles de départ), pourtant allez prédire ce que vous jouer vos adversaires !Il y a fort à parier qu'ils joueront de toute façon n'importe comment
(enfin, de manière non optimale).De toute façon, ces jeux finis je n'y comprend jamais rien. Il paraît qu'Abalone est un jeu fini, pourtant je n'ai jamais compris comment gagner...
Krka dit: Vous me direz, mais non, car les autres joueurs peuvent s'entendre sur une politique pour lui nuire. Mais, j'ai l'intuition que cette politique de nuisance pourrait avoir un effet suicidaire pour le joueur la mettant en œuvre (c'est-à-dire qu'elle permettrait seulement à un autre de gagner, mais pas à lui).
exactement : mais non car bla bla bla (à moins que la stratégie du joueur 3 soit assez puissante pour gagner même si tous les autres sont ligués contre lui, mais je ne pense pas), si la seule facon de gagner pour les autres joueurs c'est de pourrir le 3ième joueur, ils doivent le faire (sinon de toute facon c'est le troisième joueur qui va gagner, si oui c'est un des autres joueur, donc forcément un de ceux qui pourissent le troisième)
je ne pense pas qu'un jeu à plus de deux et avec un minimum d'interaction puisse être fini (aucun joueur ne peut avoir de stratégie gagnante si tous les autres s'accordent pour lui taper dessus...)
le poney dit:A Caylus par contre, il n'y a pas de hasard mais plus de mécanismes, peut-être que là...
Allez tous en choeur !
Je trolle, tu trolles, il trolle, vous trollez, nous trollons, ils trollent !
Pour ce qui est du caractère fini de PR... Euh comment dire... euh bah c'est-à-dire que PR est aussi "fini" que n'importe quel jeu où le hasard à une place faible. Par exemple FMP c'est un jeu fini ? Bah sûrement... ou en fait non... Va savoir.
Sans compter que la prise en compte des autres joueurs est essentiels. Je sais par exemple, ton fameux 3ème joueur. Bah s'il base disons ses revenus sur la production de café et que le 2ème joueur se lance aussi dans le café, bah il risque de pas pouvoir en vendre beaucoup et donc de ne pas gagner beaucoup d'argent. Sauf s'il s'adapte (autres productions, comptoir,...). Donc si tu considères qu'un algorithmicien puisse parvenir à prendre en compte l'ensemble des tirages de ressources, l'ensemble des choix des autres joueurs, alors oui PR est fini... Mais alors Caylus, Tigre&Euphrate, Funkenschlag, j'en passe et des meilleurs sont tous plus ou moins finis aussi (et caylus qui est celui dans lequel le hasard est le moins présent certainement plus que les autres... je trolle, tu trolles, il trolle,...
euh je ne voulais qu'essayer de trouver un exemple de jeu sans hasard dans les règles pour essayer de pousser le raisonnement de krka...
c'est tout ! 
Monsieur Bilbo, j'essaye toujours de joueur avec les joueurs les plus rationnels possibles, sinon, je ne m'amuse pas !
Bibirico, à FMP, face à des joueurs expérimentés, il est difficile de prendre des initiatives. C'est à dire que si j'attaque un joueur pourra accroitre mes zones de ramassage, j'éloigne mon gros tas et des chars de ma zone de départ, je crée des faiblesses dans ma zone de défense, et l'autre joueur le plus proche de moi, en profite pour faire un carnage sauvage dont je ne me remettrai pas. Donc, face à des joueurs rationnels, je moissonne dans mon coin, et c'est à peux près tout.
L'homme par nature n'est pas prfait donc faillible...
Et si on suit ce résonnement, aucuns êtres humains ne peut logiquement ne jamais faire d'erreur.
Il ya toujours un petit quelque chose qui vient pourrir sa belle stratégie et encore une chance.
Sinon tous les jeux qui n'offrent que peu de place à la change seraient condamnés à ne plus être joués un jour ou l'autre ...et c'est bien triste.
Même si tu es le meilleur des meilleurs, il y a en général une chose que tu ne peux pas, voir peu prévoir c'est les réactions de ton adversaire. Surtout si tu ne joue pas habituellement avec lui, si c'est le cas... j'admets c'est plus facile.
Personnellement j'ai fais peu être une bonne vingtaine de parties de PR, ce qui me permet de voir un peu plus que la belle mecanique de ce jeu. Et il existe des dizaines de stratégies possibles et viables. Après il faut les tester, une part partie et part groupes de joueurs identiques.... je te laisse faire le calcul.
Donc avant de faire le tour de ce jeu, je te souhaite bonne chance et si tu y arrive, ne donne pas ta recette miracle à d'autres.
Laisses les jouer avec l'idée plaisante que eux ne trouverons jamais "la stratégie ultime".
Krka dit:Monsieur Bilbo, j'essaye toujours de joueur avec les joueurs les plus rationnels possibles, sinon, je ne m'amuse pas !
Je prétends justement que c'est cela qui est impossible. Prévoir les coups d'un seul adversaire sur toute une partie, je peux l'envisager (très à la rigueur !) pour certains génies ou autistes, mais anticiper les coups purement rationnels de 4 adversaires, et les pondérer avec la distribution de probabilité du tirage des plantations relève d'une puissance de calcul totalement surhumaine.
Supposons que vous trouviez un joueur génial capable d'un tel prodige, encore faudrait-il que vous trouviez autres génies comme lui et que vous les convainquiez tous de se réunir pour faire une petite partie de PR.
Donc pour moi sur des jeux dont les mécanismes dont déjà assez complexes je pense qu'il ne peuty avoir de jeu vraiment fini à plus de deux joueurs. M'est d'avis qu'Andreas Seyfarth lui même n'est pas entièrement rationnel lorsqu'il joue à Puerto Rico.
tonym301 dit:L'homme par nature n'est pas prfait donc faillible...
Et si on suit ce résonnement, aucuns êtres humains ne peut logiquement ne jamais faire d'erreur.
pourtant je ne perd jamais au morpion, je suis un dieu?
Euh, le problème de rationnalité, là j'ai du mal à le voir ?
En tous cas à deux joueurs ce n'est pas du tout un problème, vu que si un coup "non rationnel" conduit à la victoire, alors c'était certainement le meilleur coup à faire, et "rationnellement", le coup à faire...
A plus de joueurs, ça voudrait dire qu'un joueur serait prêt à se sacrifier pour entraîner la défaite d'un joueur donné, qui serait "sûr de gagner" s'il ne le fait pas. Bon, déjà entre humains je trouve ça un peu pénible comme attitude, mais on peut considérer que l'intérêt du joueur en question est la défaite d'un autre joueur donné. Il agira donc "rationnellement" tout au long de la partie dans ce but.
D'ailleurs, le jeu de Nim à 3 joueurs n'est pas un jeu "fini" : je rappelle qu'à deux joueurs c'est sans doute le jeu "fini" le plus simple à concevoir. Mais à trois joueurs il y en a forcément un qui a la fin devra choisir entre deux coups faisant gagner l'un ou l'autre de ses adversaires...
scand1sk dit:Euh, le problème de rationnalité, là j'ai du mal à le voir ?
Il veut dire par là que pour essayer de mettre en place une stratégie gagnante à tous les coups. On est obligé de considérer que tous les joueurs vont jouer leur meilleur coup, sinon on ne peut prévoir quels seront leur coup et donc notre stratégie "gagnante à tous les coups" tomberait à l'eau. Or jouer son meilleur coup c'est ce que l'on pourrait appeler un comportement "rationnel". Et je ne pense pas qu'il existe effectivement la moindre partie de PR où tous les joueurs ont constamment adopté un comportement "rationnel". De PR ou de n'importe quel jeu d'ailleurs... Même aux echecs parmi les plus grands...bien que cela soit sûrement là que l'on s'en approche le plus.
bibirico dit:scand1sk dit:Euh, le problème de rationnalité, là j'ai du mal à le voir ?
Il veut dire par là que pour essayer de mettre en place une stratégie gagnante à tous les coups. On est obligé de considérer que tous les joueurs vont jouer leur meilleur coup, sinon on ne peut prévoir quels seront leur coup et donc notre stratégie "gagnante à tous les coups" tomberait à l'eau. Or jouer son meilleur coup c'est ce que l'on pourrait appeler un comportement "rationnel". Et je ne pense pas qu'il existe effectivement la moindre partie de PR où tous les joueurs ont constamment adopté un comportement "rationnel". De PR ou de n'importe quel jeu d'ailleurs... Même aux echecs parmi les plus grands...bien que cela soit sûrement là que l'on s'en approche le plus.
Mmmh si un joueur ne joue pas son meilleur coup, ça veut dire que la stratégie gagnante sera encore plus facile à réaliser : aux échecs, une "stratégie gagnante" prend normalement en compte tous les coups de ses adversaires, même les plus improbables.... Mais tout ça ne reste valable que sur un jeu à deux joueurs entièrement "visible", sans hasard. A priori, il n'existe aucun jeu à plus de deux joueurs qui puisse être "fini", si les trois joueurs commencent avec les mêmes données en début de partie.
Je n'ai pas tout lu, mais je pense pouvoir vous éclairer.
Dans le cas d'un jeu à deux joueurs sans hasard, mathématiquement, il y n'y a qu'une alternative : soit les deux joueurs peuvent assurer le nul à coup sûr, soit un joueur peut gagner à coup sûr. Si le nul est exclu par la règle, alors un des deux joueurs peut gagner à coup sûr. Par exemple, l'Awélé a été "résolu" récemment (comme on dit) et il a été prouvé que le joueur qui commence a une stratégie (ou plutôt un arbre de stratégies, fonction des coups de son adversaire) gagnante à coup sûr. Au Puissance 4, c'est le second joueur (c'est assez rare, d'ailleurs).
Aux échecs, la quasi-certitude est que les joueurs peuvent assurer le nul, mais cela n'a pas encore été démontré.
Un peu comme au Tic-Tac-Toe (le joueur qui commence peut assurer le nul à coup sûr), sauf que c'est légèrement plus complexe comme modèle...
En fait, bien que le nombre théorique de parties (suite de coups amenant les joueurs à déterminer un vainqueur ou à constater un nul) soit fini, il dépasse de très loin les capacités de calcul de tous les ordinateurs possibles. Pour résoudre l'awélé, il a fallu réduire par des raisonnements mathématiques le nombre de parties à calculer jusqu'à atteindre un nombre suffisamment raisonnable pour pouvoir lancer une machine.
Dans le cas d'un jeu à n joueurs, c'est plus compliqué.
Dans le cas d'un jeu avec du hasard comme Puerto Rico, ça se complique encore. Le problème est qu'il y a une part des informations qui n'est disponible qu'au fur et à mesure en cours de partie. Il est possible alors que d'autres cas de figure apparaissent, et qu'il n'y ait de stratégie dominante pour aucun joueur.
Cependant, dans le cas de Puerto, j'ai tendance à penser qu'il doit être possible de démontrer un résultat universel pour toutes les configurations possibles... Du genre le 3ème joueur peut assurer la victoire ou quelque chose comme ça.
Pour ceux qui s'inquiéteraient de savoir que l'existence d'une stratégie dominante pour l'un des joueurs à Caylus à 2 est un fait mathématiquement établi, et qui craindraient de voir gâcher leurs parties, rassurez-vous : le nombre de configurations à calculer est tellement colossal que je doute qu'on puisse jamais construire une machine capable de calculer un algorithme même pour les 3 premiers coups.
EDIT : Je viens de voir que scand1sk avait en gros déjà dit tout ça. L'exemple du Nim est très bon pour le jeu à 3 joueurs.
Moi je joue à PR à l'instinct
Rien ne me gave plus que de lire des traités stratégiques, le plaisir de decouvrir par soi même et d'experimenter est unique
Fabrice dit:Moi je joue à PR à l'instinct
Rien ne me gave plus que de lire des traités stratégiques, le plaisir de decouvrir par soi même et d'experimenter est unique
Ah ben oui, t'as infiniment raison, mais c'était pas la question, là...
La part de hasard n'empêche en rien l'optimisation.
Et pour répondre à la première question et appuyer la phrase ci-dessus, j'ajouterais que ce n'est pas un algorithme qui résoudra le problème, mais une métaheuristique, outil d'optimisation (originaire des simples heuristiques) qui permet de résoudre des problèmes d'optimisation complexes avec de nombreuses contraintes, et ce en utilisant une part de hasard.
Je pense qu'un "recuit simulé" suffirait, mais faut voir. Les fourmis" peut être intéressant aussi, comme il y a plusieurs joueurs.
J'ai plus le temps de faire ce genre de projets, mais ça peut être très intéressant. Je serais curieux de lire la définition des contraintes et de l'espace des solutions, surtout.
Loris.
C'est bien le problème, va-t-en définir les variables et les contraintes sur un jeu aussi complexe que Puerto Rico, et, pire, définir des critères à optimiser, surtout si tu veux essayer de faire "voir" le système plusieurs tours à l'avance...
Enfin une fois qu'on a ça, il y a tout ce qu'il faut en termes de méthodes de résolution efficaces et autres metaheuristiques, c'est même le sujet de ma thèse :p