{{ message }}

# betaveros / probabilistic-poliwraths Public

Code base for Probabilistic Poliwraths' participation in Art of Problem Solving's 2013–2014 Deterministic Frogs contest

Switch branches/tags
Nothing to show

## Files

Failed to load latest commit information.

# Probabilistic Poliwraths

This is the code base for Probabilistic Poliwraths' participation in Art of Problem Solving (AoPS)'s Deterministic Frogs contest.

The code is ugly. A better way to describe it would be an unholy kluge-packed conglomeration of Java, Haskell, and Perl. You have been warned. Maybe I'll polish or document it further later, but don't count on it.

## Data

Known sessions are stored in files named `s1.txt` to `s32.txt`.

As a silly hack to look at and compare guesses, I would often choose a small positive integer `k` and store guesses for session `n` in a file `s(300k + n).txt`. Such guess files are created by `report.pl` (even though it would have obviously been more logical to just write it into the Haskell). See below.

The final submitted guesses are in `actual-guess-27.txt` to `actual-guess-32.txt`. Guesses for 27 and 28 were made with `haunter`; guesses for 29 to 32 were made with `regigigas`. The Pokémon names are names of strategies; see below.

• 26 -> 27: score 54.084980
• 27 -> 28: score 59.306732
• 28 -> 29: score 59.905945
• 29 -> 30: score 61.873245
• 30 -> 31: score 57.911050
• 31 -> 32: score 60.654076

Final score: `54.084980 + 59.306732 + 2*(59.905945 + 61.873245) + 6*(57.911050 + 60.654076) = 1068.340848`

## Analysis Programs

### FrogViewer.java

`FrogViewer.java` contains a Java GUI viewer of sessions. Once you've compiled and run it, enter commands in the format `[char][number]` into the console.

`a17` shows session 17. Afterwards, `r18` overlays session 18 as the (inverted) red channel. `d19` partially grays out the displays from `a17`, and `r18` if applicable, and adds dots displaying session 19. `D20` displays session 20 as the (inverted) red channel on the dots. Of course, the numbers 17~20 are arbitrary.

FrogViewer also draws squares on cells with the right mod-3 coordinates. The squares' pattern are haphazardly hard-coded; the larger squares are the ones that (I think) are higher-ranked. This was done to make it easier to notice patterns.

`z17`, `x17` and `c17` are cheap shortcut hacks (again, 17 is arbitrary) for sequences of commands:

• `z17` = `a17`, `d18`, `D318`.
• `x17` = `a17`, `d18`, `D618`.
• `c17` = `a17`, `d18`, `D918`.

This is useful to view guesses placed in output files simultaneously as the actual session and the previous session, where the output files are generated by `report.pl`. See below.

### Other Scripts

`mod3.hs` contains a script to display frequencies of frogs by variously transformed coordinates mod 3. The transformations were more or less adjusted by hand to find the pattern.

`score.hs` compares two files with guesses or session data and calculates the difference between them, using AoPS's formula.

`report.pl` is a hack that runs the strategy for known sessions and outputs the predicted guesses to files of the form `s#.txt` where the number is a small multiple of 300 plus the session number that the guess is for. It then scores the files against the actual data and outputs the result.

For example, `perl report.pl regigigas 300` creates files `s303.txt` to `s332.txt` using the strategy named `regigigas`. See the section on Strategies.

Why 300? It should be a multiple of 3 so that FrogViewer draws mod-3-score squares correctly, since where those squares go depend on the session number mod 3, and FrogViewer is hacky enough not to have any other cues to determine what the session number is.

After running `report.pl`, I used FrogViewer to compare the guesses to the correct answers and tried to figure out any patterns that a strategy was missing.

## Strategies

`smart.hs` contains the main strategies for prediction. Except for the earliest `dumb` and `smart` and `medium` strategies, each strategy is named after a Pokémon, because wynaut?

A note: Before session 26, mod3score only looked at one dimension; it was essentially `((r - c + sess + 1) mod 3)` (with scaling). Early strategies were developed with this metric. So the strategy that gets used if you choose an earlier Pokémon name isn't actually the one I had early on.

Some strategies have magical-looking weights. They were chosen through extremely haphazard trial and error; that's all.

To run the strategy, install Haskell, then compile it with `ghc smart.hs -o smart`.

• Predict session 17 using given data with strategy `regigigas`, and output guess: `./smart regigigas 17` (Note: Most of the strategies analyze two previous grids, hence they can only predict session 3 and above.)
• Predict each currently known session except for the first two (this range is hard-coded) and score them against the actual data with strategy `regigigas`: `./smart regigigas`
• Predict sessions 10 to 19 inclusive and score them against the actual data with strategy `regigigas`: `./smart regigigas 10 19`

You could also skip compilation and interpret the script, passing the arguments described below analogously, by calling `runhaskell smart.hs <args>`. It used to be that compiling was significantly faster because I was doing stuff like indexing lists of lists, instead of using arrays. Now the difference isn't very large.

Okay, now for an English description of the strategies.

Suppose we're trying to predict a square in session number `s`. Below, `r` will be the row, `c` will be the column (zero-indexed), and `k` will be the number of frogs neighboring it in the previous session (i.e. session `s - 1`).

