Project4: Join the dots.

You are given a set of points in the unit square with the property that no three points lie on a single line. You play against an opponent, alternating moves. The aim is to connect points in such a way that a closed cycle of at least 3 points is formed. A player who closes a cycle of length $n$ scores $n$ points.

A player may choose any two points to join with a straight line, as long as that line does not cross an existing line segment in the game.

If a player closes a cycle, then all points on the cycle are removed from the game, along with each line that has an endpoint on the cycle.

The game continues until fewer than three points remain. You cannot ``skip'' a turn. The winner is the player with the most points.

For example, consider the following board.

   

Player 1 joins two points with the solid line, and player 2 with the dashed line to give the following position.

   

After two more moves, the position looks like this:

   

Note that in this position there are no cycles that can be completed in one move; we cannot form a 3-cycle by joining the top-left point with the rightmost point because the connecting line would cross the intervening vertical line. Player 1 must now allow player 2 to create a cycle. (Which move would you choose now as player 1?)

Player 1 and player 2 play as shown in the left diagram below. Player 2 has formed a 3-cycle, so player 2 scores 3 points and the triangle is removed, as in the right diagram below.

        

Player 1 closes the remaining 3-cycle, scoring 3 points, and the game is over because fewer than 3 points remain. The result is a 3-3 tie.

You are required to write a program to play this game against an opponent, with the aim of winning the game. We will provide interface specifications and a driver program that checks the legality of moves.

Think about some special cases:

1. All points lie on a circle.
2. Points are randomly generated.
3. Small numbers of points. For example, how many non-equivalent game configurations are there with 4 points? With 5 points?
4. An exhaustive analysis for the 8-point game given above.

We will run tournaments for various kinds of dot maps.