After an attempt to solve dog vs cats with siamese net, I have moved to MNIST dataset.
Solving MNIST was surprisingly easy. After a few epochs on random triplets the problem seemed to be solved.
During my work on this project I have found help in these works:
https://arxiv.org/pdf/1503.03832.pdf
https://arxiv.org/pdf/1706.07567.pdf
omoindrot/tensorflow-triplet-loss#6 (discussion on stuck loss)