How to deal with item belonging to more than one category
There are multiple ways you can do it. The first two options you propose would be valid but I'm not sure if the log-loss allows you to use probabilities as target as opposed to just binary labels, but if that is the case they will work for what you want. I have another suggestion. Let's say there are at any point n possible moves available (In case of a 2x2x2 there are three dimensions and in every dimension 4 moves I think, so that would be 12 options) you could train 12 classifiers or in the case of a neural networks just twelve sigmoids in the output layer. Then you can represent every move as a probability, represent the training targets as a vector of 1s and 0s with 1 as being an optimal move and then during classification pick the one with the highest probability.

An extension of your first option would be to add all the optimal moves as state. Say move 2 and 4 are optimal you could just add the same state twice with different labels.

EDIT: That said, I think your second option is the best one if the math works out (I'm uncertain about this and don't have time to figure it out right now) but the others will work as well.

EDIT2: According to Neil Slater the second option will work if it's implemented properly and I think that is the cleanest solution so I would go for that if possible, otherwise I would go for either go for the multiple samples for multiple optimal moves or the 12-way binary classification.