Représentation du jeu du moulin

Version imprimable

19/08/2020, 19h45
Roland Chastain

Représentation du jeu du moulin
Bonjour !

J'aimerais bien travailler sur le jeu du moulin, qui est connu aussi sous d'autre noms. Si vous ne connaissez pas, voici deux (très beaux) logiciels qui permettent d'y jouer :
- Morris
- Mühle Projekt
Comment vous y prendriez-vous pour représenter la table de jeu ? Je ne parle de la représentation visuelle, mais de la représentation logique. Comment désigner les cases ou les emplacements ? Comment déterminer que deux cases sont reliées ? Comment déterminer que trois cases sont alignées ?

Le problème est d'autant plus amusant que le jeu a des variantes (on peut s'en faire une idée en regardant cette page).

Il faut donc imaginer une notation pour les coups, déterminer si les coups sont possibles, s'ils ont pour résultat un moulin (un alignement de trois pièces)...

Qu'en pensez-vous ? Pour ma part, à première vue, je trouve ça assez compliqué. :aie:

Bonjour Roland,

Effectivement cela paraît assez compliqué. Pour la représentation en mémoire, je partirais de l'existence de 24 intersections et de 16 moulins, chaque intersection ayant 2 ou 3 intersections adjacentes et appartenant à 2 moulins :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 type TIntersection = Record Valeur : Integer; IndiceAdjacent1 : Integer; IndiceAdjacent2 : Integer; IndiceAdjacent3 : Integer; IndiceMoulin1 : Integer; IndiceMoulin2 : Integer; end; TMoulin = Record Complet : Boolean; IndiceIntersection1 : Integer; IndiceIntersection2 : Integer; IndiceIntersection3 : Integer; end; TIntersections = Array [1..24] of TIntersection; TMoulins = Array [1..16] of TMoulin;
Chaque changement de valeur d'une intersection se reporterait ainsi sur les deux moulins qu'elle concerne et il serait aisé d'accéder à la complétude (ou non) des deux moulins liés à chaque intersection. Une version objet ou avec des enregistrements étendus serait bien sûr plus élégante. D'autres auront peut-être des idées plus performantes. ;)

Salut Roland,

cela me fait penser à un "morpion" sous stéroïde. L'emploi d'un algo genre NegaMax / MinMax devrait permettre de trouver si il y un "moulin" correcte et/ou permettre de déterminer les mouvements de l'IA.

Pour ce qui est de la structure, je ferai peut-être quelques chose orienté objet dans ce style :

Code:

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
Type
  TPlayerType = (ptHuman, ptComputer);
 
  TCellStatus = (csUndefined, csPlayer1, csPlayer2);
  TBoard = Array of TCellStatus;//Array[0..cMaxBoardSize-1] of TCellStatus;  
  TMills = Array of Array of Byte;
 
 
  TBoardGame = class
  private
     FMaxBoardSize : Byte;
     FMaxVoisin : Byte;
     FBoardName : String;
     FBoardWidth, FBoardHeight : Byte;
 
     FBoard : TBoard;
 
     FMaxMills : Byte;
     FMaxMillTokens : Byte;
     FMills : TMills
   // Exemple  FMills avec FMaxMills = 16 FMaxMillToken = 3
   // Moulins horizontaux
  { (0, 1, 2),      (3, 4, 5),      
   (6, 7, 8),      (9, 10, 11),   
   (12, 13, 14), (15, 16, 17),
   (18, 19, 20), (21, 22, 23),
   // Moulins Verticaux
   (0, 9, 21),     (3, 10, 18),
   (6, 11, 15),   (1, 4, 7),
   (16, 19, 22), (8, 12, 17),
   (5, 13, 20),  (2,14,23) }
 
  protected
 
  public     
     Constructor Create;
     Destructor Destroy;
 
     function getBoard : TBoard;
 
     property MaxBoardSize : Byte read FMaxBoardSize;
     property MaxVoisin : Byte read MaxVoisin;
     property BoardName : String read FBoardName;
     property FBoardWidth : Byte read FBoardWidth;
     property BoardHeight : Byte read FBoardHeight;
     property MaxMills : Byte read FMaxMills;
     property MaxMillTokens : Byte read FMaxMillTokens;
 
     property Mill[MillIndex : Integer; TokenIndex : Integer] : Integer read getMillToken;
     property Cell[Index : Integer] : TCellStatus read getCell write setCell
  end;
 
  TPlayer = Class
  private
    FBoard : TBoardGame;
    FPlayerType : TPlayerType;
 
    function CanMove(OldPos, NewPos : Integer) : Boolean;
  public
     Constructor Create(ABoard : TBoardGame);
 
     procedure SetMove(NewPos : Integer):
     procedure UpdateMove(OldPos, NewPos : Integer):
 
     function CheckIfWin : Boolean;
 
     property PlayerType : TPlayerType read FPlayerType write FPlayerType;
  end;

Il manque quelques éléments pour obtenir des plateaux de jeux persos. A voir comment ajouter, personnaliser la position des cases en fonction de l'algo pour dessiner les grilles de jeu. On pourrait également ajouter un tableau pour stocker tous les voisins à une position X (un peu comme le FMills) Ce qui simplifierait les tests.

A+

Jérôme

21/08/2020, 21h44
Roland Chastain

Citation:

Envoyé par Alcatîz

Bonjour Roland,

Effectivement cela paraît assez compliqué. Pour la représentation en mémoire, je partirais de l'existence de 24 intersections et de 16 moulins, chaque intersection ayant 2 ou 3 intersections adjacentes et appartenant à 2 moulins :

Intéressant. C'est déjà un peu plus clair. Merci !

Je prends encore quelques jours pour jouer et bien assimiler les règles, et je passe aux travaux pratiques.
21/08/2020, 21h56
Roland Chastain

Citation:

Envoyé par BeanzMaster

Pour ce qui est de la structure, je ferai peut-être quelques chose orienté objet dans ce style :

Merci Jérôme pour toutes ces idées. Je vais m'en inspirer.

Au fait, j'ai encore trouvé un autre logiciel, qui a quelques années, mais qui fonctionne parfaitement : http://belasius.com/mulino/

Il y a aussi celui-ci, en C, qui est plus basique, mais qui fonctionne bien aussi : https://github.com/paul-maxime/merreles

Ce serait amusant de faire un tournoi de robots. Il faudrait inventer un protocole... Bon, nous n'en sommes pas là, mais l'idée me plaît bien. Ça m'a même presque empêché de dormir. :)

salut

un tableau ou un arbre

tu as un maximum 4 connexions

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
   Directions = (Haut,Bas,Droite,Gauche)
 
TCellule = Class
 
TConnexion = Class 
  Voisin : Array[Directions] of TCellule;
End
 
TCellule = Class 
   Ident         : integer;
   Position     : Tpos;
   Connexion : TConnexion;
End;

Je partirais sur quelque chose de ce style :

Des pions valant 1 (blanc) ou -1 (noir), un moulin complet valant +3 ou -3.
Des moulins contenant la liste de leurs points.
Des points contenant leur couleur actuelle, la liste des moulins les contenant et les points connectés pour déplacement.
Des joueurs avec leur couleur et les points qu'ils possèdent.
Code:

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 type TMoveResult = (tmDenied, tmPartial, tmFull); // Point déjà occupé, moulin partiel ou complet TCell = class; TMill = class Cells :array of TCell; function IsFull :boolean; // +3: blanc, -3:noir end; TCell = class Color :shortint; // 0: vide, 1: blanc, -1:noir Mills :array of TMill; // Moulins concernés Cells :array of TCell; // Points connexes pour déplacement function Move(aDest :TCell) :TMoveResult; end; TPlayer = class Color :shortint; // 1: blanc, -1:noir (constante) Cells :array of TCell; // Points avec sa couleur, augmente de 1 à 9 puis se réduit de 9 à 2 end; TBoard = class Players :array[boolean] of TPlayer; Current :boolean; // Joueur actuel Grid : array of array of TCell; // Grille contenant ou non (nil) un point function Move(aSource, aDest :TCell) :TMoveResult; end;
Sur OnMouseDown, contrôle de la validité du pion pour le joueur actuel et sur OnMouseUp TBoard.Move appelle TCell.Move pour contrôler la validité du déplacement puis assigne la cellule au joueur qui la remplit de sa couleur et éventuellement retire un pion adverse, etc, etc.

26/08/2020, 09h57
Roland Chastain

Merci pour vos précieuses contributions.

Citation:

Envoyé par Andnotor

Sur OnMouseDown, contrôle de la validité du pion pour le joueur actuel et sur OnMouseUp TBoard.Move appelle TCell.Move pour contrôler la validité du déplacement puis assigne la cellule au joueur qui la remplit de sa couleur et éventuellement retire un pion adverse, etc, etc.

Dans un premier temps je pense faire une application console, où l'on entre les coups au clavier.
26/08/2020, 17h43
Roland Chastain

Petite parenthèse, sur le nom du jeu. Si l'on en croit Littré, le nom du jeu serait... marelle. Je suis allé voir aussi l'article moulin : on n'y trouve aucune mention d'un jeu qui porterait ce nom.

P.-S. Plus d'informations dans cet article.

Je n'ai pas oublié cette discussion. J'ai regardé d'un peu plus près ce programme-ci. Je l'ai trouvé très bien écrit. J'ai bien envie de le traduire en Pascal.

Autrement j'ai commencé à réfléchir à la façon de numéroter les intersections.
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 7 000------------001------------002 | | | 6 | 008-------009-------010 | | | | | | 5 | | 016--017--018 | | | | | | | | 4 007--015--023 019--011--003 | | | | | | 3 | | 022--021--020 | | | | | | | 2 | 014-------013-------012 | | | | 1 006------------005------------004 a b c d e f g
La plupart des programmes que j'ai vus numérotent les lignes de haut en bas. Moi j'ai tendance à préférer comme ça. Mais il vaudrait peut-être mieux suivre l'usage le plus commun.

P.-S. J'ai trouvé aussi ce livre, qui a l'air intéressant : Récréations mathématiques

18/12/2022, 10h52
Roland Chastain

2 pièce(s) jointe(s)

J'ai mis à jour le petit programme en C dont j'avais parlé plus haut.

Ci-joint le programme en Pascal que j'ai écrit pour fabriquer l'image du plateau.
18/12/2022, 11h33
Alcatîz

Bonjour Roland,

:ccool: Je retiens en passant le site https://opengameart.org/.

Oui ce site est très utile.

Pour la représentation des données, je pense partir de ton idée, avec une petite modification.

Code:

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
 
type
  TIntersection = Record
    Valeur: Integer;
    IndiceAdjacent: Array[1..4] of Integer;
    IndiceMoulin: Array[1..2] of Integer;
  end;
 
  TMoulin = Record
    Complet: Boolean;
    IndiceIntersection: Array[1..3] of Integer;
  end;
 
  TIntersections = Array [1..24] of TIntersection;
  TMoulins = Array [1..16] of TMoulin;
 
