Programming Forums
User Name Password Register
 

RSS Feed
FORUM INDEX | TODAY'S POSTS | UNANSWERED THREADS | ADVANCED SEARCH

Reply
 
Thread Tools Display Modes
Old Dec 4th, 2005, 1:26 PM   #1
UnKnown X
Hobbyist Programmer
 
UnKnown X's Avatar
 
Join Date: Dec 2005
Location: Sandvika, Norway
Posts: 114
Rep Power: 0 UnKnown X is an unknown quantity at this point
Send a message via MSN to UnKnown X
Tic-Tac-Toe AI problem

I am making a Tic-Tac-Toe game with a twist to test my C++ skills (which aren't really very good). The twist is that the user can select how many rows and columns there should be and the amount of Xs or Os you need in a row to win. That way, I can't make the AI so specific. I managed to make a working AI that even beats me at times, but there is one problem. I can't figure out how to make it check for "gaps".


I.e, in this situation:

    1   2   3

 1  O |   | X
   ---|---|---
 2    |   |
   ---|---|---
 3  O |   | X

I can't figure out how to make it know that this makes it win:

    1   2   3

 1  O |   | X
   ---|---|---
 2  O |   |
   ---|---|---
 3  O |   | X

and this prevents the enemy from winning:

    1   2   3

 1  O |   | X
   ---|---|---
 2    |   | O
   ---|---|---
 3  O |   | X



I tried, but I made it over-complicated and ended up with a lot of code that I'm not even sure what does anymore.


I'm not so desperate that I need someone to write the entire function for me (yet :p). I just need to get ideas for methods I can use to make it.

The board matrix is a two-dimensional char array, and I am not using any pointers or references, since I'm not too familiar with that yet. I think that's all you need to know. If not, just tell me.


Thanks if you can help!

Last edited by UnKnown X; Dec 4th, 2005 at 1:27 PM. Reason: Added "problem" to the title, + fixed typos
UnKnown X is offline   Reply With Quote
Old Dec 4th, 2005, 1:52 PM   #2
nnxion
Programming Guru
 
nnxion's Avatar
 
Join Date: Jun 2005
Location: elemental plane
Posts: 1,429
Rep Power: 5 nnxion is on a distinguished road
You need to think about in which situtation one wins or loses. One wins if one has a number of 0's or X's horizontally, vertically or diagonally. If you have a function to calculate them you, then you are half-way there.

Show us some (pseudo) code and we can help you improve/correct it.
__________________
"Employ your time in improving yourself by other men's writings, so that you shall gain easily what others have labored hard for."
-- Socrates
nnxion is offline   Reply With Quote
Old Dec 4th, 2005, 2:08 PM   #3
UnKnown X
Hobbyist Programmer
 
UnKnown X's Avatar
 
Join Date: Dec 2005
Location: Sandvika, Norway
Posts: 114
Rep Power: 0 UnKnown X is an unknown quantity at this point
Send a message via MSN to UnKnown X
Here was my initial plan, but by looking at the long if statement, you can see that this is getting too complicated (at least for me).

This only checks one of the directions for the gap.

// function to check if the bot can win on the next turn by putting its 'O' inbetween other 'O's
bool BotGapWin(void)
{
    int count = 0;
    int temp, tempm, tempn;    // temporary variables (didn't get to the point where I need those)
    char c = 'O';    // so it's easier for me to copy and paste the code later... I'm lazy
    bool again = false;    // if the user has selected more than 3 rows/columns
    for (int m = 0; m < rowcols; ++m)    // search the grid matrix[m][n]
        for (int n = 0; n < rowcols; ++n)
        {
            temp = tempm = tempn = count = 0;    // initialize variables in case something goes wrong
            if (matrix[m][n] == c)    // if found a character
            {
                if (matrix[m-1][n]!='X' && matrix[m-1][n]!='O' && m-1>=0)    // check if there is a gap above
                {
                    for (count = 0; matrix[m+count][n] == c && m+count < rowcols; ++count)    // count the amount of 'O's below the 'O' found
                        ;
                    while (true)
                    {
                        --count;    // need to subtract this for later
                        cout << "Checking matrix[m-2-(count+(winScore-3))][n] =\nmatrix[" << m << "-2-(" << count << "+(" << winScore << "-3))][" << n << "] =\nmatrix[" << m-2-(count+(winScore-3)) << "][" << n << "] =\n\'" << ((unsigned char)matrix[m-2-(count+(winScore-3))][n]) << "\'\n";    // just for checking while running the programme
                        if (matrix[m-2-(count+(winScore-3))][n] == c && matrix[m-2-(count+(winScore-3))][n] != (c == 'O' ? 'X' : 'O') && m-2-(count+(winScore-3)) < rowcols && m-2-(count+(winScore-3)) >= 0 && (winScore == 3 ? matrix[m-2-(count+(winScore-3))+1][n]==' ' : matrix[m-2-(count+(winScore-3))+1][n]==' ' && matrix[m-2-(count+(winScore-3))-1][n]==c))    // I'm not sure what the hell I was trying to do here... :p
                        {
                            matrix[m-1][n] = 'O';    // put 'O' in the gap (doesn't work because I messed up the if above)
                            cout << "Return true!\n";    // for testing
                            return true;
                        }
                        if (winScore==3)    // no need to do this again if the win score is 3
                            break;
                        if (again == false)
                        {
                            again = true;
                            continue;    // count is decremented again at the start of the loop
                        }
                    }
                    again = false;
                }
            }
        }
    return false;    // no useful gaps found
}

I bet you could laugh at me all day over this code...
UnKnown X is offline   Reply With Quote
Old Dec 4th, 2005, 2:43 PM   #4
ivan
Professional Programmer
 
ivan's Avatar
 
Join Date: Sep 2005
Location: serbia & montenegro
Posts: 484
Rep Power: 4 ivan is on a distinguished road
I believe that MiniMax game trees would be a good solution for that.
Here is a link to get the idea:

http://www.cprogramming.com/tutorial...imaxtree1.html
ivan is offline   Reply With Quote
Old Dec 4th, 2005, 2:44 PM   #5
Arevos
Programming Guru
 
Arevos's Avatar
 
Join Date: Aug 2005
Location: England
Posts: 1,499
Rep Power: 5 Arevos is on a distinguished road
Quote:
Originally Posted by UnKnown X
I am making a Tic-Tac-Toe game with a twist to test my C++ skills (which aren't really very good). The twist is that the user can select how many rows and columns there should be and the amount of Xs or Os you need in a row to win. That way, I can't make the AI so specific. I managed to make a working AI that even beats me at times, but there is one problem. I can't figure out how to make it check for "gaps".
Well, presumably you'd want some code that would return arrays for rows, columns and diagonals:
board.row(n);   // returns nth row array
board.column(n);   // returns nth column array
board.diagonal_top();   // the diagonal from the top left to bottom right
board.diagonal_bottom();   // the diagonal from the bottom left to top right
Then you'd want some count functions:
count_crosses(array);   // counts the number of crosses in an array
count_noughts(array);   // counts the number of naughts in an array
count_blanks(array);   // counts the number of empty squares in an array
The logic for it would go something like:
if array has s-1 noughts and 1 blank, or array has s-1 crosses and 1 blank:
   then place your symbol in the blank space on that row
Where s is the size of the board.

That doesn't account for all possibilities, but it's a step in the right direction. For more complex behaviour, you could have predictive AI:
test board = copy of actual board
for each blank square in test board:
   place your symbol on blank square
   if you have won:
      place symbol in the same place on the actual board
   for each blank square in test board:
      place your opponent's symbol there
      if you have lost:
         do not place your symbol in that position on the actual board
Arevos is offline   Reply With Quote
Old Dec 4th, 2005, 2:55 PM   #6
UnKnown X
Hobbyist Programmer
 
UnKnown X's Avatar
 
Join Date: Dec 2005
Location: Sandvika, Norway
Posts: 114
Rep Power: 0 UnKnown X is an unknown quantity at this point
Send a message via MSN to UnKnown X
Thanks, ivan, but I think that's a little too complicated for me just yet.


Your idea seems a little simpler, Arevos, but I can't help but notice the . operator. Is that for accessing classes? I don't have my grid in a class, and I'm not good at using classes. Care to explain a bit?

I think I can see a way to do this with my two-dimensional array, but I'm not quite sure...


Edit: Also, that last example seems very promising. It can also replace my current non-gap check functions. I'll give it a shot.

Last edited by UnKnown X; Dec 4th, 2005 at 3:12 PM. Reason: typo
UnKnown X is offline   Reply With Quote
Old Dec 4th, 2005, 2:56 PM   #7
Symptom
Newbie
 
Symptom's Avatar
 
Join Date: Sep 2005
Posts: 28
Rep Power: 0 Symptom is on a distinguished road
Since a tic tac toe board is usually 3x3 it will be easier for you to check each column and each row before the pc plays in order to find the right move. Maybe two functions
char* find_lose_conditions()
and
char* find_win_conditions()
can check whether the pc can win in the next turn or is about to loose and return a pointer to the array, which will point the next move of the pc. If nothing of the above happens, you can just play in a box randomly or figure out which one is best by weighted values for each box(see how many winning lines go through each box).

If you don't mind going really deep you should check the minimax algorithm(also min-max algorithm) which is often used in such applications(especially chess engines). Here are some links that will get you started :

http://ai-depot.com/LogicGames/MiniMax.html
http://en.wikipedia.org/wiki/Minimax_theorem
http://www.stanford.edu/~msirota/soco/minimax.html
__________________
The geeks shall inherit the earth.
Symptom is offline   Reply With Quote
Old Dec 4th, 2005, 3:02 PM   #8
UnKnown X
Hobbyist Programmer
 
UnKnown X's Avatar
 
Join Date: Dec 2005
Location: Sandvika, Norway
Posts: 114
Rep Power: 0 UnKnown X is an unknown quantity at this point
Send a message via MSN to UnKnown X
In this Tic-Tac-Toe game, the user decides the amount of rows and columns when the program is run so it'll be slightly more challenging (for me) to code than to simply code in all the possible conditions.

Again, I'd use the minimax algorithm if I hadn't already written over 800 lines of (clumsy :p) code, since I'm waaay too lazy. Besides, I've never used a data tree before, so I need some simpler practice before jumping into something like this.
UnKnown X is offline   Reply With Quote
Old Dec 4th, 2005, 6:13 PM   #9
UnKnown X
Hobbyist Programmer
 
UnKnown X's Avatar
 
Join Date: Dec 2005
Location: Sandvika, Norway
Posts: 114
Rep Power: 0 UnKnown X is an unknown quantity at this point
Send a message via MSN to UnKnown X
Well, I've started on Arevos' last idea, and it forced me to put more of my code in functions, which made me remove over 400 lines of code (50% of the programme), which is really quite an improvement by itself :p
UnKnown X is offline   Reply With Quote
Old Dec 4th, 2005, 7:07 PM   #10
UnKnown X
Hobbyist Programmer
 
UnKnown X's Avatar
 
Join Date: Dec 2005
Location: Sandvika, Norway
Posts: 114
Rep Power: 0 UnKnown X is an unknown quantity at this point
Send a message via MSN to UnKnown X
It's finished now. I re-wrote nearly all the code, and whilst there are some imperfections, it's as good as it gets by me (at the moment, anyway). Thanks for the help everyone!

I'll have to give this another shot later when I've grasped the min-max algorithm...
UnKnown X is offline   Reply With Quote
Reply

Bookmarks

« Previous Thread in Forum | Next Thread in Forum »

Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)
 
Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Forum Jump




DaniWeb IT Discussion Community
All times are GMT -5. The time now is 10:06 AM.

Powered by vBulletin® Version 3.7.0, Copyright ©2000 - 2008, Jelsoft Enterprises Ltd.
Copyright ©2007 DaniWeb® LLC