Thread: make the computer smarter

  1. #1
    Registered User
    Join Date
    Dec 2009
    Posts
    11

    make the computer smarter

    So here's one for ya. I have this gomoku (5 ina row tic tac toe) code and I want to change it so the computer AI is not super stupid. Currently, all the computer does is put a piece in the first row. It doesn't even try to block. I simply want to make it a little smarter.

    Code:
    /* A simple Tic Tac Toe game */
    
    #include<stdio.h>
    
    #include<stdlib.h> 
    
    char matrix[15][15]; /* the tic tac toe matrix */ 
    
    char check(void);
    
    void init_matrix(void);
    
    void get_player_move(void);
    
    void get_computer_move(void);
    
    void disp_matrix(void); 
    
    int main(void)
    
    {
    
      char done; 
    
      printf("This is the game of Tic Tac Toe. \n");
    
      printf("You will be playing against the computer. \n"); 
    
      done = ' ';
    
      init_matrix (); 
    
      do {
    
        disp_matrix();
    
        get_player_move();
    
        done = check(); /* check if winner */
    
        if (done != ' ') break; /* winner! */
    
        get_computer_move();
    
        done = check(); /* see if winner */
    
      } while( done == ' '); 
    
      if (done == 'X') printf("You won! \n");
    
      else printf("I won!!! \n");
    
      disp_matrix(); /* Show final positions */ 
    
      return 0;
    
    } 
    
    /* Initialize the matrix */
    
    void init_matrix(void)
    
    {
    
      int i, j; 
    
      for (i=0; i<15; i++)
    
        for (j=0; j<15; j++) matrix[i][j] = ' ';
    
    } 
    
    /* Get a player's move */
    
    void get_player_move(void)
    
    {
    
      int x, y; 
    
      printf("Enter X,Y coordinates for your move: ");
    
      scanf("%d%*c%d", &x, &y); 
    
      x--; y--; 
    
      if(matrix[x][y] != ' ') {
    
        printf("Invalid move, try again. \n");
    
        get_player_move();
    
      }
    
      else matrix[x][y] = 'X';
    
    } 
    
    /* Get a move from the computer */
    
    void get_computer_move(void)
    
    {
    
      int i, j; 
    
      for(i=0; i<15; i++) {
    
        for (j=0; j<15; j++)
    
          if (matrix[i][j] == ' ') break;
    
        if (matrix[i][j] == ' ') break;
    
      } 
    
      if (i*j == 225) {
    
        printf("draw\n");
    
        exit (EXIT_SUCCESS);
    
      }
    
      else
    
        matrix[i][j] = '0';
    
    } 
    
    /* Display the matrix on the screen */
    
    void disp_matrix(void)
    
    {
    
      int t; 
    
      for (t=0; t<15; t++) {
    
        printf(" %c | %c | %c | %c | %c | %c | %c | %c | %c | %c | %c | %c | %c | %c | %c ", matrix[t][0], matrix[t][1], matrix[t][2], matrix[t][3], matrix[t][4], matrix[t][5], matrix[t][6], matrix[t][7], matrix[t][8], matrix[t][9], matrix[t][10], matrix[t][11], matrix[t][12], matrix[t][13], matrix[t][14]);
    
        if(t!=14) printf("\n---|---|---|---|---|---|---|---|---|---|---|---|---|---|---\n");
    
      }
    
      printf("\n");
    
    } 
    
    /* See if there is a winner */
    
    char check(void)
    
    {
    
      int i; 
    
      for (i=0; i<4; i++) /* check rows */
    
        if (matrix[i][0] == matrix[i][1] && matrix[i][0] == matrix[i][2] && matrix[i][0] == matrix[i][3] && matrix[i][0] == matrix[i][4]) 
          return matrix[i][0]; 
    
      for (i=0; i<4; i++) /* check columns */
    
        if (matrix[0][i] == matrix[1][i] && matrix[0][i] == matrix[2][i] && matrix[0][i] == matrix[3][i] && matrix[0][i] == matrix[4][i]) 
          return matrix[0][i]; 
    
      /* test diagonals */
    
      if(matrix[0][0] == matrix[1][1] && matrix[1][1] == matrix[2][2] && matrix[2][2] == matrix[3][3])
    
        return matrix[0][0]; 
    
      if(matrix[0][2] == matrix[1][1] && matrix[1][1] == matrix[2][0])
    
        return matrix[0][2]; 
    
      return ' ';
    
    }

  2. #2
    Registered User
    Join Date
    Apr 2006
    Posts
    2,149
    Great. Good luck to ya!

    While you do that you can also shorten the super long lines, by splitting them with a few newlines!

    And you can fix get_player_move(), so that it uses a loop instead of dangerous recursion!
    It is too clear and so it is hard to see.
    A dunce once searched for fire with a lighted lantern.
    Had he known what fire was,
    He could have cooked his rice much sooner.

  3. #3
    Registered User
    Join Date
    Oct 2006
    Location
    Canada
    Posts
    1,243
    So whats the question? "want to make the computer smarter" isnt a question.

    Have you looked at basic AI techniques? That would be the first place to go. You will be able to find AI discussions on a game like tic-tac-toe, which of course can be applied to any of its derivatives (i.e. whatever game your working on.

    The easiest (and therefore slowest) "AI" would be to have the computer look at the current state of the game. So it should check every possible line and see how many more pieces it needs to win. Say there were three lines the opponent (human) was "working on", one which had 4/5 required boxes, the other two had 3/5 and 2/5. It would compare all of these possibilities and realize that it should try and block the 4/5 line before the others, so it should make its turn at that spot.

    This is just the defensive side, but of course you usually dont win by just being defensive. The same technique can be used to try and win (instead of trying to stop the human from winning)--i.e. offensive. So it checks its current possibilities, and chooses the one with minimum required steps to win.

    It should weight both the offensive and defensive states and choose the one that would be the "smartest". I.e. if you need 2 moves to win and the human needs 1, it should obviously choose defensive and stop the human from winning. There is a concept called "ply" which you could look into if you wanted it to "think ahead" (i.e. 2, 5, 10, N moves ahead), versus just thinking of the next one move.

    Also, I didnt read any of your code--absolutely no point in me doing so.

  4. #4
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    What you want to add is some kind of look ahead. The most commonly used algo for that in chess & checkers, and TTT, is mini-max. Preferably, alpha-beta variety (way faster).

    Here's a link to the basics: Minimax Explained - AI Depot

    You can find scads of info on this on the net. It's a very neat algorithm to study.

  5. #5
    Registered User slingerland3g's Avatar
    Join Date
    Jan 2008
    Location
    Seattle
    Posts
    603
    There are other methods such as the 'monte carlo' brute force methods as used in higher level chess code and in the most challenging game to program called "Go".

  6. #6
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Mini-max is brute force. Every leaf on the tree is created and visited. Alpha-beta is very much like mini-max, (just a few extra lines of code), and will generate exactly the same results, but it is significantly smarter, and thus, faster. If a leaf node can't improve the currently best move score, then that leaf node is not visited.

    I don't know what chess programs you've been looking at, but everyone I've heard of, uses Alpha-beta (there are several variants and customizations of A-b). That includes *all* the world's champion chess programs, from Kaissa, up to the current champ, Rybka.

  7. #7
    Registered User
    Join Date
    Dec 2009
    Posts
    11
    thanks for all the informative responses. Unfortunately, I'm still very stumped. I'm not the best programmer in the world and trying to teach myself makes it even harder. I think I get how alpha beta works, but I'm still stumped on the implementation with the existing code I have.

  8. #8
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    How about making it just a little smarter?

    For instance, you make an evalu8 function that favors making moves on more strategic squares, instead of on the edge of the board. If that function returned a score, say from -100 (the opponent will win on his next move), to positive 100 (you have a won game next move). 0 score means the game is approx. equal.

    Now, you need to make a list of the possible moves, and copy the current board into a board2 array, and send that array to your evalu8 function, to get a score.

    You'll save the scores from each move, and the move that made that score, in another small array. After you score each move, you make the one move that scored highest (or randomly choose between moves with equal scores), and even if you just go 1 move (a ply) deep into the move tree, this way, your game will play much better.

    And I guarantee that within 90 days of programming that, you'll be *so* anxious to make it really smarter still, with a full A-b depth first search. I suggest Negamax.

    Your game code may have to be changed, but maybe not much. You still will use the same functions you have now to get moves from the human, display the board, check for a won game, generate possible legal moves from a position, etc.





    You can't find a working source code in C for gomoku? Should be some around.
    Last edited by Adak; 12-01-2009 at 10:22 PM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Can anyone help?
    By javalurnin in forum C Programming
    Replies: 11
    Last Post: 12-02-2009, 06:02 AM
  2. how to make copy of hard drive from HD recorder?
    By happyclown in forum Tech Board
    Replies: 1
    Last Post: 10-12-2009, 09:06 AM
  3. Makefile Problem: None rule to make target
    By chris24300 in forum Linux Programming
    Replies: 25
    Last Post: 06-17-2009, 09:45 AM
  4. What to make?
    By Caldus in forum C++ Programming
    Replies: 4
    Last Post: 04-06-2005, 01:12 PM
  5. How to make my computer beep
    By emglespaul85 in forum C++ Programming
    Replies: 6
    Last Post: 03-04-2005, 07:27 AM