Questions tagged [tic-tac-toe]
For questions about the tic-tac-toe (aka noughts and crosses) in the context of artificial intelligence.
15
questions
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, ...
- 11
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 ...
- 11
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 ...
- 235
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 ...
- 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?
...
- 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 (...
user9947
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 ...
user9947
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 =...
- 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' ...
- 23
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?
- 153
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) ...
- 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 ...
- 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 ...
- 71
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 ...
- 210
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'...
- 39