• Advertisement
Sign in to follow this  

Tic-Tac-Toe Winning proof?

This topic is 4680 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

So, I've spent a few minutes googling without turning anything really useful up, so... While I have my own idea of how to prove that someone has won the game, what are your ideas on proving a win?

Share this post


Link to post
Share on other sites
Advertisement
I ment as far as storing and proving mathmatically/logicaly in programming. This IS a programming forum, so I sort of figured I wouldn't have to state that part of the question.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
"Tic Tac Toe Board (Gray is the actual board shown in the game)

Numbers: 0 1 2

0 4 9 2
1 3 5 7
2 8 1 6

By looking at the table above, you will initialize all of the numbers above in the multi-dimensional array. If you add the three numbers in vertical or horizontal or diagonal, the results will be 15. So, have a function to the do the calculation for that. Whichever player put the X or O in one of the slots in the table, you will then assign that number appropriately to that user and show the X or O in the table instead of number."

Maybe this will work for you :D

Share this post


Link to post
Share on other sites
Tic-tac-toe isn't a particularly big game. You could just search all possible moves from the current board position and verify that they all lead to a win for the same person.

Share this post


Link to post
Share on other sites
The board is 3x3, there are 8 winning positions for each side. Testing each individually isn't overwhelming.

Share this post


Link to post
Share on other sites
thats probably the simplest way to do it. Jsut check the 8 possibilities.

Share this post


Link to post
Share on other sites
I wrote this:


#include <iostream>
#define C(v) cout<<(v?v==X?'X':'O':'.')
using namespace std;enum P{N,X,O};P p=O,b[9],c;int d
[]={0,3,1,3,2,3,0,1,3,1,6,1,0,4,2,2},t,*u;int main()
{for(;;){y:for(t=0;t<9;++t)t=N;for(;;){z:for(t=0;
t<9;++t)C(t)<<((t+1)%3?' ':'\n');p=p==X?O:X;for(;
;){C(p)<<", enter your move (1-9): ";cout.flush();cin
.sync();t=cin.get()-'1';t=t%3+3*(2-t/3);if(t>-1&&t<9
&&!t)break;}t=p;for(u=d;u<d+16;u+=2)if((c=b[*u
]))for(t=1;t<3;)if(c!=b[*u+t*u[1]])break;else if(++t
>2){C(c)<<" Wins!\n";goto y;}for(t=0;t<9;++t)if(!t[b
])goto z;cout<<"Draw!\n";goto y;}}}



It's a little known fact that by using as little white space as possible and using one character variable names your programs will run faster.*

*This is a lie, it in fact just makes it harder to read.

Share this post


Link to post
Share on other sites
Well, there are better and worse ways of going through eight possibilities :)

I would suggest a data-driven approach:


// We set up some data which represents the possible ways to win. Then later we
// can set up a loop, instead of explicitly testing each case in a separate
// statement.
char possible_wins[8][3] = {
{0, 1, 2},
(3, 4, 5},
{6, 7, 8}, // rows
{0, 3, 6},
{1, 4, 7},
{2, 5, 8}, // columns
{0, 4, 8},
{2, 4, 6} }; // diagonals

// We'll use a bitmask to indicate the states we want to test for.
const int X = 1;
const int O = 2;
const int EMPTY = 4;

int linesContaining(int types) {
int count = 0;
// symbolAt() should return X, O, or EMPTY according to what's in that space
// Depending on how things are represented in the rest of the game, you may
// not need it ;)
int myboard[9];
for (int i = 0; i < 9; i++) { myboard = symbolAt(i); }
for (int i = 0; i < 8; i++) {
if ((myBoard[possible_wins[0]] & types) &&
(myBoard[possible_wins[1]] & types) &&
(myBoard[possible_wins[2]] & types)) { count++; }
}
return count;
}

// For example, "linesContaining(X)" will be non-zero if X has won, similarly O.
// The extra flexibility is built in to make it more useful for AI routines.

Share this post


