Discussion :

[Paul--]

bonjour, j'ai programmé un jeu de tétris, ou les 5 types de pièces sont générées aléatoirement.

J'aimerai programmer une fonction qui permette à l'ordinateur de jouer tout seul en parallèle au joueur, c'est-à-dire qu'il déplace les pièces de manière optimale. Avez vous une idée de raisonnement à faire ?

Merci

[JHelp]

Tu as la méthode naïve :
Tester toutes les positions tourner dans tous les sens et prendre la meilleur.
La meilleur étant d'abord :
1) Celle qui fait le plus de ligne compléte
2) Si y en a pas, celle qui monte le moins haut et fait le moins de trou
Avec cette méthode tu as déjà de trés bon résultat.
Si tu connais la piéce suivante, tu peux jouer "virtuellement" deux coups et voir la combinaisons la meilleure

[Paul--]

JHelp, ok merci, c'est un peu bourrin mais ça marche.
Le mieux est de tester chaque configuration possible, et de la noter selon plusieurs facteurs : hauteur, trous, puits...

la méthode absolue étant de rechercher à l'avance les combinaisons de toutes les pièces pour chaque damier possible :

7 * ( 2 ^ 200) pour un damier de 20 * 10 = 200 cellules ...
quasi impossible à réaliser quoi.

L'autre problème est aussi la vitesse de l'algorithme, qui doit se plier au rythme du tetris.

[hamster]

bonjour, j'ai programmé un jeu de tétris, ou les 5 types de pièces sont générées aléatoirement.

Sans vouloir te décourager, il y en a 7 !

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
X
X  X    X   X  X
X  X    X  XX  XX   X   XX
X  XX  XX  X    X  XXX  XX

[ggnore]

bonjour, j'ai programmé un jeu de tétris, ou les 5 types de pièces sont générées aléatoirement.

Sans vouloir te décourager, il y en a 7 !

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
X
X  X    X   X  X
X  X    X  XX  XX   X   XX
X  XX  XX  X    X  XXX  XX

Il a du oublié les pièces symétriques entre elles.
Les 2 pièces qui ressemblent à un L
Les 2 pièces qui ressemblent à un S

[Earthwormjim]

Tu as la méthode naïve :
Tester toutes les positions tourner dans tous les sens et prendre la meilleur.

Bonjour,

Je relance ce topic suite à cette réponse : y a t'il une autre méthode moins "naïve" que celle-ci ?

J'ai moi aussi codé un tetris en suivant cette idée, mais la vitesse d'execution de mon code ne me permet pas de calculer 2 coups à l'avance, je suis limité à 1 (c'est fait avec shockwave, qui n'est pas spécialement rapide )

Pour info, mon tetris est jouable ici : http://earthwormjim.free.fr
tout en bas de la page, il est dans le bloc "Game Tests".

Appuyez sur la touche Return pour activer/désactiver l'IA, et a,z ou e pour contrôler la vitesse d'affichage de l'IA

[ToTo13]

bonjour,

il est étonnant qu'avec une méthode aussi naive ne nécessitant qu'un arbre d'une hauteur 2, tu n'arrives pas à lancer ton IA .

[Earthwormjim]

bonjour,

il est étonnant qu'avec une méthode aussi naive ne nécessitant qu'un arbre d'une hauteur 2, tu n'arrives pas à lancer ton IA .

Non, c'est pas ça le problème :p
l'IA fonctionne trés bien en utilisant deux coups d'avance, le problème vient du temps d'execution de ce calcul : le langage shockwave n'est pas spécialement véloce, et dans ce cas précis le fait de calculer deux coups à l'avance prends environ 500ms, ce qui provoque un blocage désagréable du jeu à chaque nouvelle piece qui arrive.

Je voulais faire une version ou l'on joue contre l'IA, mais avec un tel blocage, ça nuirait au gameplay

voilou, c'est pour ça que je voulais savoir si une autre méthode moins "brute" existait...

[ToTo13]

Bonjour,

