Is this a Q-learning algorithm or just brute force?
Kudos for figuring out a working tic-tac-toe playing algorithm from scratch!


  Question 1: Can I successfully argue that I am estimating the reward based on history, and still claim the algorithm is reinforced learning or even Q-learning?


First things first, this is definitely not Q-learning.

However, I do think it classifies as Reinforcement Learning. You have implemented these key components of RL:


A state (the current board), used as input on each step.
An action (desired next board arrangement), used as output. When the action is effectively to choose the next state directly, this is sometimes called the afterstate representation. It is commonly used in RL for deterministic games.
Rewards generated by the environment, where the agent's goal is to maximise expected reward.
An algorithm that can take data about states, actions and rewards, and learn to optimise expected reward through gaining experience within the environment.


Your algorithm is closest IMO to Monte Carlo Control, which is a standard RL approach.

One of the big advantages of Q Learning is that it will learn an optimal policy even whilst exploring - this is known as off-policy learning, whilst your algorithm is on-policy, i.e. it learns about the values of how it is currently behaving. This is why you have to reduce the exploration rate over time - and that can be a problem because the exploration rate schedule is a hyper-parameter of your learning algorithm that may need careful tuning.


  Question 2: If I replace the reward lookup which is based on the board layout, with a neural network, where the board layout is the input and the reward is the output, could the algorithm be regarded as deep reinforcement learning?


Yes, I suppose it would be technically. However, it is unlikely to scale well to more complex problems just from adding a neural network to estimate action values, unless you add in some of the more sophisticated elements, such as using temporal-difference learning or policy gradients. 


  Question 3: I'd don't think that I have either a learning rate or a discount factor. Is that important?


A discount factor is not important for episodic problems. It is only necessary for continuous problems, where you need to have some kind of time horizon otherwise the predicted reward would be infinite (although you could also replace the discount mechanism with an average reward approach in practice).

The learning rate is an important omission. You don't explain what you have in its stead. You have put update reward for board layout based on game outcome - that update step typically has the learning rate in it. However, for tic-tac-toe and Q-Learning, you can actually set the learning rate to 1.0, which I guess is the same as your approach, and it works. I have written example code that does exactly that - see this line which sets learning rate to 1.0. However, more complex scenarios, especially in non-deterministic environments, would learn badly with such a high learning rate.


  Question 4: Can tictactoe algorithms be classed as real learning rather than simply brute force?


Your algorithm is definitely learning something from experience, albeit inefficiently compared to a human. A lot of the more basic RL algorithms have similar issues though, and often need to see each possible state of a system multiple times before they will converge on an answer. 

I would say that an exhaustive tree search from the current position during play was "brute force". In a simple game like tictactoe, this is probably more efficient than RL. However, as games get more and more sophisticated, the machine learning approach gets competitive with search. Often both RL and some form of search are used together.