Answers.Body: <h3>Model your problem as an MDP</h3>
  
  <p>To solve a problem with reinforcement learning, you need to model your problem as a Markov decision process (MDP), so you need to define </p>
  
  <ul>
  <li>the state space, </li>
  <li>the action space, and</li>
  <li>the reward function</li>
  </ul>
  
  <p>of the MDP.</p>
  
  <h3>Understand your problem and the goal</h3>
  
  <p>To do define these, you need to understand your problem and define it as a goal-oriented problem.</p>
  
  <p>In the knight tour problem, there's a knight that needs to visit each square of a chessboard <strong>exactly once</strong>. The knight can perform <strong>only <span class="math-container">$L$</span>-shaped moves</strong> (as for the rules of chess). See the animation below (taken from <a href="https://en.wikipedia.org/wiki/Knight%27s_tour" rel="nofollow noreferrer">the related Wikipedia article</a>).</p>
  
  <p><a href="https://i.sstatic.net/oEY0H.gif" rel="nofollow noreferrer"><img src="https://i.sstatic.net/oEY0H.gif" alt="enter image description here"></a></p>
  
  <p>The <strong>goal</strong> is then, by making <span class="math-container">$L$</span> moves, to find a path through the squares such that each square is visited exactly once. </p>
  
  <h3>What is the state space?</h3>
  
  <p>You could think that the state space <span class="math-container">$S$</span> could be the set of all squares of the chessboard. So, if you have an <span class="math-container">$n \times n$</span> chessboard, then <span class="math-container">$|S| = n^2$</span>, i.e. you will have <span class="math-container">$n^2$</span> states. </p>
  
  <p>However, this can be problematic because a square alone doesn't tell you all the information that you need to know to take the optimal action. So, you need to define the states such that all available information is available to the agent, i.e. you need to define a state as the position of the current square and the position of the other available squares.</p>
  
  <h3>What is the action space?</h3>
  
  <p>The action space could be defined as the set of all actions that the knight can take across all states. Given that the knight can only take <span class="math-container">$L$</span> moves, whenever the knight is in state <span class="math-container">$s$</span>, only <span class="math-container">$L$</span>-shaped actions are available. Of course, it is possible that, for each state <span class="math-container">$s$</span>, there's more thane one valid <span class="math-container">$L$</span>-shaped action. That's fine. However, the chosen <span class="math-container">$L$</span>-shaped action will definitely affect your next actions, so we need a way of guiding the knight. That's the purpose of the reward function!</p>
  
  <h3>What is the reward function?</h3>
  
  <p>The reward function is typically the most crucial function that you need to define when modeling your problem as an MDP that needs to be solved with an RL algorithm.</p>
  
  <p>In this case, you could give a reward of e.g. <span class="math-container">$1$</span> for each found path. More precisely, you will let your RL agent explore the environment. If it eventually finds a correct path (or solution), you will give it <span class="math-container">$1$</span>. You could also penalise the knight if it ends in a situation where it cannot take an <span class="math-container">$L$</span>-shaped action anymore. Given that you don't really want this to happen, you could give it a very small reward e.g. <span class="math-container">$-100$</span>. Finally, you could give it a reward of <span class="math-container">$0$</span> for each action taken, which could imply that you don't really care about the actions that the knight takes, as long as it reaches the goal, i.e. find a path through the chessboard.</p>
  
  <p>The design of the reward function will highly affect the behaviour and performance of your RL agent. The above-suggested reward function may actually not work well, so you may need to try different reward functions to get some satisfactory results. </p>
  
  <h3>Which RL algorithm to use?</h3>
  
  <p>Of course, you will also need to choose an RL algorithm to solve this problem numerically. The most common one is Q-learning. You can find its pseudocode <a href="https://github.com/udacity/rl-cheatsheet/blob/master/cheatsheet.pdf" rel="nofollow noreferrer">here</a>.</p>
  
  <h3>How to implement this with OpenAI's gym?</h3>
  
  <p>You probably need to create a custom environment and define the state and action spaces, as well as the reward function. I cannot tell you the details, but I think you can figure them out.</p>
  
  <h3>Is RL the right approach to solve this problem?</h3>
  
  <p>RL isn't probably the most efficient approach to solve this problem. There are probably more efficient solutions. For example, there's a divide-and-conquer approach, which I am not familiar with, but that you may also try to use and compare with the RL approach. </p>
  
  <p>You could also read the paper <a href="https://core.ac.uk/download/pdf/81943311.pdf" rel="nofollow noreferrer">Solution of the knight's Hamiltonian path problem on chessboards</a> (1994), especially, if you are already familiar with the Hamiltonian path problem (HPP). Note that the knight tour problem is an instance of the HPP. </p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-05-20T14:32:37.337Z
Answers.Text: Thank you very much for your answer! I do really appreciate it! I'll try to implement it! :) And thanks a lot for the 2 links you put into your answer, I'll also read them!
Answers.UserDisplayName: Marc Vana
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-05-20T14:34:03.407Z
Answers.Text: I was redirected from StackOverflow to here and I'm surprised by how well you organized your answer:)
Answers.UserDisplayName: Marc Vana
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-05-20T14:34:55.480Z
Answers.Text: @MarcVana I like to write good answers (especially when they are related to a topic that I really like, in this case RL). I try my best to achieve that, but I know they are not perfect, but, hopefully, they will be at least useful :)
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-05-20T14:35:46.997Z
Answers.Text: But I need to create an environment, right? So I need to type the line `gym.make('some_string_here')'`. What do I type in there? Or I need to create a new custom gym environment as shown [here](https://github.com/openai/gym/blob/master/docs/creating-environments.md)?
Answers.UserDisplayName: Marc Vana
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-05-20T14:38:27.907Z
Answers.Text: @MarcVana In this answer, I tried only to give you the foundations so that you could implement an RL algorithm to solve this problem. As I said in the answer, I think you will need to create a custom environment. How? I think you can figure these things out. Honestly, so far, I haven't used Gym but for simple or toy problems. If you have problems while using gym to solve this problem, I suggest you ask another more specific question. Note that my answer is already quite long. That means that your question was already quite broad.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-05-20T14:40:38.677Z
Answers.Text: Ok alright, I'm sorry for any inconvenience:) thanks again! I'll try it
Answers.UserDisplayName: Marc Vana
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-05-20T14:40:59.610Z
Answers.Text: @MarcVana To answer your question more directly, yes, I think you will need to create a custom environment (I edited my answer to say this).
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-05-20T14:42:42.857Z
Answers.Text: @MarcVana Also, note that this site focus more on theoretical problems. We don't like programming issues :) See our on-topic page https://ai.stackexchange.com/help/on-topic for more details. Hopefully, I will see you around asking new questions (and maybe answer questions too) in the next days, weeks and months :)
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-05-20T15:00:07.370Z
Answers.Text: Of course! For sure :)
Answers.UserDisplayName: Marc Vana
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-05-20T15:03:48.120Z
Answers.Text: Just to add to this answer that modeling state space isn't as simple as defining $n \times n$ board. If you do that you will not have fully observable environment so you would have to model it as POMDP. To make it MDP you would also need to have a set of flags to know which states you already visited. So to make it MDP, number of states is much larger than $n^2$
Answers.UserDisplayName: Brale
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-05-20T15:07:58.397Z
Answers.Text: @Brale Yes, I also thought that my suggestion was problematic. But I didn't have a solution at the time. Thanks for pointing this out.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-05-20T15:14:29.963Z
Answers.Text: @Brale Let me know if you think that my last edit is sufficient to correct the answer. I think so.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-05-20T15:16:44.343Z
Answers.Text: @MarcVana Please, see my last edit to my question. As Brale pointed out above in a comment, it's problematic to define the states as the squares of the chessboard.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-05-20T15:48:28.937Z
Answers.Text: Yes, I see it now and I understand what you mean. Thanks both of you!
Answers.UserDisplayName: Marc Vana
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-05-20T14:18:04.563Z
Answers.LastActivityDate: 2020-05-20T15:12:55.823Z
Answers.LastEditDate: 2020-05-20T15:12:55.823Z
Answers.UserDisplayName: nbro
Body: <p>I've read about <a href="https://en.wikipedia.org/wiki/Knight%27s_tour" rel="nofollow noreferrer">the Knight Tour problem</a>. And I wanted to try to solve it with a reinforcement learning algorithm with OpenAI's gym.</p>
  
  <p>So, I want to make a bot that can move on the chess table like the knight. And it is given a reward each time it moves and does not leave the table or step in an already visited place. So, it gets better rewards if it survives more.</p>
  
  <p>Or there is a better approach to this problem? Also, I would like to display the best knight in each generation.</p>
  
  <p>I'm not very advanced at reinforcement learning (I'm still studying it), but this project really caught my attention. I know well machine learning and deep learning.</p>
  
  <p>Do I need to start implementing a new OpenAI's gym environment and start all from scratch, or there is a better idea?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-05-20T12:44:37.253Z
