Exercices autour des dames¶
Comment écrire une fonction qui retourne tous les pions qu’une dame peut prendre au jeu de dames.
Après avoir créé un damier, on créé deux fonctions :
une fonction qui retourne les dames et les pions
une fonction qui retourne les pions qu’une dame peut prendre
Il suffira d’appeler la fonction pour toutes les dames du jeu pour connaître tous les pions qu’un joueur peut prendre avec ses dames.
Dans un premier temps, il convient de représenter le damier. On choisira une matrice numpy qu’il faut remplir de valeur numérique :
0: case vide
1: pion blanc
2: pion noir
3: dame blanche
4: dame noir
Les valeurs numériques sont toujours plus efficace que des chaînes de caractères. Elles prennent moins de place en mémoire et les opérations sont plus efficaces.
Partie I : sans les classes¶
[1]:
import numpy as np
def damier_exemple(n: int = 10):
d = np.zeros(
(n, n), dtype=int # il est préférable d'avoir des entiers plutôt que des réels
)
d[0, 0] = 3
d[4, 4] = 2
d[4, 6] = 2
return d
damier = damier_exemple()
print(damier)
[[3 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 2 0 2 0 0 0]
[0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0]]
On cherche maintenant toutes les dames. On retourne une liste de position. Il n’est pas utile de retourner ce que contient chaque case. On peut retrouver cette information avec le damier.
[2]:
def cherche_dames(damier) -> list[tuple[int, int]]:
res = []
for i in range(damier.shape[0]):
for j in range(damier.shape[1]):
if damier[i, j] > 0:
res.append((i, j))
return res
res = cherche_dames(damier)
res
[2]:
[(0, 0), (4, 4), (4, 6)]
Et maintenant, le plat principal, une fonction retourne les possibles prises pour une dame. L’idée est de regarder dans une direction, de chercher un pion ou une dame de couleur différente et une autre case derrière, et plus précisément, la dernière case où la dame peut se poser. La fonction retourne deux positions : [(i1, j1), (i2, j2)]. La première position est le pion ou la dame à prendre. La dame peut alors se poser dans l’intervalle entre ces deux positions, la première exlue.
Comme cet algorithme est le même quelle que soit la direction, nous allons créer deux fonctions, une pour traiter une direction, l’autre pour les quatre.
[3]:
def position_prise_direction(
damier, position_dame: tuple[int, int], direction: tuple[int, int]
) -> list[tuple[int, int]]:
assert damier[position_dame] >= 3, f"ce n'est pas une dame {damier[position_dame]}"
couleur = damier[position_dame] % 2
prise = None
pose = None
i, j = position_dame
di, dj = direction
i += di
j += dj
while i >= 0 and i < damier.shape[0] and j >= 0 and j < damier.shape[1]:
case = damier[i, j]
if prise is None:
if case == 0:
i += di
j += dj
continue
if case % 2 == couleur: # même couleur
return None, None
# sinon on prend
prise = i, j
i += di
j += dj
continue
# si la prise a déjà eu lieu
if case == 0:
# on peut poser la dame
pose = i, j
i += di
j += dj
continue
# sinon
if prise is None:
# pas de case libre derrière donc on ne peut pas prendre
return None, None
return prise, pose
# La boucle est terminée sans passer par une instruction return?
return prise, pose
prise, pose = position_prise_direction(damier, (0, 0), (1, 1))
print(f"prise={prise}, pose={pose}")
prise=(4, 4), pose=(9, 9)
Et la fonction suivante pour traiter les quatre directions :
[4]:
def position_prise(damier, position_dame: tuple[int, int]) -> list[tuple[int, int]]:
res = []
for di in [-1, 1]:
for dj in [-1, 1]:
prise, pose = position_prise_direction(damier, position_dame, (di, dj))
if prise is None:
continue
res.append((prise, pose))
return res
res = position_prise(damier, (0, 0))
print(res)
[((4, 4), (9, 9))]
Partie 2 : Avec les classes¶
Dans cette partie, on construit deux classes Coup et Damier avec pour objectif de déterminer si le fait de commencer est un avantage dans une partie où les deux joueurs jouent de façon aléatoire. Pour y répondre, il faut simuler un grand nombre de parties.
La classe Coup contient au moins deux positions, celle de départ et celle d’arrivée. Elle peut en contenir plus si le pion ou la dame peut en prendre plusieurs.
[5]:
class Coup:
def __init__(self, positions: list[tuple[int, int]]):
self.positions = positions
def __len__(self) -> int:
"Retourne le nombre de positions."
return len(self.positions)
def __str__(self) -> str:
"Appelée implicitement par Python si print(c) où c est un Coup"
return str(self.positions)
def __getitem__(self, i):
"Donne un sens à c[0] où c est de type Coup."
return self.positions[i]
# Vérification rapide.
c = Coup([(0, 0), (3, 3)])
print(c)
[(0, 0), (3, 3)]
Maintenant le Damier:
[6]:
class Damier:
def __init__(self, N: int = 10):
self.damier = np.zeros((N, N), dtype=int)
def __str__(self) -> str:
"Appelée implicitement par Python si print(c) où c est un Coup"
return str(self.damier)
def __len__(self) -> int:
"Retourne la dimension du damier."
return len(self.damier)
def init(self):
"Initialise le damier pour un début de partie."
N = len(self)
for i in range(N):
if i in ((N - 1) // 2, N // 2):
continue
c = 3 if i < N // 2 else 4
for j in range(N):
if (i + j) % 2 == 0:
self.damier[i, j] = c
def joue(self, coup: Coup):
"Joue un coup. On suppose que celui-ci est valide."
for i in range(1, len(coup)):
self.annule(coup[i - 1], coup[i])
self.damier[coup[1]] = self.damier[coup[0]]
self.damier[coup[0]] = 0
def annule(self, p1: tuple[int, int], p2: tuple[int, int]):
"Annule toutes les cases du damier entre deux positions."
di = (p2[0] - p1[0]) // abs(p2[0] - p1[0])
dj = (p2[1] - p1[1]) // abs(p2[1] - p1[1])
for k in range(1, abs(p2[0] - p1[0])):
self.damier[p1[0] + di * k, p1[1] + dj * k] = 0
d = Damier()
d.init()
print(d) # équivalent à print(d.__str__())
[[3 0 3 0 3 0 3 0 3 0]
[0 3 0 3 0 3 0 3 0 3]
[3 0 3 0 3 0 3 0 3 0]
[0 3 0 3 0 3 0 3 0 3]
[0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0]
[4 0 4 0 4 0 4 0 4 0]
[0 4 0 4 0 4 0 4 0 4]
[4 0 4 0 4 0 4 0 4 0]
[0 4 0 4 0 4 0 4 0 4]]
On écrit un test unitaire pour vérifier que la méthode init est valide.
[7]:
def test_init():
d = Damier(4)
d.init()
assert d.damier.tolist() == [
[3, 0, 3, 0],
[0, 0, 0, 0],
[0, 0, 0, 0],
[0, 4, 0, 4],
], f"{d.damier.tolist()}"
test_init()
On fait de même pour la méthode joue.
[8]:
def test_coup():
d = Damier(4)
d.init()
d.joue(Coup([(0, 0), (1, 1)]))
assert d.damier.tolist() == [
[0, 0, 3, 0],
[0, 3, 0, 0],
[0, 0, 0, 0],
[0, 4, 0, 4],
], f"{d.damier.tolist()}"
test_coup()