IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Langage Perl Discussion :

Programmation autours d'un jeu [KHALOU]


Sujet :

Langage Perl

Vue hybride

Message précédent Message précédent   Message suivant Message suivant
  1. #1
    Candidat au Club
    Profil pro
    Inscrit en
    Février 2013
    Messages
    3
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Février 2013
    Messages : 3
    Par défaut Programmation autours d'un jeu [KHALOU]
    Bonjour,
    Je recherche un programmeur qui pourrait m’aider a faire tourner un ptit programme au sujet d’un jeu.
    Ce jeu se nomme KHALOU et est disponible gratuitement sur Itunes pour Iphone et Ipad.
    https://itunes.apple.com/fr/app/khalou/id589404904?mt=8
    Je vous laisse en lire les règles. Voici mes requêtes :
    Il existe pour ce jeu 2^16 = 65536 positions différentes.
    Les jetons de ce jeu peuvent se retourner de différentes façons. Je cherche un petit script a faire tourner qui pourrait me donner :
    *Pour chacune des positions : le nombre de retournement minimum pour rendre le damier du jeu tout blanc (le but du jeu). Cela est toujours faisable en 5 retournements minimum (démontré via théorie des groupes).
    *Trouver ainsi le nombre totale de positions résolvables en : 1, 2, 3, 4 et 5 retournements minimum.

    Qui pourrait m’aider pour cette programmation ?
    ****************************

    Regles : Le Khalou est un jeu de plateau 4X4 comportant des jetons bifaces (noires et blanches).

    Le principe du jeu est le suivant :

    *Le jeu débute par une répartition aléatoire des jetons (et de leurs faces visibles) sur le plateau
    *Le but est de parvenir en une succession de mouvements différents à un plateau de jeu tout blanc (tous les jetons avec leurs faces visibles blanches).

    *2 Types de mouvements principaux sont autorisés :

    *Retournement des faces visibles sur une ligne, colonne, ou grande diagonale. Dans ce cas chacun des 4 jetons sur toute la ligne, colonne ou diagonale sélectionnée voit sa face visible changer de couleur.




    *Retournement des faces visibles sur « un coude » : le coude est une position en « L » impactant 3 jetons dans n’importe quelle direction. Chacun des 3 jetons sélectionnés par ce retournement voit ainsi sa face visible changer de couleur.


    Le but du jeu du Khalou est donc de rendre blancs tous les jetons uniquement grâce à ces types de retournements. Cela est toujours possible en 5 retournements maximum.

    **************************************

    Idee d'algorithme :

    Il existe 2^16-1 positions = 65.535. En effet on ne compte pas la position avec jetons tout blancs.
    *On peut représenter chaque position par un nombre de 16 chiffres composé de 0 ou de 1 (0 = blanc et 1 = noir) et faire tourner toutes les possibilités. En ne comptant pas celle composée de 16 chiffres 0.
    *Il existe 46 mouvements possibles. Chaque mouvement permet de changer 3 ou 4 chiffres du nombre désignant la position initial. Par exemple si les couleurs des 16 jetons sont représentées dans le chiffres de gauche a droite et de haut en bas alors le retournement de la ligne du haut change les 4 premiers chiffres du nombre a 16 chiffres représentant la position d’origine.
    Ainsi si la position d’origine est : 1000.1100.0001.1010 retourner la première ligne aboutit à la position notée : 0111.1100.0001.1010
    Ou si la position d’origine est : 1000.1100.0001.1010 retourner le premier coude aboutit à la position notée : 0100.0100.0001.1010
    Le but étant avec un minimum de retournements d’aboutir au chiffre : 0000.0000.0000.0000
    *Il suffit alors de faire tourner les 65.535 positions et pour chacune d’elles de modifier le chiffre de cette position avec les 46 puis 46^2 puis 46^3 puis 46^4 retournements possibles.
    Quand le chiffre 0000.0000.0000.0000 apparait (cela arrivera plusieurs fois souvent) on note le nombre de retournements minimum utilisés. Sinon c’est qu’il eut fallu 5 retournements.
    Ce n’est de loin pas le meilleur algorithme mais selon moi le plus simple.

    D’autres idées ????

  2. #2
    Rédacteur/Modérateur

    Avatar de Lolo78
    Homme Profil pro
    Conseil - Consultant en systèmes d'information
    Inscrit en
    Mai 2012
    Messages
    3 612
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Yvelines (Île de France)

    Informations professionnelles :
    Activité : Conseil - Consultant en systèmes d'information
    Secteur : High Tech - Opérateur de télécommunications

    Informations forums :
    Inscription : Mai 2012
    Messages : 3 612
    Billets dans le blog
    1
    Par défaut
    Alors, à vue de nez, sur une position de départ donnée, il y a 5 puissance 46 parties possibles. C'est énorme (environ 1,4 x 10 puissance 32), il n'est sans doute pas possible d'examiner toutes les parties possibles dans un temps raisonnable. L'approche force brute ne marche donc sans doute pas. Il faut donc trouver des moyens d'élaguer rapidement et à chaque étape les mouvements non rentables, pour que l'arbre des possibilités reste raisonnable.

    Mais il faut se méfier, il semble très possible que, dans certains cas, la solution optimale passe par une augmentation initiale du nombre des pions noirs, en vue de les réorganiser pour rendre les coups suivants plus efficaces. Un peu comme le joueur de dames qui donne des pions "à manger" à son adversaire pour mieux le surprendre en fin de compte, ou comme les très bons joueurs de Rubik's Cube qui développent des stratégies "non progressives" (quatre coups avant la fin, on n'a pas vraiment l'impression d'avoir progressé).

    Hmmm, le sujet me paraît intéressant, et il y a même peut-être des aspects théoriques à creuser, mais je n'ai pas trop le temps de travailler sur ce genre de truc en-dehors des week-ends.

  3. #3
    Candidat au Club
    Profil pro
    Inscrit en
    Février 2013
    Messages
    3
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Février 2013
    Messages : 3
    Par défaut
    Je ne suis pas d'accord, je dirais plutot 46 puissance 5.
    Et en partant du principe nque 2 retournements identiques s'annulent il faut au max 46*45*44*43*42 retournements.

    De plus comme on sait que tout est resoluble en 5 retournements max il ne faut pour chacune des 64.000 positions traiter que 46*45*44*43 enchainements possibles et retenir celui qui occasionne le moins de retournements.

  4. #4
    Rédacteur/Modérateur

    Avatar de Lolo78
    Homme Profil pro
    Conseil - Consultant en systèmes d'information
    Inscrit en
    Mai 2012
    Messages
    3 612
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Yvelines (Île de France)

    Informations professionnelles :
    Activité : Conseil - Consultant en systèmes d'information
    Secteur : High Tech - Opérateur de télécommunications

    Informations forums :
    Inscription : Mai 2012
    Messages : 3 612
    Billets dans le blog
    1
    Par défaut
    Citation Envoyé par lepatagon Voir le message
    Je ne suis pas d'accord, je dirais plutot 46 puissance 5.
    Exact, je me suis misérablement planté.

    Mais ça fait tout de même presque 206 millions de possibilités.

    Citation Envoyé par lepatagon Voir le message
    Et en partant du principe nque 2 retournements identiques s'annulent il faut au max 46*45*44*43*42 retournements.
    Deux retournements identiques ne s'annulent réellement que s'ils sont consécutifs. Ils ne s'annulent pas si une ou plusieurs pièces concernées ont été retournées entre temps pa.

    Citation Envoyé par lepatagon Voir le message
    De plus comme on sait que tout est resoluble en 5 retournements max il ne faut pour chacune des 64.000 positions traiter que 46*45*44*43 enchainements possibles et retenir celui qui occasionne le moins de retournements.

  5. #5
    Rédacteur/Modérateur

    Avatar de Lolo78
    Homme Profil pro
    Conseil - Consultant en systèmes d'information
    Inscrit en
    Mai 2012
    Messages
    3 612
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Yvelines (Île de France)

    Informations professionnelles :
    Activité : Conseil - Consultant en systèmes d'information
    Secteur : High Tech - Opérateur de télécommunications

    Informations forums :
    Inscription : Mai 2012
    Messages : 3 612
    Billets dans le blog
    1
    Par défaut
    Citation Envoyé par lepatagon Voir le message
    Je ne suis pas d'accord, je dirais plutot 46 puissance 5.
    Exact, je me suis misérablement planté.

    Mais ça fait tout de même presque 206 millions de possibilités (pour chacune des 65-k positions de départ).

    Citation Envoyé par lepatagon Voir le message
    Et en partant du principe nque 2 retournements identiques s'annulent il faut au max 46*45*44*43*42 retournements.
    Deux retournements identiques ne s'annulent réellement que s'ils sont consécutifs. Ils ne s'annulent pas si une ou plusieurs pièces concernées ont été retournées entre temps par un autre coup.

    Citation Envoyé par lepatagon Voir le message
    De plus comme on sait que tout est resoluble en 5 retournements max il ne faut pour chacune des 64.000 positions traiter que 46*45*44*43 enchainements possibles et retenir celui qui occasionne le moins de retournements.
    46*45*44*43 enchainements possibles? Pourquoi pas 46*45*44*43*42? Il est tout de même utile de savoir quel(s) enchaînement(s) conduisent à une solution, non? De plus, si l'on ne trouve pas de solution pour une position de départ donnée, alors on sait que le programme a un bug, ce qui n'est pas inutile à savoir. En revanche, il est vrai que l'on peut arrêter le parcours de l'arbre s'il reste plus de 4 pions noirs après le quatrième coup (ou plus de 8 après le troisième coup), ce qui peut alléger assez nettement le nombre de solutions à tester.

    L'algorithme peut être très simple en principe, la seule chose un peu casse-pieds est de coder la liste des coups possibles.

    Mais je persiste à penser qu'il faut penser à des stratégies d'optimisation pour réduire le nombre de solutions à visiter.

  6. #6
    Expert confirmé

    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Avril 2009
    Messages
    3 577
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 59
    Localisation : France, Bas Rhin (Alsace)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : Avril 2009
    Messages : 3 577
    Par défaut
    Cependant, les 206 millions de combinaisons ne seront pas appliquées pour toutes les grilles, puisqu'un certains nombre ne nécessiterons que 1, 2, 3 ou même 4 retournements (206M est un max)

    La force brute se programme facilement : si le temps est trop long pour obtenir le résultat, il est possible d'envisager des heuristiques ou des stratégies de recherche (comme prioriser certains mouvement pouvant mener plus vite au résultat, notamment par exemple, choisir tout de suite le bon retournement pour des matrices où seul un retournement est nécessaire, ce qui élague des tas de cas/sous cas).

  7. #7
    Expert confirmé

    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Avril 2009
    Messages
    3 577
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 59
    Localisation : France, Bas Rhin (Alsace)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : Avril 2009
    Messages : 3 577
    Par défaut
    Bon, après quelques essais, la force brute trouve bien des résultats, mais les premiers trouvés ne sont pas optimaux... Si l'on ne veut donc pas parcourir toutes les combinaisons comme je l'indiquais dans mon post précédent, il est donc impératif d'utiliser une stratégie particulière pour trouver les mouvements minimaux.

    Donc j'ai dit n'importe quoi. Je suppose qu'il s'agit d'un exercice de math ou d'algorithmique ?

Discussions similaires

  1. Programmation pattern missile pour jeu style shoot'em up
    Par mixka13 dans le forum XNA/Monogame
    Réponses: 7
    Dernier message: 19/05/2012, 14h36
  2. programmer une carte d’un jeu de stratégie
    Par swo.line dans le forum Développement 2D, 3D et Jeux
    Réponses: 4
    Dernier message: 10/01/2008, 22h20
  3. Réponses: 1
    Dernier message: 15/03/2007, 20h16
  4. Programmer autour du wifi.
    Par johnnyjohnny dans le forum Développement
    Réponses: 2
    Dernier message: 07/09/2006, 17h20
  5. Help ! Programmer un jeu vidéo
    Par Jay Bee dans le forum DirectX
    Réponses: 7
    Dernier message: 18/03/2004, 18h38

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo