Spécification des règles du Jeu de Go en Coq

1

Spécification des règles du Jeu de Go en Coq

Travail d’Etude et de Recherche

Ngoc-Trang CAO 2007/2008

2

Sommaire

1. Représentation du Jeu de Go2. Parcours de Goban3. Identifier les groupes4. Calcul des libertés5. Reconnaître les « yeux »6. Les méthodes de décompte

3

1. Représentation du Jeu de GoLa partie est représentée par une

liste de tour de jeu.Un tour de jeu est caractérisé par

une couleur (noir ou blanc) et d’une action (un coup ou un passe).

4

Inductive couleur : Set :=| noir| blanc| vide.

Inductive tour : Set :=| coup : couleur -> nat -> nat -> tour| pass : couleur -> tour.

Inductive partie : Set :=| pvide : nat -> partie| joue : tour -> partie -> partie.

1. Représentation du Jeu de Go

5

1. Représentation du Jeu de GoCette représentation est intuitive

et simple.Elle suffit à représenter

complètement une partie, mais n’est pas adaptée à l’analyse d’une configuration.

Une configuration de jeu est représentée par une fonction finie qui à chaque coordonnée indique son état.

6

1. Représentation du Jeu de Go(* fonction représentant le goban *)Definition gob_fun := nat->nat->couleur.

(* goban + sa taille *)Record goban : Set := mk_goban{ size : nat; content : gob_fun}.

7

1. Représentation du Jeu de GoA partir de la liste des coups,

nous voulons construire l’état du goban à n’importe quel moment de la partie.

Une liste de coup vide correspond donc à une fonction qui renvoie « vide » pour toute intersection.

A chaque coup, nous surchargeons cette fonction en conséquences.

8

1. Représentation du Jeu de GoFixpoint goban_of_game' (p:partie) (g:goban){struct p}:=match p with| pvide n => mk_goban n (fun x y => vide)| joue t q => match t with | pass _ => goban_of_game' q g | coup c lig col => vide_vois (mod_cont

(goban_of_game' q g) lig col c) lig col endend.

Definition goban_of_game (p:partie) := goban_of_game' p (mk_goban 0 (fun x y => vide)).

9

2. Parcours de GobanCoq n’accepte que des fonctions

dont l’argument de récursion est à chaque appel, structurellement plus petit.

Le parcours du goban est décomposé en 2 fonctions récursives.

La première parcours une ligne entière de size-1 à 0.

Ensuite, la seconde fait appel à la première pour chaque ligne du goban.

10

2. Parcours de Goban(* type des fonctions qui renvoient des fonctions info *)Definition func_info := goban->info->nat->nat->info.

(* parcours d'une ligne de goban *)(* avec en parametre une fonction renvoyant une nouvelle info *)Fixpoint iter_lig_info (g: goban) (f:info) (h:func_info) (x y :nat) {struct x}:(info) :=match x with| 0 => h g f x y| S q => iter_lig_info g (h g f x y) h q yend.

(* parcours du goban *)(* avec en parametre une fonction renvoyant une nouvelle info *)Fixpoint iter_gob_info (g:goban) (f:info) (h:func_info) (y:nat) {struct y}:(info) :=match y with| 0 => iter_lig_info g f h (g.(size)-1) y| S p => iter_gob_info g (iter_lig_info g f h (g.(size)-1) y) h pend.

11

3. Identifier les groupesChaque groupe du goban est

numéroté (également les groupes vides).

L’appartenance d’une intersection à un groupe est « stockée » par une fonction de type :

Definition info := nat->nat->nat.Le but est de définir cette

fonction en un seul parcours de goban.

12

3. Identifier les groupesTout d’abord, nous avons besoin

d’une fonction initiale qui à chaque intersection associe un groupe différent.

Ensuite une fonction qui fusionne deux groupes :

Definition merge (f:info) (a b : nat) :=let max := max a b inlet min := min a b infun x y => if (beq_nat (f x y) max) then min else (f

x y).

13

3. Identifier les groupesLa fonction de fusion de groupe

appliquée à chaque voisin :Definition merge_voisN (g:goban) (f:info) (x y : nat): info :=if negb(beq_nat y (g.(size)-1)) then if egc (g.(content) x y) (g.(content) x (S y)) then merge f (f x y) (f x (S y)) else felse f.Definition merge_vois (g:goban) (f:info) ( x y :nat): info :=merge_voisN g (merge_voisE g (merge_voisS g

(merge_voisO g f x y) x y) x y) x y.

14

3. Identifier les groupesFinalement, on applique cette

fusion à toutes les intersections grâce au parcours du goban :

Definition info_grp (g:goban) :=iter_gob_info g (init_gr g.(size)) merge_vois (g.

(size)-1).

15

4. Calcul des libertésUne liberté d’un groupe est une

intersection libre connexe au groupe.

Le but est de lister les libertés d’un groupe.

Le principe est de parcourir de goban, lorsque l’on tombe sur le groupe concerné, on vérifie si ses voisins sont des libertés.

16

4. Calcul des libertésRecord liberte : Set := mk_lib { col : nat ; lig : nat }.

Definition eq_lib (a b : liberte) :=match a, b with| mk_lib n m, mk_lib n' m' => beq_nat n n' && beq_nat m m'end.

Fixpoint app_lib (a : liberte) (l : list liberte) {struct l} :=match l with| nil => false| b :: l' => if (eq_lib a b) then true else app_lib a l'end.

Definition add_lib (a : liberte) (l:list liberte) :=if (app_lib a l) then l else a :: l.

17

5. Reconnaître les « yeux »Un œil est une liberté dont les 4

voisins sont de la même couleur (noir ou blanc).

De plus, ils doivent être du même groupe sinon c’est un faux œil.

Pour vérifier si un groupe est vivant, il ne reste plus qu’à parcourir la liste de ses libertés et trouver au moins 2 yeux.

18

5. Reconnaître les « yeux »Definition est_oeil (g:goban) (a:nat) (x y : nat) :=match g.(content) x y with| vide => let grp := info_grp g in (if negb(beq_nat x (g.(size)-1)) then beq_nat a (grp (S

x) y) else true) && (if negb(beq_nat x 0) then beq_nat a (grp (x-1) y) else

true) && (if negb(beq_nat y 0) then beq_nat a (grp x (y-1)) else

true) && (if negb(beq_nat y (g.(size)-1)) then beq_nat a (grp x

(S y)) else true)| _ => falseend.

19

6. Les méthodes de décompteA la fin de la partie, les pierres

mortes sont retirées, on calcule le score de chaque joueur.

Le résultat est la différence des scores.

Les joueurs de Go utilisent 3 règles différentes de décompte du score : la règle Chinoise, Japonaise et Française.

20

6. Les méthodes de décompteEn règles Chinoise : le score de chaque

joueur est la somme du nombre de ses pierres et du nombre d’intersections libres qu’il a entourées.

Les scores en règles Japonaise se compte autrement : c’est le nombre d’intersections libres contrôlées auquel on soustrait le nombre de prisonniers (c.à.d. les pierres capturées par l’adversaire durant la partie et les pierres mortes retirées à la fin).

21

6. Les méthodes de décompte

En règles chinoises :Noir : 36Blanc : 45Donc N+9.

En règles japonaises :Noir : 25Blanc : 17Donc N+8.

22

6. Les méthodes de décomptePar l’exemple précédent, nous

venons de montrer clairement la différence entre les règles chinoises et japonaises.

La règle Française utilise le même procédé de décompte que la Chinoise.

Les joueurs français étant habitué à la règle japonaise préfèrent compter « à la japonaise ».

23

6. Les méthodes de décomptePour avoir l’équivalence entre les

deux, la règle Française dit en plus :◦À chaque « passe », étant donné que le

joueur ne pose pas la pierre sur le goban, il doit la donner en tant que prisonnier à son adversaire.

◦Blanc doit passer le dernier.Avec ses conditions en plus,

l’équivalence des deux méthodes de décompte est assurée.

24

ConclusionImplémentation du jeu de Go en Coq.Fonction d’analyse des groupesCalcul des libertésDétection des yeuxPreuves informelles des décomptes

A faire :◦Implémentation des règles de décompte◦Preuves concernant la capture

25

Les gens normaux jouent au Renju, le jeu d’Echecs est pour les

Héros, le Go est réservé aux Dieux.

Proverbe japonais.