• Posts
  • RSS
  • ◂◂RSS
  • Contact

  • Simplest Interesting Game

    August 12th, 2013
    games  [html]
    Yesterday in the discussion on aliens don't play chess people suggested various contenders for the title of simplest abstract game that's interesting enough that a professional community could reasonably play it full time. I went thinking Go was the clear winner, but people suggested Checkers and Dots and Boxes might be simpler while remaining sufficiently interesting. [1] Is Checkers actually simpler than Go? If so, how much? How would we decide this?

    Initially you might approach this by writing out rules. There's an elegant set for Go and I wrote some for Checkers, but English is a very flexible language. Perhaps my rules are underspecified? Perhaps they're overly verbose? It's hard to say.

    A more objective test is to write a computer program that implements the rules. It needs to determine whether moves are valid, and identify a winner. The shorter the computer program, the simpler the rules of the game. This only gives you an upper bound on the complexity, because someone could come along and write a shorter one, but in general we expect that shorter programs imply shorter possible programs.

    To investigate this, I wrote ones for each of the three games. I wrote them quickly, and they're kind of terse, but they represent the rules as efficiently as I could figure out. The one for Go is based off Tromp's definition of the rules while the other two implement the rules as they are in my head. This probably gives an advantage to Go because those rules had a lot of care go into them, but I'm not sure how much of one.

    The programs as written have some excess information, such as comments, vaguely friendly error messages, whitespace, and meaningful variable names. I took a jscompiler-like pass over them to remove as much of this as possible, and making them nearly unreadable in the process. Then I ran them through a lossless compressor, gzip, and computed their sizes:

    • Checkers: 646 bytes
    • Dots and Boxes: 499 bytes
    • Go: 593 bytes

    Update 2013-08-13: Added Hex. It comes in at 377 bytes gzipped, without the "swap rule". It's also been independently invented, which is some evidence for the claim that simpler games are more likely to be played elsewhere.

    (The programs are on github. If you have suggestions for simplifying them further, send me a pull request.)


    [1] Go is the most interesting of the three, and has stood up to centuries of analysis and play, but Dots and Boxes is surprisingly complex (pdf) and there used to be professional Checkers players. (I'm having a remarkably hard time determining if there are still Checkers professionals.)

    Comment via: google plus, facebook, lesswrong

    Recent posts on blogs I like:

    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

    Collections: Teaching Paradox, Europa Universalis IV, Part III: Europa Provincalis

    This is the third part of our series (I, II) examining the historical assumptions of Paradox Interactive’s grand strategy computer game set in the early modern period, Europa Universalis IV (which is in turn the start of a yet larger series looking at sev…

    via A Collection of Unmitigated Pedantry May 14, 2021

    Randal O’Toole Gets High-Speed Rail Wrong

    Now that there’s decent chance of US investment in rail, Randal O’Toole is resurrecting his takes from the early Obama era, warning that high-speed rail is a multi-trillion dollar money sink. It’s not a good analysis, and in particular it gets the reality…

    via Pedestrian Observations May 12, 2021

    more     (via openring)


  • Posts
  • RSS
  • ◂◂RSS
  • Contact