Discussion :

[eyquem]

Ah zut, j'ai vu cette page sans m'y arrêter, je me suis fait avoir par la petite typographie des symboles que je cherchais. Merci de m'y ramener, shadowsam.
J'ai un peu de mal à saisir les subtilités, il va falloir que je potasse.

Qu'appelle-t-on "coder en dur" ?
Est-ce que cela signifie qu'on écrit toutes les valeurs possibles d'une variable au moyen de valeurs précises pour ses éléments, et non pas en utilisant des indices qu'on fait varier dans des plages ou des ensembles de valeurs ?
Cela veut-il dire 'de façon explicite' ? = 'A la main' ?
Par exemple
li=[ (1,2),(1,3),(1,4),(2,2),(2,3),(2,4)] est-elle codée en dur
tandis que li = [ (x,y) for x in (1,2) and y in (2,3,4) ] ne l'est pas ?


Pour ton code, je ne l'ai encore qu'un peu regardé.
Bien vu pour le (0,SIZE**2,SIZE), j'ai eu besoin d'un truc comme ça à un moment mais je n'ai pas pensé à ceci précisément..... Oublier une possibilité pareille !! (normalement ici: smiley mangeant nerveusement son chapeau mais y a pas )
J'attaque ton code comme un gateau au chocolat bien consistant. J'aime bien les codes concis au point d'être cryptiques comme tu dis. Miam !!

[shadowsam]

li=[ (1,2),(1,3),(1,4),(2,2),(2,3),(2,4)] est-elle codée en dur
tandis que li = [ (x,y) for x in (1,2) and y in (2,3,4) ] ne l'est pas ?

Techniquement même ta 2eme solution n'est pas ce que je cherchais car elle reste tributaire de la taille du plateau et donc ne marche que dans le cas d'un plateau de dimension 3.

Donc l'idée c'était d'écrire les fonctions de parcourt dans le plateau qui permettent d'extraire les indexes à tester afin de vérifier qu'il y a une colonne/diagonale/ligne complète. Par exemple extraire [0,3,6] pour vérifier la première colonne.... etc...

Et puis bon, j'ai aussi condenser le code au delà de toute décence, mais ca c'était pour m'amuser parce que jamais j'irais écrire un truc pareil dans le cadre d'un projet de développement, c'est vraiment trop difficile a relire et a comprendre.

EDIT:
A propos de ca :

Code :

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

1
2
3
dicokeys = dico.keys()
dicokeys.sort()
for i in dicokeys:

J'ai l'habitude de faire comme ca:

Code :

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

1
2
for i in sorted(dico.keys()):
  print i

[eyquem]

Une remarque sur le début de ton code.
Dans la continuité de ce qu'a écrit oiffrig, je considérais la variable plateau comme le conteneur des symboles écrits successivement par les joueurs, une valeur de plateau représentant un état de la partie à un moment donné.
Ce que tu affiches sous le terme de Plateau, je l'appellerais plutôt damier numéroté puisqu'il s'agit de la répartition fixe des numéros repérant les cases. Ce n'est pas décisif mais il faudrait s'entendre sur les termes, surtout s'ils sont révélateurs d'une manière d'envisager l'algorithme.

Au passage, map(lambda: ) ne me plaisait pas trop (je ne sais pas bien pourquoi...) mais surtout la répétition de print. Mon dada récent est de rassembler autant que possible tous les caractères que je veux imprimer dans une seule variable de type chaine, avec des '\n' aux bons endroits pour obtenir les retours à la ligne, et de lancer un seul print plutôt que plusieurs. J'ai remarqué que chaque appel à print prend du temps; de même, print a,'---',b est plus long à exécuter que print a+'---'+b. Du moins il me semble, car je n'ai pas mesuré. Intellectuellement en tous cas, je trouve plus logique de préparer ce qu'on veut afficher puis de l'envoyer d'un coup au lieu de découper les activités d'affichage ou d'écriture.
Donc après 2 heures d'essais tordus, je suis enfin arrivé à coder l'affichage du damier d'une façon qui me plait:

Code :

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

print '\n\n'.join([ SIZE*'%2d ' % tuple(xrange(i,i+SIZE)) for i in xrange(0,SIZE**2,SIZE)])

C'est clean, non ?


Je ne vois pas trop l'intérêt de passer par un dictionnaire WALK_FCT pour créer la liste ALL_TESTS.

Code :

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

1
2
ALL_TESTS = [lambda i:i+i*SIZE,lambda i: (SIZE-1)*(SIZE-i)]
[ALL_TESTS.extend([(lambda n: lambda i: n*SIZE+i)(n),(lambda n: lambda i: i*SIZE+n)(n)]) for n in xrange(SIZE)]

