Algorithm playing modification of “Hey, That's My Fish!” game

Question

Ok, I must admit this a task from my studies but I'm stuck.

Rules of the game are on Wikipedia. However, we have a modified version: on input we have a board with x fields, there are y penguins on some fields, there may be gaps between fields. All penguins are the same, they can move only to the farthest possible location (in a straight line, can't jump over gaps and other penguins). There is one player and he needs to move the penguins in such manner so as to get the maximal number of fish. I have to come up with an algorithm that finds the sequence of moves that leads to the best possible result.

I tried something like guessing the final arrengment of the fields (f.e. all the penguins left on fields with just one fish each) and then reverse-engineer the steps but I didn't go any further with my idea.

I also thought it would be probably good to represent this as a graph, possibly with weighted edges and then do some graph search but again, I don't know what next.

Finally, there was a thought about using Monte Carlo method. However, this just seems too hardcore for a class project like this and that would be too diffult for me.

Any ideas where should I start?