Checking Who Won Tic Tac Toe More Efficient C++
I'm writing a Tic Tac Toe Game and I would like to know how I can make an efficient function to check who won. A two dimensional array congaing X's, O's, or blank spaces represents the board.
char CheckWin(const char board[][NUM_COLS], int& sum) // tic tac toe board - IN
{
char tmp;
int lcv;
tmp = ' ';
if (sum == 9)
{
return 'T';
}
else if (sum != 9)
{
if (((tmp = board[1][1]) != ' ' && board[0][0] == tmp && board[2][2] == tmp) || (board[2][0] == tmp &&开发者_Python百科amp; board[0][2] == tmp))
{
return tmp;
}
for (lcv = 0; lcv < 3; lcv++)
{
if ((tmp = board[lcv][0]) != ' ' && board[lcv][1] == tmp && board[lcv][2] == tmp)
{
return tmp;
}
else if ((tmp = board[lcv][0]) != ' ' && board[lcv][1] == tmp && board[lcv][2] == tmp)
{
return tmp;
}
}
}
return 'N';
}
Besides doing something similar to this over and over again, how could I check who won and return an X if X has won, an O if O has one, a T if it's a tie, and N if no one has one yet. Thanks in advance. I'm trying to get familiar with C++ and programming in general still.
EDIT: I just went with the simple method, but I somehow messed it up, anybody know how? It looks like it's not return anything because when I call it in the main after a player picks a row and column(that's working fine), it doesn't output anything
You could convert the array into two nine-bit values, one for the O positions and one for the X position, and a count of blank spaces:
x_mask = 0
y_mask = 0
empty_count = 0
mask = 1
for each square
if x then x_mask |= mask
if y then y_mask |= mask
if empty then empty_count++
mask <<= 1
Then compare the x_mask and y_mask against the eight possible winning combinations:
for each player
for each winning combination
if player_mask & winning_mask == winning_mask then player has won
and then handle the cases neither player has won:
if neither player won
if empty_count == 0
its a tie
else
moves still available
A simple "structured" approach
If you think of the board as:
A B C
D E F
G H I
Then one minimal selection of boxes that any winning layout must touch would be:
A B C
D
G
You can conceive the movement from any of these locations in a winning line in terms of a shift of 0, 1 or -1 positions in each of the X and Y directions. We can list the movements that you'd need to check:
A: (++x) (++x, ++y) (++y)
B: (++y)
C: (++y) (--x, ++y)
D: (++x)
E: (++x)
In C++, you can create a list/vector of the x/y coordinates of the starting points and the +/-/0 x/y movement deltas shown above, then use three nested loops to evaluate each line across the board.
This is considerably more work than just hardcoding the two loops over x and y coordinates and the two diagonals (below), but it's a more algorithmic approach that might appeal intellectually: more like what you might have to do if you were handling a much bigger board.
Obvious brute force approach
For the record, that simpler approach would look like this:
int x;
for (row = 0; row < 3; ++row)
if ((x = board[row][0]) != Empty &&
board[row][1] == x && board[row][2] == x)
return x;
// similar loop for columns...
...
// hardcode diagonals...
if ((x = board[1][1]) != Empty &&
(board[0][0] == x && board[2][2] == x ||
board[2][0] == x && board[0][2] == x))
return x
I suppose you could assign each winning board possibility a number (basically a hash value) and then check if the current board matches any of the values in the table by generating its hash value. On the other hand, I wouldn't suggest spending too much time trying to make the CheckWin function super-efficient. Unless it's being called millions of times or something and needs to be really fast, spend your time on something else--it probably won't be a bottleneck.
精彩评论