1
$\begingroup$

I am simulating a Tic-Tac-Toe game with a human opponent. The way the RL trains is through policy/value iterations for a fixed number of iterations all specified by the user. Now, whether the human player has turn 1 or turn 2 will decide the starting state (1st move by human or empty). The starting states for the 1st case can differ as the human can make 9 different moves.

So, my questions are:

  • In tic-tac-toe, what is the effect of the starting state on the state and action value function?
  • Does it converge to the same stable value for all starting states?
  • Will the value functions change if the starting players are changed? (human vs RL to RL vs human)

NOTE: I will be enumerating all states since there are approximately 20000 states which I believe is not a big number and thus convergence should not be a problem.

Improve this question
$\endgroup$
10
  • $\begingroup$ I would like to note that there's a way to play tic tac toe so that none of the players ever loses and so it's always a tie. I think this holds no matter which action is initially taken (by the player that first plays). $\endgroup$
    – nbro
    Commented Mar 17, 2019 at 12:34
  • $\begingroup$ @nbro the position of first move is the starting state according to my terminology. $\endgroup$
    – user9947
    Commented Mar 17, 2019 at 12:38
  • $\begingroup$ Value function defined for all states (of the MDP), and that include of cause all starting states. Converge or nor is dependent on the method. Table-based Q-learning converge for Tic Tac Toe (for any competing policy). Value function defined on states, actions, transitions and rewards. It doesn't depend on quality of the agent. I suggest you read any textbook on Markov Decision Process (MDP) and Reinforcement Learning. Everything explained in depth in textbooks, stackexchange is not suitable format for those explanations. $\endgroup$
    – mirror2image
    Commented Mar 17, 2019 at 13:50
  • 1
    $\begingroup$ @NeilSlater starting state to me is the first move. For an RL opponents first move will be it's starting state if human player has turn 1. Also I am using the entire model that is explicitly creating all states and assigning values like policy/value iteration subject to the fact the opponent makes a random move for every RL move. $\endgroup$
    – user9947
    Commented Mar 17, 2019 at 16:04
  • 1
    $\begingroup$ I've written a self-play TicTacToe using basic Python and no neural networks etc here: github.com/neilslater/game_playing_scripts/blob/master/… - however, that doesn't do quite what you want in the question, mine is a self-play learner using minimax variant of Q learning. Also I use after states rather than state/action split. It might still help though? $\endgroup$
    – Neil Slater
    Commented Mar 17, 2019 at 16:25

1 Answer 1

Reset to default
1
$\begingroup$

My understanding - from comments on the question - is that you are looking to train a Reinforcement Learning agent on the game of Tic Tac Toe (perhaps just in theory), where the agent should learn to play against a "human" opponent. In practice you may want a model of a human opponent.

In this case, the RL agent will be presented with a board state, it will take an action (to put its mark on an empty place in the grid) and either:

  • Win immediately, receiving a positive reward. It is common to use +1 in a game like Tic Tac Toe, so I will assume that later.

  • Lose on opponent's turn, receiving a negative reward (assumed -1 later in the answer), as opponent makes a move that causes it to win. This is effectively "immediately" in terms of time steps, the agent does not get to act afterwards.

  • Receive zero reward, and a new board state that includes the opponent's move

  • Receive zero reward, and the game ends in a draw

In all cases, the opponent is considered part of the environment. That makes the opponent behaviour critical to the value function and choice of optimal play. Training versus different opponents can result in very different state values.

For training to be stable, the opponent should behave with the same probability of action choices for each interim state that it observes. That includes it behaving deterministically, even optimally, purely randomly or anything in-between provided the probability distribution is fixed.

With the above context, it is possible to give sound answers to your questions:

In tic-tac-toe, what is the effect of the starting state on the state and action value function?

Each state of the board, or each state/action pair if you want to track action values, should converge to a value, depending on the agent's estimated, expected result at the end of the episode. As there is only a single reward possible at the end of each game, this will vary between -1 and +1. If either the agent or the opponent can make mistakes at random, then non-zero values between -1 and +1 are possible.

Does it converge to the same stable value for all starting states?

That depends on behaviour of the opponent. In the scenario you are working with, the agent may not learn to play optimally in general, instead it will learn to gain optimal results against the supplied opponent. If the opponent can make mistakes, then moves which take advantage of that fact will have higher values.

Without a detailed description of the opponent it is not possible to make many statements about the actual state values and action values.

Against a perfect opponent, with the RL going second, it should converge to state values which are all zero and action values which are all zero or -1 for moves which would be mistakes.

Against a completely random opponent, I would have to run it to be sure, but I would expect state values to have 3 different values, all slightly positive, depending if opponent chose middle, edge or corner cases - each of these would have slightly different chance of leading to a win for the agent going forward.

Will the value functions change if the starting players are changed?

Due to the turn-based nature of the game, all the states observed would be different depending on who was the first player. When the agent goes first it will get to score the empty grid and action values of any position it would like to make a first mark in - it gets to see state after turn 0 on time step 1, after turn 2 on time step 2, after turn 4 on time step 3 etc. When the agent goes second it will get to see and evaluate the outpt of other turns - turn 1 at t=1, turn 3 at t=2, turn 5 at t=3 etc.

That means the sets of states and state/action pairs for each case (RL first or RL second) are disjoint, and you cannot ask if one agent has the same value for a specific state as the other agent - it simply won't know about the other agent's values.

If you train a single agent, sometimes starting first, sometimes starting second, the two sets of values never interact with each other directly - in an enumerated table, as per the question, this is not at all, but if an agent uses function approximation such as neural networks, then they can affect each other.

Improve this answer
$\endgroup$
2
  • $\begingroup$ It seems to me that your last statement is not true in general. Even in turn-based games like this, if you use function approximation, then the two sets of values would interact. Like in AlphaGoZero $\endgroup$
    – Philip Raeisghasem
    Commented Mar 17, 2019 at 17:21
  • $\begingroup$ @PhilipRaeisghasem: You are right, my statement only applies to enumerated states - that does apply to OP, but I will add a caveat. Also in Go I think it is possible for the board to be identical on a black or white player's move due to pieces being removed from the board $\endgroup$
    – Neil Slater
    Commented Mar 17, 2019 at 17:36

You must log in to answer this question.