Je suis parvenu à comprendre à peu près ce que fais la fonction test(). En résumant:
pour chacune des 12 fonctions f (pour SIZE==5) , [f(i) for i in [0,1,2,3,4] ] décrit une ligne donnée, verticale, horizontale ou diagonale,
et plateau[f(i)] contient le contenu de cette ligne,
tandis que print ["%2d=%s" %(f(i),plateau[f(i)]) for i in xrange(SIZE)] visualise l'état de cette ligne.
Le test est effectué dans

Code :

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

 sum([plateau[f(i)] is True for i in xrange(SIZE)])==SIZE

.
Il sort True si toute la ligne testée est composée de valeurs True ou le contraire si le contraire.
J'avoue que je ne l'ai pas décortiqué dans ses détails ultimes, parce qu'il semble marcher. Mais il me semble bien tortueux relativement à l'objectif visé. Quand on pense qu'il faut faire ça 12 fois sur l'ensemble des lignes, et répéter l'opération à chaque coup d'un joueur.....

Au delà de cette première impression de complication, il y a le problème de savoir comment cette procédure doit être utilisée pour controler la progression du jeu.
Le programme commence par initialiser toutes les cases à true. Et après, que doit-il se passer quand un joueur joue ?


Ce que tu donnes n'est qu'un début de code. Comment envisages-tu la suite ? Par exemple, le problème posé par la nécessité d'user de deux symboles.?




Je pense que le problème reste ardu tel quel (examiner plusieurs lignes, et ce à chaque coup) tant qu'on ne fait que vouloir transposer en actions informatiques les actions que l'on fait avec un papier et un crayon.
Pour moi, il faut cesser de penser géométriquement le problème: il faut l'algébriser. Avec ce principe, après ça va tout seul. Enfin presque.




- Le sorted(), je connaissais, et ça aussi je l'avais oublié !

- Qu'appelles-tu ma deuxième solution ? Pour l'affichage ?

- «j'ai aussi condensé le code au delà de toute décence» Moi j'aime bien quand c'est concis, que ce soit lumineux ou cryptique

- j'ai cherché ce que pouvait bien dire «coder en dur». Comme je n'ai rien trouvé et pas lu de réponse là dessus, je continuerai à avoir les idées molles sur le codage en dur

[Guigui_]

Pour info, il y a un source d'un morpion sur la page Source Python

j'ai cherché ce que pouvait bien dire «coder en dur». Comme je n'ai rien trouvé et pas lu de réponse là dessus, je continuerai à avoir les idées molles sur le codage en dur

