I am having trouble figuring out an efficient way to perform the checks for how a winner is determined in a 3D tic tac toe program (that is 3x3x3). Winners can be three spaces in any vertical, horizontal, or diagonal, including those between the 3 "boards." There are over 50 winning possibilities, but I'm not sure exactly how many there are. The grid is represented by the 3D array char grid[3][3][3]. My intention is to check every possible winning combination by adding up the ASCII values held by each position (which will either be a ' ', 'X', or 'O', with respective ASCII values of 32, 88, and 79) and dividing it by 3. That value will be assigned to a variable int sum. Then I will have an if statement after each check as follows:

if(sum==88 || sum==79)
        {
          return sum;
        }

By returning sum, it will tell me whether X or O won, based on if 88 or 79 was returned.

Can anyone help?

Not sure what the question is, but presumably if the code above is in a function called:

int checkWinner()

you would harness the return value like this:

int returnValue = checkWinner();

if(returnValue == 79)
{
    // code for when O wins
}
else if(returnValue == 88)
{
    // code for when X wins
}
else
{
    // code for when no one has won yet.
}

I understand HOW to check if X or O wins, or if it is a draw, but I am not sure of an effective way to actually PERFORM all 50+ necessary checks to see if there is a winner. For one, Im not even sure how many possible winning combinations there are. Second, I wish I knew an algorithm that would simplify the execution of those many checks.

At the end of each check, it would perform the code that I stated before:

if(sum==88 || sum==79)
        {
          return sum;
        }

Any ideas?

And by the way, looking back, I can see why my question was unclear the first time. Sorry about that :)

Take it a plane at a time and do it the way you check it normal 2-D Tic-Tac-Toe.

For each 3 x 3 plane, there are 8 ways to win: 3 in one direction, 3 in the other direction, 2 diagonal.

There are 3 x-y planes (one where z is 0, one where z is 1, one where z is 2), so make that 8 times 3 ways = 24 ways to win on an x-y plane.

So there are also 24 ways to win on the x-z plane and 24 ways to win on the y-z plane, so there are 24 plus 24 plus 24 = 72 ways to win on a plane. Finally there are 4 ways to win diagonally where x, y, and z all vary. 76 altogether.

So systematically check all possible ways, one plane at a time, so you're probably looking at a loop within a loop within a loop.

for(int z = 0; z < 3; z++)
{
    // check the 8 ways for this value of z.
}

// at this point you've checked 24 of the 76 possibilities

for(int y = 0; y < 3; y++)
{
    // check the 8 ways for this value of y.
}

// at this point you've checked 48 of the 76 possibilities

for(int x = 0; x < 3; x++)
{
    // check the 8 ways for this value of x.
}

// at this point you've checked 72 of the 76 possibilities

// now check the remaining 4 diagonals

Edited 6 Years Ago by VernonDozier: n/a

Here, this is lua code which should make it clear, the board has been squished from a '2d' table (array) into a 1d array of 'X', 'O' and 'EMPTY' strings. so if we had

XXO
OXO
OOX

it would turn into XXOOXOOX from here we just check wether the tokens are in a ceartin order. continuing on with the above example testing for a X win, it is obvious from the board that X will win on a diagonal, the squares involved in this win have the location in a 2d array of 1,1 + 2, 2 + 3, 3. these dimensions equate to 1,5,9 in the 1d representation XXOOXOOX. if you looks below at the wins table inside it there in another table with these exact numbers. so we therefore loop through each of these win tables checking the 1d representtion which itself is an array in this case called 'self' . so when index reaches 1 in the for loop we do

wins element 1 = { 1, 5, 9 } -> elements 1, 5, 9 of XXOOXOOX must be equal

i.e

if XXOOXOOX element 1 == XXOOXOOX element 5 == XXOOXOOX element 9

they are equal and we therefore have a winner!

from this concept you can compress the 3d grid into a 1d one then check for wins by changing the tables in wins

I hope that made sense, good luck & have fun

function board:win()

    local wins = {
                    {1,5,9},
                    {3,5,7},
                    {1,4,7},
                    {2,5,8},
                    {3,6,9},
                    {1,2,3},
                    {4,5,6},
                    {7,8,9},
                 };

    for index = 1, 8, 1 do 

        if self[wins[index][1]] == self[wins[index][2]] and self[wins[index][2]] == self[wins[index][3]] then 

            return self[wins[index][1]];

        end 

    end 

    return false;

end 

Edited 4 Years Ago by HenryH: misread as 2d not 3d

Comments
Not 3d

There is a fully-commented and -explained 3DTTT program - in FORTRAN - in* Programming the IBM 1130 and 1800* by Robert K. Louden (Prentice-Hall, 1967). (And if you don't know FORTRAN the book has a good tutorial on the 1130's specific dialect.) He stores move values as 0 (empty), 1 (player), and 5 (machine). I should mention that this program plays 4x4x4 TTT. Using these values there are small unambiguous values for the state of each row. e.g. a sum of 2 in a row means there are two player moves and no machine moves. The board is represented as a simple vector of 64 cells. The program also has a list of all of the cells that make up the rows (76 of them in 4x4x4; this is conceptually a 76x4 array). To compute its move the program begins by iterating through all of the rows, computing the sum of the cells in each row, storing the sums in a 76-element array. It would be possible to keep these sums incrementally, updating them as the machine and the player make each move, but doing 304 additions just doesn't take that long. Then the fun begins of finding interesting combinations of non-empty rows with common free intersecting points. Strategy "targets" are represented in a 14x3 array representing 14 scenarios described as one, two, or three rows with specified sums and, for two or three rows, with common intersecting empty cells. The search involves eight nested loops. The program's approach could easily be extended to deeper strategies.

This article has been dead for over six months. Start a new discussion instead.