Cet article fait partie de notre série d’articles d’introduction au langage Go. Dans ma présentation des premiers pas avec go j’ai brièvement couvert l’installation du compilateur et l’organisation des sources. Aujourd’hui je vais parler du langage au travers d’un exemple simple : le jeu Quarto.
Le jeu se joue sur un plateau de 4×4 et se compose de 16 pièces. Chaque pièce possède 4 caractères :
Chaque combinaison de ces 4 caractères est représentée exactement une fois.
Au début de la partie, le plateau est vide et les pièces sont regroupées en un seul lot sur le coté du plateau.
Le but du jeu est de former un alignement de 4 pièces partageant au moins un caractère commun. Il existe une variante où l’on compte comme gagnant 4 pièces partageant au moins un même caractère regroupées en carré.
Le déroulement est simple puisqu’à chaque tour, on place une pièce sur n’importe quelle case vide du plateau. La principale contrainte du jeu est que c’est l’adversaire qui va choisir la pièce à poser. Un tour se compose donc de deux actions qui s’effectuent dans l’ordre : poser la pièce que l’adversaire nous donne et choisir la pièce que l’adversaire devra poser à son tour.
Lors du premier tour, le joueur ne fait que le choix de la pièce à jouer par l’adversaire.
Le but de notre programme est de faire office d’intelligence artificielle pour Quarto. Pour cela, nous allons diviser notre développement en composants :
Aujourd’hui nous allons modéliser notre jeu. Dans le prochain article, nous réaliserons l’algorithme de séléction d’un coup.
Dans le package n25/quarto je vais réunir l’ensemble des modèles du jeu.
Le plateau est une grille 4×4 contenant les pièces du jeu. On peut avoir la déclaration de type suivante :
type Board [4][4]Piece
Cette déclaration nous permettra par la suite d’attacher des fonctions au plateau, à la manière de méthodes sur un objet. En fait en Go, il n’y a pas directement d’objets. À la place, on peut associer des méthodes à des types de données. Ainsi on aura d’un coté les données et d’un autre les opérations que l’on peut y appliquer.
Dans la déclaration précédente, on a laisser entendre qu’un type Piece existait.
Voici la déclaration de ce dernier :
type Piece uint8
L’opération qui sera la plus fréquente sera de détecter si plusieurs pièces partagent un caractère commun. Pour cela, j’ai déjà en tête d’utiliser le ET booléen mais nous y reviendrons.
Ainsi, chaque bit représente un caractère : 1 bit pour grande pièce, 1 bit pour petite pièce, etc. Attention, ce n’est pas 1 bit à 1 pour grande pièce et le même bit à 0 pour une petite pièce…
Pour contruire une pièce, on va utiliser une série de constantes :
const (
PIECE_EMPTY = 0
PIECE_TALL = 1
PIECE_SMALL = 2
PIECE_BLACK = 4
PIECE_WHITE = 8
PIECE_ROUND = 16
PIECE_SQUARE = 32
PIECE_FULL = 64
PIECE_SPARSE = 128
)
Construire une pièce devient aussi simple que cela :
Piece(PIECE_TALL | PIECE_BLACK | PIECE_ROUND | PIECE_FULL)
Ici T() est une conversion vers le type T, dans notre cas il s’agit de Piece. La
syntaxe de conversion fonctionne avec d’autres types, référez vous à la documentation du
langage (partie [conversions][go-convertions]) pour plus d’informations.
Pour représenter les pièces à poser, on pourrait utiliser une liste chainée, disponible
dans le package container/list. Cependant vu la taille des données a manipuler,
je préfère utiliser une structure plus légère à laquelle j’ajouterais uniquement les
opérations qui me seront utiles.
type Stash [16]Piece
On peut réunir les éléments du jeu dans un même type.
type Game struct {
Board Board
Stash Stash
}
Le type Game correspond donc à une structure contenant deux champs nommés : Board
et Stash, respectivement de types Board et Stash.
Enfin, un coup est représenté par une position sur la grille et l’indice de la pièce à jouer dans l’ensemble des pièces disponibles. La position est elle même représentée par des coordonnées sur le plateau comprisent entre 0 et 3.
type Position struct {
i, j uint8
}
type Move struct {
Pos Position
Idx uint8
}
Jusqu’à présent, chaque champ de structure, chaque type commençait par une majuscule. La convention en Go est que les noms commençant par une majuscule sont exportés hors du package. Cette convention est vérifiée par le compilateur.
Il est intéressant de voir que l’approche bas niveau de Go permet d’avoir une occupation
mémoire totalement sous contrôle. Voici un bilan de l’espace occupé par un jeu (Game) :
Piece : 8 bits soit 1 octetBoard : 128 bits soit 16 octetsStash : 128 bits soit 16 octetsGame : 256 bits soit 32 octetsSur une machine 64 bits, la représentation d’un état du jeu occupera théoriquement un espace équivalent à 4 entiers.
Chaque coup (Move) se représente sur 24 bits soit 3 octets.
À présent que nos types sont déclarés, intéressons nous à leur construction. Go propose plusieurs moyens d’allouer de la mémoire.
Dans un premier temps on peut utiliser le mot clé new. Par exemple l’instruction
suivante va allouer l’espace nécessaire à un plateau et retourner un pointeur vers
celui-ci :
new(Board)
Ensuite, il est possible d’allouer de nouveaux objets à chaque exécution d’une portion de code. C’est à dire que si une allocation se trouve dans une boucle alors pour chaque passage dans la boucle, une nouvelle allocation est effectuée.
On utilise, entre autres, les notations suivantes :
// Tableaux à n éléments de type T
[n]T{x1, x2, ... xn} // Entièrement initialisé
[n]T{x1, x2} // Premiers indices initialisés, reste à zéro
[n]T{4: x1, 5: x2} // Indices 4 et 5 initialisés, reste à zéro
[n]T{} // Tous les indices à zéro
[...]T{x1, x2, ... xn} // Le compilateur devine la taille
// Structures
Position{i: 1, j: 2} // Champs tous spécifiés
Position{1, 2} // Sans information de champs
Position{i: 1} // Champs manquants à zéro
// Tableaux de structures, notations équivalentes
[...]Position
[...]Position{Position{1, 2}, Position{0, 0}}
[...]*Position
[...]*Position{&Position{1, 2}, &Position{0, 0}}
// Maps (on y reviendra peut être plus tard)
map[string]int{"key": 5, "yek": -5}
// Slices
// idem tableaux sans taille spécifiée, càd []
Enfin, et nous en reparlerons dans un futur article, il existe le mot clé make qui
s’applique uniquement sur les types de données : slice, map et channel.
Go dispose d’un système d’inférence de type permettant de déduire le type d’une variable
lors de sont assignation. Il est toutefois possible de déclarer une variable avec le mot
clé var afin de la typer explicitement.
Voici quelques exemples de déclaration :
var board *Board // Déclaration + typage
var board *Board = new(Board) // Déclaration + typage + assignation
var board = new(Board) // Déclaration + assignation + inférence
board := new(Board) // Déclaration implicite + assignation + inférence
Les fonctions sont des citoyens de première classe en Go. L’extrait suivant est donc bien valide et présente la déclaration d’une variable de type fonction. Cette variable est assignée avec une fonction anonyme puis utilisée juste après.
var plus_5 func(i int) int
plus_5 = func(x int) int { return 5 + x }
plus_5(5)
Les fonctions, peuvent bien entendu être déclarées de manière plus classique, avec un nom. Attention seul les noms commençant par une majuscule seront visibles hors du package…
func MakePiece(c1, c2, c3, c4 uint8) Piece {
return Piece( c1 | c2 | c3 | c4 )
}
import "errors"
// Plusieurs variables de retour + déclaration
func MakePiece(c1, c2, c3, c4 uint8) (err error, p Piece) {
p = Piece( c1 | c2 | c3 | c4 )
if !p.IsValid() {
err = errors.New("Piece is not valid.")
}
return
}
Dans l’exemple précédent, on a vu l’appel de fonction p.IsValid(). Cette notation
ressemble fort à l’appel d’une méthode sur un objet dit receveur… Pour déclarer
ce type de fonction, voici comment faire :
func (p Piece) IsValid() bool {
return p == 0 ||
((p & PIECE_TALL) > 0) != ((p & PIECE_SMALL) > 0) &&
((p & PIECE_BLACK) > 0) != ((p & PIECE_WHITE) > 0) &&
((p & PIECE_ROUND) > 0) != ((p & PIECE_SQUARE) > 0) &&
((p & PIECE_FULL) > 0) != ((p & PIECE_SPARSE) > 0)
}
En Go, le passage de paramètre se fait par valeur. Ainsi, lorsque l’on passe des types complexes en paramètre, c’est une copie qui est passée. C’est la même choses pour la donnée retournée. On peut utiliser les références pour éviter de la copie inutile, nous le verrons plus tard.
Maintenant que vous connaissez un peu mieux Go, voici les constructeurs associés aux types de données ci-dessus.
Pour créer un plateau vide, il suffit de créer une valeur de type Board. En Go les
valeurs numériques sont initialisées à zéro. Ainsi notre représentation dans son
état initial correspond à un plateau vide.
var emptyBoard Board = Board{}
On a déjà vu le moyen de construire une valeur de type Piece au moyen d’une
conversion : Piece(). Cependant il est plus simple de passer par une fonction de
fabrication dédiée afin d’avoir plus de contrôle sur le processus de création. C’est
également vrai pour le plateau de jeu… Nous ne ferons pas de vérification lors de
la création d’une pièce :
func MakePiece(c1, c2, c3, c4 uint8) Piece {
return Piece( c1 | c2 | c3 | c4 )
}
Notre modèle Stash doit être initialisé avec les 16 pièces du jeu.
func MakeFullStash() (s Stash) {
s[0] = MakePiece(PIECE_TALL, PIECE_BLACK, PIECE_ROUND, PIECE_FULL)
s[1] = MakePiece(PIECE_TALL, PIECE_BLACK, PIECE_ROUND, PIECE_SPARSE)
s[2] = MakePiece(PIECE_TALL, PIECE_BLACK, PIECE_SQUARE, PIECE_FULL)
s[3] = MakePiece(PIECE_TALL, PIECE_BLACK, PIECE_SQUARE, PIECE_SPARSE)
s[4] = MakePiece(PIECE_TALL, PIECE_WHITE, PIECE_ROUND, PIECE_FULL)
s[5] = MakePiece(PIECE_TALL, PIECE_WHITE, PIECE_ROUND, PIECE_SPARSE)
s[6] = MakePiece(PIECE_TALL, PIECE_WHITE, PIECE_SQUARE, PIECE_FULL)
s[7] = MakePiece(PIECE_TALL, PIECE_WHITE, PIECE_SQUARE, PIECE_SPARSE)
s[8] = MakePiece(PIECE_SMALL, PIECE_BLACK, PIECE_ROUND, PIECE_FULL)
s[9] = MakePiece(PIECE_SMALL, PIECE_BLACK, PIECE_ROUND, PIECE_SPARSE)
s[10] = MakePiece(PIECE_SMALL, PIECE_BLACK, PIECE_SQUARE, PIECE_FULL)
s[11] = MakePiece(PIECE_SMALL, PIECE_BLACK, PIECE_SQUARE, PIECE_SPARSE)
s[12] = MakePiece(PIECE_SMALL, PIECE_WHITE, PIECE_ROUND, PIECE_FULL)
s[13] = MakePiece(PIECE_SMALL, PIECE_WHITE, PIECE_ROUND, PIECE_SPARSE)
s[14] = MakePiece(PIECE_SMALL, PIECE_WHITE, PIECE_SQUARE, PIECE_FULL)
s[15] = MakePiece(PIECE_SMALL, PIECE_WHITE, PIECE_SQUARE, PIECE_SPARSE)
return
}
J’en conviens, ce n’est pas très élégant.
Pour les types Game, Move et Position, on peut compter sur la syntaxe qu’on a
déjà vu :
game := Game{Stash: MakeFullStash()}
move := Move{Position{0, 0}, 10}
Essayons maintenant de créer une fonction qui appliquera un coup sur un jeu…
func (m Move) ApplyTo(pieceIndex uint8, g Game) Game {
piece := g.Stash.PickPieceAtIndex(pieceIndex)
g.Board.DropPieceAt(m.Pos, piece)
return g
}
Cette fonction qui est applicable a un mouvement va appliquer ce mouvement sur un jeu.
Pour cela il faut également préciser sur quelle pièce on applique le coup.
Chaque appel à ApplyTo créé un nouvel élément de type Game en mémoire, ce n’est
pas un problème dès lors que c’est maîtrisé.
Comme vous le voyez ApplyTo s’appuie sur deux fonctions : PickPieceAtIndex et
DropPieceAt. Ces deux fonctions, contrairement à la précédente vont modifier en
place la valeur du receveur, ne pas créer de copie. Pour cela on va utiliser la
référence du receveur lors de la déclaration de la méthode.
func (s *Stash) PickPieceAtIndex(i uint8) (p Piece) {
p = s[i]
s[i] = PIECE_EMPTY
return
}
func (b *Board) DropPieceAt(pos Position, p Piece) {
b[pos.i][pos.j] = p
}
Le fonctionnement est similaire aux pointeurs que l’on retrouve en C à l’exception que
le déréférencement se fait automatiquement. Il n’y a pas, en Go, d’accesseur ->.
Pour chaque type de donnée T, il existe un type « référence vers T » noté *T. Pour
chaque valeur de type T on peut obtenir une référence vers celui-ci grâce à
l’opérateur &, par exemple &Position{0, 3}. De la même manière on peut passer de la
référence à l’objet :
var pos Position = Position{0, 3}
var ref *Position = &pos
pos == *ref
Dans les exemples précédents, on utilise un passage par référence afin de modifier le receveur.
Afin de pouvoir proposer un coup, le serveur doit être capable de proposer un coup. Pour cela on va réaliser une méthode permettant d’obtenir une liste de coups depuis un état de jeu et une pièce à jouer.
func (g *Game) PossibleMoves(pieceIndex uint8) []Move {
count := int(g.Board.EmptyCellCount()) * (int(g.Stash.PieceCount()) - 1)
moves := make([]Move, count)
var i, j, k, n uint8
for k = 0; k < 16; k++ {
if g.Stash[k] != PIECE_EMPTY && k != pieceIndex {
for i = 0; i < 4; i++ {
for j= 0; j < 4; j++ {
if g.Board[i][j] == PIECE_EMPTY {
moves[n] = Move{Position{i, j}, k}
n++
}
}
}
}
}
return moves
}
Cette méthode retourne un slice, une structure semblable aux tableaux mais permettant une utilisation plus avancée. Un slice est en fait un triplet composé d’une référence vers un tableau, d’une taille et d’une capacité. Une syntaxe spécifique permet de jouer avec les éléments de ce triplet.
Le nombre maximum de coup possible pour un état est de 240. En effet, lorsque le plateau
est vide, on a 1 pièce donnée à poser sur 1 emplacement parmi 16 et 1 pièce à choisir
parmi les 15 restantes. On a donc 16 x 15 coups possibles. Ainsi, on peut utiliser des
compteurs de type uint8 (i, j, k et n).
Pour simplifier l’algorithme, on pourrait créer un tableau de taille 240 et retourner uniquement le slice contenant les coups. Ici, je préfère calculer à l’avance le nombre de coups afin d’allouer le minimum de mémoire.
Les fonctions EmptyCellCount et PieceCount sont laissées en exercice.
Pour aiguiller l’intelligence artificielle que nous allons réaliser, il faut être en mesure d’évaluer un état du jeu. Dans notre cas, nous allons partir sur une évaluation très basique : l’état gagnant. Cet état sera le but à atteindre pour notre joueur fictif.
func (b *Board) IsWinningAt(pos Position) bool {
return b.isRowWinningAt(pos) ||
b.isColWinningAt(pos) ||
b.isDiag1WinningAt(pos) ||
b.isDiag2WinningAt(pos)
}
func (b *Board) isRowWinningAt(pos Position) bool {
return (b[pos.i][0] & b[pos.i][1] & b[pos.i][2] & b[pos.i][3]) > 0
}
func (b *Board) isColWinningAt(pos Position) bool {
return (b[0][pos.j] & b[1][pos.j] & b[2][pos.j] & b[3][pos.j]) > 0
}
func (b *Board) isDiag1WinningAt(pos Position) bool {
return (pos.i + pos.j == 3) && (b[0][3] & b[1][2] & b[2][1] & b[3][0] > 0)
}
func (b *Board) isDiag2WinningAt(pos Position) bool {
return (pos.i == pos.j) && (b[0][0] & b[1][1] & b[2][2] & b[3][3] > 0)
}
Ici, vous pouvez voir que je fais le choix d’utiliser des fonctions auxiliaires privées. Elles commencent par une lettre minuscule.
Pour finir, mettons en place le choix d’un coup. Parmi les coups possibles, choisissons en un qui ne permettra pas à l’adversaire de gagner. Bien sur il est toujours possible que l’adversaire ne laisse que des coups perdants pour notre joueur fictif.
func (g *Game) PlayWith(pieceIndex uint8) (Move, bool) {
moves := g.PossibleMoves(pieceIndex)
// If there is a wining move, just do it
for _, move := range moves {
game := move.ApplyTo(pieceIndex, *g)
if game.IsWinningAt(move.Pos) {
return move, true
}
}
MyMoves:
for _, move := range moves {
game := move.ApplyTo(pieceIndex, *g)
opponentMoves := game.PossibleMoves(move.Idx)
for _, opponentMove := range opponentMoves {
opponentGame := opponentMove.ApplyTo(move.Idx, game)
if opponentGame.IsWinningAt(opponentMove.Pos) { continue MyMoves }
}
return move, false
}
return moves[0], false
}
Cette fonction introduit deux nouveautés : itérateurs et labels. Les itérateurs
permettent de parcourir un slice grâce au mot clé range. On peut également voir une
nouvelle forme de for qui n’utilise qu’une range-clause. Les labels permettent
d’utiliser des instructions comme break ou continue depuis une boucle imbriquée.
Cette fonction retourne également un booléen indiquant si un coup gagnant est retourné.
On peut tester cet algorithme en faisant s’affronter deux joueurs fictifs.
import "fmt"
func main() {
game := Game{Stash: MakeFullStash()}
move := game.PlayWith(0)
game = move.ApplyTo(0, game)
fmt.Printf("Play at (%d, %d), give #%d\n", move.Pos.i, move.Pos.j, move.Idx)
o_move := game.PlayWith(move.Idx)
game = o_move.ApplyTo(move.Idx, game)
fmt.Printf("Play at (%d, %d), give #%d\n", o_move.Pos.i, o_move.Pos.j, o_move.Idx)
move = game.PlayWith(o_move.Idx)
game = move.ApplyTo(o_move.Idx, game)
fmt.Printf("Play at (%d, %d), give #%d\n", move.Pos.i, move.Pos.j, move.Idx)
o_move = game.PlayWith(move.Idx)
game = o_move.ApplyTo(move.Idx, game)
fmt.Printf("Play at (%d, %d), give #%d\n", o_move.Pos.i, o_move.Pos.j, o_move.Idx)
...
}
On peut faire de même dans un for pour aller plus loin.
Si vous désirez aller un peu plus loin autour de ce jeu de quarto, vous pouvez :
S’en est terminé pour cette semaine. Dans le prochain article, nous rendrons ce programme plus graphique en réalisant un serveur de jeu et une interface web basée sur Sinatra. Voila un petit teaser pour ce prochain article :-)
En attendant, j’espère vous avoir montré que Go est un langage plutôt simple. Sa spécification est concise et je vous invite vivement à la consulter. Vous pouvez également consulter le code de cet article sur notre dépôt Github synbioz/article-go2.
L’équipe Synbioz.
Libres d’être ensemble.
