3
$\begingroup$

I am training a neural network to play tic-tac-toe. The input is the board (a vector of 9 doubles) and the output is a vector of Q-values (9 doubles).

The input vector is analyzed as follows: If a cell in the input vector is below -0.5 the cell is occupied by the Nought. If the cell is over 0.5 it is occupied by Cross and otherwise the cell is empty.

My goal is to create an AI that can play against a human as a Nought or as a Cross. I see several ways of trying to achieve this:

  1. We are going to train only one model. The AI does not know if it is a Nought or a Cross. The training is executed as follows: The AI is going to play against itself by first picking an action according to the output of the current model. To get the reward for the action we have to predict how the opponent would respond to our action. We use our current model and pick an action to our opponent. After the opponent action is chosen we can calculate the reward and fit the model.

  2. Same as above but instead of using the new state (state after our action) as such, we invert the new state (Noughts become Crosses and vice versa) before predicting the opponents action.

  3. We are going to train two models. The AI knows which side it is playing and can use the specific model trained to play that side. The training is executed as follows: The Model for the Cross gets to start and pick an action. The action is appended to the state which is passed to the Noughts model so it can decide on an action. After Nougths model has chosen an action the reward can be calculated for Cross' model and the model can be fit against the new learned weights. Nought's model can be fit similarly after it has learned how Cross responded to its action.

  4. Same as 1 but we fit the model for opponent moves too.

  5. Same as 2 but we fit the model for opponent moves too.

Strategy 1 seems hopeless to me because the training happens from one side only and because of this I suspect that the chosen actions for the opponent are garbage.

I see strategy 2 as a little bit better than strategy 1 because the opponent moves are chosen from the inverted board, but this has the problem that the board states are never same as the states which the model was fitted for. (There is never a case where Cross would choose an action on a board having more noughts than crosses and be fitted for the chosen action. However the opponent actions are predicted on states like this)

Only minus I can think of with the strategy 3 is that AI has to know which side it is playing on to know which model to use to choose it's actions.

Strategies 4 and 5 seem like best choices (I don't know if one is better than other) and now we come to the question in the title. Is it possible for the AI to use only one model to play both sides or should I use two models? In addition: Which of the strategies would be the best choice? Or is there a strategy I have not thought of?

$\endgroup$
4
$\begingroup$

Your game is zero-sum - i.e. if one player wins, the other loses. Therefore if player A's reward is +1, player B's reward must be -1 and vice-versa.

This allows you to take a variant of your approach (2). But instead of inverting the board or all the reward values when the player turn switches, just have the network switch between maximising or minimising the action value. The agent does need to know whose turn it is taking in that case in order to know whether it wants to take the argmax or argmin action. But this does achieve your goal of having a single model which the agent is able to use to play as either X or O.

This is a common game theory approach, called minimax, and is used in many self-play reinforcement learning environments.

Technically minimax is a separate algorithm to RL, and can be used in tree search for game solutions with any heuristic. In the case of tic-tac-toe a minimax tree search will work fine without any interim heuristic at all, just the eventual win/draw/loss rewards, due to small size of search tree. Effectively RL learns useful heuristics so that a tree search can have less depth or be more efficient.

If you use just single-step greedy look ahead (an action value or afterstate value), then you can use minimax with RL and rely on the RL to learn accurate heuristics, no need for a tree search. In more complex games, then RL, minimax and tree search - plus alpha-beta pruning of the search for efficiency - can be used together.

Regarding the neural network, try first using a tabular Q-learning approach (enumerating all after states, and estimating value of each one separately), as that is more reliable and perfectly suitable when there are not many possible game states. This will demonstrate that you have the Q-learning set up correctly before you add the extra complication of a neural network. Neural networks used in Q-learning can be unstable and need careful tuning of hyper-parameters to work, so you'll want to be sure you are adding one into a process that already works.


Here is some pseudocode for a basic Q-learning algorithm that could be applied to any two player zero-sum game with perfect information, using notation similar to Sutton & Barto:

Input: Reward function $R(s) \in \mathbb{R}$, returning reward to player A when state changes to $s$

Input: Move function $M(s,p) \subset \mathcal{S}^{+}$, allowed next states when starting in state $s$ for player $p$

Parameters: learning rate $\alpha$, exploration rate $\epsilon$, discount factor $\gamma$

Initialise: $V(s) \in \mathbb{R}, \forall s \in \mathcal{S}$

Initialise: $V(s) \leftarrow R(s)$ for all terminal states.

Repeat (episode):

$\qquad$ Init state $S$

$\qquad$ Init player $P \leftarrow playerA$

$\qquad$ Repeat (step):

$\qquad\qquad$ If $P = playerA$, then:

$\qquad\qquad\qquad$ $S^* \leftarrow \text{argmax}_{s' \in M(S,P)} V(s')$

$\qquad\qquad$ Else:

$\qquad\qquad\qquad$ $S^* \leftarrow \text{argmin}_{s' \in M(S,P)} V(s')$

$\qquad\qquad$ $V(S) \leftarrow V(S) + \alpha(R(S) + \gamma V(S^*) - V(S))$

$\qquad\qquad$ $S' \leftarrow S^*$

$\qquad\qquad$ With probability $\epsilon$, $S' \leftarrow \text{random sample from } M(S,P)$

$\qquad\qquad$ Take the action:

$\qquad\qquad\qquad$ $S \leftarrow S'$

$\qquad\qquad\qquad$ If $P = playerA$, then:

$\qquad\qquad\qquad\qquad$ $P \leftarrow playerB$

$\qquad\qquad\qquad$ Else:

$\qquad\qquad\qquad\qquad$ $P \leftarrow playerA$

$\qquad$ Until $S$ is terminal

The reward function can just be +1 if player A wins, 0 for a draw, -1 if player B wins, occurring on the terminal state. Also, you can just set $V(s) \leftarrow 0$ for all states initially. Typically for a simple game like tic-tac-toe you might set $\epsilon = 0.1, \alpha = 1.0, \gamma = 1.0$

$\endgroup$
2
  • $\begingroup$ I will checkout this minimax you mentioned and accept this as an answer if that turns out to be solution I need. If not I will be contacting you for further discussion. About first using Q-tables: I have everything else in place (batch replays, etc..) except for this learning strategy, so I would like to try out this first. $\endgroup$ – Horttanainen Sep 28 '17 at 20:22
  • 1
    $\begingroup$ @Horttanainen: I put together a tabular Q-Learning TicTacToe agent in Python (because game-playing bots is something I am interested in, but for many things I have only done the theory). It works using the principle of alternating argmax/argmin as described in my answer. github.com/neilslater/game_playing_scripts/blob/master/… - feel free to use any parts of it to study or for your project. I think it proves the validity of the approach without NNs. Adding NNs will make your project harder initially, but extends better to more complex games later on. $\endgroup$ – Neil Slater Sep 30 '17 at 15:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.