const
  CIntersections: TIntersections = (
    (Valeur: 0; IndiceAdjacent: (0, 0, 0, 0); IndiceMoulin: (0, 0)),
    (Valeur: 0; IndiceAdjacent: (0, 0, 0, 0); IndiceMoulin: (0, 0)),
    (Valeur: 0; IndiceAdjacent: (0, 0, 0, 0); IndiceMoulin: (0, 0)),
    (Valeur: 0; IndiceAdjacent: (0, 0, 0, 0); IndiceMoulin: (0, 0)),
    (Valeur: 0; IndiceAdjacent: (0, 0, 0, 0); IndiceMoulin: (0, 0)),
    (Valeur: 0; IndiceAdjacent: (0, 0, 0, 0); IndiceMoulin: (0, 0)),
    (Valeur: 0; IndiceAdjacent: (0, 0, 0, 0); IndiceMoulin: (0, 0)),
    (Valeur: 0; IndiceAdjacent: (0, 0, 0, 0); IndiceMoulin: (0, 0)),
 
    (Valeur: 0; IndiceAdjacent: (0, 0, 0, 0); IndiceMoulin: (0, 0)),
    (Valeur: 0; IndiceAdjacent: (0, 0, 0, 0); IndiceMoulin: (0, 0)),
    (Valeur: 0; IndiceAdjacent: (0, 0, 0, 0); IndiceMoulin: (0, 0)),
    (Valeur: 0; IndiceAdjacent: (0, 0, 0, 0); IndiceMoulin: (0, 0)),
    (Valeur: 0; IndiceAdjacent: (0, 0, 0, 0); IndiceMoulin: (0, 0)),
    (Valeur: 0; IndiceAdjacent: (0, 0, 0, 0); IndiceMoulin: (0, 0)),
    (Valeur: 0; IndiceAdjacent: (0, 0, 0, 0); IndiceMoulin: (0, 0)),
    (Valeur: 0; IndiceAdjacent: (0, 0, 0, 0); IndiceMoulin: (0, 0)),
 
    (Valeur: 0; IndiceAdjacent: (0, 0, 0, 0); IndiceMoulin: (0, 0)),
    (Valeur: 0; IndiceAdjacent: (0, 0, 0, 0); IndiceMoulin: (0, 0)),
    (Valeur: 0; IndiceAdjacent: (0, 0, 0, 0); IndiceMoulin: (0, 0)),
    (Valeur: 0; IndiceAdjacent: (0, 0, 0, 0); IndiceMoulin: (0, 0)),
    (Valeur: 0; IndiceAdjacent: (0, 0, 0, 0); IndiceMoulin: (0, 0)),
    (Valeur: 0; IndiceAdjacent: (0, 0, 0, 0); IndiceMoulin: (0, 0)),
    (Valeur: 0; IndiceAdjacent: (0, 0, 0, 0); IndiceMoulin: (0, 0)),
    (Valeur: 0; IndiceAdjacent: (0, 0, 0, 0); IndiceMoulin: (0, 0))
  );
  CMoulins: TMoulins = (
    (Complet: FALSE; IndiceIntersection: (0, 0, 0)),
    (Complet: FALSE; IndiceIntersection: (0, 0, 0)),
    (Complet: FALSE; IndiceIntersection: (0, 0, 0)),
    (Complet: FALSE; IndiceIntersection: (0, 0, 0)),
    (Complet: FALSE; IndiceIntersection: (0, 0, 0)),
    (Complet: FALSE; IndiceIntersection: (0, 0, 0)),
    (Complet: FALSE; IndiceIntersection: (0, 0, 0)),
    (Complet: FALSE; IndiceIntersection: (0, 0, 0)),
    (Complet: FALSE; IndiceIntersection: (0, 0, 0)),
    (Complet: FALSE; IndiceIntersection: (0, 0, 0)),
    (Complet: FALSE; IndiceIntersection: (0, 0, 0)),
    (Complet: FALSE; IndiceIntersection: (0, 0, 0)),
    (Complet: FALSE; IndiceIntersection: (0, 0, 0)),
    (Complet: FALSE; IndiceIntersection: (0, 0, 0)),
    (Complet: FALSE; IndiceIntersection: (0, 0, 0)),
    (Complet: FALSE; IndiceIntersection: (0, 0, 0))
  );
 
var
  Intersections: TIntersections;
 
begin
  Intersections := CIntersections;
end.

