CCINP 2024¶
Note
- Ce corrigé peut contenir des erreurs ! Merci de me les signaler si vous en trouvez
- Un code complet permettant de jouer à l'awale en joueur contre joueur ou contre une IA (algorithme min max) et crée au fil des questions est donné en fin de corrigé
Enoncé¶
Partie I - Présentation et règles¶
Question 1¶
Alice peut choisir de jouer n'importe quelle case non vide de son camp, donc ici les cases 2, 4 et 5
Question 2¶
La situation initiale est :
1 | 0 | 1 | 0 | 1 | 2 |
0 | 0 | 2 | 0 | 16 | 5 |
Voici les différentes configurations obtenues selon le coup joué :
- Si Alice joue la case 2, son gain est nul
1 | 0 | 1 | 0 | 1 | 2 |
0 | 0 | 0 | 1 | 17 | 5 |
- Si Alice joue la case 4 elle récolte les cases 7 (3 graines), 8 (2 graines) et 9 (3 graines) pour un gain de 8:
2 | 1 | 0 | 0 | 0 | 4 |
1 | 1 | 3 | 1 | 0 | 7 |
- Si Alice joue la case 5, son gain est nul
1 | 1 | 2 | 1 | 2 | 3 |
0 | 0 | 2 | 0 | 16 | 0 |
Question 3¶
Dans les deux situations, Alice ne peut jouer que la case 5.
- Dans la première situation, on obtient :
0 | 2 | 2 | 2 | 2 | 2 |
0 | 0 | 0 | 0 | 0 | 0 |
Mais la récolte d'Alice affame alors son adversaire et donc le coup n'est pas valide !
- Dans la seconde situation, on obtient :
1 | 0 | 0 | 0 | 0 | 0 |
0 | 0 | 0 | 0 | 0 | 0 |
Car Alice peut alors récolter les cases 6 à 10 (qui contiennent chacune 2 graines) pour un gain de 10.
Partie II - Programmation de la structure du jeu¶
Question 4¶
def tour_joueur1(jeu):
'''Renvoie True si c'est le tour du joueur 1, False sinon.'''
# jeu['n'] est nombre de tour déjà joués c'est le tour du joueur 1 lorsque jeu['n'] est pair
return jeu['n'] % 2 == 0
Question 5¶
def tourner_plateau(jeu):
'''Ne renvoie rien et modifie le plateau pour inverses les cases des joueurs 1 et 2'''
jeu['plateau'][0:6], jeu['plateau'][6:12] = jeu['plateau'][6:12], jeu['plateau'][0:6]
Question 6¶
Au plus, une case contient la totalité des graines donc 48. Donc 6 bits sont nécessaires pour stocker le nombre de graines de chaque case comme \(2^6 = 64\), on peut représenter sur 6 bits les entiers de \(0\) à \(65\).
Question 7¶
def copie(jeu):
'''Renvoie une copie du dictionnaire jeu'''
copie_jeu = {}
copie_jeu['joueur1'] = jeu['joueur1']
copie_jeu['joueur2'] = jeu['joueur2']
copie_jeu['score'] = jeu['score'].copy()
copie_jeu['n'] = jeu['n']
copie_jeu['plateau'] = jeu['plateau'].copy()
return copie_jeu
Question 8¶
def deplacer_graines(plateau, case):
a_semer = plateau[case]
plateau[case] = 0
# La prochaine position où on va semer
pos = (case + 1) % 12
while a_semer != 0:
plateau[pos] += 1
a_semer -= 1
pos = (pos + 1) % 12
# On ne doit pas semer dans la case initiale
if (pos == case):
pos = (pos + 1) % 12
return (pos-1) % 12
Note
On pouvait aussi utiliser la fonction d'initialisation awale_jcj donnée dans l'énoncé pour initialiser la copie et rensuite recopier ensuite les éléments différents.
Question 9¶
def case_ramassable(plateau, case):
'''Renvoie True si la case est ramassable, False sinon'''
return (6 <= case <= 11) and (2 <= plateau[case] <= 3)
Question 10¶
def ramasser_graines(plateau, case):
'''Ramasse les graines de la case et renvoie le nombre de graines ramassées'''
# le cas de base
if not case_ramassable(plateau, case):
return 0
# l'appel récursif
recolte = plateau[case]
plateau[case] = 0
return recolte + ramasser_graines(plateau, case - 1)
Question 11¶
def test_famine(plateau, case):
'''Renvoie True lorsque la récolte ne conduit pas à la famine de l'adversaire'''
copie_plateau = plateau.copy()
derniere_case = deplacer_graines(copie_plateau, case)
recolte = ramasser_graines(copie_plateau, derniere_case)
# On parcourt les cases de l'adversaire si l'une contient des graines, il n'y a pas famine
for i in range(6, 12):
if copie_plateau[i] != 0:
return True
return False
Question 12¶
On a surligné la ligne à compléter (on vérifie simplement que les 3 conditions de l'énoncé sont valides)
def test_case(plateau, case):
'''Vérfie si la case choisie par le joueur est acceptable
renvoie True si la case est acceptable, False sinon'''
condition3 = test_famine(plateau, case)
# case acceptable
test = (0 <= case <= 5) and (plateau[case] != 0) and condition3
return test
Question 13¶
def cases_possibles(jeu):
'''Renvoie la liste des cases jouables'''
plateau = jeu['plateau']
return [i for i in range(6) if test_case(plateau, i)]
Question 14¶
def tour_suivant(jeu):
'''Renvoie True si le jeu peut continuer'''
# On vérifie les conditions de fin de partie (voir page 9 du sujet)
# 1. Un joueur a récolté au moins 25 graines
if jeu['score'][0] >= 25 or jeu['score'][1] >= 25:
return False
# 2. Le nombre de tours joués >= 100
if jeu['n']>=100:
return False
# 3. Il reste moins de 3 graines sur le plateau
reste = 0
for graines in jeu['plateau']:
reste += graines
if reste <= 3:
return False
# 4. Le joueur actif n'a pas de coup valide
if len(cases_possibles(jeu)) == 0:
return False
return True
Question 15¶
def tour_jeu(jeu, case):
plateau = jeu['plateau']
if test_case(plateau, case): # La case jouée est acceptable
# Semer et récupérer la derniere case atteinte
derniere_case = deplacer_graines(plateau, case)
# Récolter depuis la derniere case
graines_gagnees = ramasser_graines(plateau, derniere_case)
if tour_joueur1(jeu):
jeu['score'][0] += graines_gagnees
else:
jeu['score'][1] += graines_gagnees
jeu['n'] += 1
tourner_plateau(jeu)
return tour_suivant(jeu)
else:
print("La case choisie n'est pas valide !")
return True
Question 16¶
def gagnant(jeu):
# Suivant le joueur actif on regarde quelle partie du plateau ramsser
if tour_joueur1(jeu):
for i in range(0, 6):
jeu['score'][0] += jeu['plateau'][i]
for i in range(6, 12):
jeu['score'][1] += jeu['plateau'][i]
else:
for i in range(6, 12):
jeu['score'][0] += jeu['plateau'][i]
for i in range(0, 6):
jeu['score'][1] += jeu['plateau'][i]
if jeu['score'][0] > jeu['score'][1]:
return jeu['joueur1']
elif jeu['score'][0] < jeu['score'][1]:
return jeu['joueur2']
else:
return "égalité"
Partie III - Programmation de l'Intelligence Artificielle (IA)¶
Question 17¶
def gain(jeu, case):
'''Renvoie le nombre de graines gagnées et un nouveau dictionnaire'''
njeu = copie(jeu)
plateau = njeu["plateau"]
# Semer et récupérer la derniere case atteinte
derniere_case = deplacer_graines(plateau, case)
# Récolter depuis la derniere case
graines_gagnees = ramasser_graines(plateau, derniere_case)
if tour_joueur1(jeu):
jeu['score'][0] += graines_gagnees
else:
jeu['score'][1] += graines_gagnees
njeu['n'] += 1
tourner_plateau(njeu)
return graines_gagnees, njeu
Question 18¶
Alice jouera la case 5 (branche centrale), en effet la valeur de jeu remontée pour cette branche est 2 (elle gagne 2 graines et Bob ne peut obtenir aucun gain au coup suivant). La branche gauche remonte une valeur de jeu nulle (elle gagne 4 graines, mais un des coups suivants de Bob lui permet aussi de gagner 4 graines) et il en est de même pour la branche droite.
Question 19¶
Les lignes qui devaient être complétées sont surlignées
def Negawale(jeu, profondeur_max, profondeur):
#Ce sont les conditions décrites à la page 12 du sujet : noeud feuille, profondeur maximale atteinte ou autre
# Condition1 : noeud feuille (le jeu se termine)
if (not tour_suivant(jeu)):
if (tour_joueur1(jeu) and gagnant(jeu)==jeu["joueur1"]) or (not tour_joueur1(jeu) and gagnant(jeu)==jeu["joueur2"]):
return 500
elif (tour_joueur1(jeu) and gagnant(jeu)==jeu["joueur2"]) or (not tour_joueur1(jeu) and gagnant(jeu)==jeu["joueur1"]):
return -500
else:
return 0
# Condition 2 : profondeur maximale atteinte
elif profondeur==profondeur_max:
return 0
else:
choix_cases = cases_possibles(jeu)
vals_jeu = []
for case in choix_cases:
g, nouveau_jeu = gain(jeu, case)
p = Negawale(nouveau_jeu,profondeur_max, profondeur+1)
vals_jeu.append([case, g-p])
return max_vals(vals_jeu, profondeur)
Question 20¶
def max_vals(vals_jeu, profondeur):
# On recherche l'indice du maximum
ind_max = 0
for i in range(1, len(vals_jeu)):
# vals_jeu contient des couples (case, valeur de jeu)
if vals_jeu[i][1] > vals_jeu[ind_max][1]:
ind_max = i
# Les deux cas à distinguer (le noeud de départ correspond à une profondeur nulle)
if profondeur==0:
return vals_jeu[ind_max][0]
else:
return vals_jeu[ind_max][1]
Question 21¶
La ligne modifiée par rapport à awale_jcj a été surlignée.
def awale_ia(nom_joueur1, nom_joueur2):
jeu = initialisation(nom_joueur1, nom_joueur2)
jeu_continue = True
while jeu_continue:
affiche(jeu)
case_choisie = Negawale(jeu, 6, 0)
jeu_continue = tour_jeu(jeu, case_choisie)
_ = input("")
return gagnant(jeu)
Question 22¶
Question 23¶
La requête suivante donne le nombre de parties victorieuse pour le joueur 1 lorsque la case "0" (lettre 'a') a été jouée au premier coup, on l'utilise dans une sous requête dans la réponse
SELECT 100.0 * (SELECT COUNT(*)
FROM Partie
WHERE jeu LIKE "a%" AND resultat=1) / COUNT(*)
FROM Partie WHERE jeu LIKE "a%";