Project 4: Polygolf

In this project, you'll be writing a player to play golf. Each hole on the golf course is a polygon, and two points within the interior of the polygon are marked as the start and end points respectively. Every shot you take is expected to land and roll entirely within the polygon. In the event of a violation, your player must repeat the stroke and take a one shot penalty. The shape of the polygon is provided as a ``map'' and we'll consider a variety of maps for this project. In fact, we'll also be asking groups to submit maps and will be rating them as described later.

A player plays with a certain level of skill. The skill level is measured by a parameter s, where $10 \leq s \leq 100$ and a larger s corresponds to a more skillful player. The player aims for a point on the polygon, and hits the ball. A player's aim is not perfect, and the simulator will calculate an actual landing point for the ball using a statistical distribution based on skill. The distance a player can hit is also dependent on the skill level. When the ball lands it rolls an extra 10% of the distance that it initially traveled, in a straight line, before it comes to rest. The entire rolling portion must be within the polygon, although it is legal for the ``in the air'' portion of the trajectory to temporarily go outside the polygon boundary then come back inside. Think of the exterior of the polygon as a lake: it's ok to go over the lake, but you can't land on it.

A player's distance rating is 200+s meters. So a top professional can reach 300 meters, while an unskilled golfer can reach 210 meters. The point that a golfer aims for must be within their distance rating. The distance the ball actually travels is chosen by the simulator from N(d,d/s), the normal distribution with mean equal to d, the distance to the aimed point, and standard deviation d/s. The angle at which the shot is made may also differ from the aimed direction. If we take an angle of zero radians to mean directly towards the aiming point, then the actal angle will follow a normal distribution N(0,1/(2s)).

For shots with a destination closer than 20 meters, the simulator will allow your player to specify that it's using a putter, which just means that the entire trajectory will be along the ground. For shots with a putter, you may not go outside the polygon boundary even temporarily.

On each turn, your player will aim a shot, and then be told by the simulator what the outcome of the shot is. A successful shot will put you in a new position, presumably closer to the hole, from which you will attempt your next shot. If at any time during the rolling phase of a shot, the ball comes within 5.4cm of the hole, then you've completed the hole and you can add up the total number of shots taken (plus any penalty shots) as your score. When using a putter, the entire trajectory can be considered the rolling phase. An unsuccessful shot is one that lands outside the polygon boundary. When that happens, your player receives a penalty shot, and must continue from the previous position once more.

The goal of your player is to minimize the expected score over a large number of rounds on a variety of maps. We will cap the number of shots for any single map at 10. Any player who reaches 10 shots will get a score of 10 and terminate. Maps should be designed with conventional golf par ratings from 3 to 5 in mind. So a ``par 4'' polygon would be one for which the designer anticipated that a score of 4 would be typical.

What makes a good map? I hope we'll get to discuss this issue in class, so that we might come up with a formula to rank maps based on how players performed on them. For now, here are some high-level characteristics of a good map:

• It has a goldilocks property: not too easy but not too hard.
• Differences between skilled and less-skilled players are effectively translated into differences in expected scores, across all skill ranges.
• The map gives players more than one approach to completing the hole.
• Even unskilled players should be able to complete the hole in under 10 shots.

Maps must be simple polygons, with no donut-like holes etc. Maps do not need to be convex. For example, many real-world golf courses have dog-leg-shaped holes. Avoid useless detail in the polygon, such as many small edges to simulate a curve, because that could increase the complexity of your player's task of ``understanding'' the polygon.

We'll run a bunch of tournaments at the end to see how well your players perform. A few basic maps will be supplied with the simulator, and your first deliverable will be a map, so that we'll have a repertoire of maps to use. At the time of the final code submission, each group will also get to submit a new (previously unseen) map for use in the tournament.