It's possible to arrive same board configuration via different paths. Realized that when I got some unexpected results. A better approach should isolate the implementation of "canonical representation of a symmetry group" from its users, say by returning it via a method.įinally, the structure to hold the connection between groups via player moves is a graph, not a tree. For reasons I'll explain later, I want to have a single, "canonical" state that represents the group and going to place that group at the first element of the list. SymmetryGroup = List Why a list but not a Traversable ( sets are traversable too)? Well. A longer project should use more human readable structures.Įxample state: TOP_LEFT_STATE = ((1, 0, 0),Ī symmetry group, a set of states that are equivalent under rotation and mirror, can be represented via a list of States. I was able to keep constraints in my mind over the few hours I worked on the problem. But this type gave me a least complicated functional structure to hold a state. Better practice could be using enums for tile values, and a class for a state. There are additional unspoken constraints on the State type, such as inner tuple should be made of tree integers, 0, 1 or 2. Because I am solving a very specialized function, I wanted to do it using primitives and basic structures given with Python without writing my own classes.Ĭhose to use tuples to represent a board state. Need to hold individual board states, hold their symmetry groups, and have a traversable structure to connect successive states. The actual number is surprisingly low! Data StructuresĪfter clarifying the problem, next is to define data structures to use to solve it. So, the problem is to find the number of unique board states and how they are connected via player moves. To discover the true underlying structure via unique states, one needs to group individual states into symmetry groups, set of states which are equivalent under these symmetry transformations. The board is symmetric under rotations and mirroring. You can rotate the board 90 degrees counter-clockwise and have the same state (Or turn your head 90 degrees clockwise. For example, initially putting an X at the top left corner or top right corner does not matter in terms of strategy. Some board configurations are equivalent to others. Unlike chess tic-tac-toe does not have a sense of direction. Assuming that X starts first, the number of X's is either equal to the number of O's or can be only one more.ĭrawing all paths can be fun, however that approach hides some internal structure of the problem. And also, some of these configurations are not legitimate states there is no path that leads to those states in a game that obeys the rules. This approach ignores the succession between them via player moves. A tile can be empty, or can have X or O on it, hence 3 states. More than enough space! :-)Īnother way of looking at the problem is to compute all possible board configurations. Actually, most games end before 9 steps, so only a few leaves have that depth. If each board takes 9 pixels, and we'll draw each path in the tree, there are at most 9! different paths: First move is to place an X on a tile among 9. My first idea was to draw the whole tree on my screen, which is 4K, 3,840 x 2,160 ~= 8M pixels. (Spoilers: the correct data structure is not a tree but a graph, and also the unit state is not an individual board configuration but its symmetry groups but I'll come to that later, please bear with me.) I evaluated it a bit and this time I realized that I finally have the capacity to solve it, once and for all!įirst, I thought about the problem space/size and how to implement and traverse a tree structure to store successive moves. (It was recommended by Alan Kay in a Quora question.) It triggered memories of my former struggle with the Tic-Tac-Toe problem. Yesterday, I was surveying computer science books for future study and saw the below illustration in the first chapter of " The Pattern On The Stone" by Daniel Hillis. I remember thinking about it a decade ago and giving up on computing all of them because I didn't know much about data structure and algorithms. "All states of Tic-Tac-Toe" was one of these problems. I ponder about and evaluate them, struggle with them a little bit but then give up because my knowledge and expertise is not enough to finish solving it. There are certain problems that come to my mind once in a while. All Board States and Moves of Tic-Tac-Toe A splinter in my mind
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |