Back to For Beginners

Tic-Tac-Toe Winning proof?

For Beginners

Started by Luckless March 29, 2005 04:08 PM

17 comments, last by The Forgotten Mindset 19 years ago

Zahlman

1,682

March 29, 2005 11:32 PM

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.

smart_idiot

1,298

March 29, 2005 11:50 PM

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 . .

Chess is played by three people. Two people play the game; the third provides moral support for the pawns. The object of the game is to kill your opponent by flinging captured pieces at his head. Since the only piece that can be killed is a pawn, the two armies agree to meet in a pawn-infested area (or even a pawn shop) and kill as many pawns as possible in the crossfire. If the game goes on for an hour, one player may legally attempt to gouge out the other player's eyes with his King.

garyfletcher

250

March 30, 2005 01:22 AM

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..:)

Gary.Goodbye, and thanks for all the fish.

Matt Apple

200

March 30, 2005 09:17 AM

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.

CyberSlag5k

514

March 30, 2005 09:28 AM

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!

Without order nothing can exist - without chaos nothing can evolve.

Squirm

481

March 30, 2005 09:33 AM

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 :)

ApochPiQ

23,138

March 30, 2005 09:45 AM

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 23 4 56 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.

Wielder of the Sacred Wands
[Work - ArenaNet] [Epoch Language] [Scribblings]

CyberSlag5k

514

March 30, 2005 10:06 AM

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!

Without order nothing can exist - without chaos nothing can evolve.

The Forgotten Mindset

416

March 30, 2005 05:02 PM

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 oneint 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;}

The G'Bro GameDev Society! -The Southeastern US GameDev Gathering Group

Tic-Tac-Toe Winning proof?

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Tic-Tac-Toe Winning proof?

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines