Deep-Reinforcement-Rubiks-Cube-Solver

A Rubik's cube solver utilizing Double Deep Q-Reinforcement Learning

Implementation

We have 2 networks; an online- and a targetnetwork. The weights of each are represented by the symbols $\phi$ and $\phi^-$.

The onlinenetwork is updated with N-steps.
The targetnetwork is updated by copying the online network once every epoch.

The weights are updated via. gradient descent from the following equation:

$$\phi_{t+1} = \phi_{t} + \alpha \cdot TPD(n,t)\cdot \nabla_{\phi_t} Q(s_{t}, a; \phi_{t})$$

Skal det være plus eller minus

n-step target temporal difference:

$$TPD(n,t) = \sum_{k=0}^{n-1}\left( \gamma^{k} r_{t+k} + \gamma^{n} \underbrace{Q(s_{t+n},\underbrace{\underset{a}{\text{argmax}}[Q(s_{t+n}, a; \phi_{t})]}{\text{Online net picks action}}; \phi^{-}{t})}{\text{target network}} - \underbrace{Q(s_t, a_t; \phi{t})}_{\text{online network}}\right)$$

n-step temporal difference is used, since it achieves better results when using experience replay.¹ (As well as given a more accurate/stable representation of the temporal difference?)

Experiment with taking the average temperoal difference at n-steps.

1 Source: https://arxiv.org/abs/2007.06700 ↩

Data representation

To represent our Rubik's cube, we use vectors to indicate which color the indiviual tiles have. Since we have a total of 6 colours (Red, Green, Blue, Yellow, White, Orange) the vector describing the tiles colour will also be 6 long. A tile with a given colour, will exhibit this by having a "1" in the appropriate location, whilst the remaining 5 "slots" are filled with "0"'s. an example could be a red tile with the vector (0,1,0,0,0,0) or a yellow tile with the vector (0,0,0,1,0,0)

We represent our Rubik's cube by one-hot coding the color of the tiles in the form of a vector.

$$R, G, B, Y, W, O$$

Training

Initially we use trajectories generated by our shuffle mechanic to train our network, as rewards are scarce and training of our NN's otherwise would be VERY slow. This is accomplished by doing a lot of shuffels and remembering all the moves and states along the process, such that they may be used as states with an action we know is the "best", since it is the quickest path to a solves state. We reward our DDQN for making the reverse action of the shuffle, and punsish it if it doesnt.

Throughout the training process we will slowly introduce more and more instances of "real" training in the wild as the AI improves and becomes better at predicting the "correct" action in a given state. We chose to do this because the NN's are statistically very unlikely to end up in the goal state (due to its choices initially being essentially random), and will therefor seldom optain any reward in a wild enviroment.

EXPERIMENT!!!!!!!!!!!!!!!

sticky actions vs $\large\epsilon$-greedy

TODO

Tweak representation of Rubik's cube (DONE)
- Make the colours vectors (DONE)
- Expand upon the shuffle function, such that it cannot shuffle back upon itself (DONE)
- Make it save the shuffels for use in experience replay (DONE)
Make NN's
- Online and Target
- Make the NN's update at the appropriate times
  - Online = 5
  - Target = 1000
Implement experience replay based on shuffles
Make our model show us shuffels in 3D

LISCENCE

THIS PROJECT IS DUAL LISCENCED UNDER THE Apache Liscense Version 2.0 and the MIT Liscense.

yashkumar1992 / deep-reinforcement-rubiks-cube-solver Goto Github PK