TOURS DE HANOÏ: INTRODUCTION AUX ALGOS RÉCURSIFS.

cs_Kirua Messages postés 3006 Date d'inscription dimanche 14 avril 2002 Statut Membre Dernière intervention 31 décembre 2008 - 6 févr. 2004 à 17:38
cs_Kirua Messages postés 3006 Date d'inscription dimanche 14 avril 2002 Statut Membre Dernière intervention 31 décembre 2008 - 19 juil. 2004 à 23:51

Cette discussion concerne un article du site. Pour la consulter dans son contexte d'origine, cliquez sur le lien ci-dessous.

https://codes-sources.commentcamarche.net/source/20173-tours-de-hanoi-introduction-aux-algos-recursifs

cs_Kirua Messages postés 3006 Date d'inscription dimanche 14 avril 2002 Statut Membre Dernière intervention 31 décembre 2008
19 juil. 2004 à 23:51

cherche du côté des algos MiniMax et Alpha-Beta (alpha beta c'est une amélioration de minimax).

ça permet de faire remonter le meilleur mouvement à faire en prévoyant x coups à l'avance (le postulat de départ étant que l'adverseraire tentera lui aussi de tjs effecteur le meilleur coup, ce qui paraît logique, et de tte façon s'il ne le fait pas, ça augmente les chance de victoire de l'IA)

Utilisateur anonyme
18 juil. 2004 à 10:38

Ben, on peux faire ca par force brute:
pour chaque pièce, faire chaque coup, tester si le coup est gagnant, perdant, stratégie gagnante, ou rien.
On fait ce procédé "récursivement" *.
*: bon, ici, on peux pas faire de la vraie récursion, parce que sinon le prog va bloqué comme il existe des parties infinies, donc on utilise un compteur pour la profondeur de recherche, pour chercher par exemple 10 coups d'avance.
Bon, c'est vraiment de la merde cet algo, parce que l'on sait pas déterminer si une position est mieux qu'une autre, etc...

C'est un problème vachement dur.

coucou747 Messages postés 12303 Date d'inscription mardi 10 février 2004 Statut Membre Dernière intervention 30 juillet 2012 44
17 juil. 2004 à 23:06

ah non, ça j'ai compris, mais vous avez dit que ça servais pour les ia, et en ce moment, je fais un jeu d'échec en C et un othello en javascript (il est finit mais nul, et un peu buggé)
Et donc, j'ai réussi a mettre une ia sur mon othello, mais pas sur mon jeu d'échecs, et parfois, je bat mon othello 60 a 4 ou 58 a 0 alors évodement, c'est pas récursif, il cherche juste sur un coup pour le othello, alors il est pas performant, j'aimerais savoir comment faire une ia en économisant le plus possible de mémoire. J'ai aussi fait un morpion en javascript, mais lui, est imbatable, et pas récursif, j'ai mis if (...) then joue(1) ect... il a plein de lignes comme ça, mais aux échecs, on ne peut évidement pas faire ça, étant donné le nombre de possibilitées, alors j'ai pensé a un minimax, ce qui oblige la récursivitée, (et donc, je demande de l'aide pour le placer dans le programme) J'ai vu un linux mag sur les ia de jeux d'échecs avec minimax, mais j'ai rien compris, et donc, coincé...

cs_dominion Messages postés 230 Date d'inscription mardi 21 janvier 2003 Statut Membre Dernière intervention 15 mai 2008
17 juil. 2004 à 22:57

NOTE : a mon avis c'est débile comme fonction ya bcp plus simple, mais c du récursif :-D

cs_dominion Messages postés 230 Date d'inscription mardi 21 janvier 2003 Statut Membre Dernière intervention 15 mai 2008
17 juil. 2004 à 22:56

c un peu simplifié

pour vérifier la case :

string typecase(int type, int pos)
{
string retour = "";

//tu check
if (type == 1)
retour = "cavalier";

if (type < 12) // = le nombre de pions possibles(pion, tour, cavalier, fou, roi, dame) x2 pour la couleur
{
type ++;
typecase(type, pos);
}
return retour;
}

coucou747 Messages postés 12303 Date d'inscription mardi 10 février 2004 Statut Membre Dernière intervention 30 juillet 2012 44
17 juil. 2004 à 20:29

