programmation autours d'un jeu

programmation autours d'un jeu - Divers - Programmation

Marsh Posté le 18-02-2013 à 12:41:28    

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 ?  
 
Merci  
 
Dan
 

Reply

Marsh Posté le 18-02-2013 à 12:41:28   

Reply

Marsh Posté le 18-02-2013 à 12:53:45    

C'est pas clair,  
 
Tu dis :

Citation :

Cela est toujours faisable en 5 retournements minimum (démontré via théorie des groupes).


 
puis :

Citation :

*Trouver ainsi le nombre totale de positions résolvables en : 1, 2, 3, 4 et 5 retournements minimum.


 

Reply

Marsh Posté le 18-02-2013 à 13:10:00    

Je souhaite connaitre pour chacune des 64000 positions le nombre minimum de retournements necessaires. Je pense qu'il faut lire la regle du jeu

Reply

Marsh Posté le 18-02-2013 à 13:25:54    

Pour info j'ai pas trouvé la règle du jeu.

Reply

Marsh Posté le 18-02-2013 à 13:29:23    

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.

Reply

Marsh Posté le 18-02-2013 à 14:24:08    

pour moi il y a 46 mouvements possibles dont 36 mouvements en coudes.

Reply

Marsh Posté le 18-02-2013 à 14:26:30    

J'avais mal lu les règles sur les coudes (en forme de L, j'étais parti sur des coudes de 4 cases, et toujours en coin).
Il y a 36 coudes (1 coude par coin, 2 coudes par case du bord qui n'est pas un coin, et 4 coudes par case centrale) 1*4 + 2*8 + 4*4 = 36
On voit a la base que il y a 4 + 4 + 2 + 34 = 46 mouvements distincts donc peut procéder en partant d'un damier blanc et en effectuant les 44 mouvements pour les solutions en 1 coup, puis partant des solutions en un coup, les 45 mouvements (on ne fait pas deux fois de suite le même mouvement, car cela s'annule) pour les solutions en deux coups (pas déjà trouvées dans les solutions en un coup) etc.  
A+,


Message édité par gilou le 18-02-2013 à 14:30:15

---------------
There's more than what can be linked! --    Iyashikei Anime Forever!    --  AngularJS c'est un framework d'engulé!  --
Reply

Marsh Posté le 18-02-2013 à 14:26:34    

46 positions resolvables en 1 coup
46*45/2 positions resolvables en 2 coups

Reply

Marsh Posté le 18-02-2013 à 14:33:12    

Oui, 36, pas 34 pour les coudes, si j'arrive plus à faire une addition correctement...
au plus 188628750 opérations de transformation à effectuer, ça doit être possible dans un temps correct.
Je regarderais si ça prends pas trop de temps en perl ce soir, parce que je suis offline d'ici la.
A+,


---------------
There's more than what can be linked! --    Iyashikei Anime Forever!    --  AngularJS c'est un framework d'engulé!  --
Reply

Marsh Posté le 18-02-2013 à 14:37:29    

Pour moi le plus simple et rapide serait de representer chaque position par un nombre de 16 chiffres composé de 0 ou de 1 (0 = blanc et 1 = noir) et de faire tourner toutes les  posibilités

Reply

Marsh Posté le 18-02-2013 à 14:37:29   

Reply

Marsh Posté le 18-02-2013 à 14:38:34    

Genial Gilou, merci  

Reply

Marsh Posté le 18-02-2013 à 19:00:24    


*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 ????  
 

Reply

Marsh Posté le 19-02-2013 à 00:53:45    

Code :
  1. #!/usr/bin/perl
  2.  
  3. use strict;
  4. use warnings;
  5.  
  6. my @boards;
  7.  
  8. # initialisation des boards
  9. for (my $i = 0; $i < 2**16; ++$i) {
  10.  $boards[$i] = [0, 0, 0];
  11.  # premier champ: nombre de mouvement pour revenir à une solution
  12.  # second champ: mouvement à effectuer
  13.  # troisième champ: résultat après le mouvement
  14. }
  15.  
  16. my @moves = (15, 19, 35, 38, 49, 50, 70, 76, 98, 100, 140, 196, 200, 240, 304, 560, 608,
  17.          784, 800, 1120, 1216, 1568, 1600, 2240, 3136, 3200, 3840, 4369, 4680, 4864,
  18.          8738, 8960, 9728, 12544, 12800, 17476, 17920, 19456, 25088, 25600, 33825,
  19.          34952, 35840, 50176, 51200, 61440);
  20.  
  21. foreach (@moves) {
  22.  $boards[$_]->[0] = 1;
  23.  $boards[$_]->[1] = $_;
  24. }
  25.  
  26. for my $level (1..4) {
  27.  for (my $i = 0; $i < 2**16; ++$i) {
  28.    if ($boards[$i]->[0] == $level) {
  29.      foreach (@moves) {
  30.         my $result = $i^$_;
  31.         unless ($result == 0 or $boards[$result]->[0]) {
  32.           $boards[$result]->[0] = $level+1;
  33.           $boards[$result]->[1] = $_;
  34.           $boards[$result]->[2] = $i;
  35.         }
  36.      }
  37.    }
  38.  }
  39. }
  40. # @boards contient maintenant toute l'information nécessaire
  41.  
  42. my @count = (0, 0, 0, 0, 0, 0);
  43. for (my $i = 0; $i < 2**16; ++$i) {
  44.  ++$count[$boards[$i]->[0]];
  45. }
  46.  
  47. foreach (0..5) {
  48.  print "Nb de positions de depart solvables en un minimum de $_ coups: $count[$_]\n";
  49. }


 

C:\Perl>perl khalou.pl
Nb de positions de depart solvables en un minimum de 0 coups: 1
Nb de positions de depart solvables en un minimum de 1 coups: 46
Nb de positions de depart solvables en un minimum de 2 coups: 987
Nb de positions de depart solvables en un minimum de 3 coups: 10680
Nb de positions de depart solvables en un minimum de 4 coups: 39067
Nb de positions de depart solvables en un minimum de 5 coups: 14755


 
C'est peut être optimisable, mais même sur ma vieille bécane qui n'a que 2 Go de mémoire et un pentium4, ça ne prend que qques secondes, donc ça vaut pas trop la peine de chercher à optimiser cela.
 
A+,


Message édité par gilou le 19-02-2013 à 01:37:44

---------------
There's more than what can be linked! --    Iyashikei Anime Forever!    --  AngularJS c'est un framework d'engulé!  --
Reply

Marsh Posté le 19-02-2013 à 01:09:01    

Le truc qui a pris le plus de temps, c'est de déterminer tous les mouvements pour générer @moves.
Je me suis servi de deux fonctions auxiliaires qui me permettent de lire et imprimer un board:
 

Code :
  1. # en entrée un nombre, en sortie, le board correspondant
  2. sub printboard {
  3.  print join("\n", (reverse(unpack("B16", pack("n", shift))) =~ m/..../g)), "\n";
  4. }
  5.  
  6. # en entrée un board, en sortie, le nombre correspondant
  7. sub readboard {
  8.  my $input = shift;
  9.  my $str = reverse($input);
  10.  $str =~ tr/01//cd;
  11.  die "Error: incorrect board:\n  $input" unless (length($str) == 16);
  12.  unpack("n", pack("B16", $str));
  13. }


 
et d'une liste des 64 boards représentant un mouvement:
 

Code :
  1. my @boardmoves = (
  2. #lignes
  3. "
  4. 1111
  5. 0000
  6. 0000
  7. 0000", #1
  8. "
  9. 0000
  10. 1111
  11. 0000
  12. 0000", #2
  13. "
  14. 0000
  15. 0000
  16. 1111
  17. 0000", #3
  18. "
  19. 0000
  20. 0000
  21. 0000
  22. 1111", #4
  23. #colonnes
  24. "
  25. 1000
  26. 1000
  27. 1000
  28. 1000", #5
  29. "
  30. 0100
  31. 0100
  32. 0100
  33. 0100", #6
  34. "
  35. 0010
  36. 0010
  37. 0010
  38. 0010", #7
  39. ...
  40. "
  41. 0000
  42. 0000
  43. 0011
  44. 0010", #44
  45. "
  46. 0000
  47. 0010
  48. 0110
  49. 0000", #45
  50. "
  51. 0000
  52. 0000
  53. 0110
  54. 0010", #46
  55. );


(on peut retrouver cette liste en appliquant printboard aux éléments de @moves)
 
Le seul truc qu'il fallait voir, c'est qu'on pouvait coder tout board initial comme un entier entre 0 et 65535, par sa représentation binaire, tout mouvement comme un entier dans cet intervalle aussi, et que partant d'un board b, l'opération qui consiste à lui appliquer un mouvement m revient a faire le xor de b et m.
 
A+,


---------------
There's more than what can be linked! --    Iyashikei Anime Forever!    --  AngularJS c'est un framework d'engulé!  --
Reply

Marsh Posté le 19-02-2013 à 01:28:40    

A partir du code donné, on peut facilement écrire une routine résolvant n'importe quelle position de départ en un minimum de mouvements:

Code :
  1. #!/usr/bin/perl
  2.  
  3. use strict;
  4. use warnings;
  5.  
  6. my @boards;
  7.  
  8. # initialisation des boards
  9. for (my $i = 0; $i < 2**16; ++$i) {
  10.  $boards[$i] = [0, 0, 0];
  11.  # premier champ: nombre de mouvement pour revenir à une solution
  12.  # second champ: mouvement à effectuer
  13.  # troisième champ: résultat après le mouvement
  14. }
  15.  
  16. my @moves = (15, 19, 35, 38, 49, 50, 70, 76, 98, 100, 140, 196, 200, 240, 304, 560, 608,
  17.          784, 800, 1120, 1216, 1568, 1600, 2240, 3136, 3200, 3840, 4369, 4680, 4864,
  18.          8738, 8960, 9728, 12544, 12800, 17476, 17920, 19456, 25088, 25600, 33825,
  19.          34952, 35840, 50176, 51200, 61440);
  20.  
  21. foreach (@moves) {
  22.  $boards[$_]->[0] = 1;
  23.  $boards[$_]->[1] = $_;
  24. }
  25.  
  26. for my $level (1..4) {
  27.  for (my $i = 0; $i < 2**16; ++$i) {
  28.    if ($boards[$i]->[0] == $level) {
  29.      foreach (@moves) {
  30.         my $result = $i^$_;
  31.         unless ($result == 0 or $boards[$result]->[0]) {
  32.           $boards[$result]->[0] = $level+1;
  33.           $boards[$result]->[1] = $_;
  34.           $boards[$result]->[2] = $i;
  35.         }
  36.      }
  37.    }
  38.  }
  39. }
  40.  
  41. # en entrée un nombre, en sortie, le board correspondant
  42. sub printboard {
  43.  print join("\n", (reverse(unpack("B16", pack("n", shift))) =~ m/..../g)), "\n";
  44. }
  45.  
  46. # en entrée un board, en sortie, le nombre correspondant
  47. sub readboard {
  48.  my $input = shift;
  49.  my $str = reverse($input);
  50.  $str =~ tr/01//cd;
  51.  die "Error: incorrect board:\n  $input" unless (length($str) == 16);
  52.  unpack("n", pack("B16", $str));
  53. }
  54.  
  55. sub resoudre {
  56.  my $b = readboard(shift);
  57.  my $mvt = 0;
  58.  print "Depart:\n\n";
  59.  while ($b != 0){
  60.    printboard($b);
  61.    print "\n";
  62.    ++$mvt;
  63.    print "Mouvement $mvt:\n\n";
  64.    printboard($boards[$b]->[1]);
  65.    print "\n";
  66.    $b = $boards[$b]->[2];
  67.    print ($b?"Resultat:\n\n":"Termine\n\n" );
  68.  }
  69. }
  70.  
  71. my $board = "
  72. 0101
  73. 1010
  74. 1100
  75. 0011";
  76.  
  77. resoudre($board);


Ce qui donne:

Depart:
 
0101
1010
1100
0011
 
Mouvement 1:
 
0000
0000
0010
0011
 
Resultat:
 
0101
1010
1110
0000
 
Mouvement 2:
 
0000
0100
0110
0000
 
Resultat:
 
0101
1110
1000
0000
 
Mouvement 3:
 
0100
1100
0000
0000
 
Resultat:
 
0001
0010
1000
0000
 
Mouvement 4:
 
0000
0000
1100
1000
 
Resultat:
 
0001
0010
0100
1000
 
Mouvement 5:
 
0001
0010
0100
1000
 
Termine


 
 
A+,


Message édité par gilou le 19-02-2013 à 12:20:11

---------------
There's more than what can be linked! --    Iyashikei Anime Forever!    --  AngularJS c'est un framework d'engulé!  --
Reply

Marsh Posté le 19-02-2013 à 12:27:13    

Ca semble super, je vais regarder.
 
merci bcp

Reply

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed