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.
Ideally, all of these values should be represented in memory exactly the same way:
That would make the game hard to play, since you’d have to think about where your move would end up since it won’t stay on the cell you click.
I think you’re wanting to store them that way so that you can easily check for win conditions, maybe? But that’s the wrong approach. Store the cells as they appear to the player, in a 2d Array (or 1d Array with indexing math. That’s how I’d do it).
Then you can take advantage of symmetries in your win condition code, if you like. But it really couldn’t be much simpler than counting the matching cells in each row, column, and diagonal. That’s just 8 groups of 3.
I agree with others that this is drastically overthinking it. If you want to take a fancier approach, I’d recommend taking inspiration from chess. You can represent the board using two numbers: X/O, and set/unset (you can combine these into one number even since it’d be a total of 9 * 2 = 18 bits). For checking if a player has won, you could have numbers representing winning boards, and do some math to determine which player has won.
Why does the way you present the data change how the memory is managed? I think you are mixing data storage with display logic.