Tag: greedy

Quirk #2: Stupid isn’t good either

Quirk #2: Stupid isn’t good either

by Gus Martin ♥ 0 Leave a Comment

For today’s Quirk, it’s an attempt to fix the greed issue on the base shot function. I added one simply look ahead step to ensure that the current maximum has at least one option going forward, so that the function doesn’t settle on a tile with no good moves.

It worked, to an extent. As you can see below:

greedisbetter

So while it does avoid certain obstacles, it ends up taking too many strokes to do so. Issue is also with the obstacle detection: if the line of a stroke so much as brush through a tree tile, for example, that stroke is completely discarded in favor of something else. I’ll add now a function to analyze the angle between the potential stroke and the center of the hazard, and allow it to pass through if the angle is large enough.

With that in place, in the example above, it could easily reduce 2 strokes off the base shot, making it more acceptable. (This is a Par 4 hole based on distance).

Here’s hoping that the third time is the charm!

Quirk #1: Greed isn’t good

Quirk #1: Greed isn’t good

by Gus Martin ♥ 0 Leave a Comment

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.