moi, je trouve ça pas mal pour aprendre comment faire une fonction ia,
Quelqu'un sait-il comment je peux implenter un truc de ce style dans un programme d'échec sans aucune struct, l'échiquier est placé dans un tableau, les fonctions d'interdit et d'autorisé sont gérés, c[x+y*8] est une case de l'échiquier, cette case vaut 1 si il y a une tour sur cette case, 2 si il y a un caval ect

C'est pas mal pour aprendre, mais ça m'aide pas directement...

Utilisateur anonyme
26 avril 2004 à 10:24

Bon bah j'ai quand même mis niveau 1 pour faire plaisir... ;-)

Utilisateur anonyme
26 avril 2004 à 10:21

Ouai, c'est même le premier exemple que j'ai vu en Intelligence Artificielle. Mais ici tout le monde n'a pas fait d'AI ou bien de DB.
La plupart des gens qui n'en ont pas fait restent cantoné en itératif.
Alors il vaut niveau 2. Bon 3 je sais pas pourquoi j'ai mis ça, mais je reconnais que c'était trop.

cs_nEUrOne Messages postés 41 Date d'inscription dimanche 17 novembre 2002 Statut Membre Dernière intervention 14 avril 2004
26 avril 2004 à 08:49

C'est un des premiers exemples que l'on voit en structure de données ... c'est du niveau 1 !

Utilisateur anonyme
8 avril 2004 à 18:16

ouai bon, je me suis peut être un peu emporté sur ca.
Mais ca reste à un niveau conceptuel plus élevé que la programmation impérative classique. Je sais plus trop pourquoi j'ai mis expert. À l'époque je devais avoir un prétexte.

surfeurnet Messages postés 68 Date d'inscription vendredi 28 février 2003 Statut Membre Dernière intervention 17 août 2005
8 avril 2004 à 15:56

D'accord c'est l'exemple de base d'un algo récursif mais de là à ce qu'il soit niveau 3 !

Hylvenir Messages postés 364 Date d'inscription mercredi 11 février 2004 Statut Membre Dernière intervention 5 octobre 2006 2
23 févr. 2004 à 18:08

Pour info, le "return 0;" à la fin du main en C++ n'est pas obligatoire.
Et c'est dans le standard. ;-)

Utilisateur anonyme
11 févr. 2004 à 20:26

nan, mais Kirua à un peu raison, cela m'a permis d'apprendre ce qu'était ces fameux using namespace. Je savais pas et maintenant je sais. Ca m'avance... ;-)
Puis en fait, je l'ai pas pris comme une critique du prog, même si c'était pas le cas.

cs_dominion Messages postés 230 Date d'inscription mardi 21 janvier 2003 Statut Membre Dernière intervention 15 mai 2008
11 févr. 2004 à 20:02

Je suis tout à fait d'accord : il faut que le code soit correctement écrit. Mais celui-ci compile et using namespace ou pas, le résultat apparent est le même. Donc dans ce cas-ci, ce n'était pas grave.

cs_zmc Messages postés 147 Date d'inscription vendredi 26 avril 2002 Statut Membre Dernière intervention 26 avril 2008 1
11 févr. 2004 à 19:39

Visiblement tu comprends pas ce que je veux dire, autant en rester la...

TeLeTUbIz >> ouais, sympa l'exemple

zmc

cs_Kirua Messages postés 3006 Date d'inscription dimanche 14 avril 2002 Statut Membre Dernière intervention 31 décembre 2008
11 févr. 2004 à 18:56

critiquer c'est pas forcément négatif, y a svt méprise là dessus. et puis pq il faut tjs donner un avis positif? armf, c une discussion qui survient trop souvent sur CS, c'est énervant. moi j'ai pas voulu être méchant enfin, relisez mon premier poste, il est agressif ??

Utilisateur anonyme
11 févr. 2004 à 18:36

M'enfin, sinon, le tuto, il est bien ?

Utilisateur anonyme
11 févr. 2004 à 18:36

