2022 Developer Survey is open! Take survey.

Questions tagged [tic-tac-toe]

For questions about the tic-tac-toe (aka noughts and crosses) in the context of artificial intelligence.

Filter by
Sorted by
Tagged with
0 votes
0 answers
32 views

How does the Markov assumption hold true for episodic task?

The Markov assumption assumes that the current state is sufficient for taking the next action. Consider an episodic task, where the RL agent is trying to learn to play the game of tic-tac-toe. Here, ...
user avatar
1 vote
1 answer
91 views

How are rewards calculated for episodic tasks like playing chess or tic-tac-toe?

I am new to Reinforcement Learning and trying to understand the concept of reaping rewards during episodic tasks. I think in games like tic-tac-toe, rewards will be in terms of a win or lose. But does ...
user avatar
2 votes
2 answers
280 views

What is the optimal score for Tic Tac Toe for a reinforcement learning agent against a random opponent?

I guess this problem is encountered by everyone trying to solve Tic Tac Toe with various flavors of reinforcement learning. The answer is not "always win" because the random opponent may ...
user avatar
4 votes
1 answer
786 views

Why is tic-tac-toe considered a non-deterministic environment?

I have been reading about deterministic and stochastic environments, when I came up with an article that states that tic-tac-toe is a non-deterministic environment. But why is that? An action will ...
user avatar
  • 183
1 vote
2 answers
122 views

Non-Neural Network algorithms for large state space in zero sum games

I was reading online that tic-tac-toe has a state space of $3^9 = 19,683$. From my basic understanding, this sounds too large to use tabular Q-learning, as the Q table would be huge. Is this correct? ...
user avatar
  • 573
1 vote
1 answer
205 views

How to make the RL player a perfect/expert (tic-tac-toe/chess) player?

I asked a question related to tic-tac-toe playing in RL. From the answer, it seems to me a lot is dependent on the opponent (rightly so, if we write down the expectation equations). My questions are (...
user avatar
1 vote
1 answer
433 views

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

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 ...
user avatar
2 votes
1 answer
184 views

Given these two reward functions, what can we say about the optimal Q-values, in self-play tic-tac-toe?

This corresponds to Exercise 1.1 of Sutton & Barto's book (2nd edition), and a discussion followed from this answer. Consider the following two reward functions Win = +1, Draw = 0, Loss = -1 Win =...
user avatar
  • 209
2 votes
1 answer
612 views

Why isn't my Q-Learning agent able to play tic-tac-toe?

I tried to build a Q-learning agent which you can play tic tac toe against after training. Unfortunately, the agent performs pretty poorly. He tries to win but does not try to make me 'not winning' ...
user avatar
4 votes
1 answer
315 views

How do we find the length (depth) of the game tic-tac-toe in adversarial search?

When we perform the tic-tac-toe game using adversarial search, I know how to make a tree. Is there a way to find the depth of the tree, and which level is the last level?
user avatar
4 votes
2 answers
3k views

Why does self-playing tic-tac-toe not become perfect?

I trained a DQN that learns tic-tac-toe by playing against itself with a reward of -1/0/+1 for a loss/draw/win. Every 500 episodes, I test the progress by letting it play some episodes (also 500) ...
user avatar
  • 71
3 votes
2 answers
743 views

How can both agents know the terminal reward in self-play reinforcement learning?

There seems to be a major difference in how the terminal reward is received/handled in self-play RL vs "normal" RL, which confuses me. I implemented TicTacToe the normal way, where a single ...
user avatar
  • 71
5 votes
1 answer
800 views

What are good learning strategies for Deep Q-Network with opponents?

I am trying to find out what are some good learning strategies for Deep Q-Network with opponents. Let's consider the well-known game Tic-Tac-Toe as an example: How should an opponent be implemented ...
user avatar
9 votes
3 answers
2k views

How should I represent the input to a neural network for the games of tic-tac-toe, checkers or chess?

I've been reading a lot about TD-Gammon recently as I'm exploring options for AI in a video game I'm making. The video game is a turn-based positional sort of game, i.e. a "units", or game ...
user avatar
2 votes
1 answer
1k views

Why can I still easily beat my Q-learning agent that was trained against another Q-learning agent to play tic tac toe?

I implemented the Q-learning algorithm to play tic-tac-toe. The AI plays against the same algorithm, but they don't share the same Q matrix. After 200,000 games, I still beat the AI very easily and it'...
user avatar
  • 39