Collection Of Variable Length Sequences and Descriptions: A Search Problem I have a tough problem and need some advice:

Suppose I have a collection of variable length sequences, many of which are unique -- imagine the moves to a chess game, eg


  
  d4 Nf6
  c4 g6
  Nc3 Bg7
  e4 d6
  Nf3 O-O
  Be2 c5
  O-O Bg4
  


...

and for each item in this collection, I have another collection of descriptions generated by humans (think comments - comment_1: "cool game", comment_2: "awesome sacrifice")

The goal is to mine the associations between the comments and the sequences to tag the sequences with human readable labels for search purposes.

I've thought about topic modeling for label generation + clustering/grouping the sequences, but I cannot figure out how to do something like cluster the games. I have millions of examples of the sequences if that helps. Any idea how I can measure the distance/similarity between sequences like this? Some kind of embedding? I've thought about trying a word2vec / doc2vec approach, but haven't tested yet.

Ideally I'd be able to input an unseen sequence and suggest labels/human-readable description for this sequence as well.
While an RNN using one-hot encoded moves is possible, I would suggest that your model needs to understand chess (or similar complex games) at a deeper level to be able to associate comments to positions. 

I would encode the position itself (eg a layered representation like in Alpha-Zero paper), and pass those through a conv-RNN to model the temporal relationship between positions corresponding to annotations. (Maybe you can find a pretrained model for evaluation as a baseline).

I read a fair amount of chess commentary, and one thing that is common is that there are cases of single move as well as comments about several moves at a time (think opening lines, or forced continuations), which are fairly discrete (my 'move 10 sacrifice' and my 'move 15 blunder' are not related by a hidden state). This leads me to think that instead of an RNN model, you are really trying to first Partition then Embed moves in a comment space - which then leads to a model that is first an RNN which may learn likely partitions of moves to be commented on, then another model, perhaps conditional autoencoder, is trained jointly on (position | comment) subsequences (you should still have plenty of features to work with at this point, so no worry about a weak signal). 

The 'search' functionality here points not at a pure deep learning model, since you want to find specific instances of positions, rather than a typical position with that comment (ie sampling a latent space). This leads me to think that you create an explicit data-structure to map points in your final embedding space to their positions. So if you wanted to search 'Nice Sacrifice', model would find closest points in 'comment space' and return those games using something like cosine distance, or this last step is clustering of the (position | comment) space. 

Either way, interesting problem, try the simpler thing first.