Kirua a raison de respecter les normes; toutefois, la norme ne précise pas d'utilier using namespace std; seulement le standart conseil cette forme et déconseille la forme #include
Par contre, c'est pas en dehors de la norme. On a le droit de le faire mais pour des raisons de compilation ou autre, c'est pas conseillé c'est tout.
(et ouai, depuis le post de Kirua, je suis allé me renseigné dans des bouquins sur ces using namespace, et j'ai lu un peu la norme actuelle)

cs_zmc Messages postés 147 Date d'inscription vendredi 26 avril 2002 Statut Membre Dernière intervention 26 avril 2008 1
11 févr. 2004 à 18:20

salut dominion,
avant tout, je suis pour le code propre et le respet des standards. Je trouve simplement que c'est pas très cool de poster un commentaire uniquement pour critiquer un code, sans meme donné son avis dessus.
C'est tout.

zmc

cs_dominion Messages postés 230 Date d'inscription mardi 21 janvier 2003 Statut Membre Dernière intervention 15 mai 2008
11 févr. 2004 à 15:40

Oui mais de là a me faire ch*** pour un return 0; sur un tableau... Enfin la rigueur toujours la rigueur... ;-)

cs_Kirua Messages postés 3006 Date d'inscription dimanche 14 avril 2002 Statut Membre Dernière intervention 31 décembre 2008
11 févr. 2004 à 15:34

si tu mets #using namespace std ton compilo va rien dire parce qu'il sera même pas appelé, c'est le préprocesseur qui va gueuler ;-)

et puis faut pas dire grand puriste O_o j'essaye de respecter les standards, voilà tout. et d'ailleurs je vous enjoints tous à me le faire remarquer qd je ne respecte pas une norme.

cs_dominion Messages postés 230 Date d'inscription mardi 21 janvier 2003 Statut Membre Dernière intervention 15 mai 2008
11 févr. 2004 à 15:25

Peace and love les gars !

Pour info, le cotoyant tous les jours, Kirua est un grand puriste. Il est du genre à m'emmerder parce que j'ai oublié de mettre le return 0; à la fin de ma fonction int main() écrite à la craie sur un tableau !

Je suis d'accord avec zmc : du moment qu'on a l'idée... De plus, mon compilo (BCB) accepte #include sans #using namespace std mais si je met #include alors #using namespace std est nécessaire (me demandez pas pourquoi j'en sait rien)

Utilisateur anonyme
9 févr. 2004 à 23:10

oula, y'a de la tension...
Enfin, engueulez vous chez moi, tant que vous cassez rien, ca me gène pas ;-D

cs_Kirua Messages postés 3006 Date d'inscription dimanche 14 avril 2002 Statut Membre Dernière intervention 31 décembre 2008
9 févr. 2004 à 22:55

n'empeche, je maintiens que c t pas la peine d'être agressif (j'ai bien essayé de régler ça via PM avec zmc mais il a répondu ?, en postant ici il vera peut ê de quoi je parle)

Utilisateur anonyme
9 févr. 2004 à 22:38

lol
d'autant plus que moi et les namespace,...
c'est pas que j'aime pas, c'est plutôt que je connais pas des masses; mais bon, je fais une lecture de mise à niveau (la prog à la fac, c'est pas appris très rigoureusement; alors faut lire des bouquins à la norme)

cs_zmc Messages postés 147 Date d'inscription vendredi 26 avril 2002 Statut Membre Dernière intervention 26 avril 2008 1
9 févr. 2004 à 21:40

bon exemple, 8/10

kirua : je vois que tu perd rarement une occasion de te faire remarquer...
J'imagine que le but de cette source est avant tout de demontrer une technique de programmation, pas de faire un tutorial sur les namespace...

zmc

cs_Kirua Messages postés 3006 Date d'inscription dimanche 14 avril 2002 Statut Membre Dernière intervention 31 décembre 2008
6 févr. 2004 à 17:38

comprends pas que ça compile, c'est iostream, pas iostream.h et il faut mettre using namespace std; en dessous des include, ou bien utiliser std::cout.

vala ;-)

Discussions similaires

Tours de hanoï

lien Facebook vers actualité sous typo3

solution tours de hanoi sur XNA

exercices corrigés pour debutant vbs

Tour de Hanoï

Votre réponse

Discussions similaires