On m´a posé un problème marrant avant hier soir. Alors je vous le pose moi aussi.

On considère le jeu a deux joueurs suivant. On dispose d´une ligne d´un nombre pair de piece. Chaque joueur a son tour prend une des pieces en bordure de la ligne (Soit celle qui est tout a gauche, soit celle qui est tout a droite). A la fin, chaque joueur a donc le meme nombre de pieces. Mais les pieces n´ayant pas toutes la meme valeur, il est possible qu´un des joueurs obtienne une plus grosse somme que l´autre.
Question: Donner une stratégie gagnante pour joueur 1.

PS: par gagnante, j´entends joueur 1 ne gagne pas moins que joueur 2

Le joueur 1 doit cacher des pièces dans sa poche .

ou frapper le joueur 2

Écrire un programme qui donne la stratégie gagnante pour 1 et la moins perdante possible pour 2, ce n´est pas très dur (avec une exploration en profondeur, ça doit aller assez vite). Mais je ne vois pas d´astuce plus intelligente que ça qui permette à un humain de trouver la solution.

une girafe de biere m´a bien aidé

Il y a une programmation dynamique en O(n^2). Mais avoir la meilleur stratégie ne dit pas que 1 a plus d´argent a la fin

Godrik > On se fait une ligne ?
Godrik > une girafe de biere m´a bien aidé

--> Oh la déprave ! Qu´est ce qu´ils vont penser les jeunes maintenant ? Ceux qui te prenaient comme modèle

ils finiront comme moi: pauvre dans la recherche francaise

c´est marrant, j´ai vu cet exo en TD d´IA cette année...

Je cherche mon cours pour voir ce qui a été dis a ce sujet

...

...

... <- matérialise le temps qui passe d´une manière tres explicite

...

...

arf pas d´algo spécifique, juste de la construction de graph et de la recherche par alpha/beta.
Ca doit pouvoir passer avec un nombre raisonnable de pieces, on tombe avec un arbre avec 2^n feuilles. Ca reste explorable...

c´est pour ca que je déteste les cours d´IA, ca ne raconte jamais rien d´interessant.

"un arbre avec 2^n feuilles"
Quand meme, il y a beaucoup plus efficace que ca...

pour défendre mes pov´ profs d´IA je dirais que j´ai vu ce "jeu" au deuxieme ou troisieme TD de cette matiere dont le but était justement l´exploration d´arbre (et surtout comment ne pas se faire chier a tout parcourir)

enfin c´est vrai que ça fait gros bourin comme methode

bah, il y a des jours ou on a pas le choix. L´exemple n´est pas tres bien choisit pour un cours. Sur le probleme des n-reine ou un probleme du meme enre, il n´y a pas vraiment d´algorithme beaucoup plus intélligent que recherche exhaustive. Ca aurait été un meilleur choix peut etre.

on a fais les n-reines en cours ;)