Cette page vous donne les différences entre la révision choisie et la version actuelle de la page.
pwnium2k14_prog1 [2014/07/06 15:16] Spl3en créée |
pwnium2k14_prog1 [2017/04/09 15:33] (Version actuelle) |
||
---|---|---|---|
Ligne 41: | Ligne 41: | ||
- | // Se connecte, lit l'état initial du challenge, puis boucle tant que le victoire n'est pas remportée) | + | <code C> |
- | int main (int argc, char **argv) | + | // 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}; | + | { |
- | + | char buffer[1024] = {0}; | |
- | // Initialisation de la connexion | + | |
- | es_init(); | + | // Initialisation de la connexion |
- | sock = es_client_new_from_ip("41.231.53.40", 2048); | + | 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)); | + | // Réception de l'état de base du challenge |
- | grid_fill(buffer, true); | + | es_recv(sock, buffer, sizeof(buffer)); |
- | + | grid_fill(buffer, true); | |
- | // Boucle de jeu | + | |
- | bool victory = false; | + | // Boucle de jeu |
- | while (!victory) { | + | bool victory = false; |
- | // Calcul du meilleur coup par l'IA | + | while (!victory) { |
- | Move result = iterativeDeep (); | + | // Calcul du meilleur coup par l'IA |
- | // Envoi au serveur | + | Move result = iterativeDeep (); |
- | victory = sendMove (result.move); | + | // Envoi au serveur |
- | } | + | victory = sendMove (result.move); |
- | + | ||
- | return 0; | + | |
} | } | ||
+ | |||
+ | return 0; | ||
+ | } | ||
- | // Envoie une commande au serveur, récupère le nouvel état et synchronise notre structure | + | // Envoie une commande au serveur, récupère le nouvel état et synchronise notre structure |
- | bool sendMove (int command) | + | bool sendMove (int command) |
- | { | + | { |
- | char answer[1024] = {0}; | + | char answer[1024] = {0}; |
- | es_send(sock, commands[command], 2); | + | es_send(sock, commands[command], 2); |
- | es_recv(sock, answer, sizeof(answer)); | + | es_recv(sock, answer, sizeof(answer)); |
- | printf("answer = %s\n", answer); | + | printf("answer = %s\n", answer); |
- | return grid_fill (answer, false); | + | 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"); | ||
} | } | ||
- | + | ||
- | // Convertit la grille envoyée par le serveur en tableau 2D de 4*4 int | + | // Une grille est composée de 4 lignes |
- | bool grid_fill (char *msg, int firstMsg) | + | char *endOfLine = msg; |
- | { | + | char *startOfLine[4] = {msg, NULL, NULL, NULL}; |
- | // On ne lit pas le header | + | |
- | if (firstMsg) { | + | // On décompose les 4 lignes en 4 strings |
- | msg = str_bet(msg, "r: Right\n\n\n", "\n\n"); | + | for (int i = 0; i < 3; i++) { |
- | } else { | + | endOfLine = str_pos_after_ptr(endOfLine, "\n"); |
- | msg = str_pos_after_ptr(msg, "\n\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; | ||
} | } | ||
- | |||
- | // 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; | ||
} | } | ||
+ | |||
+ | return win; | ||
+ | } | ||
- | // Convertit la ligne envoyée par le serveur en tableau de 4 int | + | // Convertit la ligne envoyée par le serveur en tableau de 4 int |
- | bool line_fill (int line[4], char *lineStr) | + | bool line_fill (int line[4], char *lineStr) |
- | { | + | { |
- | // 4 nombres à lire par ligne | + | // 4 nombres à lire par ligne |
- | for (int i = 0; i < 4; i++) { | + | for (int i = 0; i < 4; i++) { |
- | lineStr = read_number(lineStr, &line[i]); | + | lineStr = read_number(lineStr, &line[i]); |
- | if (line[i] == 2048) { | + | if (line[i] == 2048) { |
- | return true; | + | return true; |
- | } | + | |
} | } | ||
- | |||
- | return false; | ||
} | } | ||
+ | |||
+ | return false; | ||
+ | } | ||
- | // Lit un nombre dans la ligne | + | // Lit un nombre dans la ligne |
- | char *read_number (char *line, int *entier) | + | char *read_number (char *line, int *entier) |
- | { | + | { |
- | *entier = strtol(line, &line, 10); | + | *entier = strtol(line, &line, 10); |
- | if (*entier == 0) { | + | if (*entier == 0) { |
- | return line + 2; // on saute ". " | + | return line + 2; // on saute ". " |
- | } | + | |
- | + | ||
- | return line; | + | |
} | } | ||
+ | |||
+ | return line; | ||
+ | } | ||
+ | </code> | ||
Ligne 144: | Ligne 145: | ||
Un algorithme [[http://en.wikipedia.org/wiki/Minimax#Minimax_algorithm_with_alternate_moves|Minmax]] élagué par un [[http://en.wikipedia.org/wiki/Alpha-beta_pruning|alpha-beta]] est donc applicable pour ce genre de jeu. | Un algorithme [[http://en.wikipedia.org/wiki/Minimax#Minimax_algorithm_with_alternate_moves|Minmax]] élagué par un [[http://en.wikipedia.org/wiki/Alpha-beta_pruning|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 [[https://github.com/ov3y/2048-AI|Matt Overlan]] : | + | La valeur calculée de chaque noeud peut être calculé en utilisant la solution de [[https://github.com/ov3y/2048-AI|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; | + | |
- | } | + | |
+ | <code C> | ||
+ | // 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; | ||
+ | } | ||
+ | </code> | ||
Ligne 167: | Ligne 169: | ||
- | // Cherche le meilleur coup | + | <code C> |
- | // result : meilleur coup trouvé | + | // Cherche le meilleur coup |
- | // grid : l'état de la grille | + | // result : meilleur coup trouvé |
- | // playerTurn : définit le tour du joueur | + | // grid : l'état de la grille |
- | // depth : profondeur du minmax (nombre de tours précalculés) | + | // playerTurn : définit le tour du joueur |
- | void search (Move *result, int **grid, bool playerTurn, int depth, float alpha, float beta, int positions, int cutoffs) | + | // 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; | + | float bestScore = 0.0; |
- | int **newGrid; | + | int bestMove = -1; |
- | + | int **newGrid; | |
- | if (playerTurn) { | + | |
- | // Player turn | + | if (playerTurn) { |
- | bestScore = alpha; | + | // Player turn |
- | for (int direction = 0; direction < 4; direction++) { | + | bestScore = alpha; |
- | newGrid = grid_clone(grid); | + | for (int direction = 0; direction < 4; direction++) { |
- | if (doMove(newGrid, direction)) { | + | newGrid = grid_clone(grid); |
- | positions++; | + | if (doMove(newGrid, direction)) { |
- | if (grid_isWin(newGrid)) { | + | positions++; |
- | *result = (Move) {.move = direction, .score = 10000, .positions = positions, .cutoffs = cutoffs}; | + | if (grid_isWin(newGrid)) { |
- | return; | + | *result = (Move) {.move = direction, .score = 10000, .positions = positions, .cutoffs = cutoffs}; |
- | } | + | return; |
- | + | } | |
- | if (depth <= 0) { | + | |
- | result->move = direction; | + | if (depth <= 0) { |
- | result->score = ai_eval(newGrid); | + | result->move = direction; |
- | } else { | + | result->score = ai_eval(newGrid); |
- | search (result, newGrid, false, depth - 1, bestScore, beta, positions, cutoffs); | + | } else { |
- | free_grid(newGrid); | + | search (result, newGrid, false, depth - 1, bestScore, beta, positions, cutoffs); |
- | positions = result->positions; | + | free_grid(newGrid); |
- | cutoffs = result->cutoffs; | + | positions = result->positions; |
- | } | + | cutoffs = result->cutoffs; |
- | + | } | |
- | if (result->score > bestScore) { | + | |
- | bestScore = result->score; | + | if (result->score > bestScore) { |
- | bestMove = direction; | + | bestScore = result->score; |
- | } | + | bestMove = direction; |
- | if (bestScore > beta) { | + | } |
- | cutoffs++; | + | if (bestScore > beta) { |
- | *result = (Move) {.move = bestMove, .score = beta, .positions = positions, .cutoffs = cutoffs}; | + | cutoffs++; |
- | return; | + | *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; | ||
- | else { | + | bool available[4][4]; |
- | // computer's turn, we'll do heavy pruning to keep the branching factor low | + | float scores[4][4]; |
- | bestScore = beta; | + | grid_availableCells(available); |
- | + | for (int x = 0; x < 4; x++) { | |
- | bool available[4][4]; | + | for (int y = 0; y < 4; y++) { |
- | float scores[4][4]; | + | if (available[y][x]) { |
- | grid_availableCells(available); | + | n[y][x] = 2; |
- | for (int x = 0; x < 4; x++) { | + | scores[y][x] = -grid_smoothness(grid) + grid_islands(grid); |
- | for (int y = 0; y < 4; y++) { | + | n[y][x] = 0; |
- | 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); | + | // now just pick out the most annoying moves |
- | bool candidates[4][4]; | + | float maxScore = grid_maxValueFloat(scores); |
- | for (int x=0; x<4; x++) { | + | bool candidates[4][4]; |
- | for (int y=0; y<4; y++) { | + | for (int x=0; x<4; x++) { |
- | if (scores[y][x] == maxScore) { | + | for (int y=0; y<4; y++) { |
- | candidates[y][x] = true; | + | if (scores[y][x] == maxScore) { |
- | } | + | candidates[y][x] = true; |
} | } | ||
} | } | ||
- | + | } | |
- | // search on each candidate | + | |
- | for (int x=0; x<4; x++) { | + | // search on each candidate |
- | for (int y=0; y<4; y++) { | + | for (int x=0; x<4; x++) { |
- | if (candidates[y][x]) { | + | for (int y=0; y<4; y++) { |
- | newGrid = grid_clone(grid); | + | if (candidates[y][x]) { |
- | newGrid[y][x] = 2; | + | newGrid = grid_clone(grid); |
- | positions++; | + | newGrid[y][x] = 2; |
- | search(result, newGrid, true, depth - 1, alpha, bestScore, positions, cutoffs); | + | positions++; |
- | free_grid(newGrid); | + | search(result, newGrid, true, depth - 1, alpha, bestScore, positions, cutoffs); |
- | positions = result->positions; | + | free_grid(newGrid); |
- | cutoffs = result->cutoffs; | + | positions = result->positions; |
- | + | cutoffs = result->cutoffs; | |
- | if (result->score < bestScore) { | + | |
- | bestScore = result->score; | + | if (result->score < bestScore) { |
- | } | + | bestScore = result->score; |
- | if (bestScore < alpha) { | + | } |
- | cutoffs++; | + | if (bestScore < alpha) { |
- | *result = (Move) {.move = -1, .score = alpha, .positions = positions, .cutoffs = cutoffs}; | + | cutoffs++; |
- | return; | + | *result = (Move) {.move = -1, .score = alpha, .positions = positions, .cutoffs = cutoffs}; |
- | } | + | return; |
} | } | ||
} | } | ||
} | } | ||
} | } | ||
- | |||
- | *result = (Move) {.move = bestMove, .score = bestScore, .positions = positions, .cutoffs = cutoffs}; | ||
} | } | ||
+ | |||
+ | *result = (Move) {.move = bestMove, .score = bestScore, .positions = positions, .cutoffs = cutoffs}; | ||
+ | } | ||
+ | </code> | ||
On code un wrapper de cette fonction pour effectuer la recherche. | 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. | 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 | + | <code C> |
- | Move iterativeDeep (void) | + | // performs iterative deepening over the alpha-beta search |
- | { | + | Move iterativeDeep (void) |
- | Move best; | + | { |
- | search (&best, n, true, 4, -10000, 10000, 0 ,0); | + | Move best; |
- | return best; | + | search (&best, n, true, 4, -10000, 10000, 0 ,0); |
- | } | + | return best; |
+ | } | ||
+ | </code> | ||
Le flag est renvoyé une fois le nombre 2048 atteint. | Le flag est renvoyé une fois le nombre 2048 atteint. | ||
- | |||