Link to post
Share on other sites
That's kind of the method I used in my program, although mine uses a 1D array. It's in pairs, the starting position in the array, and the offset for each element:

0, 3

1 . .
2 . .
3 . .


1, 3

. 1 .
. 2 .
. 3 .


2, 3

. . 1
. . 2
. . 3


0, 1

1 2 3
. . .
. . .


3, 1

. . .
1 2 3
. . .


6, 1

. . .
. . .
1 2 3


0, 4

1 . .
. 2 .
. . 3


2, 2

. . 1
. 2 .
3 . .

Share this post


Link to post
Share on other sites
Perhaps something like (in C++ anyhow)


char Board::stateOfPlay()
{
const int WINNING_ROW[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}};

vector<BoardTile*>::const_iterator boardIter = m_Tiles.begin();

for (int row = 0; row < 8; ++row)
{
if((!((*(boardIter+WINNING_ROW[row][0]))->isEmpty()) &&
(((*(boardIter+WINNING_ROW[row][0])))->getPiece()) ==
((*(boardIter+WINNING_ROW[row][1])))->getPiece()) &&
(((*(boardIter+WINNING_ROW[row][1])))->getPiece()) ==
((*(boardIter+WINNING_ROW[row][2])))->getPiece())
{
return ((*(boardIter+WINNING_ROW[row][0])))->getPiece();
}
}

int emptyCount = 0;

for(boardIter = m_Tiles.begin(); boardIter < m_Tiles.end(); ++boardIter)
{
if((*boardIter)->isEmpty())
{
++emptyCount;
}
}

if (!emptyCount)
{
return TIE;
}

return NOONE;
}



The 2-D array WINNING_ROWS stores all possible winning combinations which I then use as an offset in my board vector (vector of pointers to a class of tiles with various member functions).

Source can be found here if you want to take a closer look.

Good luck..:)

Share this post


Link to post
Share on other sites
Quote:
Original post by Fruny
The board is 3x3, there are 8 winning positions for each side. Testing each individually isn't overwhelming.


Yep, and a win isn't even possible until the fifth square(of nine) gets filled in. Don't even test for a win condition until squares_filled > 4

TicTacToe was the first game I coded. Seems like I made a string of the length 24(which is the 8 possible ways to win times 3 squares each), initialized it to blanks and then whenever a square got filled in I put either an X or O into the correct position. Then when squares_filled > 4 i stepped through a FOR loop by 3s and looked for the substring "XXX" or "OOO". When I found it I set the win condition to true and jumped out of the loop. Then all you have to do is re-initizalize the string to blank when you start a new game.

Not the prettiest way to do it but it worked.

Share this post


Link to post
Share on other sites
To make it slightly more efficient (which I guess would be "cooler"), after each player moves don't check the positions specific to each player's token, just check to see if they're all the same (then check one of them to make sure it's not blank). If they're all the same, the winner is the person who just moved. That way you aren't checking both:

XXX
...
...

and

OOO
...
...

You're just checking if those top positions are all the same character and that that character isn't a '.'. This is of course so rediculously unnecessary unless you're using a computer from 1975, but this is as "cool" as it gets, I'm afraid. There's no mathematical wonder formula to be applied.

Good luck!

Share this post


Link to post
Share on other sites
If you assign a bit to each square (1, 2, 4, 8, ... 512)
Then each winning combination of 3 is an int (7, 56, ... ) with a total of 8 winning numbers, which go in an array called winners.

sum = (total of value of squares containing players pieces)
For each combo in winners
if (sum & combo == combo)
player has won

There, just to be different :)

Share this post


Link to post
Share on other sites
Well, if by "cool solutions" you want "obfuscated solutions," then here's one for you:

Define squares on the playing field as bits in a bitmask:
0 1 2
3 4 5
6 7 8


Have one variable storing all moves made by X, and one storing all moves made by O. To determine if a player has made a move to a specific square, just check if (PlayerField & (2 << square_id)) != 0.

