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.



Approximate search space on a 5x5x5 cube with 3 different possible classes?
The set of boards which have any symmetry is microscopic compared with the total number of boards, so the number of boards up to symmetry is roughly $3^{125}/48 \approx 9.1\times 10^{57}$.


The probability that a random board has a particular $5$ in a row is $2/(3^5)$, and if I count correctly there are $94$ places to win. So, the expected number of wins is $188/243 \lt 1$. At least $1-\frac{188}{243}$ of the boards have no $5$ in a row.


As I commented, you may want to force #crosses-#noughts to be $0$ or $1$, but that is not a very strong condition on a random board, only reducing the number by a factor of about $11.5$. 


These are not independent conditions, but the interactions are of lower order. There are at least $2\times 10^{56}$ boards up to symmetry with no win yet so that the players could reach the position by alternating.


