Printable View
I'm taking an introductory C++ class. I'm having trouble with a current assignment. I have to write a simple tic tac toe program. It doesn't have an AI. It just goes back and forth between two users. The program has to use Arrays, and Functions. We haven't gotten to fancy displays or anything. So the whole program in displayed in text. I can't figure out an efficient structure for my program. If anyone could help it would be much appreciated. Thank you.
> I can't figure out an efficient structure for my program
What do you mean by this?
int board[3][3];
Seems to be a start
how does the actual algorithm work ?
Think of how the game is played. First you have your 3x3 board, that would be the int board[3][3]. Second you allow the player to select an empty location, so you would obtain the requested spot and check if that was free. If it isn't request another choice; if it is check to see if the player won. If he did, print Player 1(2) wins, if he didn't get input from the other player.
Big picture, visualize how you play TicTacToe and then code that.
There would also be 3 possible values for each of the spaces. An 'X', 'O', or empty space. You would store them into the arrays as each player inputs his move.
Also you may want to think about enumerating some types to help you with your 2D array. For example if you had 0 as free, 1 as X and 2 as O it would not be that intuitive to someone else what those values meant. Instead you could do something like
enum STATES { PLAYER_O, PLAYER_X, FREE };
Then you could check those symbolic constants instead of remembering the actual values. Just an idea though.
I don't know about enums yet..
but.. I was thinking.... how do we tell the
computer to select the place to put an 'X' or
an 'O' in order to win the game ???
i was thinking..
let's say...
1) 0 ... for empty space
2) 1 ... for 'O'
3) 2 ... for 'X'
let's say the computer is playing 'X's for example..
so it will first check horizontally vertically and diagonally
to see if there are any empty spaces (or zeros)
and then what ?
How do you write the strategy ?
is it as simple as summing up the arrays (horizontally, vertically or diagonally) whereever the empty spaces or 'X's are and checking to see which sum brings the highest number.... and telling it to place the X in that location ?????
COOL PROGRAMS @ www.akilla.tk
That would require AI. I believe the original post only wanted a 2-player game. I suggest you search for tic-tac-toe in the Game Programming forum. There's bound to be a topic on AI.
I see that people are using 100s of if conditions and calling it AI
Is that ok ?
I wan't to do it in a simple and effective way. Like- relating it to mathematics. Is there a way to somehow "add up" the values and search for the best position to place the 'X' or the 'O' ?
Any advise is appreciated.
CHECK OUT - MATH BRAIN @ www.akilla.tk
You can use search trees to search for possible combinations and return the best position. Depth first search and breadth first search are popular in AI. Since there's not too many possibilities in TTT, a ton of if conditions will suffice. However with more complicated games, it would take forever to search all possibilities so cutting the search to a certain number of levels will do.
For instance, you would analyze the positions in TTT and rank these situations and assign them points:
1) 3 in a row win for you
2) blocking an opponent's 2 in a row
3) creating simultaneous 2 in a row situations for certain win
4) preventing opponent from any chance of winning
etc...
For opening moves you can do something like adding a certain number of points for moves that give you the most possible combinations for a victory. Then you can subtract it with the opponent's strenghth in position which would give you the total score to choose your move.
Games such as chess commonly use an opening book for preset moves. This way the AI won't search through unnecessary paths which are inferior.
are there any sample code that I can refer to that use this tree search ?
Try this. Do not worry about the warnings, most of them can be removed by using type casting.
Compiler:Borland C++ 5.0
Y'know its just my opinion, but if your taking an introductory C++ class I wouldn't get too involved with complicated data structures and algorithms just yet. When I did a 2 player tictactoe game the checkForWin() function just contained a few if statements with all the winning possibilities covered. Thats plenty if your not too experienced with C++.
>Try this. Do not worry about the warnings, most of them can be >removed by using type casting.
>Compiler:Borland C++ 5.0
I've already seen that file.. there are too many if conditions in it. Maybe all the possibilities of that game.
I don't want to think about all the possibilities. I am trying to find a relation mathematically (if it exists) that will teach the computer a strategy to win the game.
>Y'know its just my opinion, but if your taking an introductory >C++ class I wouldn't get too involved with complicated data >structures and algorithms just yet. When I did a 2 player >tictactoe game the checkForWin() function just contained a few >if statements with all the winning possibilities covered. Thats >plenty if your not too experienced with C++.
I am not taking an intro class. Programming is my hobby,
although I didn't write very complicated programs yet. Just
learning and I am new to C/C++
I don't mind working hard on writing a Tic Tac Toe program.
However, I don't want to use too many if conditions
(if that's possible.)
Thanks for the replies.
MY HOMEPAGE @ www.akilla.tk
Whoever started the thread mentioned an introductory class thats why I said it. Anyway, I think 2 player TTT is simple enough not to require complex AI. Here is the function I was talking about, in case it helps at all:
I'm sure there are more concise ways of accomplishing the same thing, cos thats some damn ugly code!!Code:int CLineWindow :: checkForWin( )
{
if ( (m_nGridState [ 0 ] == 1 && m_nGridState [ 1 ] == 1 && m_nGridState [ 2 ] == 1) ||
(m_nGridState [ 3 ] == 1 && m_nGridState [ 4 ] == 1 && m_nGridState [ 5 ] == 1) ||
(m_nGridState [ 6 ] == 1 && m_nGridState [ 7 ] == 1 && m_nGridState [ 8 ] == 1) ||
(m_nGridState [ 0 ] == 1 && m_nGridState [ 3 ] == 1 && m_nGridState [ 6 ] == 1) ||
(m_nGridState [ 1 ] == 1 && m_nGridState [ 4 ] == 1 && m_nGridState [ 7 ] == 1) ||
(m_nGridState [ 2 ] == 1 && m_nGridState [ 5 ] == 1 && m_nGridState [ 8 ] == 1) ||
(m_nGridState [ 0 ] == 1 && m_nGridState [ 4 ] == 1 && m_nGridState [ 8 ] == 1) ||
(m_nGridState [ 2 ] == 1 && m_nGridState [ 4 ] == 1 && m_nGridState [ 6 ] == 1) )
{
return 1; // X wins!
}
if ( (m_nGridState [ 0 ] == 2 && m_nGridState [ 1 ] == 2 && m_nGridState [ 2 ] == 2) ||
(m_nGridState [ 3 ] == 2 && m_nGridState [ 4 ] == 2 && m_nGridState [ 5 ] == 2) ||
(m_nGridState [ 6 ] == 2 && m_nGridState [ 7 ] == 2 && m_nGridState [ 8 ] == 2) ||
(m_nGridState [ 0 ] == 2 && m_nGridState [ 3 ] == 2 && m_nGridState [ 6 ] == 2) ||
(m_nGridState [ 1 ] == 2 && m_nGridState [ 4 ] == 2 && m_nGridState [ 7 ] == 2) ||
(m_nGridState [ 2 ] == 2 && m_nGridState [ 5 ] == 2 && m_nGridState [ 8 ] == 2) ||
(m_nGridState [ 0 ] == 2 && m_nGridState [ 4 ] == 2 && m_nGridState [ 8 ] == 2) ||
(m_nGridState [ 2 ] == 2 && m_nGridState [ 4 ] == 2 && m_nGridState [ 6 ] == 2) )
{
return 2; // O wins!
}
for ( int i = 0; i < 9; i++ )
{
if ( m_nGridState [ i ] == 0 )
{
return 0; // game not finished
}
}
return -1; // game drawn
}
I d'loaded that TTT game posted previously and was overwhelmed to find 1900+lines of code. :eek: Holy frijoles!!
Is that a 'typically' sized TTT game?
In my imagination I was figuring about 4-500 lines would do it. However, I'm a noob, only about halfway thru the SAMS 21 day book.
I goota say, that file has me a little scared, lol :(
Yeah, 1900+ lines is really long for a TTT game.
Here's a link if you want to get a brief intro on these search trees:
http://sern.ucalgary.ca/courses/CPSC...Boyd/game.html
You may want to do a search on depth first search. This will help you get started.
Here's a couple of hints:
Think about the symmetry of the game. Say for example, an opponent's first move is in the middle. You have 2 possibilities: a corner move or a side move. That way you won't have to search for all the possibilities since they're symmetric.
And if a position you search shows that you win 100% of the time, you can stop searching for any other possibilities.
Good luck
Mmm, here's an AI-free version in 150 lines
My MFC windowed version is only about 500 lines, 1900 lines is huge for tictactoe
I made TTT with Windows GDI, with very very limited *ai* (selects a random open spot :D)... it took 287 lines of code (minus a resource file). I made it in MSVC++, so maybe there's some behind-the-scenes stuff goin' on... anyways, you can take a look if you want.
http://www.geocities.com/hunterguy_2/