Approximate search space on a 5x5x5 cube with 3 different possible classes? - MathOverflow

Approximate search space on a 5x5x5 cube with 3 different possible classes?

2011-04-01T05:09:20Z

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--

Eliminate duplicate boards (equivalent after rotation, reflection)
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.
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.
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.

Answer by Gerhard Paseman for Approximate search space on a 5x5x5 cube with 3 different possible classes?

2011-04-01T08:36:41Z

There are a couple of approaches you can take.

One is to reduce things by a dimension: There are 233 possible tuples for a row of 5, instead of 243, if I read your constraints correctly. You can now loop through 3 iterations to determine an approximate number of 5x5 boards: for every 3 tuple of possible rows, compute the number of possibile completions (ignoring the difference between X's and O's) by assuming the three rows are three middle rows, and then finding how many of the remaining (233^2) pairs fit for each board. The nice thing about choosing the middle three rows is that the outcome for each remaining row can be done independently (if I read the constraints right), and so you don't have (233^2) remaining iterations. In fact, by preprocessing each triple of rows, you can determine what squares are restricted or fixed, and then compute the number of legal rows that fit those restrictions.

This idea extends to a rough estimate for the cube. Instead of choosing the middle three rows, choose the middle 9 columns in the cube, randomly select legal columns, and either use the 5x5 stats to extrapolate allowed sections of the cube, or do an analysis stage which restricts the number of allowed squares, and use that to (over-) estimate the number of completions. If you are worried about the difference between O's and X's, you can keep a running tally of the difference until you run into the last few of the 16 undetermined columns. This is like the random sampling suggested in an earlier comment, but uses a little more precision because you are picking legal rows of 5 at random instead of indivisual cells.

The other way, which might be prudent, is to do a game tree search. Start by generating all first moves, then all second moves, then all third moves, and so on. After each level of moves, apply whatever symmetry operations you wish to reduce cases, but keep track of the size of each equivalence class. Then when the tree is large enough, pick a random sample of branches to do a continuation of the game tree for a small fraction of the space, and repeat until each branch has its own full blown extension, then select a fraction of those branches, etc, until you get an idea how much pruning gets done. For example, after 5 moves you might run out of memory to store the game tree, but you realize that, say , something like .001% of the possible configurations were pruned because they did not meet the constraints. Then choose , say, a few hundred thousand of these positions, and continue them for another four or five moves. Note that perhaps .1% of those branches had to be pruned. Repeat and observe how the constraints affect the percentage of allowed positions to decrease. This may allow you to get a rough estimate of the size of the game space.

In the first method above, I would not bother with rotations/reflections because you are using a small portion of the space to eliminate possibilities for the larger portion. In the second method, it helps to have as complete a game tree as possible, so eliminating symmetric cases early on results in more coverage of the full game tree. However, the difference between any partial tree and one shrunk by taking rotations and reflections into consideration will reduce the size by a factor of less than 100 (less than 48, more precisely), and for rough estimates like these that is not a consideration.

As a sanity check, suppose I estimate the number of positions after 10 moves. Including possibilities that are not allowed by the constraints, and taking the symmetry group into consideration, I would expect something not far from (125 choose 10) * (10 choose 5)/48, which is in the neighborhood of 10^14--10^16. If you take the second method, and compute, say, 10^7 game positions for the first 5 moves up to symmetry, then you are on track toward this estimate. If , for each of 1000 randomly chosen positions, each one generates a five move subtree of size about 10^7, then the simulation (in my mind) bears out the hand-waving calculation I just made. If instead, the average size of each of the 1000 subtrees is more like 10^6, then the constraints are having more of an effect, and you may be able to extapolate how much I am overestimating the count.

Gerhard "Ask Me About System Design" Paseman, 2011.04.01

Answer by Douglas Zare for Approximate search space on a 5x5x5 cube with 3 different possible classes?

2011-04-01T08:52:24Z

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.