Winner Yi Cao (Buy a ticket)

Darkness 2007-05-09 12:00:00 UTC
 
Twilight 2007-05-10 12:00:00 UTC
 
Daylight 2007-05-11 12:00:00 UTC
 
Finish 2007-05-16 12:00:00 UTC

Peg Solitaire - Rules

Arrow_down  Download Sample Code

Peg Solitaire is the 15th MATLAB Online Programming Contest.

The Problem

This contest is based on a simple peg jumping game, sometimes called Peg Solitaire. In a typical game of Peg Solitaire, the board contains pegs (sometimes marbles) and at least one empty space. You try to remove as many pegs with an artful combination of jumping moves.

Naturally our version is a little more complicated. In this contest, your goal is to jump pegs in such a way that you make your score as low as possible. This may not mean removing all the pegs.

Here's how it works. Each peg has a value, or weight. A move consists of one peg jumping over and thereby removing another peg. A "jump" is a horizontal or vertical move in which one peg passes over exactly one other peg and comes to rest on an empty space. Diagonal jumps are not permitted. You are rewarded for every peg that you remove from the board according to its weight, BUT you pay for each jump according to the weight of the jumping peg. Thus you want to harvest the high value pegs by jumping over them with low value pegs. The bigger the difference between the value of the two pegs, the better your score. If, however, you jump over a low value peg with a high value peg, the situation is reversed: your score will get worse.

In the picture above, a peg with weight 1 jumps over a peg with weight 3. The reward is 3, but the penalty is 1, so the total value of the move is 2. If you can arrange to make several jumps in a row using the same peg, however, you only have to pay the penalty once.

Here are the details.

  • Each peg has a weight. Weights are always positive.
  • The board is a matrix. Any positive number indicates a peg. Zeros indicate empty squares. Negative ones indicate squares that are off limits.
  • Every move is a four-element row vector with the format [from_row from_column to_row to_column].
  • Your code must return a four-column move matrix in which each row represents one move. This matrix can have any number of rows between 0 and (numpegs-1). Any rows in excess of (numpegs-1) are ignored.
  • The point value of each move has two parts: the REMOVAL BONUS and the LIFTING PENALTY.
  • Removal bonus: We add the value of jumped peg and remove it from the board.
  • Lifting penalty: We subtract the value of the jumping peg.
  • Consecutive moves by a single peg only incur one lifting penalty. In other words, it is to your advantage to make consecutive jumps when possible.
  • The score starts at a high value (the sum of all the peg weights). After each move the point value of that move is subtracted from the score. The goal is to minimize the score. It is possible to play in such a way that the score actually gets worse.
  • An invalid move does not generate an error. The board remains unchanged and you still pay the appropriate lifting penalty.

An Example Game

The initial score for this board is 31, or the sum of all the weights on the board. The removal bonus for this move is 8, but we have to pay a lifting penalty of 2, so the value of the move is (8 - 2) or 6 points. The score after this move is 31 - 6 = 25 points.

In move 2 there is no lifting penalty because we are still using the same peg. The score after this move is 25 - 7 = 18 points.

At this point there is no jump that will improve the score. We could jump the 4 peg over the 3 peg, but this would only make our result worse, since the lifting penalty would be worse than the removal bonus. Final score for this game: 31 - 6 - 7 = 18 points.

Here is an alternative, and slightly better, series of moves. Starting from the same initial configuration as shown above, the 4 peg can be used to jump the 3, 7, and 8 pegs in succession. Despite the fact that the first jump is disadvantageous, the overall result is better. Final score: 31 - 14 = 17 points.

Scoring

The overall score for your entry is a combination of three things:

  • Your average score across all the game boards (result)
  • How fast your code runs (runtime)
  • The cyclomatic complexity of your code, as described below (complexity)

These three factors are passed to our scoring algorithm to produce a final score, according to the equation

score = k1*result + k2*e(k3*runtime) + k4*max(complexity-10,0)

All three of these are to be minimized and the lowest overall score at the end of the contest wins. We don't publish the values k1-k4, but they aren't hard to figure out.

