Hey all,

I read the meta, and I realize this question might be pretty elementary for this site, but I'm having trouble computing this, and I know it won't take too much insight for someone to give me an approximation.

Say I have a 5x5x5 tic-tac-toe board (noughts and crosses), where each of the 125 spaces on the cube can belong to one of 3 different classes (X, O, empty). Now obviously the naive observation is that there are 3^125 possible 'boards', but after taking the following eliminating criteria in mind, can someone please give me a general idea of the order of the space complexity?

1. Eliminate duplicate boards (equivalent after rotation, reflection)
2. Eliminate all boards that are not valid 'game boards'. That is, eliminate all boards where there is 5-in-a-row of one class (excluding the 'empty' class) in either horizontal, vertical, or diagonal directions, in all dimensions.
3. Similar to (2), but going one step further and eliminating all boards where there 4 in a row in any direction/dimension.
4. Because TTT (N&C) is a turn-based, ZS game, we should also eliminate possible boards where the difference in classes is greater than one.

As mentioned above, I'm certainly not looking for any kind of precise number, just looking for a broad estimate. I've tried determining this for 2-dimensional boards and simple 3-dimensional boards, but I'm quite unsure of how these would scale to 5x5x5.

Thanks in advance for the help, this has been gnawing at me for a few days now.

Hey all,

I read the meta, and I realize this question might be pretty elementary for this site, but I'm having trouble computing this, and I know it won't take too much insight for someone to give me an approximation.

Say I have a 5x5x5 tic-tac-toe board (noughts and crosses), where each of the 125 spaces on the cube can belong to one of 3 different classes (X, O, empty). Now obviously the naive observation is that there are 3^125 possible 'boards', but after taking the following eliminating criteria in mind, can someone please give me a general idea of the order of the space complexity?

--EDITED TO ADDRESS #3--

1. Eliminate duplicate boards (equivalent after rotation, reflection)
2. Eliminate all boards that are not valid 'game boards'. That is, eliminate all boards where there is 5-in-a-row of one class (excluding the 'empty' class) in either horizontal, vertical, or diagonal directions, in all dimensions.
3. Similar to (2), but going one step further and eliminating all boards where there 4 in a row in any direction/dimension and that four in a row can possibly lead to a win. So exclude all boards that contain at least one row, column, or diagonal with 4 of one class, and the 5th being empty.
4. Because TTT (N&C) is a turn-based, ZS game, we should also eliminate possible boards where the difference in classes is greater than one.

As mentioned above, I'm certainly not looking for any kind of precise number, just looking for a broad estimate. I've tried determining this for 2-dimensional boards and simple 3-dimensional boards, but I'm quite unsure of how these would scale to 5x5x5.

Thanks in advance for the help, this has been gnawing at me for a few days now.

Hey all,

I read the meta, and I realize this question might be pretty elementary for this site, but I'm having trouble computing this, and I know it won't take too much insight for someone to give me an approximation.

Say I have a 5x5x5 tic-tac-toe board (noughts and crosses), where each of the 125 spaces on the cube can belong to one of 3 different classes (X, O, empty). Now obviously the naive observation is that there are 3^125 possible 'boards', but after taking the following eliminating criteria in mind, can someone please give me a general idea of the order of the space complexity?

1. Eliminate duplicate boards (equivalent after rotation, reflection)
2. Eliminate all boards that are not valid 'game boards'. That is, eliminate all boards where there is 5-in-a-row of one class (excluding the 'empty' class) in either horizontal, vertical, or diagonal directions, in all dimensions.
3. Similar to (2), but going one step further and eliminating all boards where there 4 in a row in any direction/dimension.

As mentioned above, I'm certainly not looking for any kind of precise number, just looking for a broad estimate. I've tried determining this for 2-dimensional boards and simple 3-dimensional boards, but I'm quite unsure of how these would scale to 5x5x5.

Thanks in advance for the help, this has been gnawing at me for a few days now.

Hey all,

I read the meta, and I realize this question might be pretty elementary for this site, but I'm having trouble computing this, and I know it won't take too much insight for someone to give me an approximation.

Say I have a 5x5x5 tic-tac-toe board (noughts and crosses), where each of the 125 spaces on the cube can belong to one of 3 different classes (X, O, empty). Now obviously the naive observation is that there are 3^125 possible 'boards', but after taking the following eliminating criteria in mind, can someone please give me a general idea of the order of the space complexity?

1. Eliminate duplicate boards (equivalent after rotation, reflection)
2. Eliminate all boards that are not valid 'game boards'. That is, eliminate all boards where there is 5-in-a-row of one class (excluding the 'empty' class) in either horizontal, vertical, or diagonal directions, in all dimensions.
3. Similar to (2), but going one step further and eliminating all boards where there 4 in a row in any direction/dimension.
4. Because TTT (N&C) is a turn-based, ZS game, we should also eliminate possible boards where the difference in classes is greater than one.

As mentioned above, I'm certainly not looking for any kind of precise number, just looking for a broad estimate. I've tried determining this for 2-dimensional boards and simple 3-dimensional boards, but I'm quite unsure of how these would scale to 5x5x5.

Thanks in advance for the help, this has been gnawing at me for a few days now.