Hutter Prize

The Hutter Prize is a cash prize funded by Marcus Hutter which rewards data compression improvements on a specific 1 GB English text file, with the goal of encouraging research in artificial intelligence (AI).

Launched in 2006, the prize awards 5000 euros for each one percent improvement (with 500,000 euros total funding) in the compressed size of the file ''enwik9'', which is the larger of two files used in the Large Text Compression Benchmark; enwik9 consists of the first 1,000,000,000 characters of a specific version of English Wikipedia. The ongoing competition is organized by Hutter, Matt Mahoney, and Jim Bowery.

Goals

The goal of the Hutter Prize is to encourage research in artificial intelligence (AI). The organizers believe that text compression and AI are equivalent problems. Hutter proved that the optimal behavior of a goal-seeking agent in an unknown but computable environment is to guess at each step that the environment is probably controlled by one of the shortest programs consistent with all interaction so far. However, there is no general solution because Kolmogorov complexity is not computable. Hutter proved that in the restricted case (called AIXI^tl) where the environment is restricted to time ''t'' and space ''l'', a solution can be computed in time ''O''(t2^l), which is still intractable.

The organizers further believe that compressing natural language text is a hard AI problem, equivalent to passing the Turing test. Thus, progress toward one goal represents progress toward the other. They argue that predicting which characters are most likely to occur next in a text sequence requires vast real-world knowledge. A text compressor must solve the same problem in order to assign the shortest codes to the most likely text sequences.

Rules

The contest is open-ended. It is open to everyone. To enter, a competitor must submit a compression program and a decompressor that decompresses to the file ''enwik9''. It is also possible to submit a compressed file instead of the compression program. The total size of the compressed file and decompressor (as a Win32 or Linux executable) must not be larger than 99% of the previous prize winning entry. For each one percent improvement, the competitor wins 5,000 euros. The decompression program must also meet execution time and memory constraints.

Submissions must be published in order to allow independent verification. There is a 30-day waiting period for public comment before awarding a prize. In 2017, the rules were changed to require the release of the source code under a free software license, out of concern that "past submissions hich did not disclose their source codehad been useless to others and the ideas in them may be lost forever."

History

The prize was announced on August 6, 2006 with a smaller text file: ''enwik8'' consisting of 100MB. On February 21, 2020 it was expanded by a factor of 10, to ''enwik9'' of 1GB, similarly, the prize goes from 50,000 to 500,000 euros. The original prize baseline was 18,324,887 bytes, achieved by PAQ8F. The expanded prize baseline was 116MB.

On August 20 of that same year, Alexander Ratushnyak submitted PAQ8HKCC, a modified version of PAQ8H, which improved compression by 2.6% over PAQ8F. He continued to improve the compression to 3.0% with PAQ8HP1 on August 21, 4% with PAQ8HP2 on August 28, 4.9% with PAQ8HP3 on September 3, 5.9% with PAQ8HP4 on September 10, and 5.9% with PAQ8HP5 on September 25. At that point he was declared the first winner of the Hutter prize, awarded 3416 euros, and the new baseline was set to 17,073,018 bytes.

Ratushnyak has since broken his record multiple times, becoming the second (on May 14, 2007, with PAQ8HP12 compressing ''enwik8'' to 16,481,655 bytes, and winning 1732 euros), third (on May 23, 2009, with decomp8 compressing the file to 15,949,688 bytes, and winning 1614 euros), and fourth (on Nov 4, 2017, with phda compressing the file to 15,284,944 bytes, and winning 2085 euros) winner of the Hutter prize.

See also

* List of computer science awards

References

External links

* {{Official website, http://prize.hutter1.net/

Awards established in 2006
Computer science awards
Data compression
Challenge awards