• 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 should we do about network-effect monopolies?

    Many large companies today are software monopolies that give their product away for free to get monopoly status, then do horrible things. Can we do anything about this?

    via benkuhn.net July 5, 2020

    More on the Deutschlandtakt

    The Deutschlandtakt plans are out now. They cover investment through 2040, but even beforehand, there’s a plan for something like a national integrated timetable by 2030, with trains connecting the major cities every 30 minutes rather than hourly. But the…

    via Pedestrian Observations July 1, 2020

    How do cars fare in crash tests they're not specifically optimized for?

    Any time you have a benchmark that gets taken seriously, some people will start gaming the benchmark. Some famous examples in computing are the CPU benchmark specfp and video game benchmarks. With specfp, Sun managed to increase its score on 179.art (a su…

    via Posts on Dan Luu June 30, 2020

    more     (via openring)


  • Posts
  • RSS
  • ◂◂RSS
  • Contact