Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

I'm trying to code a tic tac toe game in java and I need help figuring out how to efficiently and without freezing the program check if someone won the game.

I'm only in the design stages now, I haven't started programming anything but I'm wondering how would I know at all times the state of the game and exactly when someone wins?


Response to MarkR: (note: had to place comment here, it was too long for comment section)

It's not a homework problem, I'm trying to get more practice programming GUI's which I've only done once as a freshman in my second introductory programming course. I understand I'll have a 2D array. I plan to have a 2D integer array where x would equal 1 and o would equal 0. However, won't it take too much time if I check after every move if someone won the game? Is there a way or a data structure or algorithm I can use so that the program will know the state (when I say state I mean not just knowing every position on the board, the int array will take care of that, I mean knowing that user 1 will win if he places x on this block) of the game at all times and thus can know automatically when someone won?

share|improve this question
5  
You could most likely check whether either player has won thousands of times without facing any performance problem. Don't worry about it –  Jaakko Lipsanen Oct 11 '12 at 19:50
5  
You're drastically underestimating the power of the modern processor. –  Byte56 Oct 11 '12 at 20:36

4 Answers 4

The brute force approach as recommended by others is how you should proceed. Modern CPU's, even mobile ones, can check the whole board several thousand times per second, so you should not worry about game freezing.

However in your question you ask can this be speeded up, a question that will become very important if your game becomes more complex. And the answer is 'yes', it can and it should be speeded up, and indeed you should practice this on tic-tac-toe. The idea is not to brute force check the whole grid, but to check if the last move created a winning combinatin. So you start from the newly placed move, and then check in all directions if any makes a winning move.

For tic-tac-toe, this more complex algorithm will probabaly be slower then brute force one, because 3x3 grid is very small. But the algorithm scales very nicely, where brute force approach does not.

share|improve this answer

Just do a brute force check on the grid after each turn, simple. It's a 3x3 grid. Doesn't exactly require massive amounts of computational power.

share|improve this answer

I don't think you really need to worry about "freezing the program". A function to check who has won in tic-tac-toe would be able to execute very quickly.

This sounds like a homework question - I don't want to write your answer for you. But I expect you would have some kind of two-dimensional array containing the state of each square on the board. This would have to be maintained throughout the program's running

share|improve this answer

Here's some untested C++ code adapted from http://www.gamedev.net/topic/606358-how-many-games-are-possible-in-tictactoe/page_view_findpost_p_4835877 which avoids the need for any searching. It should be fairly simple to convert to Java.

Note that most of the constants are octal. Displaying the current board is left as an exercise ;)

static unsigned const magic[9] = {
  010010010, 010001000, 010000101,
  001010000, 001001011, 001000100,
  000110001, 000101000, 000100110
};

enum Status {WIN, DRAW, PLAYING};

unsigned p[2] = {011111111, 011111111};
unsigned unused = 0777;
unsigned to_play = 0;

Status get_status()
{
  if (p[!to_play] & 044444444)
    return WIN; // Last move was a win                                            
  if (p[0]+p[1] == 055555555)
    return DRAW; // Full board
  return PLAYING;
}

bool make_move(int i)
{
  if (unused & (1u<<i))
  {
    p[to_play] += magic[i];
    to_play ^= 1u;
    unused ^= 1u<<i;
    return true;
  }
  return false;
}
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.