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).
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.
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 (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.
