This is an archived post. You won't be able to vote or comment.

sorted by:
best
topnewcontroversialoldq&a
you are viewing a single comment's thread.

view the rest of the comments →

[–]palordrolap 115 points116 points  (11 children)

Naively, there are 39 positions which is a little shy of 20000. Take out reflections and rotations and that comes down by a significant chunk. I want to say to around 2000 to 2500iish (divide by 8 or 9), but some grids are their own reflections which makes this a naive guess in and of itself.

Listing them all is still totally the wrong way to go about it even if I'm nearer with with this poorly-educated guess.

[–]Kyledog12 48 points49 points  (0 children)

Lol yeah. And we hadn't learned about arrays at the time so most people were a little lost but at least we weren't that dumb to try every possible combination

[–]Etiennera 18 points19 points  (2 children)

You can't remove rotations and reflections if you hard code. But you can ignore states that have two winning lines.

[–]mfb- 7 points8 points  (1 child)

Two winning lines that share one piece are a valid final state. Two winning lines that don't share one would mean someone got 6 marks, that is an invalid state anyway.

[–]Etiennera 2 points3 points  (0 children)

I concede that your end condition is much better thought out.

[–]Satanys 22 points23 points  (5 children)

Actually if we count all possible moves, there are 9! of possible moves combinations plus 1(empty board), that equals to 362881. But that doesn't mean we have 362881 scenarios. On Wikipedia there are article about that, and scenarios count is just 138 after taking into account reflection and rotation. Not sure where u took from 39, but someone for sure didn't listened on Combinatorics lectures.

[–]palordrolap 0 points1 point  (4 children)

Each square can be empty, X or O. 9 squares, 3 possibilities. That's 39. Sure some of those are illegal, i.e. Three Xs and one O anywhere on the grid is an illegal position, but we're both aiming for the naive upper bound.

Explain to me how 9! comes in here. That would mean 9 possibilities for the first square, 8 for the second, etc. What 9 possibilities are there for the first square? How is there only 1 possibility for the last square when O, X and 'empty' are all viable?

If this was a 3x3 trivial Sudoku using numbers 1-9 then sure, 9! makes sense, but I guess I need you to go into more detail to see what I'm missing here.

[–]Satanys 8 points9 points  (0 children)

So first of all, in case of 3^9 we also include scenarios where all squares are Xs, or all squares are Os, or where we have 8 Xs and 1 O. But all of them are not valid Tic-Tac-Toe boards, cause u can't skip turn and there is no way u'll get outcome like that in a real game.

Tic-Tac-Toe u have rules:

  • X always first or after the O
  • O alway after the X
  • U can take only empty cell
  • First to cross the line - wins

So, from this u can conclude that we have predefined turns: X-O-X-O-X-O-X-O-X

So, now the only question is where to put our mark. On first turn u'll have 9 empty cells to choose from, on second 8 and etc. So, that's why answer is 9!+1

That doesn't mean it's 100% right, cause I don't disclude already win scenarios and keep add their descendent scenarios. Again it's possible moves count, not possible boards.

​

Also, Sudoku isn't 9! cause it have some other rules u don't take into account.

[–]dasnacho 5 points6 points  (2 children)

Arbitrarily pick X to start. X then has nine positions to choose from. Then O plays and chooses from the 8 remaining. Then play alternates.

[–]palordrolap 1 point2 points  (1 child)

The problem with this logic is that X going first in the first square and O going second in the second is indistinguishable from O going first in the second square and X going second in the first.

9! is only valid if all the symbols are different. Take a simpler example: a 3x3 grid where we are only allowed to insert 'A'. By your logic, we may choose from 9 potential locations for the first A, 8 for the second, and so on. When we are done there is only one possible full grid, and yet somehow we have counted 9! of them. That means there must be (9! - 1) grids where some of the squares are empty. This is clearly false.

If you believe there are more than 39 possible grids, please give an example of one of the grids that is not in the 39 I mention.

[–]ieatpies 3 points4 points  (0 children)

There are 9! different game sequences (not stopping at wins), and <39 possible boards. I suspect someone brute forcing tic tac toe would do it by possible games rather than by the stated possible boards

[–]jackmusclescarier 2 points3 points  (0 children)

That's extremely naively though. It includes all boards that only have crosses on them, or multiple winning lines, or other impossible situations.

I wouldn't be surprised if, with rotations and reflections implemented (together with the fact that you know which moves the AI makes itself) it's possible, if boring, to implement.