• Posts
  • RSS
  • ◂◂RSS
  • Contact

  • Nomic Game 3

    February 7th, 2019
    nomic  [html]
    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.

    Comment via: facebook, hacker news

    Recent posts on blogs I like:

    What I've been doing instead of writing

    I’ve been too busy with work to write much recently, but in lieu of that, here’s a batch of links to other stuff I’ve been doing elsewhere. The thing I’m most excited about: Wave raises $200m from Sequoia, Stripe, Founders Fund and Ribbit at a $1.7b valuati…

    via benkuhn.net September 11, 2021

    Some reasons to measure

    A question I get asked with some frequency is: why bother measuring X, why not build something instead? More bluntly, in a recent conversation with a newsletter author, his comment on some future measurement projects I wanted to do (in the same vein as ot…

    via Posts on Dan Luu August 27, 2021

    Songs about terrible relationships

    [Spoilers for several old musicals.] TV Tropes lists dozens of examples of the “I want” song (where the hero of a musical sings about their dream of escaping their small surroundings). After watching a bunch of musicals on maternity leave, I’m wondering h…

    via The whole sky July 17, 2021

    more     (via openring)


  • Posts
  • RSS
  • ◂◂RSS
  • Contact