3
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

You are probably supposed to use exhaustive search, that is, recursively try all possible moves. They made it easier by restricting the number of possible moves. One optimization which might be needed is storing board positions and the number of fish obtained from them, so that you don't analyze twice the same sub-position; there might be too many of them to store, and in that case you should only store "large" positions. Alpha-beta pruning could also be useful perhaps, but if you haven't learned about that, there is probably no need to use it.

$\endgroup$
  • $\begingroup$ And what would be the complexity of this algorithm? $\endgroup$ – pmichna Oct 25 '13 at 0:45
  • $\begingroup$ Exponential. Presumably they chose the parameters small enough so that the problem is feasible. $\endgroup$ – Yuval Filmus Oct 25 '13 at 5:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.