Bonjour, 

Le but ici, n'est pas de crée un puissance 4 en entier, avec des amis nous nous sommes réparti différentes tâches...

ainsi mon rôle est de codé les conditions de victoire; horizontalement, verticalement et en diagonale.

Mes amis n'ayant pas encore finis la partie qui est censée être avant la mienne, j'aimerais que vous me disiez , si ceci tournera correctement, si non: pourquoi ?

et si vous avez des conseils, parce que, nous nous sommes renseigné et les 250 à 300 lignes de codes qui nous attendent nous font un peu peur :/

bref, voilà mon bout de code:

def partiegagnee(i,j):
    ## horizontalement
    global mat
    gagnehoriz=false
    jeton=mat[i][j]
    for i in range(4):
        n=0
        while n<4 and mat[i][k+n]==jeton:
            n+=1

        if n>=4:
            gagnehoriz=true

    if(gagnehoriz):
        print("Partie finie, les",jeton," gagnent horizontalement")
    return(gagnehoriz)

    ## verticalement
    global mat
    gagnevertic=false
    jeton=mat[i][j]
    for i in range(4):
        n=0
        while n<4 and mat[k+n][j]==jeton:
            n+=1

        if n>=4:
            gagnevertic=true

    if(gagnevertic):
        print("Partie finie, les",jeton," gagnent verticalement")
    return(gagnevertic)

    ## en diagonale
    global mat
    gagnediago=false
    jeton=mat[i][j]
    for i in range(4):
        n=0
        while n<4 and mat[k+n][k+n]==jeton:
            n+=1

        if n>=4:
            gagnediago=true

    if(gagnediago):
        print("Partie finie, les",jeton," gagnent par la diagonale")
    return(gagnediago)

c'est presque 3 fois la même chose, je sais que la première concernant la victoire horizontale marche, mais les autres sont-elles correcte ?

-
Edité par oeol 31 janvier 2013 à 19:57:42

Tu as l'air de pas mal te servir des variables globales (e.g. k, mat), ce qui est generalement deconseille.

-
Edité par stackOverflow 1 février 2013 à 9:41:31

pourquoi cela est-il déconseillé, quels en sont les risques ? et comment faire autrement ?

Voici un article qui explique bien pourquoi l'usage de variables globales est deconseille. Y figurent aussi les maniere de l'eviter.

-
Edité par stackOverflow 31 janvier 2013 à 21:26:42

Je pense que le PO a des problèmes plus urgents à régler que l'usage abusif du mot-clé global sur ce coup : son code n'a absolument aucune chance de compiler, d'une part, et de fonctionner d'autre part.

Salut,

Je suis moi-même sur un projet de Puissance 4 en Python avec un ami (kindermoumoute si tu nous lis), et notre fonction de détection de victoire fonctionne à merveille.