`dumb` was my first strategy --- with the old metric, it was simply: predict 1 frog if `2 * ((r - c + s + 1) mod 3) + k >= 6`, 0 frogs otherwise.

Afterwards, I scaled up the scores for the mod 3 part by 4 so I could make it sharper. There are two variants, called `mod3score` and `viiScore`, which again depend on mod 3 coordinates but don't really lend themselves to an English explanation. Just look at the source code or play with `mod3.hs`. `viiScore` is named because it inserts a 7 into the simpler and, by itself, unnecessarily-scaled-up `mod3score`. It also fits with the Pokémon theme. Nonexistent Generation VII. Kind of.

(Also, I just realized how `score` is inconsistently capitalized. Sorry.)

My second strategy `smart` actually simulated the frogs moving after ranking squares. The most important criterion was that squares ought to have at least 2 frog neighbors in the previous session. If not, they should have at least 1. Once the neighbor condition is satisfied, the mod 3 metric is used to further rank squares. If there are still ties, they are broken by lexicographic order. Using this ranking algorithm, we first prioritize all frogs in the previous grid by the ranking of their squares based on the grid-before-previous; the idea is that if a frog got to a good square, it would usually have had higher priority. Then going down the priority list, each frog moves to the best square that's a king's-move away.

`smart` is better than `dumb`, but simply averaging their guesses for every square improves further. This is strategy `medium`.

The Pokémon start here, and are actually just averaging variants of `dumb` and `smart`. By averaging, I mean running the strategies separately and taking a (sometimes weighted) average of their guesses for each square.

• `doduo` averages two copies of `smart`, with one of their tie-breaking lexicographic orders reversed.
• `dodrio` averages one copy of `dumb` with the two rankings of `doduo`.
• `octillery` averages eight variants of `smart` with different lexicographic orders --- row / column first, rows forward or backward, columns forward or backward. (Upon further reflection, the mod-3 ranking should always break ties along the secondary lexicographic dimension, so there were really only four distinct strategies.)
• `ninetales` averages one copy of `dumb` with the eight (not-really-distinct) variants of `smart` from `octillery`.
• `staryu` averages one copy of `dumb` with the four actually distinct variants of `smart` from `octillery`.
• `starmie` is `staryu` with the copy of `dumb` weighted double.
• `gastly` averages sixteen variants of `smart`. This time, the lexicographic tiebreaker used for prioritizing frogs and the one used for moving them were separately enumerated.
• `haunter` averages `dumb`, weighted x4, with the sixteen variants of `smart` from `gastly`. This was the strategy used for the first two score-counting sessions.
• `deoxys` averages `dumb`, weighted x12, with sixteen variants of `smart` from `gastly` and sixteen more variants of `smart` as in `gastly` but using `viiMetric`.
• `regigigas`, our final strategy, is a 562-way average between weighted variants of 97 different strategies. These weird numbers were chosen with trial and error.
• weight 18: `dumb`
• weight 4 (x16): each of 16 variants of `smart`, as in `gastly`
• weight 12 (x16): each of 16 variants of `smart`, as in `gastly`, but using `viiMetric`
• weight 1 (x32): each of 32 simulations, where frog moving is done as in `smart` using `mod3score` but frogs are prioritized with a naive lexicographic order.
• weight 8 (x32): each of 32 simulations, where frog moving is done as in `smart` using `viiScore` but frogs are prioritized with a naive lexicographic order.

Obviously, AoPS's frogs probably wouldn't have a priority ordering anything close to lexicographic order, so consistently breaking ties one way is bad. This is why `smart` evolved into `doduo` and so on.

However, a problem with entirely `smart`-based strategies (if our rankings and concept of frog movement are right) is that they consistently mispredict frogs that happen to start on high-ranked squares but are forced to move. Because those high-ranked squares were low-ranked in the previous grid, the algorithm will assume that they had low priority. What happens in `smart` is that they block other frogs from taking their high-ranked square and then vacate it when it's finally their turn to move, when no more frogs are left to move in. But in reality, it's somewhat likely that at least one neighboring frog will have lower priority and be able to move in. To balance this out, I added some strategies without fancy prioritization rules in `regigigas`.

## Average Scores

Here we list the average scores of some of our strategies. Starred strategies were run with the earliest `mod3score`, an equivalent of which is commented out in `smart.hs`. They are given as such to better reflect my actual progression of strategy accuracy. Strategies in parentheses were never my most accurate strategy at any point in time. All averages are for the strategy's predictions for sessions 3 to 32.

• `dumb`*: 43.1276
• `smart`*: 44.01683
• `medium`*: 49.266296
• `doduo`*: 49.63604
• `dodrio`*: 51.303288
• `octillery`*: 52.188797
• `staryu`*: 52.889343
• (`dumb`: 46.382164)
• (`smart`: 49.643814)
• (`medium`: 53.929264)
• (`doduo`: 52.479572)
• (`dodrio`: 55.119328)
• (`octillery`: 53.516605)
• `staryu`: 55.367916
• `starmie`: 55.63335
• (`gastly`: 54.56559)
• `haunter`: 56.111553
• `deoxys`: 57.38003
• `regigigas`: 59.260647

MIT, not that it matters.

Code base for Probabilistic Poliwraths' participation in Art of Problem Solving's 2013–2014 Deterministic Frogs contest