Now, define a winning condition as a mask of three indices. For example, 0 1 2 is a win; this can be converted to a mask of (2 << 0) | (2 << 1) | (2 << 2) which of course equals 7. To see if a player has acheived this winning position, check if (PlayerField & WinningMask) == WinningMask. Now just store a constant array of integers, one for each winning bitmask. Test each entry in this array against the player's play history mask after their turn to see if they have won.

Share this post


Link to post
Share on other sites
Quote:
Original post by Squirm
If you assign a bit to each square (1, 2, 4, 8, ... 512)
Then each winning combination of 3 is an int (7, 56, ... ) with a total of 8 winning numbers, which go in an array called winners.

sum = (total of value of squares containing players pieces)
For each combo in winners
if (sum & combo == combo)
player has won

There, just to be different :)


Very clever, Squirm. Nice job!

Share this post


Link to post
Share on other sites
Quote:
Original post by smart_idiot
That's kind of the method I used in my program, although mine uses a 1D array. It's in pairs, the starting position in the array, and the offset for each element:

0, 3

1 . .
2 . .
3 . .


1, 3

. 1 .
. 2 .
. 3 .


2, 3

. . 1
. . 2
. . 3


0, 1

1 2 3
. . .
. . .


3, 1

. . .
1 2 3
. . .


6, 1

. . .
. . .
1 2 3


0, 4

1 . .
. 2 .
. . 3


2, 2

. . 1
. 2 .
3 . .


That's exactly how I did it!

Behold, messy code:

#define MARK_X 0
#define MARK_O 1

// Returns MARK_X if X won, MARK_O for O, -1 for no one
int CheckWinner()
{
// Check all horizontal rows for 3 in a row
for( int r = 0; r < 3; r++ )
{
if( g_BoardMap[r][0]==g_BoardMap[r][1] &&
g_BoardMap[r][1]==g_BoardMap[r][2] &&
g_BoardMap[r][2]==MARK_X)
return MARK_X;
else
if( g_BoardMap[r][0]==g_BoardMap[r][1] &&
g_BoardMap[r][1]==g_BoardMap[r][2] &&
g_BoardMap[r][2]==MARK_O)
return MARK_O;

}
// Check all vertical columns for 3 in a row
for( int c = 0; c < 3; c++ )
{
if( g_BoardMap[0][c] == g_BoardMap[1][c] &&
g_BoardMap[1][c] == g_BoardMap[2][c] &&
g_BoardMap[2][c]==MARK_X)
return MARK_X;
else
if( g_BoardMap[0][c] == g_BoardMap[1][c] &&
g_BoardMap[1][c] == g_BoardMap[2][c] &&
g_BoardMap[2][c]==MARK_O)
return MARK_O;
}
// Check all diagonal rows for 3 in a row
// Check diagonal 1 (top-left to bottom-right)
if( g_BoardMap[0][0]==g_BoardMap[1][1] &&
g_BoardMap[1][1]==g_BoardMap[2][2] &&
g_BoardMap[2][2]==MARK_X)
return MARK_X;
else
if( g_BoardMap[0][0]==g_BoardMap[1][1] &&
g_BoardMap[1][1]==g_BoardMap[2][2] &&
g_BoardMap[2][2]==MARK_O)
return MARK_O;

// Check diagonal 2 (top-right to bottom-left)
if( g_BoardMap[0][2]==g_BoardMap[1][1] &&
g_BoardMap[1][1]==g_BoardMap[2][0] &&
g_BoardMap[2][0]==MARK_X)
return MARK_X;
else
if( g_BoardMap[0][2]==g_BoardMap[1][1] &&
g_BoardMap[1][1]==g_BoardMap[2][0] &&
g_BoardMap[2][0]==MARK_O)
return MARK_O;

// Check for a Cat (no body wins -a draw)
for( int row = 0; row < 3; row++ )
{
for( int col = 0; col < 3; col++ )
{
if( GetMark(col, row) == 0 )
return -1; // no cat

// has the whole map been checked?
if( row == 2 && col == 2 )
return -2; // CAT/DRAW !!!
}
}

// no winners :(
return -1;
}


Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement