Solving Rubik's cube can be thought of as a Planning problem which has :

  • a state space $S$
  • a set $G \subseteq S$ of goal states (in this case singleton)
  • actions $A(s) \subseteq A$ applicable in each states in $S$
  • action costs $c(a, s)>0$ (optional)
  • discount factor $\gamma$ (optional)

On the other hand a MDP has an extra point:

  • transition probabilities $P_a(s'|s)$ for $s\in S$ and $a\in A(s)$

So can solution to Rubik's cube be seen from the point of view of Markov Decision Process ? What are the practical problems where principles of solving Rubik's cube can be applied ?

  • $\begingroup$ This question is a bit vague and broad. Could you better explain what you are looking for? Maybe provide some context? $\endgroup$ – A.P. Jun 10 '15 at 21:43
  • $\begingroup$ Let me know if any other clarification is needed $\endgroup$ – aroyc Jun 11 '15 at 17:02

Yes, you could perfectly model that as a MDP. Keep in mind to specify a positive reward for all terminal/goal states.

However, I would say it will not be the most effective approach. If you are planning to use reinforcement learning, I see a few problems / disadvantages. Typically you use random exploration, but here it will not help much and a planning algorithm with a good heuristic would perform much better. Another issue is the amount of possible starting points that you will need to consider if you want to obtain a good generic policy.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.