Added more test cases including random test cases. If no path is found, the solution should return [].

Kind of, yes. But target state can be outside of the cycle.

Math, write out the a few cases, do you notice a pattern? Then your code should try and force the other player into the position you don't want. The code that's running this definitely is just taking two instances of your class(add some System.out.println's) very easy to detect.

The key really is who moves first!

You should find strategy, how to decrease number of cakes without giving opponent chance to win. Each your move not only shortens cakes amount, but also prevents opponent from eating same number of cakes as you.