Nomic Game 3


Our third game of nomic ended quickly, before all of the players had even managed to join (#107). While trying to fall asleep last night I realized a way I could win: #33 gives a point per PR merged, and #49 allows transferring points between players. To keep someone from gaining unbounded points from transfers, #49 requires the total number of points to decrease. This also allows you to make PRs that reduce your points without anyone else having to approve, which is how I could have won last game (#103).

So what I realized I could do was create PRs like #112 that all consisted simply of adding the file players/jeffkaufman/bonuses/lose-a-point with contents -1. All of these PRs would be allowed to merge, but then the file would only be created once, and if I merged N pull requests I would expect to gain N-1 points. The key thing is that git does not consider it a merge conflict if two different PRs create the same file with the same contents.

Your chance of winning is 1/100,000 per point you have, per PR merged. (See validate.py:determine_if_winner) Intuitively, you need about 2*sqrt(100,000), or about 650 one-point PRs to win. For safety I rounded up to 1,000 and started work.

I made 1000 local commits, each creating the same "lose me a point file". I needed them to all have different hashes, and the easiest way to do this was to sleep at least a second each time, since timestamp goes into the hash calculation:

 for i in {1000..2000}; do git checkout master git checkout -b testing-$i echo -1 > players/jeffkaufman/bonuses/lose-a-point git add players/jeffkaufman/bonuses/lose-a-point git commit -m "lose a point" sleep 1.1 done

This took about fifteen minutes, and then I started pushing these to GitHub:

 for i in {1000..2000}; do git checkout testing-$i git push done

This was pretty slow, about four seconds per push. I could have parallelized by using multiple git checkouts, but I was pretty sleepy at this point and just let it run.

I started running PRs for each of these (#113 through #213) and merging them as they finished passing tests.

It was pretty slow going, which got me thinking more about how to speed this up. I realized I could create #214 and #215 which each added files giving me 1,000,000, and each added a same-named file losing me 1,000,001. Since the same-named losing file would be lost in resolving merge conflicts I would end up with tons of points and win.

Unfortunately there were two problems. First, I had clogged the Travis CI queue with tons of PRs that were not worth very much. I looked at the build system, but in my sleepy state couldn't figure out how to cancel builds. Then, worse, I noticed my #215 build had been cancelled by someone else!

It turns out Todd had figured out I was causing trouble and was cancelling my build. Seeing that he could cancel builds got me to try harder, though, and I realized the reason I didn't see a cancellation button is that I wasn't logged into Travis. After logging in I could cancel all my low-value builds and focus on the two that would win me the game.

The build for #214 ran quickly and Todd merged it, I think to check if this this would keep #215 from passing. I clicked "restart" on #215's build several times but Todd just kept cancelling it. Since he could cancel it in less time than it took to run I wasn't going to get anywhere.

I duplicated #215 as #216, that build ran successfully, and when Travis went green I merged the PR to win:

(Todd could have potentially won this way, by cancelling all my builds until I was too tired to continue, and then exploiting the bug himself. Sportingly he didn't; thanks Todd!)

I declared victory and went to sleep, very tired.

The simplest fix is to require PRs to be up-to-date before merging. This means that you can't exploit merge conflicts because validation has to run on exactly what you plan to merge. We could then possibly rework when we allow out-of-date approvals to effectively implement this ourselves (#95). For now we've done just the former and restarted.