Version imprimable
Bonjour,
Le jeu des 20 batons ( un des jeux de Fort Boyard ) consiste à prendre chacun son tour un, deux ou trois batons sur les 20 proposés. Le but est DE NE PAS prendre le dernier baton.
Je souhaiterais faire un algorithme qui permet de calculer toutes les possibilités possibles et celles qui sont les bonnes.
Mais je n'est aucune idée de comment m'y prendre.
Si vous avez un tuyau merci.
PS: Dsl pour le titre et l'emplacement du topic je sais pas ou le mettre :(
ASPIC
Arf et dire que je connaissais l'astuce mais ya plus de 30 ans et saurais plus le formuler, il me semble que cela avait à voir avec la parité ou pas des rangées mais je sais plus trop.
Bon c'est vrai que sans tenir compte du langage et du framework, tu pourrais tout aussi bien poster sur le forum dédié à l'algorithmie. J'attend un peu si demain tu n'as pas de réponse, je déplacerai vers le bon forum (laisse faire ;))
Losque cela arrivera n'oublie pas de prendre le temps de présenter la shématisation du jeu, car personne n'est obligé de regarder Fort Boyard pour pouvoir de répondre :)
pas tout a fait Neguib.... pour generaliser le probleme (ne pas se limiter a fort boyard) ,la solution se presente comme telle (ATTENTION: il y a quand meme des cas dependant du nombre de batons au depart ou ce n'est pas gagné a coup sur):
soit 2 joueurs
soient N batons identiques disposés parall. les uns a cotés des autres
soit k le nombre de batons que peut choisir un joueurs en un coup (k<N fixé en debut de partie).
Le perdant est celui qui prend le dernier baton.
Le candidat doit calculer le reste de la division euclidienne de N par (k+1), qu'on appelle r, puis retirer (r-1) batons pour obtenir un nombre de batons congru a 1 modulo (k+1).
SI le nombre de batons au depart est congru a 1 modulo (k+1), soit tu passes ton tour (tricheur!!!) soit il te reste a esperer que ton adversaire ne connaissae pas la regle et attendre d'avoir un nombre de batons non congru a 1 modulo (k+1).
Pour en revenir a Fort Boyard, quand tu commences , tu prends 3 batons pour lui en laisser 17 et ensuite tu prends systematiquement le complement a 4 du nombre de batons qu'il a pris....
a toi les boyards !!!
merci bcp pour vos 2 reponses :
Effectivement tophoune tu as raison mais j'ai une erreur : y'a 21 batons je crois dans le jeu ( d'apres les topic sur internet ) dc effectvement si j'en crois la regle : le candidat dans Fort Boyard est sur de perdre !!
De plus, le congru modulo je connais pas ^^ loool je suis en 1erS masi j'ai retaper sinon j'aurais eu mon BAC cette année !!!! donc je vais attendre de voir mon année de terminal pour voir cet algorithme ^^
Sinon ce ue je voulais faire c'est pas créer un IA qui gagne toujours ^^ mais plutot envisager toutes les solutions possibles et trouver les bonnes. ( j'ai essayer un arbre mais ca marche pas... )
Merci
Salut, tout dépend de ton algorithme et du type d'arbre, de la facon dont il est concut et élagué à la construction :) Générallement les algorithmes par construction d'arbres sont trop long, mais très efficaces.Citation:
Envoyé par Aspic
mais comme préciser, à chaque tour il faut recréer l'arbre à moins que le cas n'est déja été pris en compte. D'un autre coté, pour que ton algorithme soit viable, tu ne peux pas construire un arbre ENTIER, il faut déterminer des conditions pour l'élaguer et ainsi éviter un algo trop long à l'exécution et surtout une consommation mémoire trop grande.
Essaie l'algorithme Minimax, meme si je suis pas convaincue lol
Qu'est ce que c'est l'algorithme Minimax ?
Je pense que c'est trop dur pour moi à faire mais bon merci comme meme :)
Comment traduire une congruence en language vb.net ?
Bonjour
Ton algorythme n'est pas du tout compliqué à faire !!
Tout a été dit par tophoune
En clair, ton algo c'est
(Pour 21 batons à raison de 3 batons à enlever au max) :
NombreDeBatonsAEnlever = 4 - NombresDeBatonsEnleverParAdversaire