Quirk #1: Greed isn’t good

Quirk #1: Greed isn’t good

Inaugurating the Quirk category, is an interesting problem that appeared when trying to program the base shot function to avoid tiles where the next stroke would be blocked.

As it is now, the algorithm can be considered greedy; that is, it tends to find the local maximum instead of the global maximum. What does that mean?

The function to find the next best stroke focuses on mainly one factor: Distance covered by the stroke. So the function will always try to travel as far as possible with each stroke in order to minimize the Par score. However, in taking obstacles into account, sometimes the stroke with the furthest reach is not the best stroke! As we can see below:

Greedy1

There’s at least two or three tiles before the chosen one that could be used for a perfectly fine stroke, which would eliminate the danger of hitting either of the two trees in the middle. But since the algorithm is currently greedy, it’ll maximize locally, completely ignoring the global maximum. If we tweak the course further, like below, we can safely get rid of this issue:

But this is not good. Users would look at the course and go “What! There’s a perfectly fine play to be done over there! Dumb game!”. And we can’t have that!

So it’s time to smooth out the stroke calculation to look into the future for at least one or two moves, so that it can more accurately get rid of local maximums, and aim for the global.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s