Zenk - Security

Outils d'utilisateurs

Outils du Site

Piste:
pwnium2k14_prog1

Différences

Cette page vous donne les différences entre la révision choisie et la version actuelle de la page.

Lien vers cette vue

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&quot;);+ *(endOfLine-1) = '\0'; 
 + startOfLine[i+1] = endOfLine; 
 + } 
 +  
 + // On lit chacune des lignes 
 + bool win = false; 
 + for (int i = 0; i &lt; 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.
- 
  
  
pwnium2k14_prog1.1404652577.txt.gz · Dernière modification: 2017/04/09 15:33 (modification externe)

Outils de la Page

Sauf mention contraire, le contenu de ce wiki est placé sous la licence suivante : CC Attribution-Share Alike 3.0 Unported
CC Attribution-Share Alike 3.0 Unported Donate Powered by PHP Valid HTML5 Valid CSS Driven by DokuWiki