Your entry will time out and be disqualified if it takes more than 180 seconds (three minutes).

Cyclomatic Complexity

Cyclomatic complexity, also known as McCabe complexity, is a measure of the number of independent paths through a program's source code. Typically, as this number gets higher, it becomes more difficult to understand what's happening in a program. This makes it harder to test, modify, and refactor.

Since a file can contain multiple functions, the complexity for any given file is defined as the MAXIMUM complexity of any functions contained in it. A good practice is to keep the complexity for each function below 10, so for this contest your overall score will increase according to the complexity in excess of 10. So there is no complexity penalty for submissions in which all functions have a complexity of 10 or less.

You can measure the cyclomatic (or McCabe) complexity of any function in MATLAB using the "cyc" switch for mlint. Try this, for example: 

>> mlint -cyc magic.m
We have also included a getComplexity.m function with the contest distribution to make it easier to find the complexity for your entry.

Developing Your Entry

The files you need to get started on the contest are included in a ZIP-file available on the MATLAB Central File Exchange. If you download and uncompress this ZIP-file, you will have the files described below.

Syntax

The main routine is solver.m. This is the syntax: 
  moves = solver(board)
The solution is a four column matrix in which the moves are reported as rows. This matrix can have any number of rows between 0 and (numpegs-1). Every move is a four-element row vector with the format [from_row from_column to_row to_column].

Keep in mind that these functions must have the right signature. Variable names are unimportant. To test this function with the test suite in the ZIP-file, run runcontest.m. 

 >> runcontest

Size limitations

The code is limited in size by the database architecture. The column in our MySQL database that stores the M-code is of type text, which is limited of 65535 characters. Submissions longer than this limit will fail.

Collaboration and Editing Existing Entries

Once an entry has been submitted, it cannot be changed. However, any entry can be viewed, edited, and resubmitted as a new entry. You are free to view and copy any entry in the queue. If your modification of an existing entry improves its score, then you are the "author" for the purpose of determining the winners of this contest. We encourage you to examine and optimize existing entries.

We also encourage you to discuss your solutions and strategies with others. You can do this by posting to the thread that we've started from our newsreader.

Because of the realities of modern computing, running the same code twice will result in different timings. If a winning entry is functionally identical to an existing entry, the submitter of the original will be named the winner.

Fine Print

Allowable Functions

The allowable functions are those contained in the basic MATLAB package available in $MATLAB/toolbox/matlab, where $MATLAB is the root MATLAB directory. Functions from other toolboxes will not be available. Entries will be tested against MATLAB version 7.4 (R2007a).

The following are prohibited:

  • MEX-files
  • Java commands or object creation
  • eval, feval, inline, function handles, etc.
  • Shell escape such as !, dos, unix
  • Handle Graphics commands
  • ActiveX commands
  • File I/O commands
  • Debugging commands
  • Printing commands
  • Simulink commands
  • Benchmark commands such as tic, toc, flops, clock, pause
  • error, clear, persistent

Hacking

Entries that compromise the contest machinery are no longer allowed. We've all learned some interesting MATLAB tricks in the past by contestants figuring out how to pass information from one entry to the next, or finding clever ways to execute disallowed functions, but it's too hard for the few of us running the contest to keep ahead of the group intelligence. Until we can find a more secure system, we're running up the white flag. In short, no Welching, please.

Extraction of puzzles in the test suite by manipulating the score, runtime, or error conditions is also forbidden. In the small scale, this has been an element of many past contests, but in the Blockbuster Contest, Alan Chalker turned this into a science. Tuning the entry to the contest test suite via tweak bombing or other techniques is still allowed, but we ask that you not overwhelm the queue.

FAQ

Check our FAQ for answers to frequently asked questions about the contest.

About named visibility periods

Contests are divided into segments where some or all of the scores and code may be hidden for some users. Here are the segments for this contest:

  • Darkness - You can't see the code or scores for any of the entries.
  • Twilight - You can see scores but no code.
  • Daylight - You can see scores and code for all entries.
  • Finish - Contest end time.