Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
If all you need is an estimate, I'd run a Monte Carlo code. Something like: 1) Randomly generate a position 2) Check if it's a valid position or not 3) Check under what rotations, reflections the position is invariant. 4) Repeat Once you have a lot of trials (a computer can easily do a few billion), sum the reciprocals of the numbers from step 3 of those positions which were valid. Then estimate from this the probability that a randomly chosen configuration fits your criteria, and multiply by the number of positions (3^125), for a decent estimate. –  Logan Maingi Apr 1 '11 at 5:30
    
Thanks sir, that was the next step if I didn't get an approximation on here. If you change your comment to an answer I'll give it the check. –  prelic Apr 1 '11 at 5:50
    
Do you really need to consider boards with $10$ noughts and $5$ crosses? –  Douglas Zare Apr 1 '11 at 6:47
    
Of course, requiring the difference in counts to be $0$ or $1$ only reduces the number by about a factor of $11$. –  Douglas Zare Apr 1 '11 at 6:54
    
Excellent insight, I didn't even think about that because of the way I was doing the simulation, but that's certainly another constraint –  prelic Apr 1 '11 at 7:32
add comment

2 Answers

up vote 3 down vote accepted

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.

share|improve this answer
    
Are you also considering 4 in a row? I'd like something more to convince me that there are at least 10^50 boards with no 4 (nonblank) symbols in a row. Gerhard "Ask Me About System Design" Paseman, 2011.04.01 –  Gerhard Paseman Apr 1 '11 at 18:11
    
I didn't say anything about eliminating boards with no $4$-in-a-row condition since I don't understand its relevance to the search space. The goal of the game is to get $5$ in a row, correct? So as far as I know, $4$ in a row doesn't end the game. Perhaps an unblocked $4$ in a row would mean the position is not interesting. –  Douglas Zare Apr 1 '11 at 20:00
    
I'm not sure which game you are playing. His condition 3 I interpret as eliminating boards with 4 nonblank symbols in a line (row). How are you reading it? Gehard "Looking Over The Rules Again" Paseman, 2011.04.01 –  Gerhard Paseman Apr 1 '11 at 22:47
    
Noughts and crosses is a game. When you get a complete row with one symbol, the game ends, so it is natural to exclude those from the set of states to consider if you are trying to find a strong solution to the game. I don't understand the desire to exclude boards with $4$ in a row of a particular symbol. If you make $4$ Xs in a row, and I block you, the game continues. –  Douglas Zare Apr 2 '11 at 0:39
    
While playing to get 5 in a row makes sense to me, I have seen a similar game (although I think it was 2D) with 4 in a row as a goal. I assumed the latter in my response. Perhaps I am misunderstanding the original poster's intent behind condition 3. Gerhard "Ask Me About System Design" Paseman, 2011.04.02 –  Gerhard Paseman Apr 2 '11 at 13:30
show 1 more comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.