• 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:

    Best Practices Civil Service

    I propose that transportation agencies hire people whose job is to keep abreast of global developments in the field and report on best practices. Which agencies should do it? Ideally, all urban ones. Very small ones should piggyback on large ones, or part…

    via Pedestrian Observations June 14, 2021

    Collections: The Queen’s Latin or Who Were the Romans? Part I: Beginnings and Legends

    Who were the Romans? How did they understand themselves as a people and ‘Roman’ as an identity? And what were the implications of that understanding – and perhaps more importantly the underlying reality – for Roman society and the success of the Roman Emp…

    via A Collection of Unmitigated Pedantry June 11, 2021

    It's ok to feed stray cats

    Before we had kids, Jeff and I fostered a couple of cats. One had feline AIDS and was very skinny. Despite our frugal grocery budget of the time, I put olive oil on her food, determined to get her healthier. I knew that stray cats were not a top global pr…

    via Giving Gladly May 15, 2021

    more     (via openring)


  • Posts
  • RSS
  • ◂◂RSS
  • Contact