I modeled the TicTacToe game as a RL problem - with an environment and an agent.
At first I made an "Exact" agent - using the SARSA algorithm, I saved every unique state, and chose the best (available) action given that state. I made 2 agents learn by competing against each other.
The agents learned fast - it took only 30k games for them to reach a tie stand-off. And the agent clearly knew how to play the game.
I then tried to use function approximation instead of saving the exact state. My function was a FF-NN. My 1st (working) architecture was 9 (inputs) x 36 x 36 x 9 (actions). I used the semi-gradient 1-step SARSA. The agents took much longer time to learn. After about 50k games they were still less good than the exact agent. I then made a stand off between the Exact and the NN agent - the exact agent won 1721 games from 10k, the rest were tied. Which is not bad.
I then tried reducing the number of units in the hidden layers to 12, but didn't get good results (even after playing for 500k+ games total, tweaking stuff). I also tried playing with convolution architectures, again - not getting anywhere.
I am wondering if there's some optimal function approximation solution that can get as-good of results as the exact agent. TicTacToe doesn't seem like such a hard problem for me.
Conceptually I think there should be much less complexity involved in solving it then can be expressed in a 9x36x36x9 network. Am I wrong, and it's just an illusion of simplicity? Or are there better ways? Maybe modeling the problem differently?