(Pour le moment j'ai mis des zéros partout parce que je ne suis pas encore décidé sur la manière de numéroter les cases.)

Je pourrais aussi reprendre l'idée d'anapurna, array[TDirection], au lieu de array[1..4].

L'idée d'un tableau dynamique (exemple d'Andnotor) est peut-être préférable à certains points de vue, mais la quantité de code qu'il faudra pour initialiser tout ça ! Enfin je ne sais pas, j'y réfléchis encore.

1 pièce(s) jointe(s)

On pourrait considérer le plateau de jeu comme un damier, où le mode de déplacement des pièces dépend de la case où elles se trouvent.

Code:

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
 
uses
{$IFDEF unix}
  cThreads,
{$ENDIF}
  SysUtils, ptcCrt, ptcGraph;
 
const
  A = 41;
  B = A div 2;
 
var
  gd, gm: smallint;
  i, j: integer;
 
begin
  gd := VESA;
  gm := InstallUserMode(7 * A, 7 * A, 16);
{ Procédure disponible dans la dernière version de PTCGraph :
  https://sourceforge.net/projects/ptcpas/ }
 
  if gm < 0 then
  begin
    Writeln(ErrOutput, 'Error installing user mode: ', GraphErrorMsg(gm));
    Halt(1);
  end;
 
  WindowTitle := 'Moulin';
  InitGraph(gd, gm, '');
 
 
  SetBkColor(Blue);
  SetColor(LightMagenta);
  SetFillStyle(SolidFill, LightBlue);
 
  ClearViewPort;
 
  for i := 0 to 7 do
    for j := 0 to 7 do
      if (i + j) mod 2 = 0 then
        Bar(A * i, A * j, A * i + A - 1, A * j + A - 1);
 
  Rectangle(0 * A + B, 0 * A + B, 6 * A + B, 6 * A + B);
  Rectangle(1 * A + B, 1 * A + B, 5 * A + B, 5 * A + B);
  Rectangle(2 * A + B, 2 * A + B, 4 * A + B, 4 * A + B);
 
  MoveTo(0 * A + B, 3 * A + B); LineTo(2 * A + B, 3 * A + B);
  MoveTo(4 * A + B, 3 * A + B); LineTo(6 * A + B, 3 * A + B);
  MoveTo(3 * A + B, 0 * A + B); LineTo(3 * A + B, 2 * A + B);
  MoveTo(3 * A + B, 4 * A + B); LineTo(3 * A + B, 6 * A + B);
 
  SetFillStyle(SolidFill, LightMagenta);
 
  Bar(0 * A + B - 2, 0 * A + B - 2, 0 * A + B + 2, 0 * A + B + 2); Bar(3 * A + B - 2, 0 * A + B - 2, 3 * A + B + 2, 0 * A + B + 2); Bar(6 * A + B - 2, 0 * A + B - 2, 6 * A + B + 2, 0 * A + B + 2);
  Bar(1 * A + B - 2, 1 * A + B - 2, 1 * A + B + 2, 1 * A + B + 2); Bar(3 * A + B - 2, 1 * A + B - 2, 3 * A + B + 2, 1 * A + B + 2); Bar(5 * A + B - 2, 1 * A + B - 2, 5 * A + B + 2, 1 * A + B + 2);
  Bar(3 * A + B - 2, 2 * A + B - 2, 3 * A + B + 2, 2 * A + B + 2);
  Bar(0 * A + B - 2, 3 * A + B - 2, 0 * A + B + 2, 3 * A + B + 2); Bar(1 * A + B - 2, 3 * A + B - 2, 1 * A + B + 2, 3 * A + B + 2); Bar(2 * A + B - 2, 3 * A + B - 2, 2 * A + B + 2, 3 * A + B + 2); Bar(4 * A + B - 2, 3 * A + B - 2, 4 * A + B + 2, 3 * A + B + 2); Bar(5 * A + B - 2, 3 * A + B - 2, 5 * A + B + 2, 3 * A + B + 2); Bar(6 * A + B - 2, 3 * A + B - 2, 6 * A + B + 2, 3 * A + B + 2);
  Bar(3 * A + B - 2, 4 * A + B - 2, 3 * A + B + 2, 4 * A + B + 2);
  Bar(1 * A + B - 2, 5 * A + B - 2, 1 * A + B + 2, 5 * A + B + 2); Bar(3 * A + B - 2, 5 * A + B - 2, 3 * A + B + 2, 5 * A + B + 2); Bar(5 * A + B - 2, 5 * A + B - 2, 5 * A + B + 2, 5 * A + B + 2);
  Bar(0 * A + B - 2, 6 * A + B - 2, 0 * A + B + 2, 6 * A + B + 2); Bar(3 * A + B - 2, 6 * A + B - 2, 3 * A + B + 2, 6 * A + B + 2); Bar(6 * A + B - 2, 6 * A + B - 2, 6 * A + B + 2, 6 * A + B + 2);
 
  ReadKey;
  CloseGraph;
end.

31/05/2023, 17h29
Guesset

1 pièce(s) jointe(s)

Vue d'avion

Bonjour,

Je vois que le sujet motive. Une petite participation sur la représentation des données. J'ai juste imaginé que le plateau représentait un cube vu d'avion avec une forte perspective ce qui donne un cube de ce type :

Pièce jointe 639487

Les possibilités d'indexation de Pascal permettent d'avoir un tableau sympathique [-1..1, -1..1, -1..1] qui ne gaspille que peu de place 27/24.

Un point milieu de coté se détecte simplement par (x and y) = 0.

Salutations
14/03/2024, 19h44
Roland Chastain

1 pièce(s) jointe(s)

Citation:

Envoyé par Guesset

Une petite participation sur la représentation des données.

Je trouve cette idée très astucieuse, et si je n'ai pas répondu, c'est parce que je n'ai pas trouvé le temps de travailler sur ce projet.

Aujourd'hui je reviens à cette discussion parce que je viens de découvrir un projet qui a l'air génial : Sanmill

L'adversaire artificiel est une application console, comme un moteur d'échecs, utilisant un protocole dérivé du protocole UCI. Le projet inclut trois interfaces graphiques. J'ai compilé l'interface Qt, qui est très belle. Je n'ai pas encore essayé les autres (ne connaissant pas les bibliothèques utilisées).

On pourrait écrire un moteur en Pascal, et utiliser l'une de ces interfaces... 8-)