Making Tic Tac Toe Smarter

This is a discussion on Making Tic Tac Toe Smarter within the C Programming forums, part of the General Programming Boards category; I've googled for tic tac toe AI and I know what I have to do but I'm not sure how ...

  1. #1
    Super unModrator
    Join Date
    Dec 2007
    Posts
    321

    Lightbulb Making Tic Tac Toe Smarter

    I've googled for tic tac toe AI and I know what I have to do but I'm not sure how I'm going to....... code it

    All I have to do is give each empty box a 'rank' on the basis of the current set up of the game and then hit the box with the highest rank. I can't think of how I am going to achieve this probably because of the bad design of the game I've made so far.


    • I have used 1D arrays instead of 2D arrays. Now I can't think of a way to access each box , evaluate other boxes in the same row and column and rank that particular box. (right now all it does is picks a random empty box and marks it)
    • I used 'extern' excessively and I've heard that's bad (I don't know why but I find pointers more difficult to use ).



    Anyway, I'm posting my code, let me know what you think and what I should change.

    main.c


    Code:
    #include<stdio.h>
    #include "myheader.h"
       
    char box[9]={'1','2','3','4','5','6','7','8','9'};
    char human,ai;
    int empty[9]={TRUE,TRUE,TRUE,TRUE,TRUE,TRUE,TRUE,TRUE,TRUE};
    int gameover=FALSE,num;
    
    int main()
    {
       char ch;
       /*WELCOME SCREEN*/
       printf("\n\n\n\n*******Tic Tac Toe*******\n");
    
       /*SELECT SYMBOL*/
       printf("\n1) X \n2) O\n");
       printf("\n\nPlease select your symbol(Enter 1 or 2):");
       do
       {
          scanf("%d",&num);
          if(num!=1&&num!=2)
          printf("\nInvalid choice, try again:");
          while( (ch = getchar()) != '\n' && ch != EOF);
       }while(num!=1&&num!=2);
       if(num==1)
       {
          human='X';
          ai='O';
       }
       else
       {
          human='O';
          ai='X';
       }
       /*END SELECT SYMBOL*/
       printf("\n OK, you will play with %c, and my super dumb AI will fill random boxes with %c",human,ai);
       printf("\n\nThis is the playing area:\n");
       
       while(!gameover)
       {
          gui();
          getinput();
          gameover=check();
          if(!gameover)
             playai();
       }
       printf("\nThanks for playing\n");
       return 0;
    }
    ai.c

    Code:
    #include<stdlib.h>
    #include<time.h>
    #include "myheader.h"
    void playai()
    {
       extern char box[9];
       extern int empty[9];
       extern char ai;
       int r;
       do
       {
          srand(time(NULL));
          r=rand()%9;
       }
       while(empty[r]!=TRUE);
          
       empty[r]=FALSE;
       box[r]=ai;
    }
    check.c
    Code:
    #include<stdio.h>
    #include "myheader.h"
    
    int check()
    {
       int x;
       extern char human;
       extern int empty[9];
       extern char box[9];
       for(x=0;x<=6;x+=3)
       {
          if((box[x]==box[x+1])&&(box[x+2]==box[x])&&(box[x]=='X'||box[x]=='O'))
          {
    	 gui();
    	 if(box[x]==human)
    	    printf("\nYou won!");
    	 else
    	    printf("\nAI won!");
    	 return TRUE;
          }
       }
       
       for(x=0;x<=2;x++)
       {
          if((box[x]==box[x+3])&&(box[x+3]==box[x+6])&&(box[x]=='X'||box[x]=='O'))
          {
    	 gui();
    	 if(box[x]==human)
    	    printf("\nYou won!");
    	 else
    	    printf("\nAI won!");
    	 return TRUE;
    
          }
       }
       
       if((((box[0]==box[4])&&(box[4]==box[8]))||((box[2]==box[4])&&(box[4]==box[6])))&&\
    	 (box[4]=='X'||box[4]=='O'))
       {
          gui();
          if(box[4]==human)
    	 printf("\nYou won!");
          else
    	 printf("\nAI won!");
          return TRUE;
        }
        
        for(x=0;x<=8;x++)
        {
           if(empty[x]==TRUE)
    	  return FALSE;
        }
    
        printf("\n Tie!\n");
        return TRUE;
    }
    getinput.c

    Code:
    #include<stdio.h>
    #include "myheader.h"
    
    void getinput()
    {
       int choice;
       extern char human;
       extern char box[9];
       extern int empty[9];
       char ch;
       start:
    	 
             printf("\nEnter your choice(1-9):");
             scanf("%d",&choice);
    	 while( (ch = getchar()) != '\n' && ch != EOF);
    
       if(choice>0 && choice<10 && empty[NUMBER]==TRUE)
       {
          empty[NUMBER]=FALSE;
          /*if(p==1)
             box[NUMBER]='x';
          else
             box[NUMBER]='o';*/
          box[NUMBER]=human;
    
       }
       else
       {
          printf("\nNope, enter again");
          goto start;
       }
    }
    gui.c

    Code:
    #include<stdio.h>
    
    void gui()
    {
       extern char box[9];
       printf("\n\n\n\n");
       printf("\n\t%c\t%c\t%c",box[0],box[1],box[2]);
       printf("\n");
       printf("\n\t%c\t%c\t%c",box[3],box[4],box[5]);
       printf("\n");
       printf("\n\t%c\t%c\t%c",box[6],box[7],box[8]);
       
    }
    myheader.h

    Code:
    #ifndef H_MYHEADER
    #define H_MYHEADER
    #define NUMBER choice-1
    #define TRUE 1
    #define FALSE 0
    void getinput();
    int check();
    void gui();
    void playai();
    #endif

  2. #2
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    I believe the "smartest" TTT program, is simply one that never loses, and always wins, if the other player makes a mistake.

    There are two good ways to get such a program:

    1) The program has look-ahead right to the end of the game. Using that mini-max or alpha beta, look ahead, it calculates the odds of winning, at every move, and selects the move that mathematically gives it the best odds of winning.

    2) You learn the two or three winning tricks (game strategies) of TTT which have the best chances of leading to a win. If you are the first player, you use the appropriate one for your opponent, so he has the best chance of making a mistake.

    If you are the second player, you make sure your program knows how to avoid making those particular mistakes, and thus possibly losing the game.

    Since I had not played TTT since I was a child, and even then, I played it with other young kids, I had no idea that there actually *are* a few winning strategies for TTT. Who knew??

    I'm going to grab some breakfast and a cup of coffee, get my program from my laptop, and I'll post up an example.

    I would recommend a program based on #2, unless you're already familiar with either alpha-beta or mini-max, searching.

  3. #3
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    This is an example of code for #2 type program, mentioned above. The particular trap code is highlighted in blue.

    Code:
    int getCompMove(void)	{
    	char mark;
    	int cmove = 0;
    	int has_corner = 0;
    	/*winOrBlock(), is a dual-purpose function. It's called twice - once to 
    	  see if it can win, in one move, (by switching it's mark). 2nd time, it
    	  finds any needed block, to keep the opponent from winning in one move. 
    	  Before the 2nd call, the mark is switched back to it's original char.
    	*/
    	int winOrBlock(char mark);
    	/*set the "mark", so it works for computers move with X's or O's*/
    	if(player1 == 1)       
    		mark = 'X';   /*computer has the O's, and will have to watch*/
    	else             /*out for the X's, as it works out it's next move*/
    		mark = 'O';   /*the computer has the X's, and must watch out
    							 for the O's as it sorts out it's move*/
    	/* if comp has 1st move, pick a random square */
    	if (player1 == 2 && move_num == 1)	{
    		randomize();
    		cmove = random(9) + 1;
    	}
    	else	{
    		if(player1 == 1)
    			mark = 'O';                /*set mark for offensive pov if comp plays 2nd*/
    		cmove = winOrBlock(mark);
    		
    		mark = mark == 'X' ? 'O' : 'X';  /*switch marks back for defense*/
    		if(!cmove)                           /*no one move win exists, */
    			cmove = winOrBlock(mark); /*looking for a block this time*/
    	}
    	
    	/*if a block is not needed, and human has taken a corner already, 
    	  then take the center, to avoid a trap*/
    	if(!cmove)	{
    		if (brd[1][1]==mark || brd[1][3]==mark || brd[3][1]==mark || brd[3][3]==mark)
    			has_corner = 1;
    		if(has_corner && brd[2][2] == ' ')	/*center is not taken yet*/
    			cmove = 5;                    	/*take the center sqr*/
    		else if(brd[1][1]==mark && brd[3][3]==mark || brd[1][3]==mark && brd[3][1]==mark)	{
    			/*this stops another trap I call "split diagonal"
    			X| |  	This is the state of the board. If O chooses either corner,
    			 |O|  	X chooses the corner to block O's win, and goes on to win.
    			 | |X
    
    			X| |X*	X now has a won game, next move. To stop it, you have to
    			 |O|  	know to make O's second move, must be an *inside* square 
    		       *O| |X 	(2,4,6, or 8 doesn't matter which one), move.
    			*/
    			cmove = rand() &#37; 4 + 1;
    			cmove *= 2; /*must be 2, 4, 6, or 8 only*/
    		}
    		
    			/* code for avoiding "blunted diagonal" trap */
    			/* This is the trap: Opponent has 1st move, took the center sqr.  
    			 | |O 	O's took a corner sqr. X then took another (any other corner), 
    			 |X|     sqr. If O now chooses any inside sqr, X wins:
    			X| |
    
    			 | |O   X wins next move. My opinion is this can only happen when X
    			 |X|O*  has moved twice, O has moved once, and is on the move (so
    			X| |X   move_num == 4, any other move_num voids this trap */
    
    		else if(brd[2][2] == 'X' && move_num == 4)	{
    			if(brd[1][1]=='X' || brd[1][3]=='X' || brd[3][1]=='X' || brd[3][3]=='X')	{
    				/*an empty corner sqr must be chosen by O*/
    				if(brd[1][1] == ' ') 
    					cmove = 1;
    				else if(brd[1][3] == ' ')
    					cmove = 3;
    				else if(brd[3][1] == ' ')
    					cmove = 7;
    				else if(brd[3][3] == ' ')
    					cmove = 9;
    			}
    		}
    		else
    		cmove = rand() % 9 + 1;
    	} 
    	return cmove;
    }
    int winOrBlock(char mark)	{
    	/*this looks for one-move wins 1st, from an offensive point of view, 
    	then it switches the mark, and looks for one-move blocks to save
    	the game, from a defensive point of view*/
    	int c_move = 0;
    	
    	if(brd[1][2]==mark && brd[1][3]==mark && brd[1][1]==' ') c_move = 1;	/*top row*/
    	if(brd[2][2]==mark && brd[3][3]==mark && brd[1][1]==' ') c_move = 1;	/*diagonal*/
    	if(brd[3][1]==mark && brd[2][1]==mark && brd[1][1]==' ') c_move = 1;	/*up 1st column*/
    
    	if(brd[1][1]==mark && brd[1][3]==mark && brd[1][2]==' ') c_move = 2;	/*top row*/
    	if(brd[3][2]==mark && brd[2][2]==mark && brd[1][2]==' ') c_move = 2;	/*up 2nd column*/
    
    	if(brd[1][1]==mark && brd[1][2]==mark && brd[1][3]==' ') c_move = 3;	/*top row*/
    	if(brd[2][2]==mark && brd[3][1]==mark && brd[1][3]==' ') c_move = 3;	/*diagonal*/
    	if(brd[2][3]==mark && brd[3][3]==mark && brd[1][3]==' ') c_move = 3;	/*up 3rd column*/
    
    	if(brd[1][1]==mark && brd[3][1]==mark && brd[2][1]==' ') c_move = 4;	/*up 1st column*/
    	if(brd[2][2]==mark && brd[2][3]==mark && brd[2][1]==' ') c_move = 4;	/*top row*/
    
    	if(brd[1][1]==mark && brd[3][3]==mark && brd[2][2]==' ') c_move = 5;	/*left diagonal*/
    	if(brd[1][2]==mark && brd[3][2]==mark && brd[2][2]==' ') c_move = 5;	/*up 2nd column*/
    	if(brd[1][3]==mark && brd[3][1]==mark && brd[1][3]==' ') c_move = 5;	/*right diagonal*/
    	if(brd[2][1]==mark && brd[2][3]==mark && brd[2][2]==' ') c_move = 5;	/*middle row*/
    
    	if(brd[2][1]==mark && brd[2][2]==mark && brd[2][3]==' ') c_move = 6;	/*middle row*/
    	if(brd[1][3]==mark && brd[3][3]==mark && brd[2][3]==' ') c_move = 6;	/*top row*/
    
    	if(brd[3][2]==mark && brd[3][3]==mark && brd[3][1]==' ') c_move = 7;	/*across row*/
    	if(brd[1][3]==mark && brd[2][2]==mark && brd[3][1]==' ') c_move = 7;	/*diagonal*/
    	if(brd[1][1]==mark && brd[2][1]==mark && brd[3][1]==' ') c_move = 7; /*up 1st column*/
    
    	if(brd[1][2]==mark && brd[2][2]==mark && brd[3][2]==' ') c_move = 8; /*down column*/
    	if(brd[3][1]==mark && brd[3][3]==mark && brd[3][2]==' ') c_move = 8; /*across row*/
    
    	if(brd[1][1]==mark && brd[2][2]==mark && brd[3][3]==' ') c_move = 9;	/*diagonal*/
    	if(brd[1][3]==mark && brd[2][3]==mark && brd[3][3]==' ') c_move = 9;	/*up column*/
    	if(brd[3][1]==mark && brd[3][2]==mark && brd[3][3]==' ') c_move = 9;	/*across row*/
    	
    	return c_move;
    }
    Another thought to keep in mind, is that the program has to know when to play offensively "careless", and when to play defensively and conservative. If the program can win in one move, then how careless it's defensive is (that is, the opponent could win IF he had another move), doesn't matter.

    Otherwise, it matters a lot!
    Last edited by Adak; 06-01-2008 at 09:49 AM.

  4. #4
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,046
    Why are you using 1,2,3 for your indices instead of 0,1,2?

    Also, you could make winOrBlock() somewhat easier to read by looping through each square with two nested for loops, then checking the cells where x=y and x=0 or y=0, making sure that the one you're looking at is a space and the others in the row/column/whatever are equal to mark.

    Or just examine each line, checking if it has two square that equal mark and one that is empty.
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  5. #5
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    The answer to both is "blame it on my chess program".

    I don't use the zero'th element of an array for most board games because I think in terms of row 1, column 1, not row 0, column 0, as the first square.

    For everything else I use the zero'th array element. It's a bit pendantic, isn't it?

  6. #6
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,046
    Why not something like this . . . .
    Code:
    enum {
        SQ1, SQ2, SQ3, SQS
    };
    Anyway, it's not that important.

    Here's sort of what I was thinking of.
    Code:
    /* note: this returns the x-position of the last square required to complete a row */
    int last_square_in_line(char board[3][3], char who, int xoff, int yoff, int xinc, int yinc) {
        int x, y;
        int last = -1;
        char sq;
    
        for(x = 0; x < 3; x ++) {
            for(y = 0; y < 3; y ++) {
                sq = board[xoff + x * xinc][yoff + y * yinc];
                if(sq == ' ') {
                    if(last == -1) {
                        /* this is the first empty square discovered -- record it */
                        last = x;
                    }
                    else {
                        /* this line contains more than one empty square */
                        return -1;
                    }
                }
                else if(sq != who) {
                    /* the opponent has occupied this square */
                    return -1;
                }
            }
        }
    
        return last;
    }
    
    /* returns true if a square was placed */
    int place_last_square(char board[3][3], char who, int xoff, int yoff, int xinc, int yinc) {
        int n;
    
        n = last_square_in_line(board, who, xoff, yoff, xinc, yinc);
        if(n != -1) {
            board[xoff + n][yoff + abs(n) * yinc] = who;
            return 1;
        }
    
        return 0;
    }
    
    /* the main win-or-lose function -- returns true if a square was placed */
    int check_win_or_lose(char board[3][3], char who) {
        int x, y;
    
        if(place_last_square(board, who, 0, 0, 1, 1)) return 1;
        if(place_last_square(board, who, 2, 0, -1, 1)) return 1;
    
        for(x = 0; x < 3; x ++) {
            /* horizontal */
            if(place_last_square(board, who, 0, x, 1, 0)) return 1;
    
            /* vertical */
            if(place_last_square(board, who, x, 0, 0, 1)) return 1;
        }
    
        return 0;
    }
    Note that I haven't tested that at all. I'm sure you could reduce the number of parameters to those functions by using structures or funky pointer manipulation. I tried the latter but it didn't work too well, so there you have it.

    [edit] If were going to actually use that, I'd make last_square_in_line() actually do the placing instead of place_last_square(), and eliminate place_last_square() entirely. Ah well. [/edit]
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  7. #7
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    My whole TTT program is pretty primitive except the display is beautiful and it's strategy is top notch, imo.

    I was quite shocked to learn that many TTT programs are beatable by applying one of the strategies listed earlier. Apparently, I wasn't the only one who quit playing TTT before learning all the winning tricks.

    Some other programs I tested never lost, but they played the same dull game, and rarely tried to lay a trap for the opponent, so they could win a game. How boring.

  8. #8
    Super unModrator
    Join Date
    Dec 2007
    Posts
    321
    Thanks for the Awesome posts Adak, dwks. Looks like I will have to change my arrays to 2D.

    Should I stop using extern too? Is it incorrect to use it?

  9. #9
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Quote Originally Posted by abh!shek View Post
    Thanks for the Awesome posts Adak, dwks. Looks like I will have to change my arrays to 2D.

    Should I stop using extern too? Is it incorrect to use it?
    Frankly, I think the whole slew of different files is rather silly. Looks like every function has a new file for it. Why?

    Everything in MyHeader could easily go into your main program file, along with everything else.
    TTT just isn't that big a program, imo.

  10. #10
    Super unModrator
    Join Date
    Dec 2007
    Posts
    321
    hehe I just wanted to do it coz everyone else does

    Ok now I will write TTT again from scratch with just one source file.

  11. #11
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,288
    Quote Originally Posted by abh!shek View Post
    Thanks for the Awesome posts Adak, dwks. Looks like I will have to change my arrays to 2D.
    No you don't! In fact I would recommend that you don't.
    Here I posted a simple easy way to check for all wins:
    Tell me what i did wrong!
    With a function like that, just use a simple minimax. Look that up and try coding it, it's not too hard. That should give unbeatable results and in less code than what Adak posted.
    If you want to make it possible to beat then you can add some random chance that the minimax occasionally does not consider the best move. You can also use randomness amoung equally good choices to make it seem more human as well.
    I would definitely not hard code individual strategies when you can evaluate every possible outcome in less than a millisecond anyway.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  12. #12
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    That's a very neat way to test for a TTT win, iMalc.

    Mini-max is fine, but you can't set specific traps for the opponent, unless you know what they are. If I had used m-m or negamax, I would never have learned such traps existed. The only one I remembered from childhood was "if you get three corners, you'll win next move (if the opponent can't win in his one remaining move).

    Of course, it's good to know m-m, also. More valuable to a programmer than some traps in TTT.

  13. #13
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,288
    I guess there's some truth to that. Minimax doesn't know what looks like a safe move to the player as it assumes the player knows everything. Factor in reality, that they don't know the whole thing, and it can kick butt better.
    I'd say that the best program would be one that uses minimax and also keeps a history of all previous games such that the moves that players fell victim to previously are used more often, although you'd also want to avoid using the same trick twice in a row.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  14. #14
    Registered User
    Join Date
    Dec 2006
    Location
    Canada
    Posts
    3,167
    My version of TTT:
    Code:
    #include <iostream>
    #include <stack>
    
    /* board representation
    	0 1 2
    	3 4 5
    	6 7 8
    */
    
    int rays[8][3] = {
    	{ 0, 1, 2 },
     	{ 3, 4, 5 },
      	{ 6, 7, 8 },
       
       	{ 0, 3, 6 },
       	{ 1, 4, 7 },
       	{ 2, 5, 8 },
          
        	{ 0, 4, 8 },
        	{ 2, 4, 6 }
    };
    
    int board[9] = { 0, 0, 0, 0, 0, 0, 0, 0, 0 }; //0 = unoccupied, 1 = o, 2 = x
    int num_unoccupied = 9; //number of unoccupied squares
    
    char symbols[3] = { ' ', 'o', 'x' };
    
    int game_num = 0; // game number. Used to determine who goes first 
    int stm = 1; //side to move
    int computer_side = 2;
    
    std::stack<int> *undo_stack = NULL;
    
    void make_move(int sq, int side) {
    	board[sq] = side;
    	--num_unoccupied;
    	undo_stack->push(sq);
    	stm ^= 0x3; //1 to 2, 2 to 1
    }
    
    void undo_move() { //undoes the last move
    	board[undo_stack->top()] = 0;
    	undo_stack->pop();
    	++num_unoccupied;
    	stm ^= 0x3; //1 to 2, 2 to 1
    }
    
    void print_board() {
    	std::cout << std::endl;
    	for (int i = 0; i < 9; ++i) {
    		if (i &#37; 3 == 0) {
    			std::cout << std::endl;
    		}
    		std::cout << "[" << symbols[board[i]] << "]";
    	}
    	std::cout << std::endl;
    }
    
    int get_game_state() { // 0 = still going, 1 = o won, 2 = x won, 3 = draw
    	if (num_unoccupied == 0) {
    		return 3;
    	}
    	for (int i = 0; i < 8; ++i) { //see if ray i contains all the same sides
    		if (board[rays[i][0]] == board[rays[i][1]] && board[rays[i][1]] == board[rays[i][2]] && board[rays[i][0]] != 0) {
    			return board[rays[i][0]];
    		}
    	}
    	return 0;
    }
    
    int negamax() { /* -1 if loss for stm, 0 if draw, 1 if win */
    	
    	/* terminating conditions */
    	int game_state = get_game_state();
    	
    	if (game_state == 1 || game_state == 2) {
    		if (stm == game_state) {
    			return 1;
    		} else {
    			return -1;
    		}
    	} else if (game_state == 3) {
    		return 0;
    	}
    	
    	/* the actual recursive part */
    	int scores[9]; // scores if move i is played. -2 = can't play, -1 = loss, 0 = draw, 1 = win
    	for (int i = 0; i < 9; ++i) {
    		if (board[i] == 0) {
    			make_move(i, stm);
    			scores[i] = -negamax(); /* the - in "nega"max */
    			undo_move();
    		} else {
    			scores[i] = -2;
    		}
    	}
    	int max_score = -3;
    	for (int i = 0; i < 9; ++i) {
    		if (scores[i] > max_score) {
    			max_score = scores[i];
    		}
    	}
    	
    	return max_score;
    	
    }
    
    void AI_make_move() { 
    	int scores[9]; // scores if move i is played. -2 = can't play, -1 = loss, 0 = draw, 1 = win
    	for (int i = 0; i < 9; ++i) {
    		if (board[i] == 0) {
    			make_move(i, computer_side);
    			scores[i] = -negamax();
    			undo_move();
    		} else {
    			scores[i] = -2;
    		}
    	}
    	int max_score = -3;
    	int max_idx;
    	for (int i = 0; i < 9; ++i) {
    		if (scores[i] > max_score) {
    			max_score = scores[i];
    			max_idx = i;
    		}
    	}
    	
    	print_board();
    	std::cout << "Analysis: " << std::endl;
    	for (int i = 0; i < 9; ++i) {
    		if (scores[i] != -2) {
    			std::cout << i << " : ";
    			switch(scores[i]) {
    				case 1:
    					std::cout << "win";
    					break;
    				case -1:
    					std::cout << "loss";
    					break;
    				default:
    					std::cout << "draw";
    			}
    			std::cout << std::endl;
    		}
    	}
    	make_move(max_idx, computer_side);
    }
    
    int main() {
    	std::cout << "Tic Tac Toe by Matthew Lai" << std::endl;
    	std::cout << "Ctrl+C to terminate." << std::endl;
    	
    	while (true) { /* for every game */
    		
    		/* clear the board */
    		for (int i = 0; i < 9; ++i) {
    			board[i] = 0;
    		}
    		
    		num_unoccupied = 9;
    		
    		if (undo_stack) {
    			delete undo_stack;
    		}
    		undo_stack = new std::stack<int>;
    		
    		stm = 1;
    		
    		if (game_num % 2 == 0) {
    			computer_side = 2;
    		} else {
    			computer_side = 1;
    		}
    		
    		while (get_game_state() == 0) {
    			if (stm == computer_side) {
    				AI_make_move();
    			} else {
    				print_board();
    				int t = -1;
    				while ( t < 0 || t > 8 || board[t] != 0) {
    					std::cout << "Your move: ";
    					std::cin >> t;
    				}
    				make_move(t, computer_side ^ 0x3);
    			}
    		}
    		
    		if (get_game_state() == computer_side) {
    			std::cout << "You lost." << std::endl;
    		} else if (get_game_state() == 3) {
    			std::cout << "Draw." << std::endl;
    		} else {
    			std::cout << "You won." << std::endl;
    		}
    		
    		++game_num;
    	}	
    }
    It implements minimax (the negamax flavour http://wikipedia.com/wiki/Negamax).
    I think the ray detecting method in my code is the prettiest in the thread so far =). (int get_game_state())
    I tried to comment it as much as possible.
    Prints out analysis for each legal move. (win/loss/draw assuming perfect counter-play)

    AI should be unbeatable (assuming no bug in my code), as it searches to the very end. The most you can get is a draw.

    *edit* OOPS sorry, didn't notice that this is the C board. But besides the IO and the undo stack, everything is C */edit*
    Last edited by cyberfish; 06-04-2008 at 10:42 PM.

  15. #15
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    I haven't had a chance to try your program, yet. (but I will!)

    Yes, your ray detection is a fine improvement. IMalc had that in his version as well, but I can't find his post, anymore.

    Looks quite nice, but we'll see just how it plays!

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Help me with my simple Tic tac toe prog
    By maybnxtseasn in forum C Programming
    Replies: 2
    Last Post: 04-04-2009, 06:25 PM
  2. Tic Tac Toe program
    By muzihc in forum C Programming
    Replies: 10
    Last Post: 10-21-2008, 08:08 PM
  3. making tic tac toe, need some help
    By Frantic- in forum C++ Programming
    Replies: 8
    Last Post: 06-16-2005, 09:06 AM
  4. Help with Tic Tac Toe game
    By snef73 in forum C++ Programming
    Replies: 1
    Last Post: 04-25-2003, 08:33 AM
  5. Tic Tac Toe Help
    By aresashura in forum C++ Programming
    Replies: 1
    Last Post: 11-21-2001, 11:52 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21