Hello, I am making a tic-tac-toe game with JavaScript. I have everything working, except the function that checks to see if a win (three in a row) has happened. I know that this function must be called each time that is a move is made, but I do not know how it should work. So far, I have two versions of the game board within the script, a graphical one and a data one. I store the game data in an array, and it might look something like this as the game progresses: X,O,O O,X,O O,O,X This is obviously a two-dimensional array. So, does anyone have an algorithm (or a better way to store the data as well) for checking whether or not a win (three in a row) has happened? If possible, it needs to be able to work on a much larger scale, say a grid that has about 100 squares instead of only nine.

Hi Muska, I hope you are using a Two dimensional array. Traverse the matrix and check the adjacent two elements in all directions for each element. if the elements are matching then its a win situation. Sajid Mohammed ( sajleo@yahoo.com )

Here's another way to do it. Assign each square a power of two. 1 2 4 8 16 32 64 128 256 Keep track of which squares have X's by using an integer XStatus. If X goes in the first Square, add 1 to XStatus. XStatus should always represent which squares have X's. OStatus should represent which squares have O's. There are 8 different ways to make 3 in a row. 1 + 2 + 4 = 7 8 + 16 + 32 = 56 1 + 8 + 64 = 73 4 + 16 + 64 = 84 2 + 16 + 128 = 146 1 + 16 + 256 = 273 4 + 32 + 256 = 292 64 + 128 + 256 = 448 These are the 8 winning combination numbers. Now, any time you want to check if the X guy has won, you can check XStatus against these numbers using a logical AND. If the XStatus ANDed with any of the winning combination numbers equals that winning combination number, X wins. In C code: static int WinArray[8] = {7, 56, 73, 84, 146, 273, 292, 448}; for (int i = 0; i < 8; ++i)     if((XStatus & WinArray[i]) == WinArray[i])         XWins();

woah! that looks like difficult! I would do similar, but not with powers of 2. there are only 8 winning lines. if any of those 8 have one of each X and O on them they can't be won: : : : O : X X : O in this case, the left and right columns and the bottom and middle rows CAN NOT be won, so don't need to be checked any more. If a symbol is added to a row where they already own a symbol, that row is worth 2, if they add it where the opposition owns a symbol the row is worth nothing, and is useless. use a game tree, and minimax principal to create computer players. The main idea of getting rid of the rows which can't be won is to save time processing the lines each time. in my example above only 4 lines could be won. Of course, there are lots of ways of doing this. you already have an array which I assume is: 1x1=X 1x2=: etc so to check winning rows in a simple fashion: for(row=1;row=3;row++){ for(col=1;col=3;col++){ if(array(row,col)=X){ Xline++; } if(array(row,col)=O){ Oline++; } } //if Xline=3 then X wins //if Oline=3 then O wins //otherwise, check the next row. } then you'll need to do the same for columns (reversing the for loops) I appologise if my syntax is off, I'm out of practice! hayley

Thanks for the input. Both are wonderful ideas. I am not entirely sure as to which I will use, but I will give credit to whoever's idea it is that I use. If I use the square root idea, and it is for a much larger game board, the numbers could become quite large, and it would be hasslesome to go through and determine what the numbers would be that would make up a win (say on a 5-in-a-row game like Pente). Though, maybe a slight variation might work great. With the other one, you could loop through the rows, checking for straight lines. But do you know of a way to find diagonals?

Besides the diagonals with hayley's version, I found a problem with Jim's version. If you move as so: X:: XX: ::X and you put the X in the center-left in before you complete the three-in-a-row, the numbers will not match those found in the winArray[] array.

A 25 square board would not be a problem. As long as your integers have more than 25 bits. In this case, there would be 12 possibilities in the win array. Calculating the win array only has to be done once. If you have a 10X10 game board, you'll probably have to do some extra programming to do the logical ands and compares. 100 bit integers are hard to come by. Muska, in the example you gave, the XStatus would be 1 + 8 + 16 + 256 = 281. AND that with the winarray that corresponds to the diagnol, 1 + 16 + 256 = 273. 281 ANDed with 273 does indeed turn out to be 273, so X does win. If you just want to do it in for loops, here's some C code: int CheckForXs() {     for (i = 0; i < 3; ++i)     {         for (j = 0; j < 3; ++j)         if (GameBoard[i][j] != 'X')             break;         if (j == 3)             return(true);         for (j = 0; j < 3; ++j)             if (GameBoard[j][i] != 'X')                 break;         if (j == 3)             return(true);     }     // Now check diagnols     for (i = 0; i < 3; ++i)         if (GameBoard[i][i] != 'X')             break;     if (i == 3)         return(true);     for (i = 0; i < 3; ++i)         if (GameBoard[i][3 - i - 1] != 'X')             break;     if (i == 3)         return(true);     return(false); } For a 5X5 board, subsitute 5's for the 3's.