Outils d'utilisateurs
Table des matières
Énoncé
Le but de cette épreuve était de battre le jeu 2048 en moins de 3:30. Pour rappel, le but du jeu est d'obtenir le nombre 2048 en fusionnant les numéros qui apparaissent sur le plateau.
Une fois connecté au serveur via netcat, ce dernier renvoyait le challenge de cette manière :
u: Up d: Down l: Left r: Right 2 . . . . . . . . . . . . . 2 . >
Le renvoi d'un des caractères u/d/l/r au serveur renvoyait l'état du nouveau plateau de jeu. Exemple quand on fait u (Up) :
2 . 2 . . . . . . . . . . . . 2 >
Communiquer avec le serveur
Dans un premier temps, il fallait de quoi lire la réponse du serveur, la stocker dans une structure de données puis répondre la direction à choisir.
Voici le code utilisé pour cela :
// Se connecte, lit l'état initial du challenge, puis boucle tant que le victoire n'est pas remportée) int main (int argc, char **argv) { char buffer[1024] = {0}; // Initialisation de la connexion es_init(); sock = es_client_new_from_ip("41.231.53.40", 2048); // Réception de l'état de base du challenge es_recv(sock, buffer, sizeof(buffer)); grid_fill(buffer, true); // Boucle de jeu bool victory = false; while (!victory) { // Calcul du meilleur coup par l'IA Move result = iterativeDeep (); // Envoi au serveur victory = sendMove (result.move); } return 0; } // Envoie une commande au serveur, récupère le nouvel état et synchronise notre structure bool sendMove (int command) { char answer[1024] = {0}; es_send(sock, commands[command], 2); es_recv(sock, answer, sizeof(answer)); printf("answer = %s\n", answer); return grid_fill (answer, false); } // Convertit la grille envoyée par le serveur en tableau 2D de 4*4 int bool grid_fill (char *msg, int firstMsg) { // On ne lit pas le header if (firstMsg) { msg = str_bet(msg, "r: Right\n\n\n", "\n\n"); } else { msg = str_pos_after_ptr(msg, "\n\n"); } // Une grille est composée de 4 lignes char *endOfLine = msg; char *startOfLine[4] = {msg, NULL, NULL, NULL}; // On décompose les 4 lignes en 4 strings for (int i = 0; i < 3; i++) { endOfLine = str_pos_after_ptr(endOfLine, "\n"); *(endOfLine-1) = '\0'; startOfLine[i+1] = endOfLine; } // On lit chacune des lignes bool win = false; for (int i = 0; i < 4; i++) { if (line_fill(n[i], startOfLine[i])) { win = true; } } return win; } // Convertit la ligne envoyée par le serveur en tableau de 4 int bool line_fill (int line[4], char *lineStr) { // 4 nombres à lire par ligne for (int i = 0; i < 4; i++) { lineStr = read_number(lineStr, &line[i]); if (line[i] == 2048) { return true; } } return false; } // Lit un nombre dans la ligne char *read_number (char *line, int *entier) { *entier = strtol(line, &line, 10); if (*entier == 0) { return line + 2; // on saute ". " } return line; }
L'IA
Pour ce qui est de l'IA, après quelques essais à tâtons on se rend compte qu'une IA solide est attendue pour vaincre le jeu en moins de 3:30.
2048 est un jeu qui se joue tour par tour, dont l'espace des états est fini où l'on peut pré-calculer à l'avance les coups joués (Perfect information) en considérant que le coup de l'adversaire est le “2” renvoyé par le serveur à une place aléatoire sur le plateau.
Un algorithme Minmax élagué par un alpha-beta est donc applicable pour ce genre de jeu.
La valeur calculée de chaque noeud peut être calculé en utilisant la solution de Matt Overlan. Une explication claire des différents poids utilisé dans le calcul de valeur du noeud est donnée ici : http://stackoverflow.com/questions/22342854/what-is-the-optimal-algorithm-for-the-game-2048
// Calcule la valeur d'un noeud en fonction de l'état d'une grille float ai_eval (int **grid) { float smoothWeight = 0.1, mono2Weight = 1.0, emptyWeight = 2.7, maxWeight = 1.0; float smoothness = grid_smoothness(grid) * smoothWeight; float monotonicity = grid_monotonicity(grid) * mono2Weight; float emptyness = log(grid_EmptyCells(grid)) * emptyWeight; float maxvalue = log (grid_maxValue(grid)) / log(2) * maxWeight; return smoothness + monotonicity + emptyness + maxvalue; }
L'algorithme minmax, toujours inspiré par la solution de Matt Overlan, a été implémenté comme ceci :
// Cherche le meilleur coup // result : meilleur coup trouvé // grid : l'état de la grille // playerTurn : définit le tour du joueur // depth : profondeur du minmax (nombre de tours précalculés) void search (Move *result, int **grid, bool playerTurn, int depth, float alpha, float beta, int positions, int cutoffs) { float bestScore = 0.0; int bestMove = -1; int **newGrid; if (playerTurn) { // Player turn bestScore = alpha; for (int direction = 0; direction < 4; direction++) { newGrid = grid_clone(grid); if (doMove(newGrid, direction)) { positions++; if (grid_isWin(newGrid)) { *result = (Move) {.move = direction, .score = 10000, .positions = positions, .cutoffs = cutoffs}; return; } if (depth <= 0) { result->move = direction; result->score = ai_eval(newGrid); } else { search (result, newGrid, false, depth - 1, bestScore, beta, positions, cutoffs); free_grid(newGrid); positions = result->positions; cutoffs = result->cutoffs; } if (result->score > bestScore) { bestScore = result->score; bestMove = direction; } if (bestScore > beta) { cutoffs++; *result = (Move) {.move = bestMove, .score = beta, .positions = positions, .cutoffs = cutoffs}; return; } } } } else { // computer's turn, we'll do heavy pruning to keep the branching factor low bestScore = beta; bool available[4][4]; float scores[4][4]; grid_availableCells(available); for (int x = 0; x < 4; x++) { for (int y = 0; y < 4; y++) { if (available[y][x]) { n[y][x] = 2; scores[y][x] = -grid_smoothness(grid) + grid_islands(grid); n[y][x] = 0; } } } // now just pick out the most annoying moves float maxScore = grid_maxValueFloat(scores); bool candidates[4][4]; for (int x=0; x<4; x++) { for (int y=0; y<4; y++) { if (scores[y][x] == maxScore) { candidates[y][x] = true; } } } // search on each candidate for (int x=0; x<4; x++) { for (int y=0; y<4; y++) { if (candidates[y][x]) { newGrid = grid_clone(grid); newGrid[y][x] = 2; positions++; search(result, newGrid, true, depth - 1, alpha, bestScore, positions, cutoffs); free_grid(newGrid); positions = result->positions; cutoffs = result->cutoffs; if (result->score < bestScore) { bestScore = result->score; } if (bestScore < alpha) { cutoffs++; *result = (Move) {.move = -1, .score = alpha, .positions = positions, .cutoffs = cutoffs}; return; } } } } } *result = (Move) {.move = bestMove, .score = bestScore, .positions = positions, .cutoffs = cutoffs}; }
On code un wrapper de cette fonction pour effectuer la recherche. J'ai choisis une profondeur de 4 afin que la recherche ne mette pas trop de temps.
// performs iterative deepening over the alpha-beta search Move iterativeDeep (void) { Move best; search (&best, n, true, 4, -10000, 10000, 0 ,0); return best; }
Le flag est renvoyé une fois le nombre 2048 atteint.
Le code complet est disponible à cette addresse :