Seulement, nous ne sommes pas partis sur une matrice à deux dimensions, mais sur un tableau à une seule dimension (indicé de 0 à 41, puisqu'une grille de Puissance 4 compte 42 cases), et nous avons utilisé de nombreuses propriétés mathématiques (à grands coups de modulos et de divisions euclidiennes) qui nous ont permis de détecter les bordures de la grille, et les pions alignés.

Je vais pas te donner directement notre code, ça ne serait pas constructif, mais je peux te donner des indications sur la manière de t'y prendre avec ça.

Ce code n'explore qu'un partie des solutions, pas toutes (il suppose que le jeton donné est à l'extrémité d'une série de 4, s'il est au milieu, ça ne marche pas). Je pense qu'il serait plus simple de faire une fonction qui teste toutes les possibilités.

On peut le faire avec des boucles (horizontal, vertical, diagonales (dans les 2 sens)), ça marche très bien mais c'est un peu de chipot pour "tomber juste" avec les diagonales.

Sinon, il y a une autre option, avec des masques. (c'est moins délicat sur les indices si on hard-code les solutions)

J'ai déjà fait ça (c'était en C et relativement optimisé, on représentait les jeux par 2 entiers 64bits), j'ai utilisé un système de masque pour détecter les victoires : j'avais un tableau qui reprenait chacun des 69 alignements gagnants. Pour tester si la partie était gagnée par un joueur, il fallait, pour chaque masque, faire un & entre le masque et le tableau. Si il restait 4 bits, alors c'était gagné.

... Tout ça pour dire que le nombre de "solutions" est assez restreint et qu'il serait peut-être plus simple de les hard-coder.

Par ex

solutions = [((0, 0), (0, 1), (0, 2), (0, 3)),
              ((1, 0), (1, 1), (1, 2), (1, 3)),
               # ...
               ]

Chaque élément de la liste contient les coordonnées de 4 pions.                    

-
Edité par Anonyme 1 février 2013 à 23:08:33

On peut aussi se faire plaisir avec le haut niveau de Python, et écrire une fonction (génératrice d'ordre supérieur…) qui génère les 4 lignes à tester à partir de la position du dernier pion joué.

Ça donne un code pas forcément trivial à comprendre du premier coup pour un débutant, mais plutôt élégant, somme toute :

width, height = 7, 6
grid = [[0] * height for _ in range(width)]

def possible_lines(x, y):
    yield (0, y, (lambda i, j: i+1, j))
    yield (x, 0, (lambda i, j: i, j+1))
    o = min(x, y)
    yield (x-o, y-o, (lambda i, j: i+1, j+1))
    o = min(x, height - y - 1)
    yield (x-o, y+o, (lambda i, j: i+1, j-1))


def won(x, y):
    color = grid[x][y]
    for x0, y0, move in possible_lines(x, y):
        i, j, n = x0, y0, 0
        while 0 <= i < width and 0 <= j < height:
            n = (0 if grid[i][j] != color else n + 1)
            if n == 4:
                return True
            i, j = move(i, j)
    return False

La fonction possible_lines génère les 4 lignes à tester, sous la forme d'un tuple contenant la position de départ de la ligne et une fonction qui permet de passer à la case suivante. La fonction won teste ensuite ces 4 lignes, et uniquement ces 4 lignes, sans avoir besoin de dupliquer le code et sans risquer de dépasser les bornes du tableau.

Elle s'arrête dès qu'elle trouve une suite de 4 pions identiques.

-
Edité par nohar 2 février 2013 à 7:17:49

Actuellement en terminal, je me suis aussi lancé dans un projet de puissance 4.
Ma solution un peu simplet consiste en un tableau: une liste contenant 6 listes (6 lignes) qui elles contiennent 7 éléments (7 colonnes) qui accueillent les jetons joués.

Pour savoir si il y a puissance 4, j'ai un total de 13 conditions différentes: A l'aide d'un schéma on se rend compte qu'il y a 13 façon de faire puissance 4.

Voilà, pour l'instant tout baigne. La vraie galère c'est pour la partie: Fournir une bonne stratégie à l'ordinateur

Mais bon, cette dernière partie découle assez de la partie 'un puissance 4 a-t-il été réalisé?'.

En espérant avoir été utile: R.G.

De notre côté, l'IA fonctionne plutôt bêtement.
"Pour chaque position que je suis susceptible de jouer, quel est le nombre de pions qui seront alors alignés ? Je joue là où je maximise la taille de l'alignement."

On aimerait faire un truc un peu plus évolué que ça, mais ça sera pas évident. Contacter le créateur de Deep Blue, peut-être… 

Richou D. Degenne a écrit:

On aimerait faire un truc un peu plus évolué que ça, mais ça sera pas évident. Contacter le créateur de Deep Blue, peut-être…

Pas besoin d'aller jusque là. Il existe des algorithmes très simples et suffisamment efficaces pour ça, comme le Minimax ou ses optimisations.

Il te permet même de régler le niveau de difficulté de l'IA en jouant sur la profondeur maximale du parcours.

-
Edité par nohar 12 février 2013 à 8:53:53

Jamais entendu parler, mais je crois que je vais me renseigner dessus. Merci pour le tuyau !

Bon, je me permets de double-poster…

J'ai jeté un œil à cet algorithme du Minimax, mais je vois pas comment l'appliquer à un Puissance 4…

Pour chaque coup que l'IA peut jouer à un tour donné :

• Évaluer si en jouant ce coup elle peut gagner :
  • si oui, on associe à ce coup le score 3
  • si ce coup la fait perdre, on lui associe le score 1
  • si ce coup aboutit sur la fin de la partie avec un match nul (ou si on a atteint la limite de récursion), il vaut 2
  • sinon, on suppose que le joueur en face va aussi appliquer la stratégie du Minimax et on simule sa décision (c'est le même algorithme, mais inversé) en évaluant chacun des coups qu'il pourra jouer :
    • s'il gagne en un coup, on retourne 1
    • si match nul (ou limite de récursion atteinte), on retourne 2
    • s'il perd on retourne 3
    • sinon, la partie ne serait pas terminée, donc on réapplique le minimax récursivement sur chacun des nouveaux coups jouables par l'IA...
    • L'adversaire décidera de jouer le coup qui va MINIMISER le score (1=il gagne, il veut gagner).

On se retrouve donc avec un score associé à chaque coup que l'IA peut jouer pour ce tour, le coup que l'IA décide de jouer sera donc l'un de ceux pour lequel le score (1, 2 ou 3) est MAXIMAL.

Après, tu peux choisir le niveau de difficulté de l'IA en limitant la profondeur des appels récursifs : plus tu prévois de coups à l'avance, plus l'IA sera forte. Tu peux aussi gagner (BEAUCOUP) en performances en n'évaluant pas TOUS les coups jouables à chaque fois, mais en choisissant directement un coup si tu tombes sur un 3 quand c'est l'IA qui joue, ou un 1 quand c'est l'adversaire qui joue (on appelle ça le alpha-bêta). Pour éviter que l'IA soit ennuyeuse et prévisible, dans ce cas, on évalue les coups jouables dans un ordre aléatoire.

-
Edité par nohar 22 février 2013 à 9:52:43

Ok, je vois à peu près le genre… Pour la fonction d'évaluation, pourquoi ne pas prendre plutôt quelque chose comme la somme de tous les alignements causés par le jeton posé ? Ça me paraît plus logique, non ?

Parce que si tu prends ça comme fonction d'évaluation, ce n'est plus le Minimax ?

Edit : Pour faire une réponse plus constructive : le Minimax a l'avantage d'être un algorithme générique. Il n'a pas besoin de savoir comment fonctionne ton jeu, il suffit de lui fournir une fonction qui lui dit si à un moment donné, la partie est terminée et qui a gagné, ainsi qu'un moyen d'annuler les coups qu'il simule, et il peut faire ses calculs tout seul dans son coin. C'est donc un algo d'IA que tu peux quasiment "brancher" sur n'importe quel jeu de ce genre (puissance 4, morpion, othello, dames, échecs, etc.) sans avoir à le modifier.

L'avantage, par rapport à une solution que tu baserais sur une heuristique (l'alignement), c'est qu'il gère toutes les stratégies possibles. Par exemple, il peut gagner en complétant une ligne par le milieu, alors que c'est tout de suite beaucoup plus délicat si tu commences à évaluer les alignements.

L'inconvénient, c'est sa complexité en temps : si tu calcules toutes les parties possibles de façon naïve, sans limiter les récursions, et sans élaguer (sans retourner directement le prix d'un coup lorsque tu tombes sur une victoire ou un échec, en mode alpha-bêta), ça peut prendre pas mal de temps, voire faire exploser la pile d'appel dans le cas de jeux complexes comme les échecs.

C'est ce que l'on appelle un algorithme "glouton". C'est une approche simple et générique qui évalue virtuellement toutes les possibilités quand tu le laisses faire.

-
Edité par nohar 22 février 2013 à 15:11:53

Alors, je vais peut-être avoir l'air totalement HS, mais je voudrais apporter ma solution, un peu naïve mais qui fonctionne correctement.

J'ai écrit un petit Tic-Tac-Toe en C++, et j'y ai implémenté la première fonction qui m'est venue à l'esprit. Elle devrait être parfaitement applicable en P4, elle risque juste d'être plus lourde. Je ne vais pas pousser le HS jusqu'à poster une fonction en C++, je vais juste vous expliquer en gros le fonctionnement :

• Je crée une liste de listes, destinée à contenir chaque séquence à tester (lignes, colonnes, diagonales)
• Je parcours ma grille dans les deux sens pour ajouter à ma liste de listes chaque ligne et chaque colonne, puis j'y ajoute les diagonales, avec une boucle à 2 compteurs par exemple (en Puissance 4, éviter peut-être les colonnes ayant une longueur < 4)
• Je parcours cette liste de listes en vérifiant dans chaque séquence si on trouve la séquence recherchée (ici 4 pièces de même couleur)

Ça marche à merveille pour mon TicTacToe, et ça devrait marcher aussi ici. Mais on aura forcément plus d'itérations à faire qu'avec une grille de 3*3. L'avantage, c'est que j'ai rien trouvé d'autre d'aussi clair et direct (selon moi).

À l'échelle d'un Puissance 4, c'est un algorithme hyper-glouton, dans la mesure où, au moment où un pion est posé, il suffit de tester les alignements autour du pion qui vient d'être posé. Un jeton joué à gauche va pas terminer une verticale à droite de la grille, de toute évidence.

EDIT

Après calcul, il y a 69 alignements possibles. Ça te fait une liste de 69 listes de 4 entiers, soit 276 entiers en mémoire, alors qu'il n'y en a que 21 qui sont susceptibles de t'intéresser.

Rendement mémoire ≈ 7,6 %

Pas terrible…

-
Edité par Richou D. Degenne 23 février 2013 à 17:54:14

Premature optimization is the root of all evil. (Donald E. Knuth)

C'est vrai, mais encore faut-il définir la notion de "Pré-mature"… 

Elle est évidente : ça ne sert à rien de penser à optimiser tant que tu n'as pas quelque chose de valide sur le plan fonctionnel, et que tu n'as pas fait de mesures pour identifier quelle partie de ton code est un goulot d'étranglement.

Quand bien même, 276 entiers en mémoire, ça représente 1 ou 2Ko en RAM à tout péter suivant ton architecture (et encore, en C, ces entiers tiennent largement sur des unsigned char, donc ce serait plutôt 276 octets), soit que d'alle à côté de ce que va prendre l'interface graphique.

-
Edité par nohar 24 février 2013 à 14:31:49

Bon, j'ai écrit ça, mais ça n'a pas l'air de fonctionner…

def ia(grille,profondeur,joueur):
        valMax = -10000 # Initialisation du max
        val = -10000
        coup = 0
        for i in range(0,6): # Pour chaque colonne
                position = placer(grille,i,joueur) # On place virtuellement un pion
                print("Profondeur :",profondeur,"| Colonne :",i)
                if position != -1: # Si le pion placé est valide
                        
                        if victoire(grille,position) == joueur: # Si le pion accorde la victoire à l'IA
                                grille[position] = 0 # On retire le pion virtuellement joué
                                return i # Jouer ce coup-là
                        
                        if profondeur <= 0: # Si la profondeur max n'est pas atteinte
                                val = valeur(grille,position) # On évalue l'avantage du coup
                        else:
                                val = -1 * ia(grille,profondeur-1,(joueur%2)+1) # On évalue l'avantage maximal que l'aderversaire peut obtenir par récursivité
                        grille[position] = 0 # On retire le pion virtuellement joué
                        print("Valeur[",i,"] = ",val)
                        if val >= valMax: # Si le coup testé est meilleur
                                valMax = val # Mise à jour de l'avantage max
                                coup = i # Mise à jour du coup à jouer
        return coup # Jouer le meilleur coup

À noter que valeur(grille,position) est la fonction d'évaluation.

(C'est un extrait d'un code de test, je n'avais pas encore implémenté la notation objet…