Comments.Text: Hi and welcome to AI SE! Do you know how the Q-learning algorithm works?
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-05-20T13:41:19.400Z
Comments.Text: Yes, but not in too complex situations
Comments.UserDisplayName: Marc Vana
Tags: <reinforcement-learning><ai-design><game-ai><q-learning><gym>
Title: How can I model and solve the Knight Tour problem with reinforcement learning?
UserDisplayName: Marc Vana
ThreadText: # How can I model and solve the Knight Tour problem with reinforcement learning?
  
  (Asked by: username_0 on 2020-05-20)
  
  I've read about [the Knight Tour problem](https://en.wikipedia.org/wiki/Knight%27s_tour). And I wanted to try to solve it with a reinforcement learning algorithm with OpenAI's gym.
  
  So, I want to make a bot that can move on the chess table like the knight. And it is given a reward each time it moves and does not leave the table or step in an already visited place. So, it gets better rewards if it survives more.
  
  Or there is a better approach to this problem? Also, I would like to display the best knight in each generation.
  
  I'm not very advanced at reinforcement learning (I'm still studying it), but this project really caught my attention. I know well machine learning and deep learning.
  
  Do I need to start implementing a new OpenAI's gym environment and start all from scratch, or there is a better idea?
  
  **Tags:** reinforcement-learning, ai-design, game-ai, q-learning, gym
  > **Comments:**
  > **username_1**: Hi and welcome to AI SE! Do you know how the Q-learning algorithm works?  
  > **username_0**: Yes, but not in too complex situations  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2020-05-20. Score: 1 | Accepted answer
  
  ### Model your problem as an MDP
  
  To solve a problem with reinforcement learning, you need to model your problem as a Markov decision process (MDP), so you need to define
  
  * the state space,
  * the action space, and
  * the reward function
  
  of the MDP.
  
  ### Understand your problem and the goal
  
  To do define these, you need to understand your problem and define it as a goal-oriented problem.
  
  In the knight tour problem, there's a knight that needs to visit each square of a chessboard **exactly once**. The knight can perform **only $L$-shaped moves** (as for the rules of chess). See the animation below (taken from [the related Wikipedia article](https://en.wikipedia.org/wiki/Knight%27s_tour)).
  
  [![enter image description here](https://i.sstatic.net/oEY0H.gif)](https://i.sstatic.net/oEY0H.gif)
  
  The **goal** is then, by making $L$ moves, to find a path through the squares such that each square is visited exactly once.
  
  ### What is the state space?
  
  You could think that the state space $S$ could be the set of all squares of the chessboard. So, if you have an $n \times n$ chessboard, then $|S| = n^2$, i.e. you will have $n^2$ states.
  
  However, this can be problematic because a square alone doesn't tell you all the information that you need to know to take the optimal action. So, you need to define the states such that all available information is available to the agent, i.e. you need to define a state as the position of the current square and the position of the other available squares.
  
  ### What is the action space?
  
  The action space could be defined as the set of all actions that the knight can take across all states. Given that the knight can only take $L$ moves, whenever the knight is in state $s$, only $L$-shaped actions are available. Of course, it is possible that, for each state $s$, there's more thane one valid $L$-shaped action. That's fine. However, the chosen $L$-shaped action will definitely affect your next actions, so we need a way of guiding the knight. That's the purpose of the reward function!
  
  ### What is the reward function?
  
  The reward function is typically the most crucial function that you need to define when modeling your problem as an MDP that needs to be solved with an RL algorithm.
  
  In this case, you could give a reward of e.g. $1$ for each found path. More precisely, you will let your RL agent explore the environment. If it eventually finds a correct path (or solution), you will give it $1$. You could also penalise the knight if it ends in a situation where it cannot take an $L$-shaped action anymore. Given that you don't really want this to happen, you could give it a very small reward e.g. $-100$. Finally, you could give it a reward of $0$ for each action taken, which could imply that you don't really care about the actions that the knight takes, as long as it reaches the goal, i.e. find a path through the chessboard.
  
  The design of the reward function will highly affect the behaviour and performance of your RL agent. The above-suggested reward function may actually not work well, so you may need to try different reward functions to get some satisfactory results.
  
  ### Which RL algorithm to use?
  
  Of course, you will also need to choose an RL algorithm to solve this problem numerically. The most common one is Q-learning. You can find its pseudocode [here](https://github.com/udacity/rl-cheatsheet/blob/master/cheatsheet.pdf).
  
  ### How to implement this with OpenAI's gym?
  
  You probably need to create a custom environment and define the state and action spaces, as well as the reward function. I cannot tell you the details, but I think you can figure them out.
  
  ### Is RL the right approach to solve this problem?
  
  RL isn't probably the most efficient approach to solve this problem. There are probably more efficient solutions. For example, there's a divide-and-conquer approach, which I am not familiar with, but that you may also try to use and compare with the RL approach.
  
  You could also read the paper [Solution of the knight's Hamiltonian path problem on chessboards](https://core.ac.uk/download/pdf/81943311.pdf) (1994), especially, if you are already familiar with the Hamiltonian path problem (HPP). Note that the knight tour problem is an instance of the HPP.
  
  > **Comments:**
  > **username_0**: Thank you very much for your answer! I do really appreciate it! I'll try to implement it! :) And thanks a lot for the 2 links you put into your answer, I'll also read them!  
  > **username_0**: I was redirected from StackOverflow to here and I'm surprised by how well you organized your answer:)  
  > **username_1**: @MarcVana I like to write good answers (especially when they are related to a topic that I really like, in this case RL). I try my best to achieve that, but I know they are not perfect, but, hopefully, they will be at least useful :)  
  > **username_0**: But I need to create an environment, right? So I need to type the line `gym.make('some_string_here')'`. What do I type in there? Or I need to create a new custom gym environment as shown [here](https://github.com/openai/gym/blob/master/docs/creating-environments.md)?  
  > **username_1**: @MarcVana In this answer, I tried only to give you the foundations so that you could implement an RL algorithm to solve this problem. As I said in the answer, I think you will need to create a custom environment. How? I think you can figure these things out. Honestly, so far, I haven't used Gym but for simple or toy problems. If you have problems while using gym to solve this problem, I suggest you ask another more specific question. Note that my answer is already quite long. That means that your question was already quite broad.  
  > **username_0**: Ok alright, I'm sorry for any inconvenience:) thanks again! I'll try it  
  > **username_1**: @MarcVana To answer your question more directly, yes, I think you will need to create a custom environment (I edited my answer to say this).  
  > **username_1**: @MarcVana Also, note that this site focus more on theoretical problems. We don't like programming issues :) See our on-topic page https://ai.stackexchange.com/help/on-topic for more details. Hopefully, I will see you around asking new questions (and maybe answer questions too) in the next days, weeks and months :)  
  > **username_0**: Of course! For sure :)  
  > **username_2**: Just to add to this answer that modeling state space isn't as simple as defining $n \times n$ board. If you do that you will not have fully observable environment so you would have to model it as POMDP. To make it MDP you would also need to have a set of flags to know which states you already visited. So to make it MDP, number of states is much larger than $n^2$  
  > **username_1**: @Brale Yes, I also thought that my suggestion was problematic. But I didn't have a solution at the time. Thanks for pointing this out.  
  > **username_1**: @Brale Let me know if you think that my last edit is sufficient to correct the answer. I think so.  
  > **username_1**: @MarcVana Please, see my last edit to my question. As Brale pointed out above in a comment, it's problematic to define the states as the squares of the chessboard.  
  > **username_0**: Yes, I see it now and I understand what you mean. Thanks both of you!  
  
  ---
  
  