API tools faq
paste
Advertisement
bkit4s0

[caro] finished

bkit4s0
Jan 28th, 2015
31
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 7.90 KB | None | 0 0
raw download clone embed print report
  1. #include<stdio.h>
  2. #include<stdlib.h>
  3. #define MAX  10
  4. #define SIZE 3
  5.  
  6. struct node
  7. {
  8.     int a[SIZE][SIZE];
  9.     node *next;
  10. };
  11. void assign_matrix(int a[][SIZE], int b[][SIZE])
  12. {
  13.     for (int i = 0; i < SIZE; i++)
  14.     {
  15.         for (int j = 0; j < SIZE; j++)
  16.         {
  17.             a[i][j] = b[i][j];
  18.         }
  19.     }
  20. }
  21. int isbase_case(node *n)
  22. {
  23.     int ar[SIZE][SIZE];
  24.     int val = 0;
  25.     assign_matrix(ar,n->a);
  26.     if((ar[0][0]==1&&ar[0][1]==1&&ar[0][2]==1)||
  27.         (ar[1][0]==1&&ar[1][1]==1&&ar[1][2]==1)||
  28.         (ar[2][0]==1&&ar[2][1]==1&&ar[2][2]==1)||
  29.         (ar[0][0]==1&&ar[1][0]==1&&ar[2][0]==1)||
  30.         (ar[0][1]==1&&ar[1][1]==1&&ar[2][1]==1)||
  31.         (ar[0][2]==1&&ar[1][2]==1&&ar[2][2]==1)||
  32.         (ar[0][0]==1&&ar[1][1]==1&&ar[2][2]==1)||
  33.         (ar[0][2]==1&&ar[1][1]==1&&ar[2][0]==1)
  34.         ||
  35.         (ar[0][0]==2&&ar[0][1]==2&&ar[0][2]==2)||
  36.         (ar[1][0]==2&&ar[1][1]==2&&ar[1][2]==2)||
  37.         (ar[2][0]==2&&ar[2][1]==2&&ar[2][2]==2)||
  38.         (ar[0][0]==2&&ar[1][0]==2&&ar[2][0]==2)||
  39.         (ar[0][1]==2&&ar[1][1]==2&&ar[2][1]==2)||
  40.         (ar[0][2]==2&&ar[1][2]==2&&ar[2][2]==2)||
  41.         (ar[0][0]==2&&ar[1][1]==2&&ar[2][2]==2)||
  42.         (ar[0][2]==2&&ar[1][1]==2&&ar[2][0]==2)
  43.         )
  44.         return 1;
  45.     else
  46.     {
  47.         // check for full board
  48.         int b_break = 0;
  49.         for (int i = 0; i < SIZE && !b_break; i++)
  50.         {
  51.             for (int j = 0; j < SIZE; j++)
  52.             {
  53.                 if(ar[i][j] == 0)
  54.                 {
  55.                     val = 1;
  56.                     b_break = 1;
  57.                 }
  58.             }
  59.         }
  60.         return !val;
  61.     }
  62.     return 0;
  63. }
  64. int isgoal(node *n)
  65. {
  66.     int ar[SIZE][SIZE];
  67.     int val;
  68.     assign_matrix(ar,n->a);
  69.     if((ar[0][0]==1&&ar[0][1]==1&&ar[0][2]==1)||
  70.         (ar[1][0]==1&&ar[1][1]==1&&ar[1][2]==1)||
  71.         (ar[2][0]==1&&ar[2][1]==1&&ar[2][2]==1)||
  72.         (ar[0][0]==1&&ar[1][0]==1&&ar[2][0]==1)||
  73.         (ar[0][1]==1&&ar[1][1]==1&&ar[2][1]==1)||
  74.         (ar[0][2]==1&&ar[1][2]==1&&ar[2][2]==1)||
  75.         (ar[0][0]==1&&ar[1][1]==1&&ar[2][2]==1)||
  76.         (ar[0][2]==1&&ar[1][1]==1&&ar[2][0]==1)
  77.         ||
  78.         (ar[0][0]==2&&ar[0][1]==2&&ar[0][2]==2)||
  79.         (ar[1][0]==2&&ar[1][1]==2&&ar[1][2]==2)||
  80.         (ar[2][0]==2&&ar[2][1]==2&&ar[2][2]==2)||
  81.         (ar[0][0]==2&&ar[1][0]==2&&ar[2][0]==2)||
  82.         (ar[0][1]==2&&ar[1][1]==2&&ar[2][1]==2)||
  83.         (ar[0][2]==2&&ar[1][2]==2&&ar[2][2]==2)||
  84.         (ar[0][0]==2&&ar[1][1]==2&&ar[2][2]==2)||
  85.         (ar[0][2]==2&&ar[1][1]==2&&ar[2][0]==2)
  86.         )
  87.         return 1;
  88.     else
  89.     {
  90.         // check for full board
  91.         int b_break = 0;
  92.         val = -1;
  93.         for (int i = 0; i < SIZE && !b_break; i++)
  94.         {
  95.             for (int j = 0; j < SIZE; j++)
  96.             {
  97.                 if(ar[i][j] == 0)
  98.                 {
  99.                     val = 0;
  100.                     b_break = 1;
  101.                 }
  102.             }
  103.         }
  104.         return val;
  105.     }
  106. }
  107. int static_value(node* n)
  108. {
  109.     int ar[SIZE][SIZE];
  110.     int val = 0;
  111.     int nsum, dsum, ccsum, cpsum;
  112.     int jj;
  113.     int check_done
  114.         ;
  115.     assign_matrix(ar,n->a);
  116.     if((ar[0][0]==1&&ar[0][1]==1&&ar[0][2]==1)||
  117.         (ar[1][0]==1&&ar[1][1]==1&&ar[1][2]==1)||
  118.         (ar[2][0]==1&&ar[2][1]==1&&ar[2][2]==1)||
  119.         (ar[0][0]==1&&ar[1][0]==1&&ar[2][0]==1)||
  120.         (ar[0][1]==1&&ar[1][1]==1&&ar[2][1]==1)||
  121.         (ar[0][2]==1&&ar[1][2]==1&&ar[2][2]==1)||
  122.         (ar[0][0]==1&&ar[1][1]==1&&ar[2][2]==1)||
  123.         (ar[0][2]==1&&ar[1][1]==1&&ar[2][0]==1)
  124.         )
  125.         return 10;
  126.     else if((ar[0][0]==2&&ar[0][1]==2&&ar[0][2]==2)||
  127.         (ar[1][0]==2&&ar[1][1]==2&&ar[1][2]==2)||
  128.         (ar[2][0]==2&&ar[2][1]==2&&ar[2][2]==2)||
  129.         (ar[0][0]==2&&ar[1][0]==2&&ar[2][0]==2)||
  130.         (ar[0][1]==2&&ar[1][1]==2&&ar[2][1]==2)||
  131.         (ar[0][2]==2&&ar[1][2]==2&&ar[2][2]==2)||
  132.         (ar[0][0]==2&&ar[1][1]==2&&ar[2][2]==2)||
  133.         (ar[0][2]==2&&ar[1][1]==2&&ar[2][0]==2)
  134.         )
  135.         return -10;
  136.     else
  137.     {
  138.         // return when node is deep 2
  139.         nsum = 0;
  140.         int b_break;
  141.         b_break = 0;
  142.         for (int i = 0; i < SIZE && !b_break; i++)
  143.         {
  144.             check_done = 0;
  145.             int j;
  146.             for (j = 0; j < SIZE; j++)
  147.             {
  148.                 if(ar[i][j] == 1 || ar[i][j] == 0)
  149.                 {
  150.                     nsum+=ar[i][j];
  151.                     if(j==SIZE-1)
  152.                         b_break = 1;
  153.                 }
  154.                 else
  155.                 {
  156.                     // bug 2: khi no duyet toi cot 3 thi nsum lai reset ve 0 -> done!
  157.                     check_done = 1;
  158.                     break;
  159.                 }
  160.             }
  161.             if(check_done)
  162.                 nsum = 0;
  163.         }
  164.         dsum = 0;
  165.         b_break = 0;
  166.         for (int i = 0; i < SIZE && !b_break; i++)
  167.         {
  168.             check_done =  0;
  169.             for (int j = 0; j < SIZE; j++)
  170.             {
  171.                 if(ar[j][i] == 1 || ar[j][i] == 0)
  172.                 {
  173.                     dsum+=ar[j][i];
  174.                     if(j==SIZE-1)
  175.                         b_break = 1;
  176.                 }
  177.                 else
  178.                 {
  179.                     check_done = 1;
  180.                     break;
  181.                 }
  182.             }
  183.             if (check_done)
  184.                 dsum = 0;
  185.         }
  186.         ccsum = 0;
  187.         jj = 0;
  188.         for (int i = 0; i < SIZE && jj<SIZE; i++)
  189.         {
  190.             if(ar[i][jj] == 1 || ar[i][jj] == 0)
  191.             {
  192.                 ccsum+=ar[i][jj];
  193.                 jj+=1;
  194.             }
  195.             else
  196.                 break;
  197.         }
  198.         cpsum = 0;
  199.         jj = 0;
  200.         for (int i = SIZE-1; i >= 0 && jj<SIZE; i--)
  201.         {
  202.             if(ar[i][jj] == 1 || ar[i][jj] == 0)
  203.             {
  204.                 cpsum+=ar[i][jj];
  205.                 jj+=1;
  206.             }
  207.             else
  208.                 break;
  209.         }
  210.         return nsum+dsum+ccsum+cpsum;
  211.     }
  212.     // no state has value of 2, 1 -> done!
  213. }
  214. void zeros(int a[][SIZE])
  215. {
  216.     for (int i = 0; i < SIZE; i++)
  217.         for (int j = 0; j < SIZE; j++)
  218.             a[i][j] = 0;
  219. }
  220. void generate(node *n, node* val[], int &id, int b_move)
  221. {
  222.     int b[SIZE][SIZE];
  223.     node *t;
  224.     id = 0;
  225.     for (int i = 0; i < SIZE; i++)
  226.         for (int j = 0; j < SIZE; j++) //generate all possible of computer move
  227.             if ((n->a)[i][j] == 0)
  228.             {
  229.                 zeros(b);
  230.                 assign_matrix(b,n->a);
  231.                 if(b_move == 1)
  232.                     b[i][j] = 1;    // bug 5: follow which next move (computer of player) -> done!
  233.                 else if(b_move == 2)
  234.                     b[i][j] = 2;
  235.                 t = (node *)malloc(sizeof(node));
  236.                 assign_matrix(t->a,b);
  237.                 t->next = NULL;
  238.                 val[id++] = t;
  239.             }
  240. }
  241. // bug 3: mini_max must return node*
  242. int mini_max(node *n, int b_move, int deep, node *&temp)
  243. {
  244.     if (isbase_case(n)||deep == 2)
  245.         return static_value(n);
  246.     // generate all possible move
  247.     node* val[MAX];
  248.  
  249.     //int b_move = 0; // b_move must be change when recursive call
  250.     int max, min, id, t1, t2,bb_move;
  251.  
  252.     //bb_move = b_move;
  253.     generate(n,val, id, b_move);
  254.     deep += 1;
  255.     if(b_move == 1)
  256.     {
  257.         b_move = 2;
  258.         max = mini_max(val[0],b_move,deep,temp);
  259.         temp = val[0];
  260.         for (int i = 1; i < id; i++)
  261.             //  bug 7: when recursive call b_move = 2 not back to 1 -> done!
  262.         {
  263.             t1 =  mini_max(val[i],b_move,deep,temp);
  264.             if (t1 > max)
  265.             {
  266.                 max = t1;
  267.                 // return node *
  268.                 temp = val[i];
  269.             }
  270.         }
  271.         return max;
  272.     }
  273.     else if (b_move == 2)
  274.     {
  275.         b_move = 1;
  276.         min = mini_max(val[0],b_move,deep,temp);
  277.         for (int i = 1; i < id; i++)
  278.         {
  279.             t2 =  mini_max(val[i],b_move,deep,temp);
  280.             if (t2 < min)
  281.             {
  282.                 min = t2;
  283.                 // bug 8: can't return temp correct
  284.                 // -> when root is 1 assign temp only max and otherwise
  285.                 //temp = val[i];
  286.             }
  287.         }
  288.         return min;
  289.     }
  290.     else
  291.         return 0;
  292. }
  293. void ar_printf(int a[][SIZE])
  294. {
  295.     for (int i = 0; i < SIZE; i++)
  296.     {
  297.         for (int j = 0; j < SIZE; j++)
  298.         {
  299.             printf("%d ",a[i][j]);
  300.         }
  301.         printf("\n");
  302.     }
  303. }
  304. int main()
  305. {
  306.     int ar[SIZE][SIZE];
  307.     int b_move;
  308.     int x, y, value;
  309.     //node *result;
  310.     zeros(ar);
  311.     b_move = 1;
  312.     node *t;
  313.     // code for game loop
  314.     ar[0][0] = 0;
  315.     ar[0][1] = 0;
  316.     ar[0][2] = 0;
  317.     ar[1][0] = 0;
  318.     ar[1][1] = 0;
  319.     ar[1][2] = 0;
  320.     ar[2][0] = 0;
  321.     ar[2][1] = 0;
  322.     ar[2][2] = 0;
  323.     ar_printf(ar);
  324.     /*t = (node *)malloc(sizeof(node));
  325.     assign_matrix(t->a,ar);
  326.     t->next = NULL;
  327.     printf("%d\n",isbase_case(t));*/
  328.     while(true)
  329.     {
  330.         printf("\nx y >> ");
  331.         scanf("%d %d", &x,&y);
  332.         ar[x][y] = 2;
  333.         printf("\n");
  334.         ar_printf(ar);
  335.         t = (node *)malloc(sizeof(node));
  336.         assign_matrix(t->a,ar);
  337.         t->next = NULL;
  338.         b_move = 1;
  339.         if (isgoal(t) == 1)
  340.         {
  341.             printf("You win!\n");
  342.             break;
  343.         }
  344.         else if(isgoal(t) == -1)
  345.         {
  346.             printf("Game end!\n");
  347.             break;
  348.         }
  349.         else
  350.         {
  351.             printf("wait ...\n");
  352.             // bug 6: return error output
  353.             node *result;
  354.             result = NULL;
  355.             value = mini_max(t,b_move,0,result);
  356.             printf("%d\n",value);
  357.             if (isgoal(result) == 1)    // bug 9: declare in while loop -> done!
  358.             {
  359.                 ar_printf(result->a);
  360.                 printf("You lose!\n");
  361.                 break;
  362.             }
  363.             else
  364.             {
  365.                 assign_matrix(ar,result->a);
  366.                 ar_printf(ar);
  367.             }
  368.         }
  369.         //break;
  370.     }
  371.     // bug 1: all value return 20 -> because no state has value of 2, 1
  372.     // khong the nao sinh ra nua thi tra ve gia tri static --> 10, -10, 0???
  373.     system("pause");
  374.     return 0;
  375. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
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!