Cela signifie simplement mettre directement dans le code la valeur des constantes (ce qui fait qu'un changement de valeurs nécessite de reparcourir tout le code pour changer à chaque endroit ces valeurs).
Pour ne pas coder en dur, il faut que chaque constante soit écrite dans une variable (et bien entendu toujours utiliser la variable ensuite)

[shadowsam]

Merci Guigui_ pour le lien.

Dans l'idée comme tu as pu le voir, equyem, je n'ai pas cherché a faire un morpion complet. J'ai juste été intéressé par la partie algorithmique de la recherche des configurations gagnantes.

Je vais essayer de répondre a toutes les questions que tu as posé.

1. Premièrement en ce qui concerne le damier numéroté, il n'est justement pas numéroté, mon damier. Il est rempli de "True". Valeur qui symbolise juste une valeure jouée. Et avec un minimum de changement tu peux utiliser 'X' pour un joueur et 'O' pour l'autre par exemple.
2. Ton print est encore plus bourrin que le mien Mais ca marche, c'est sur. Je n'ai pas vraiment cherché à le réduire, celui-là.
3. En ce qui concerne le dico avec les fonctions de parcourt, y'a absolument aucune valeur ajouté a l'avoir fait. Il permet juste de grouper ces fonctions qui servent a la même chose dans un centenaire commun. Ca force un peu a structurer l'écriture du code, dans mon idée.
4. A propos de ca:
   

   Mais il me semble bien tortueux relativement à l'objectif visé.

   En fait l'idée est d'avoir des fonctions de parcourt qui sélectionnent les bonnes cases a tester. Après c'est sur que je me suis amusé a compressé un peu au max. Mais l'idée n'est pas si compliqué et c'est une des 2/3 seule possibilité pour avoir une résolution indépendante du paramètre de taille de plateau.
   La solution couramment utilisé pour les algorithmes de morpion consiste plutôt à parcourir un tableau a deux dimensions à partir d'une position fixe et de tester tout les voisins jusqu'à trouver un alignement qui corresponde à la configuration cherchée. Mais connaissant cette solution j'ai voulu en faire une autre.

[eyquem]

Merci Guigui pour la parfaite définition de "coder en dur". C'est bien ce à quoi je pensais en prétendant donner un exemple de cette différence en comparant li=[ (1,2),(1,3),(1,4),(2,2),(2,3),(2,4)] et li = [ (x,y) for x in (1,2) and y in (2,3,4) ] , exemple assez mauvais d'ailleurs.
Mais en lisant des choses tarabiscotées comme dans cette page
https://listes.irisa.fr/sympa/arc/ty...msg00188.html:
«Toujours sous l'influence de l'anglais, on parle de parties "codées en dur" pour des parties du logiciels difficilement lisibles ou modifiables qui ne sont accessible au mieux que sous forme d'instructions en assembleur après décompilation, par opposition à ce qui est accessible, lisible et modifiable aisément dans la « fourchette » des « ressources », sur Macintosh.»
je doutais que cette idée simple suffise à couvrir la notion.

«accessible au mieux sous forme d'instructions en assembleur après décompilation»je me demande ce que ça veut dire exactement. Mais c'est un autre sujet.

Notre sujet à nous est beaucoup plus sérieux: il s'agit de jouer au morpion !.
Merci pour la référence vers Sources Python. C'est ce que j'avais commencé à faire: chercher des sources sur le net.
Il y a une autre page encore sur developpez.com dans la rubrique 2D-3D-Jeux
http://fearyourself.developpez.com/t...l/sdl/morpion/

C'est étonnant le grand nombre de codes du jeu de morpion qui ont été faits. C'est un sujet bateau pour travaux pratiques dans l'enseignement.
Mais je suis encore plus surpris de constater dans les quelques codes que j'ai vus (une demie-douzaine) que non seulement la fonction d'évaluation qui teste le plateau pour y détecter un alignement complet procède toujours par examen des lignes puis des colonnes puis des diagonales (alors qu'il est possible de bâtir le test sur un principe radicalement différent) mais que l'algorithme n'est même pas optimisé pour n'examiner que la colonne et l'horizontale (et éventuellement une diagonale) concernées par le coup qui vient d'être joué. Toutes les lignes sont examinées. C'est faire du trampoline avec une armure. Mais bon je n'ai regardé tout ça que succintement pour le moment.

[tyrtamos]

Bonjour,

Un morpion qui pose quelques pb de codage, c'est celui qui s'exécute sur une "grille libre", car il peut s'étendre dans une direction quelconque sur un nombre plus ou moins grand de cases. Et c'est 5 pions qu'il faut aligner. Il faudrait un algorithme d'évaluation pas trop "bestial" pour explorer les configurations gagnantes à l'intérieur du rectangle qui contient tous les pions. Et, pire encore, pour identifier les meilleurs coups à jouer, y compris en sortant du rectangle...

Pour eyquem: quand tu dis:

alors qu'il est possible de bâtir le test sur un principe radicalement différent

à quelle solution penses-tu?

Tyrtamos

[eyquem]

Est-ce que

Code :

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

1
2
SIZE = 5
print ''.join([ '%2d'%x + (' ','\n\n')[(x+1)%5==0] for x in xrange(SIZE**2)])

te convient mieux ?
Moi je trouve moins bon:
- le (' ','\n\n')[(x+1)%5==0] n'est pas très immédiatement compréhensible
- ça fait travailler le programme inutilement à faire ce calcul pour chaque valeur du xrange(SIZE**2).
Tandis que '\n'.join(listes de taille SIZE) ,c'est de compréhension naturelle et le '\n' est mis comme une fleur au bon endroit.
C'est mon avis et je le partage




Pour moi, le damier c'est le support fixe. Avec des numéros, ça reste fixe, on ne change pas les numéros en cours de partie.
Tandis que plateau c'est le damier couvert de pions en cours de partie, le plateau évolue au cours de la partie, une valeur du plateau est un état de la partie.
Mais bon, c'est personnel.




«connaissant cette solution j'ai voulu en faire une autre.»
«J'ai juste été intéressé par la partie algorithmique de la recherche des configurations gagnantes.»
Moi itou. Mais....

- Je trouve ton code obscurci par une redondance.
Le coup de sum([True,True,False,True]), je ne connaissais pas. Mais ce n'est pas utile d'écrire plateau[f(i)] is True. Si plateau[f(i)] est True, plateau[f(i)] a déjà la valeur qui permet de le considérer comme True , non ?

- Il y a aussi une insuffisance. L'astuce de sum(), c'est qu'elle discrimine True et False. Mais l'ennui, c'est qu'elle ne compte que les True. Comment lui fais-tu compter les False, autrement dit ça ramène à ma question «Comment envisages-tu (...) par exemple, le problème posé par la nécessité d'user de deux symboles.?». Après tout, le morpion se joue à deux.....
La solution est count(). je viens de decouvrir que cette fonction ne marche pas seulement sur les chaines mais aussi les listes:

Code :

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

1
2
print [True,False,True,False,False,False].count(False)
print ['x','o','o','o','x','x','x','o','x'].count('x')

affichent 4 et 5
Je trouve aussi que count() a quelque chose de plus naturel que sum() relativement au problème.
Pourquoi ne pas écrire seulement

Code :

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

print [plateau[f(i)] for i in xrange(SIZE)].count(True)

?
La valeur du count() renseigne immédiatement et même plus que True/False sur l'état de la ligne testée.

- Par

Code :

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

1
2
for f in ALL_TESTS:
    test(f)

tu fais tester toutes les lignes (vert.,hor. et diags) les unes après les autres, définies de façon générale (c'est à dire pour SIZE quelconque) au travers de fonctions qui donnent chacune l'évolution de l'indice pour parcourir une ligne.
C'est bien d'arriver à fonctionnaliser les parcours des lignes, mais je trouve que ça a le même défaut que les autres solutions que j'ai vues: ça part d'une numérotation de damier triviale, alors qu'une injection de mathématique dans la numérotation permet non seulement de parcourir les lignes de façon plus élégante mais même de fonder l'algorithme général sur un principe différent.
Le jeu "Morpion 12x12 avec alignement de 5 pièces" bouscule les règles habituelles, je veux voir dans ce cas comment mon idée s'adapte.

[shadowsam]

En ce qui concerne le 'count', t'as absolument raison, c'est ce qu'il faut faire.

A propos du plateau[f(i)] is True ca partait juste de l'idée qu'a terme ca n'était pas True qui allait être sur le plateau mais autre chose, tout simplement. Genre 'O' et 'X' pour représenter chacun des joueurs.

C'est bien d'arriver à fonctionnaliser les parcours des lignes, mais je trouve que ça a le même défaut que les autres solutions que j'ai vues: ça part d'une numérotation de damier triviale, alors qu'une injection de mathématique dans la numérotation permet non seulement de parcourir les lignes de façon plus élégante mais même de fonder l'algorithme général sur un principe différent.

Là je ne comprends absolument pas ce que tu veux dire.

Le jeu "Morpion 12x12 avec alignement de 5 pièces" bouscule les règles habituelles, je veux voir dans ce cas comment mon idée s'adapte

Pour cela, c'est très simple mais avec une approche complètement différente, il faut utiliser une méthode qui est plus celle qui est utiliser lors d'un Puissance4. L'idée est de partir de la pièce jouée et de tester de proche-en-proche les alignements de pièces/jetons identiques.
La tu as une des solutions les plus rapide possible et tu peux faire ce que tu veux.

[eyquem]

Pour répondre à ta question, j'ai "algébrisé" le problème en numérotant les cases du casier avec des valeurs particulières (dictionnaire CB dans le code ci-après) qui permettent de traduire par une seule variable V toutes les positions relatives des cases cochées par 1 joueur donné dans le casier.
En clair, V traduit la plus ou moins grande occupation de chacune des lignes par un symbole donné,
et la variable V "s'allume" dés qu'un coup produit un état du plateau 'gagnant' = une ligne (horizontale, verticale ou diagonale) remplie d'un même caractère,
sans avoir à faire plusieurs tests sur toutes les lignes (ou 2 ou 3 si l'algorithme est optimisé, mais je n'en ai pas vu).

V ne représente pas un état du plateau, il n'y a pas de relation univoque entre une valeur de V et un état du plateau: il existe des répartitions différentes d'un symbole donné qui donnent la même valeur de V. La variable V traduit seulement les rapports des cases cochées avec un même symboles les unes par rapport aux autres.
S'il y a plusieurs états correspondants à une valeur précise de V, il n'y par contre une valeur unique de V correspondant à un état précis, évidemment.
Cette variable n'est pas formée de plusieurs valeurs, V est unidimensionnelle (on dit comme ça ?).

Mais elle suffit à la détection de l'objectif visé dans un jeu de morpion simple (sans aide), et ce sur les deux symboles en même temps.... Il suffit de mettre à jour cette variable après chaque coup et de la tester.



L'intérêt du principe est qu'il est facile d'étendre les possibilités en créant une fonction signature_plateau() dont l'argument est un ensemble ou une liste de cases cochées avec un même symbole pour pouvoir faire une aide comme dans le programme très complet de tyrtamos.
Cette fonction signature_plateau() n'est pas nécessaire dans un programme de morpion simple. Appliquée à un état de plateau, elle renvoie simplement la valeur de V correspondant à cet état. Mais à moins d'avoir besoin de signature_plateau() pour autre chose il vaut mieux suivre l'évolution du plateau vers l'objectif de ligne pleine par V, ça évite la répétition de calculs qui seraient faits à chaque coups avec la fonction signature_plateau().


tyrtamos,
c'est un intéressant mais vaste programme que tu poses !
Je pense que mon principe de codage des cases fournit l'algorithme d'évaluation «pas trop bestial» que tu souhaites et qu'il peut encaisser l'extension des conditions aux limites que tu décris. Grâce aux possibilités intrinsèques de Python, et à condition de considérer que le casier n'est pas potentiellement infini: intellectuellement, cette éventualité est fun, mais pratiquement ça n'a aucun intérêt d'autoriser quelqu'un à prendre son vélo pour aller écrire une croix à 600 mètres.....arf arf arf

Par contre, même sans casier infini, l'extension du domaine de la lutte par morpion étend les problèmes de l'algorithme réglant la stratégie du jeu et je n'ai pas tellement envie de me lancer là-dedans. Le morpion à "5 pions alignés dans une grille ouverte dans toutes les directions" me semble nécessiter une adaptation délicate de mon algorithme. Y a qu'à voir le code du "Morpion 12x12 avec alignement de 5 pièces" dans la partie 2D-3D-Jeux de ce site, pour voir que c'est assez coton. Mais c'est pourtant plus intéressant qu'un morpion de maternelle à grille 3 X 3.



Je fais la coquette en ne donnant pas tout de suite le principe de mon algorithme. Ainsi ceux qui aiment chercher pourront continuer de s'amuser et me remercieront Toute l'astuce réside évidemment dans le codage spécial des cases contenu dans CB puisqu'il transcrit l'information géométrique qui n'est perceptible que visuellement en information numérique manipulable par un ordinateur.
Il y a aussi que je n'ai pas fini d'étendre mon code à des tailles de casier supérieures à 3. La création du dictionnaire CB correspondant à une SIZE quelconque ne doit pas être très difficile mais je ne l'ai pas encore écrite.
Place à la devinette.

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
nom = {0:'Edgar',1:'Janine'}
SIZE = 3
# Dictionnaire de numerotation du casier utilisee par le programme
# Les cles du dictionnaire (dans XY) sont les coordonnees utilises par les joueurs pour designer les cases
# pour SIZE==3 : XY = ['11','12','13','21','22','23','31','32','33']
XY = [ str(u)+str(v) for u in xrange(1,SIZE+1) for v in xrange(1,SIZE+1)]
case = dict(zip(XY,range(SIZE**2)))
# Initialisation d'un plateau vide
tab = (SIZE**2)*['-']
print '\n'.join([ SIZE*'%2s ' % tuple(tab[i:i+SIZE]) for i in xrange(0,SIZE**2,SIZE)])
# Dictionnaire modelisant les cases 
CB = dict(zip(XY,(---(liste de valeurs)---)))
# Liste qui va recenser les cases cochees
cases_cochees = []
 
---(instruction calculant m a partir de SIZE)---
---(initialisation de V)---     
j = 0
while XY:
    e = raw_input('\n'+nom[j]+'('+str(j+1)+') , cochez votre case : ')
    if e in XY:
        tab[case[e]] = str(j+1)
        print '\n'.join([ SIZE*'%2s ' % tuple(tab[i:i+SIZE]) for i in xrange(0,SIZE**2,SIZE)])
        ---(instruction mettant a jour V a partir de j,m,CB[e])---
        if ---(test sur V)---:
            print '\n***  ',nom[j].upper(),', vous venez de gagner ! ***\n'
            break
        XY.remove(e)
        cases_cochees.append(e)
        j = (j+1)%2
    elif e in cases_cochees:
        print 'La case que vous avez indiquee est deja cochee. Recommencez.',
    else:
        print 'Le repere de case que vous avez tape est aberrant. Recommencez',
 
if not XY:
    print "\nPersonne n'a gagne: vous etes deux morpions !"
elif len(XY) in (1,2):
    print "Mais de justesse, c'etait votre dernier coup ! Vous n'etes pas tres bon."

case et tab servent uniquement pour afficher le plateau après un coup.
CB sert a mettre a jour V

PS: si vous connaissez d'autres algorithmes différents de ceux habituels (méthode bestiale de test sur horizontales, verticales et diagonales) ça m'intéresse de les connaître.

[eyquem]

Là je ne comprends absolument pas ce que tu veux dire.

alors qu'une injection de mathématique dans la numérotation permet non seulement de parcourir les lignes de façon plus élégante mais même de fonder l'algorithme général sur un principe différent.

Avec mon précédent message, ça doit être plus clair

ça a le même défaut que les autres solutions que j'ai vues: ça part d'une numérotation de damier triviale

Je veux dire que le fait que la numérotation soit triviale condamne à faire un test des lignes horizontales, puis des colonnes puis des diagonales. Toutes tes lignes sont définies par fonction plutôt que codées en dur, sur ce point c'est bon parce que ça permet d'utiliser le programme pour des damiers de dimension quelconque, mais sur le point du test, ça reste la même chose: tes lignes sont testées les unes après les autres.
Mon algorithme règle apparemment ces deux problèmes d'un coup. En fait je retrouve la nécessité de fonctionnaliser dans la définition de ma liste CB.


À propos de numérotation, tu décris les lignes en faisant varier i dans xrange(SIZE) et:

- pour la diagonale \ par la fonction lambda i:i+i*SIZE
Mais ce n'est rien d'autre que i*(SIZE+1)
c'est à dire 0 puis 0 + (SIZE+1) puis 0 + (SIZE+1) + (SIZE+1) etc
donc [0: :(SIZE+1)]

- pour la diagonale / par la fonction lambda i: (SIZE)*(SIZE-(i+1))+(i+1)-1
qui se réécrit en (SIZE**2 - SIZE) - (SIZE-1)*i
ce qui signifie des valeurs données par [ (SIZE**2 - SIZE):0:(SIZE-1)]
Et comme (SIZE**2 - SIZE) est -SIZE, on aboutit à [ - SIZE: 0 :-SIZE+1]- idem pour les verticales et diagonales

Je veux dire que les lignes peuvent être directement décrites par du slicing de liste au lieu de fonctions avec i variant dans xrange(SIZE) et que je me suis amusé à simplifier ton code pour montrer que

Code :

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

sum([plateau[f(i)] is True for i in xrange(SIZE)])

peut se remplacer par une expression beaucoup plus simple.

J'ai simplifié une fois à ma façon:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
SIZE = 5
plateau = ['-','x','o','o','x','x','x','o','-','-','x','o','o','x','-','-','x','-','-','o','o','x','o','x','-']
 
ch = "Numerotation du damier:\n"
ch += '\n'.join([ SIZE*'%3d ' % tuple(xrange(i,i+SIZE)) for i in xrange(0,SIZE**2,SIZE)])
ch += "\n\nPlateau:\n"
ch += '\n\n'.join([ SIZE*'%3s ' % tuple(plateau[i:i+SIZE]) for i in xrange(0,SIZE**2,SIZE)])
print ch
 
 
def ecr(ln,c):
    print ligne, ligne.count('x'),c,'\n'
 
 
print "\nDenombrements de 'x' dans les lignes"
for ligne in [ plateau[0::SIZE+1], plateau[-SIZE:0:-SIZE+1] ]:
    ecr(ligne,'diagonale')
 
for ligne in [ plateau[i::SIZE] for i in xrange(SIZE) ] :
    ecr(ligne,'verticale')
 
for ligne in [ plateau[i:i+SIZE] for i in xrange(0,SIZE**2,SIZE) ]:
    ecr(ligne,'horizontale')

Et une deuxième fois en devant passer par une liste de doublets (li) pour conserver la présentation d'affichage que tu as adoptée.

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
from operator import itemgetter
SIZE = 5
plateau = ['-','x','o','o','x','x','x','o','-','-','x','o','o','x','-','-','x','-','-','o','o','x','o','x','-']
li = zip(xrange(SIZE**2),plateau)
print 'li =',li
print
 
ch = "Numerotation du damier:\n"
ch += '\n'.join([ SIZE*'%3d ' % tuple(xrange(i,i+SIZE)) for i in xrange(0,SIZE**2,SIZE)])
ch += "\n\nPlateau:\n"
ch += '\n\n'.join([ SIZE*'%3s ' % tuple(plateau[i:i+SIZE]) for i in xrange(0,SIZE**2,SIZE)])
print ch
 
ALL_LIGNES = [ li[0::SIZE+1], li[-SIZE:0:-SIZE+1] ] # diagonale \  et  diagonale /
ALL_LIGNES.extend( [ li[i::SIZE] for i in xrange(SIZE) ] ) # verticales
ALL_LIGNES.extend( [ li[i:i+SIZE] for i in xrange(0,SIZE**2,SIZE) ] ) # horizontales
 
print "\nDenombrements de 'x' dans les lignes"
for ligne in ALL_LIGNES:
    print ["%2d = %s"%u for u in ligne], 
    print '=', 
    print map(itemgetter(1),ligne).count('x')

Merci pour l'indication sur Puissance 4. Mais je regarderai plus tard car je n'ai pas envie de me lancer dans le codage d'un morpion évolué. Le forum est bourré de messages avec des explications super intéressantes et je préfère les étudier.

[tyrtamos]

Bonjour,

J'ai une proposition pour le calcul des coups gagnants.

1- paramétrage de la grille

g = la grille est représentée par une liste de listes comportant soit l'un des 2 pions ('X' ou 'O'), soit un espace (' ').

Mais pour faciliter les calculs, j'impose que la partie "utile" de la grille (celle où on peut mettre les pions), soit entourée d'une rangée vide. Par exemple pour une grille 12x12, la partie utile ira de la ligne 1 à 12 et de la colonne 1 à 12, mais il y aura la ligne 0 et 13 qui seront vides, ainsi que la colonne 0 et 13. Un avantage supplémentaire de cette config est que le calcul sera valable pour une grille "libre" puisqu'on n'aura pas besoin de tester le bord de la grille.

t = taille de la grille (12 pour une grille 12x12)

n = nombre de pions à aligner pour gagner (ex: 5)

pions = 'XO'

2- Initialisation: fabrication de la grille vide

En fonction de ce qui précède, voilà le code d'initialisation pour créer la grille vide. Ici, c'est une grille 12x12 dans laquelle il faut aligner 5 pions:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
 
g = []
t = 12
n = 5
pions = "XO"
 
t += 1
for i in xrange(0,t+1):
    g.append([])
    for j in xrange(0,t+1):
        g[-1].append(' ')

3- fonction d'affichage

Puisqu'on a besoin d'une fonction d'affichage, allons-y:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
def affichegrille():
    global g, t
 
    ch = '   '
    for j in xrange(1, t):
        ch += '%2d ' % j
    print ch
 
    for i in xrange(1, t):
        ch = '%2d ' % i
        for j in xrange(1, t):
            if g[i][j] == ' ':
                ch += ' _ '
            else:
                ch += ' ' + g[i][j] + ' '
        print ch

4- Calcul du test pour savoir si un coup est gagnant

Pour une case vide donnée (ligne i, colonne j), et un pion 'X' (par exemple), on va tester dans les 4 directions en s'éloignant de i,j d'une case à la fois et en s'arrêtant dès qu'on ne trouve plus le pion 'X'. On compte le nombre de pions 'X' dans chaque direction, ce qui permet de savoir si le coup est gagnant.

Voilà le codage du test 'coupgagnant'. Il est en fait à 3 étages: coupgagnant() appelle coupgagnant2() qui appelle coupgagnant3():

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
 
##############################################################################
def coupgagnant3(i, j, pion, di, dj):
    global g, t, n
    c = 0
    while True:
        i += di
        j += dj
        if g[i][j] == pion:
            c += 1
        else:
            break
    return c
 
##############################################################################
def coupgagnant2(i, j, pion, di, dj):
    global g, t, n
    if  coupgagnant3(i, j, pion, di, dj) + \
        coupgagnant3(i, j, pion, di*-1, dj*-1) >= n-1:
        return True
    return False
 
##############################################################################
def coupgagnant(i, j, pion):
    global g, t, n
    if  coupgagnant2(i, j, pion, 1, -1) or \
        coupgagnant2(i, j, pion, 0, -1) or \
        coupgagnant2(i, j, pion, -1, -1) or \
        coupgagnant2(i, j, pion, 1, 0):
        return True
    return False

5- test

Pour tester, j'ai créé un code qui remplit de façon aléatoire la grille initialement vide avec des pions des 2 joueurs.

Avec cette grille remplie à 50%, je teste toutes les cases vides pour trouver tous les coups gagnants pour chacun des joueurs:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 
    import time
    pion = pions[0]
    print 'pion:', pion
    tps = time.clock()
    for i in xrange(1, t):
        for j in xrange(1, t):
            if g[i][j] == ' ' and coupgagnant(i, j, pion):
                print 'position: (', i, ',' ,j, ') coup gagnant !!!'
    print u'temps passé:', '%.3f' % (time.clock() - tps)
    print
 
    pion = pions[1]
    print 'pion:', pion
    for i in xrange(1, t):
        for j in xrange(1, t):
            if g[i][j] == ' ' and coupgagnant(i, j, pion):
                print 'position: (', i, ',' ,j, ') coup gagnant !!!'
    print u'temps passé:', '%.3f' % (time.clock() - tps)
    print

Voilà l'un des résultats possibles:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 
    1  2  3  4  5  6  7  8  9 10 11 12 
 1  O  _  _  _  X  _  X  _  _  X  _  _ 
 2  _  X  _  _  _  X  _  _  O  _  _  X 
 3  _  O  O  X  _  _  _  _  _  X  _  _ 
 4  _  _  _  _  _  X  O  _  _  X  _  X 
 5  _  _  X  X  _  _  _  _  _  _  O  _ 
 6  _  X  _  X  O  _  _  O  _  O  _  X 
 7  _  _  _  O  _  X  _  X  _  _  X  _ 
 8  _  O  O  _  _  _  X  X  _  O  _  _ 
 9  X  _  _  O  _  X  _  _  O  X  _  _ 
10  _  _  X  X  X  _  _  O  _  _  O  O 
11  _  O  X  _  _  _  _  X  _  _  O  _ 
12  _  X  _  X  _  X  _  O  _  _  _  _ 
 
pion: X
position: ( 6 , 9 ) coup gagnant !!!
position: ( 11 , 4 ) coup gagnant !!!
temps passé: 0.022
 
pion: O
position: ( 5 , 6 ) coup gagnant !!!
temps passé: 0.012

Dans cet exemple, le joueur qui a le pion 'X' a 2 coups gagnants, et le joueur qui a le pion 'O' en a 1.

Dans tous les cas, le balayage total de la grille pour un joueur donné se fait en moins de 1/10 de seconde, et souvent moins.

En fait, comme les tests s'arrêtent vite, moins il y a de coups gagnants, plus c'est rapide.

Cela veut dire aussi qu'en début de jeu, la plus grande quantité de cases vides à tester sera compensée en temps par le fait que les tests seront beaucoup plus rapides. A l'extrême, je l'ai aussi vérifié, une grille totalement vide est testée en 2/1000 de secondes pour chaque pion, malgré les 144 cases à tester!

L'avantage de ce calcul, effectivement plus complexe que la méthode bestiale, c'est que ça marche aussi pour une grille "libre" puisqu'on n'utilise pas le test de dépassement des bords.

Par contre, pour recommander les meilleurs coups et pire encore, pour recommander des stratégies gagnantes sur plusieurs coups, il faudra bosser encore un peu...

Tyrtamos

EDIT: Le test coupgagnant() peut encore se simplifier de la façon suivante, cette fois-ci en 2 étages. Il donne, bien sûr, le même résultat:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
def coupgagnant2(i, j, pion, di, dj):
    global g, t, n
    c = 0
    while True:
        i += di
        j += dj
        if g[i][j] == pion:
            c += 1
        else:
            break
    return c
 
def coupgagnant(i, j, pion):
    global g, t, n
    dir = [[1, -1], [0, -1], [-1, -1], [1, 0]]
    n1 = n-1
    for di, dj in dir:
        if (coupgagnant2(i, j, pion, di, dj) + coupgagnant2(i, j, pion, -di, -dj) >= n1):
            return True
    return False

[eyquem]

Amélioré et épuré

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
SIZE,jambees = 5,xrange(0,SIZE**2,SIZE)
plateau = ['-','x','o','o','x','x','x','o','-','-','x','o',\
           'o','x','-','-','x','-','-','o','o','x','o','x','-']
 
ch = "* Numérotation du damier:\n\n"
ch += '\n'.join([ SIZE*'%3d ' % tuple(xrange(i,i+SIZE)) for i in jambees ])
ch += "\n\n\n* Plateau:\n\n"
ch += '\n\n'.join([ SIZE*'%3s ' % tuple(plateau[i:i+SIZE]) for i in jambees ])
print ch
 
def denombr(ln,c):
        print 'dans '+c.ljust(15),ln,"    ->    %d 'x'    %d 'o'    %d vides"\
              % (ln.count('x'),ln.count('o'),ln.count('-'))
 
print "\n\n* Dénombrements de 'x' et 'o' dans les lignes"
print;denombr( plateau[0::SIZE+1]       ,'diagonale \\' )
denombr( plateau[-SIZE:0:-SIZE+1] ,'diagonale /'  )
print;[ denombr( plateau[i::SIZE] ,'verticale '+str(i)) for i in xrange(SIZE)]
print;[ denombr( plateau[i:i+SIZE],'horizontale '+str(i)) for i in jambees]

[eyquem]

Propositions pour tendre vers plus de concision (c'est une façon de parler) pour l'affichage

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
t,n,pions = 12,5,"XO"
 
t += 1
g = [(t+1)*[' '] for i in xrange(t+1)]
 
print 't =',t,'len de g =',len(g)
 
def affichegrille():
    global g, t
    print  '   ' + (t-1)*'%2d ' % tuple(xrange(1, t))
    for i in xrange(1, t):
        ch = '%2d ' % i
        ch += (t-1)*' %s ' % tuple(map(lambda x: x.replace(' ','_'),g[i][1:t]))
        print ch
 
def affichegrille2():
    global g, t
    print  '   ' + (t-1)*'%2d ' % tuple(xrange(1, t))
    for i in xrange(1, t):
        ch = ('%2d '+(t-1)*' %s ') % tuple([i]+map(lambda x: x.replace(' ','_'),g[i][1:t]))
        print ch
 
def affichegrille3():
    global g, t
    print  '   ' + (t-1)*'%2d ' % tuple(xrange(1, t))
    print '\n'.join(('%2d '+(t-1)*' %s ') % tuple([i]+map(lambda x: x.replace(' ','_'),g[i][1:t])) for i in xrange(1, t)) 
 
affichegrille()
print
affichegrille2()
print
affichegrille3()

Remarques:
- je trouve un peu aberrant d'initialiser g en le remplissant de ' '
puis de l'afficher en remplaçant les ' ' par des '_', ce qui nécessite un test.
- inutile d'ecrire global g, t dans une fonction quand leur valeur n'est pas changee dans la fonction.



Ton travail sur un morpion complexe est super intéressant, tyrtamos, mais je n'ai pas le temps de rentrer dans cette voie pour le moment. Je me mets en stand-by sur le sujet.