API tools faq
paste
Nerviie

Connect4

Nerviie
Apr 23rd, 2023 (edited)
984
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 14.34 KB | None | 0 0
raw download clone embed print report
  1. #include <stdlib.h>
  2. #include <stdio.h>
  3. #include <ctype.h>
  4.  
  5. #define INF 512
  6. #define MAX_DEPTH 4
  7.  
  8. typedef struct node{
  9.     char** board;
  10.     int depth;
  11.     int lastMove;
  12.     int utility;
  13.     char player;
  14. }node;
  15.  
  16.  
  17. // typedef struct nodeMont{
  18. //     int num_plays;
  19. //     int num_plays;
  20. //     int depth;
  21. //     node* n;
  22. //     nodeMont* parent;
  23. // }nodeMont;
  24.  
  25.  
  26. node* newNode(char** board, int depth, int lastMove, char player){
  27.     node *n = malloc(sizeof(node));
  28.  
  29.     n->board = (char**)malloc(7*sizeof(char*));
  30.     for(int i = 0; i < 7; i++){
  31.         n->board[i] = (char*)malloc(6*sizeof(char));
  32.     }
  33.  
  34.     for(int i = 0; i < 7; i++){
  35.         for(int j = 0; j < 6; j++){
  36.             n->board[i][j] = board[i][j];
  37.         }
  38.     }
  39.  
  40.     n->depth = depth;
  41.     n->lastMove = lastMove;
  42.     n->player = player;
  43.  
  44.     return n;
  45. }
  46.  
  47. // nodeMont* newNodeMont(char** board, int depth, int mdepth, int lastMove, char player, int np, int nw){
  48. //
  49. //     nodeMont* n;
  50. //     n->n=newNodenewNode(board, depth, lastMove, player);
  51. //     n->num_plays=np;
  52. //     n->num_wins=nw;
  53. //     n->depth=mdepth;
  54. //
  55. //     return n;
  56. // }
  57.  
  58. int max(int a, int b){
  59.     if(b > a){
  60.         return b;
  61.     }
  62.     return a;
  63. }
  64.  
  65. int min(int a, int b){
  66.     if(b < a){
  67.         return b;
  68.     }
  69.     return a;
  70. }
  71.  
  72. char opponent(char player){
  73.     if(player == 'O'){
  74.         return 'X';
  75.     }
  76.     return 'O';
  77. }
  78.  
  79. void printBoard(char** board){
  80.     for(int i = 0; i < 6; i++){
  81.         printf("|");
  82.         for(int j = 0; j < 7; j++){
  83.             printf("%c|", board[j][i]);
  84.         }
  85.         printf("\n");
  86.     }
  87. }
  88.  
  89. void makeMove(int move, char player, char** board){
  90.     for(int i = 5; i >= 0; i--){
  91.         if(board[move-1][i] == ' '){
  92.             board[move-1][i] = player;
  93.             return;
  94.         }
  95.     }
  96.     return;
  97. }
  98. node* generateSuccessor(node* n, int move){
  99.     node *new = newNode(n->board,n->depth+1,move,opponent(n->player));
  100.     for(int i = 5; i >= 0; i--){
  101.         if(new->board[move-1][i] == ' '){
  102.             new->board[move-1][i] = n->player;
  103.             break;
  104.         }
  105.     }
  106.     return new;
  107. }
  108.  
  109. int getHorizontalUtility(char ** board, int i, int j){
  110.     int col = i;
  111.     int row = j;
  112.     int x = 0;
  113.     int o = 0;
  114.  
  115.     for(col=i; col < i+4; col++){
  116.       if(board[col][row] == 'X')
  117.           x++;
  118.       else if(board[col][row] == 'O')
  119.           o++;
  120.     }
  121.  
  122.     if(x==0){
  123.         if(o==3)
  124.             return -50;
  125.         else if (o==2)
  126.             return -10;
  127.         else if (o==1)
  128.             return -1;
  129.         else if (o==4)
  130.             return -INF;
  131.     }
  132.  
  133.     if(o==0){
  134.         if(x==1)
  135.             return 1;
  136.         else if(x==2)
  137.             return 10;
  138.         else if(x==3)
  139.             return 50;
  140.         else if(x==4)
  141.             return INF;
  142.     }
  143.  
  144.     return 0;
  145. }
  146.  
  147. int getVerticalUtility(char ** board, int i, int j){
  148.  
  149.     int utilidade = 0;
  150.     int col = i;
  151.     int x=0;
  152.     int o=0;
  153.  
  154.     // printf("Entramos en vertical con i=%i, j=%i\n",i,j);
  155.     for(int row=j; row < j+4 ;row++){
  156.         if(board[col][row] == 'X')
  157.             x++;
  158.  
  159.         else if(board[col][row] == 'O')
  160.             o++;
  161.     }
  162.  
  163.     if(x==0){
  164.         if(o==3)
  165.             return -50;
  166.         else if (o==2)
  167.             return -10;
  168.         else if (o==1)
  169.             return -1;
  170.         else if (o==4)
  171.             return -INF;
  172.  
  173.     }
  174.  
  175.     if(o==0){
  176.         if(x==1)
  177.             return 1;
  178.         else if(x==2)
  179.             return 10;
  180.         else if(x==3)
  181.             return 50;
  182.         else if(x==4)
  183.             return INF;
  184.     }
  185.  
  186.     return utilidade;
  187. }
  188.  
  189.  
  190. int getPrimaryDiagonalUtility(char ** board, int i, int j){
  191.     int col = i;
  192.     int row = j;
  193.     int x = 0, o = 0;
  194.  
  195.     while(col < i+4){
  196.         if(board[col][row] == 'X'){
  197.             x++;
  198.         }
  199.         if(board[col][row] == 'O'){
  200.             o++;
  201.         }
  202.         col++;
  203.         row++;
  204.     }
  205.  
  206.     if(o == 0){
  207.         if(x == 1){
  208.             return 1;
  209.         }
  210.         if(x == 2){
  211.             return 10;
  212.         }
  213.         if(x == 3){
  214.             return 50;
  215.         }
  216.         if(x == 4){
  217.             return INF;
  218.         }
  219.     }
  220.     if(x == 0){
  221.         if(o == 1){
  222.             return -1;
  223.         }
  224.         if(o == 2){
  225.             return -10;
  226.         }
  227.         if(o == 3){
  228.             return -50;
  229.         }
  230.         if(o == 4){
  231.             return -INF;
  232.         }
  233.     }
  234.     return 0;
  235. }
  236.  
  237. int getSecondaryDiagonalUtility(char ** board, int i, int j){
  238.     int col = i;
  239.     int row = j;
  240.     int x = 0, o = 0;
  241.  
  242.     while(col < i+4){
  243.         if(board[col][row] == 'X'){
  244.             x++;
  245.         }
  246.         if(board[col][row] == 'O'){
  247.             o++;
  248.         }
  249.         col++;
  250.         row--;
  251.     }
  252.  
  253.     if(o == 0){
  254.         if(x == 1){
  255.             return 1;
  256.         }
  257.         if(x == 2){
  258.             return 10;
  259.         }
  260.         if(x == 3){
  261.             return 50;
  262.         }
  263.         if(x == 4){
  264.             return INF;
  265.         }
  266.     }
  267.     if(x == 0){
  268.         if(o == 1){
  269.             return -1;
  270.         }
  271.         if(o == 2){
  272.             return -10;
  273.         }
  274.         if(o == 3){
  275.             return -50;
  276.         }
  277.         if(o == 4){
  278.             return -INF;
  279.         }
  280.     }
  281.     return 0;
  282. }
  283.  
  284. int utility(char** board){
  285.     int utility, temp;
  286.     utility = 0;
  287.  
  288.     for(int i = 0; i < 7; i++){
  289.         for(int j = 0; j < 6; j++){
  290.             if(i < 4){
  291.                 temp = getHorizontalUtility(board,i,j);
  292.                 if(temp >= INF || temp <= -INF){
  293.                     return temp;
  294.                 }
  295.                 utility += temp;
  296.                 if(j < 3){
  297.                     temp = getPrimaryDiagonalUtility(board,i,j);
  298.                     if(temp >= INF || temp <= -INF){
  299.                         return temp;
  300.                     }
  301.                     utility += temp;
  302.                 }
  303.                 else{
  304.                     temp = getSecondaryDiagonalUtility(board,i,j);
  305.                     if(temp >= INF || temp <= -INF){
  306.                         return temp;
  307.                     }
  308.                     utility += temp;
  309.                 }
  310.             }
  311.             if(j < 3){
  312.                 temp = getVerticalUtility(board,i,j);
  313.                 if(temp >= INF || temp <= -INF){
  314.                     return temp;
  315.                 }
  316.                 utility += temp;
  317.             }
  318.  
  319.         }
  320.     }
  321.  
  322.     return utility;
  323. }
  324.  
  325. int isMoveValid(node* n,int movement){
  326.   if (n->board[movement-1][0] == ' ') {
  327.     return 1;
  328.   }
  329.   return 0;
  330. }
  331.  
  332. int isBoardFull(char** board){
  333.     for(int i = 0; i < 7; i++){
  334.         for(int j = 0; j < 6; j++){
  335.             if(board[i][j] == ' '){
  336.                 return 0;
  337.             }
  338.         }
  339.     }
  340.     return 1;
  341. }
  342.  
  343. node* minValue(node* n);
  344. node* maxValue(node* n);
  345.  
  346. int minimaxDecision(node* n){
  347.     node* child;
  348.     child = maxValue(n);
  349.     return child->lastMove;
  350. }
  351. node* maxValue(node* n){
  352.     node* child;
  353.     node* maxChild;
  354.     int maxV = -INF;
  355.     int u = utility(n->board);
  356.     if(u >= INF || u <= -INF || n->depth >= MAX_DEPTH){
  357.         n->utility = u;
  358.         return n;
  359.     }
  360.     if(isBoardFull(n->board)){
  361.         n->utility = 0;
  362.         return n;
  363.     }
  364.     for(int s = 1; s < 8; s++){
  365.       if(isMoveValid(n, s)){
  366.         //child = newNode(generateSuccessorBoard(n->board, s, n->player), n->depth+1, s, opponent(n->player));
  367.         child = generateSuccessor(n,s);
  368.         if(maxV < (minValue(child))->utility){
  369.             maxV = child->utility;
  370.             n->utility = maxV;
  371.             maxChild = child;
  372.         }
  373.       }
  374.     }
  375.     return maxChild;
  376. }
  377. node* minValue(node* n){
  378.     node* child;
  379.     node* minChild;
  380.     int minV = INF;
  381.     int u = utility(n->board);
  382.     if(u >= INF || u <= -INF || n->depth >= MAX_DEPTH){
  383.         n->utility = u;
  384.         return n;
  385.     }
  386.     if(isBoardFull(n->board)){
  387.         n->utility = 0;
  388.         return n;
  389.     }
  390.     for(int s = 1; s < 8; s++){
  391.       if(isMoveValid(n, s)){
  392.         //child = newNode(generateSuccessorBoard(n->board, s, n->player), n->depth+1, s, opponent(n->player));
  393.         child = generateSuccessor(n,s);
  394.         if(minV > (maxValue(child))->utility){
  395.             minV = child->utility;
  396.             n->utility = minV;
  397.             minChild = child;
  398.         }
  399.       }
  400.     }
  401.     return minChild;
  402. }
  403.  
  404.  
  405. node* minAlphaValue(node* n, int alpha, int beta);
  406. node* maxAlphaValue(node* n, int alpha, int beta);
  407.  
  408. int alphaBetaSearch(node* n){
  409.  
  410.     int alpha=-INF;
  411.     int beta=INF;
  412.     node* child = maxAlphaValue(n,alpha,beta);
  413.     return child->lastMove;
  414. }
  415.  
  416.  
  417. node* maxAlphaValue(node* n, int alpha, int beta){
  418.     node* child;
  419.     node* maxChild;
  420.     int maxV = -INF;
  421.     int u = utility(n->board);
  422.     if(u >= INF || u <= -INF || n->depth >= MAX_DEPTH){
  423.         n->utility = u;
  424.         return n;
  425.     }
  426.  
  427.     for(int s = 1; s < 8; s++){
  428.         child = generateSuccessor(n,s);
  429.         if(maxV < (minAlphaValue(child,alpha,beta))->utility){
  430.             maxV = child->utility;
  431.             maxChild = child;
  432.         }
  433.         if(maxV>=beta)
  434.             return maxChild;
  435.         alpha=max(maxV,alpha);
  436.     }
  437.     return maxChild;
  438. }
  439.  
  440. node* minAlphaValue(node* n, int alpha, int beta){
  441.     node* child;
  442.     node* minChild;
  443.     int minV = INF;
  444.     int u = utility(n->board);
  445.     if(u >= INF || u <= -INF || n->depth >= MAX_DEPTH){
  446.         n->utility = u;
  447.         return n;
  448.     }
  449.     for(int s = 1; s < 8; s++){
  450.         child = generateSuccessor(n,s);
  451.         if(minV > (maxAlphaValue(child,alpha,beta))->utility){
  452.             minV = child->utility;
  453.             minChild = child;
  454.         }
  455.         if(minV<=alpha)
  456.             return minChild;
  457.         beta=max(minV,beta);
  458.     }
  459.     return minChild;
  460. }
  461.  
  462.  
  463. //returns a movement
  464.  
  465. //a árvore é geral (tem que ser atualizada pelo back-propagate)
  466.  
  467. //vector<nodeMont> tree;
  468.  
  469. // int ucb(nodeMont child, nodeMont parent){
  470. //     return ( (child->num_wins / child->num_plays) + sqrt(2)* sqrt(log(parent->num_plays)/child->num_plays));
  471. // }
  472. //
  473. // nodeMont selection(nodeMont* n){
  474. //
  475. //     nodeMont selected;
  476. //     int ucb = 0;
  477. //       if(isMoveValid(n->nod->board, s)){
  478. //
  479. //         /*//é precios implementar newNode para struct nodeMont
  480. //         child = generateSuccessor(n,s);*/
  481. //         if(){
  482. //             ucb(child) > ucb;
  483. //             ucb = ucb(child);
  484. //             selected = child;
  485. //         }
  486. //       }
  487. //
  488. //     return selected;
  489. //
  490. // }
  491. //
  492. // nodeMont* expand(nodeMont* n){
  493. //
  494. //     nodeMont* child;
  495. //     //o mov. que vamos tentar é porcolunas.
  496. //
  497. //     int col = 0;
  498. //
  499. //     for(i=tree.size()-1; i>tree.size()-8;i++){
  500. //         if(tree.at(i)->mdepth== (n->mdepth + 1) ){
  501. //             col++;
  502. //         }
  503. //     }
  504. //
  505. //     if(isMoveValid(n->nod->board, col)){
  506. //
  507. //         child->n=generateSuccessor(n,col);
  508. //         child->num_plays=0;
  509. //         child->num_wins=0;
  510. //         tree.push_back(child);
  511. //     };
  512. //
  513. //     return child;
  514. // }
  515. //
  516. // int monteCarloTreeSearch(nodeMont* n){
  517. //
  518. //     nodeMont* leaf;
  519. //     nodeMont* child;
  520. //     int result;
  521. //     int i=0;
  522. //     while(i<100){
  523. //         i++;
  524. //         leaf = Selection(tree);
  525. //         child = Expand(leaf);
  526. //         result = simulate(child);
  527. //         backPropagate(result, child);
  528. //     }
  529. //
  530. //     return
  531. // }
  532. //
  533. // char simulate(nodeMont* n){
  534. //
  535. //     char** board = (char**)malloc(7*sizeof(char*));
  536. //
  537. //     for(int i = 0; i < 7; i++){
  538. //         board[i] = (char*)malloc(6*sizeof(char));
  539. //     }
  540. //
  541. //     int eval = 0;
  542. //     int m;
  543. //     char player = n->n->player;
  544. //
  545. //     board = n->n->board;
  546. //
  547. //     node* startNode = newNode(board, 0, -1, player);
  548. //     while(eval > -INF && eval < INF){
  549. //         if(player == 'X'){
  550. //             printf("CPU turn.\n");
  551. //
  552. //                 m = minimaxDecision(startNode);
  553. //                 makeMove(m, player, board);
  554. //
  555. //
  556. //         }
  557. //         else{
  558. //             n = minimaxDecision(startNode);
  559. //             makeMove(n, player, board);
  560. //         }
  561. //
  562. //         printBoard(board);
  563. //         player = opponent(player);
  564. //         printf("\n");
  565. //         eval = utility(board);
  566. //         startNode = newNode(board, 0, -1, player);
  567. //     }
  568. //
  569. //     //vamos retornar o oponente porque o while atualiçou o player depois de ganhar.
  570. //     return opponent(player);
  571. // }
  572. //
  573. // void backPropagate(char result, nodeMont* n){
  574. //
  575. //     nodeMont* current=n;
  576. //     while(current->depth>0){
  577. //
  578. //         current->num_plays +=1;
  579. //
  580. //         if (current->n->player == result){
  581. //             current->num_wins +=1;
  582. //         }
  583. //
  584. //         current=current->parent;
  585. //     }
  586. //
  587. //     //atualizamos o nó root
  588. //     current->num_plays +=1;
  589. //     if (current->n->player == result){
  590. //         current->num_wins +=1;
  591. //     }
  592. // }
  593.  
  594.  
  595. int main() {
  596.     char** board = (char**)malloc(7*sizeof(char*));
  597.     for(int i = 0; i < 7; i++) {
  598.         board[i] = (char*)malloc(6*sizeof(char));
  599.     }
  600.  
  601.     for(int i = 0; i < 7; i++){
  602.         for(int j = 0; j < 6; j++){
  603.             board[i][j] = ' ';
  604.         }
  605.     }
  606.     //i coluna, j linha
  607.     int optAlg = 0;
  608.     int optTurn = 0;
  609.     char player;
  610.     while(optAlg != 1 && optAlg != 2){
  611.         printf("Que algoritmo quer usar?\n1:Minimax\n2:Minimax com alfa-beta pruning\n");
  612.         scanf("%d", &optAlg);
  613.     }
  614.  
  615.     while(optTurn != 1 && optTurn != 2){
  616.         printf("Quem joga primeiro:\n1:Humano 'O'\n2:Computador 'X'\n");
  617.         scanf("%d", &optTurn);
  618.         if(optTurn == 1){
  619.             player = 'O';
  620.         }
  621.         if(optTurn == 2){
  622.             player = 'X';
  623.         }
  624.     }
  625.  
  626.     int eval = 0;
  627.     int m;
  628.  
  629.     node* startNode = newNode(board, 0, -1, player);
  630.     while(eval > -INF && eval < INF){
  631.         if(player == 'X'){
  632.             printf("CPU turn.\n");
  633.             if(optAlg == 1){
  634.                 m = minimaxDecision(startNode);
  635.             }
  636.             if(optAlg == 2){
  637.                 m = alphaBetaSearch(startNode);
  638.             }
  639.  
  640.         }
  641.         else{
  642.             printf("Human to move: ");
  643.             scanf("%d", &m);
  644.         }
  645.         makeMove(m, player, board);
  646.         printBoard(board);
  647.         player = opponent(player);
  648.         printf("\n");
  649.         eval = utility(board);
  650.        
  651.         startNode = newNode(board, 0, -1, player);
  652.     }
  653.  
  654.     return 0;
  655. }
  656.  
Advertisement
Add Comment
Please, Sign In to add comment
Public Pastes
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!