Let me start by noticing, I am not interested in playing a game of Tic Tac Toe, nor programming any form of "AI". With that out of the way, let me give some background:
I have found Rust, with its ownership model, frequently nudges me to rethink whatever I am building. Usually it involves fixing some structs / enums, to avoid references. Correctly structuring an object can make me avoid lots of headaches later when I actually add functionality.
One thing I noticed that helps is understanding what kind of properties should the data have? Should it maintain a certain order, or can it be unordered? Are all of the values unique, or can it have duplicates? All of these details are very important. It is wrong to just shove everything into a Vec. A Vec implies ordering and duplicates, which could be a bad model. We need to choose something which most closely represents the data.
Ok, enough lecture. Onto the Tic Tac Toe grid. Observing this grid provides me with a few important properties:
A Tic Tac Toe grid can be rotated clockwise or counterclockwise, and the game is still the same. The grid can also be flipped over horizontally or vertically and the game will be the same. To decide if anyone won, we just need to see if any rows have 3 of the same value. The rest of the grid does not matter.
I am trying to figure out the best memory model would best represent this behavior. How to build a grid whose orientation does not matter?
Ideally, all of these values should be represented in memory exactly the same way:
X|O| X| | | |
|O| = O|O| = O|O|
| | | | X| |
But how to do this? One way I was thinking, is perhaps instead of saving a grid at all, we should just be keeping track of all of the rows.
- [X, O, E] (E = Empty)
- [O, O, E]
- etc for all the other rows..
However there are several problems with this model:
- The same cells are owned by multiple rows. This is not good. Perhaps the rows can hold a reference to the cells?
- The ordering of each row should not matter. So this shouldn't be an array. A better representation may be a Set or Bag/Multiset.
#1 continues to bug me. If we have rows holding references to all of the cells, then it will be hard to update any of them because of rust's restrictions on multiple mutable borrows. Or am I wrong here? How can I update a cell using a reference from a row? Where would the cell live anyway?
It doesn't seem to help to declare the rows inside of the cells, because that leads to cyclical references.
I continue to mull over this problem with not much success. I hope someone can help me discover a better path forward.
- The ordering of each row should not matter.
This is true for your abstracted rows, but is maintaining eight sets of three square states, two or three of which must be updated with every move, really a better model than a single sequence of nine, where only one needs to change at a time? It's more complex to think about, and is less efficient to update. When you throw in steps to canonicalize the rotation and reflection, which may produce different transformations from the input/output grid on the first three moves, you may need to change even more set items with each move.
It's true that, mathematically, the mapping from grid to sequence is arbitrary and the only thing that matters is consistency, but if you view programming languages as a way to communicate with humans, then clarity of purpose, rather than mathematical idealism, should be your goal. Use a nine-item array or a three-by-three nested array for the underlying storage and treat your eight win-checking sets as views into that more ordered structure. These views could well be functions that return a set and are themselves held in a set to be applied in any order. Similarly, treat canonicalization as another way to view the underlying board.
You could sidestep the mutable borrowing by not mutating individual squares. Take a leaf from the functional-programming books and use a function that takes a board and a move and returns an entirely new board. Or takes a board and returns one of the abstracted row sets. There are only nine squares and nine moves. The win-checking views aren't needed before move six. A bit of copying isn't going be a problem.
I'd agree with another comment that this is generally overthinking it. Are you planning on expanding this game to accommodate other features and that's why being deliberate about this memory model is important? How much time are you planning on doing this in? Ask yourself questions about your goals before diving into a solution.
A simple vector seems fine. Each item in the vector is an enum representing cell state. You can translate x y coordinates to an index pretty easily.
Nothing wrong with that. My idea was to do a vector (or fixed-size array if you prefer) in one dimension. An example would be something like [0, 1, 2, 0, 1, 0, 2, 0, 2] (where O is 1, X is 2 and 0 represents an empty cell). The math to get the index is similar to this:
https://bfnightly.bracketproductions.com/chapter_3.html#building-a-simple-map
Might be overkill for a simple tic-tac-toe game, but if you want to rotate the board or whatever, you can just change the math you do to get the index. I'm not at all a math expert, but it seems like a reasonable approach.
Do you care about modeling the cells? If not, you could represent each row with just a number. When X plays, add 1 to all the rows that include the position they played, and when O plays, subtract 1. If any row reaches +3 or -3, that player wins.
As for rotation/reflection invariance, that seems more like a math problem than a Rust problem.
Why does the way you present the data change how the memory is managed? I think you are mixing data storage with display logic.
Having thought about this some more with practicality and clarity thrown out the window in favour of abstractions, how about this?
A game is a sequence of moves. Past moves are immutable, future moves unknowable; a singly linked list fits the bill here.
Each move consists of a player token and a position. The position might ordinarily be thought of as a grid index but, as you point out, it could just as well be membership in one of the potentially winning lines. Either a move is part of one of these lines or it isn't. This makes the position equivalent to a bit field. If each potential win line is distinct, they could indeed be held sparsely in a set.
Checking for a win then consists of counting player tokens for each potential win line and checking for crossing the necessary threshold. Filter, sum, max, greater than?, any?
I think this scheme would be applicable to arbitrary game boards, with none of it requiring mutation. Is that the kind of thing you were after? The reflection/rotation equivalence isn't present here, but I still think that's more an artefact of analysis, rather than a property of gameplay.