Non, c'est pas ça le problème :p
l'IA fonctionne trés bien en utilisant deux coups d'avance, le problème vient du temps d'execution de ce calcul : le langage shockwave n'est pas spécialement véloce, et dans ce cas précis le fait de calculer deux coups à l'avance prends environ 500ms, ce qui provoque un blocage désagréable du jeu à chaque nouvelle piece qui arrive.

eurf...
Je pense qu'il est grand temps de faire un petit update et de passer sur des langages de grandes personnes comme Java, C, C# ou C++. Parce que là...

Non plus sérieusement, seule une petite heuristique personnelle peut te sortir de se mauvais pas Peut être quelques chose qui regarde juste à un coup à l'avance si l'endroit où tu places ta pièce fait monter le moins possible la pile et laisse le moins de trous possibles.

[Jedai]

Des langages de programmation de grande personne tu veux dire C/C++ et pas Java ou C#.

Non voyons, une grande personne responsable utilisera plutôt Haskell, OCaml, ou ADA au besoin...

--
Jedaï

[Alp]

C++ c'est pas mal, donc dans le cadre d'un jeu si on a fait le jeu en C++ autant le continuer en C++

Par contre, vraiment il va falloir que je me mette au Prolog.
LE SEUL langage made in Marseille

[PRomu@ld]

ou ADA au besoin...

Je ne peux que plusoyer. (et pour ceux qui ne le savent pas, c'est un langage crée par un français)

seule une petite heuristique personnelle peut te sortir de se mauvais pa

Oui, le seul moyen lorsque tu es limité, c'est d'utiliser le plus d'heuristiques possible (pour peu qu'elles ne soient pas prohibitive).

[pseudocode]

Oui, le seul moyen lorsque tu es limité, c'est d'utiliser le plus d'heuristiques possible (pour peu qu'elles ne soient pas prohibitive).

Une très jolie heuristique a été trouvée par Pierre Dellacherie (un francais !).

(traduite en C++ et C# par Colin Fahey, http://www.colinfahey.com)

[Earthwormjim]

Bonjour,

Bonjour,

eurf...
Je pense qu'il est grand temps de faire un petit update et de passer sur des langages de grandes personnes comme Java, C, C# ou C++. Parce que là...

Heu oué... sauf que si je veux un truc qui tourne facilement sur le web, sous windoz et macos et qui demande pas 5000 lignes de codes pour afficher un carré, je préfère encore utiliser shockwave
à la limite j'aurais pu le faire en java, c'est vrai...

Une très jolie heuristique a été trouvée par Pierre Dellacherie (un francais !).
(traduite en C++ et C# par Colin Fahey, http://www.colinfahey.com)

Arf merci, mais j'avais déjà visité cette page à l'époque (ça fait 4 ou 5 ans que j'ai codé ce truc), et j'avais appliqué ce qui est décrit au chapitre 6.8 de cette page, j'étais aussi entré en contact avec lui pour en parler...

j'vais tester en java...

merci

[O( N )]

Bonsoir,

je pense que tu peux enregistrer quelques combinaisons sur deux lignes et cinq colonnes par exemples.

Je m'explique : tes pièces font 5 carrés maximum de long, il me semble.
Donc tu stockes les combinaisons possibles de formes sur un carré composé de 2 carrés (profondeur) sur 5 carrés (de long)
=> 2 puissance 10 combinaisons.
L'idéal serait 5 * 5 => 2 puissance 25 mais ce n'est pas intéressant !

Tu compares les blocs existants sur une profondeur de deux carrés à ceux de ta base et
tu essais les différentes pièces, tu notes les meilleures pièces et leur position dans ces combinaisons.
Lorsque une pièce apparaît tu cherches la combinaison te donnant le meilleur score.

A chaque pièce tu cherches une dizaine de fois dans un tableau de 1024 combinaisons.
La dizaine vient du fait que tu testes le carré 1 à 5 sur une profondeur de 2,
puis le carré de 2 à 6 sur une profondeur de 2, puis le carré de 3 à 7, ...,
jusqu'au dernier carré équivalent à la largeur de ton rectangle de jeu, la profondeur équivalent à la hauteur du rectangle de jeu.

J'espère que cela sera une méthode exhaustive plus rapide

Bonne prog