What I’m trying to figure out is how to calculate the number of actions my bot will make (for both sides) if he’s brute forcing every possible state to the end (filling whole 3x3 grid).
I vaguely remember similar homework exercise in my discrete math class, but no matter how I try to google it, I only find the 9! answer.
To see that the answer is not 9!, let’s reduce our state to a 2x1 grid: _|_. It is now easy to see that to brute force this game, we’ll need 4 actions: 2 choices for player one and for each choice a single action for player two: X|_, X|O & _|X, O|X.
There is 3 possible states for each cell, so, the correct answer is 333333333 = 3^9 = 19.683 possible configurations for any small board.
Inside this number, there is some impossible to reach game states… For example, you will never see a board with 9 “X”.
Edit: Now I understood your question, if you try to build a tree, with all possible moves, without a transversal table, you will have 986.406 nodes at the end of the tree…
Formally this is sum of n-k permutations: f = sum_{k=1..n} P(n,k).
It intuitively builds up on the 9! solution, summing them up for each depth with decreasing number of possible permutations. Fun fact: this can be approximated as _e*n!.
I’ll defer to @player_one on the symmetry question
