Go to Hackademy website

Premières lignes de code avec Go

Nicolas Zermati

Posté par Nicolas Zermati dans les catégories back

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 Quarto

Matériel

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 :

  • la taille (grande ou petite),
  • la couleur (noire ou blanche),
  • la forme (ronde ou carré) et
  • le sommet (plein ou creux).

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.

But du jeu et déroulement

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.

Objectifs

Le but de notre programme est de faire office d’intelligence artificielle pour Quarto. Pour cela, nous allons diviser notre développement en composants :

  • les modèles du jeu, chargés de calculer le meilleur coup à jouer pour un état de jeu donné,
  • le serveur de coups, chargé de recevoir l’état d’un jeu via le réseau et de répondre avec un coup à jouer et
  • l’interface (web Ruby), chargée de maintenir un jeu par client et de faire le lien avec le serveur de coups.

Aujourd’hui nous allons modéliser notre jeu. Dans le prochain article, nous réaliserons l’algorithme de séléction d’un coup.

Types de données du jeu

Dans le package n25/quarto je vais réunir l’ensemble des modèles du jeu.

Le plateau

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.

Les pièces

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.

L’ensemble des pièces disponibles

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

Le jeu

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.

Un coup

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.

Espace mémoire occupé

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 octet
  • Board : 128 bits soit 16 octets
  • Stash : 128 bits soit 16 octets
  • Game : 256 bits soit 32 octets

Sur 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.

Tour d’horizon des basiques

Constructeurs

À 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.

Variables

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

Fonctions & méthodes

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.

Retour à Quarto, constructeurs

Maintenant que vous connaissez un peu mieux Go, voici les constructeurs associés aux types de données ci-dessus.

Le plateau

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{}

Les pièces

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 )
}

L’ensemble des pièces restantes

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.

Autres constructeurs

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}

Jouer un coup

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.

Coups possibles

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.

État gagnant

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.

Choix du coup

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é.

Programme de test

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.

Exercices

Si vous désirez aller un peu plus loin autour de ce jeu de quarto, vous pouvez :

  • vous demander ce qu’il se passe lorsqu’il n’y a plus un seul coup à jouer,
  • améliorer l’algorithme de choix d’un coup ou
  • corriger les bugs :-)

Conclusion

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 :-)

Teaser Go article 3

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.

Articles connexes

Ruby, Sidekiq et Crystal

25/07/2019

Dans le cadre d’une application web il nous est tous déjà arrivé de devoir effectuer une tâche assez longue en asynchrone pour ne pas gêner le flux de notre application. En Ruby la solution la plus...

Du dosage à la rouille

13/06/2019

Parlons de la rouille, cette délicieuse sauce qui accompagne nos soupes de poisson. Le bon dosage des ingrédients ravira le palais vos convives ! Pour faire une portion de rouille les ingrédients...

Une brève histoire d'Elixir et Erlang/OTP

31/01/2019

Je développe depuis plusieurs années en Ruby. Depuis mon arrivée chez Synbioz, j’expérimente en plus avec Elixir de façon assez naturelle. En quoi Elixir est-il différent, me demanderez-vous ? Pour...

Écrire une thread pool en Ruby

10/01/2019

Pouvoir exécuter plusieurs tâches en parallèle, que ce soit dans un script ou une application, peut être vraiment très utile, surtout dans le cas où le traitement de ces tâches peut être très long....