How can I model and solve the Knight Tour problem with reinforcement learning?

I've read about the Knight Tour problem. 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?

• Hi and welcome to AI SE! Do you know how the Q-learning algorithm works? – nbro May 20 '20 at 12:44
• Yes, but not in too complex situations – Marc Vana May 20 '20 at 13:41

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.

• 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! – Marc Vana May 20 '20 at 14:32
• I was redirected from StackOverflow to here and I'm surprised by how well you organized your answer:) – Marc Vana May 20 '20 at 14:34
• @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 :) – nbro May 20 '20 at 14:34
• 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$ – Brale May 20 '20 at 15:03
• @Brale Let me know if you think that my last edit is sufficient to correct the answer. I think so. – nbro May 20 '20 at 15:14