Does Checkers have simpler rules than Go?

I’ve seen var­i­ous con­tenders for the ti­tle of sim­plest ab­stract game that’s in­ter­est­ing enough that a pro­fes­sional com­mu­nity could rea­son­ably play it full time. While Go prob­a­bly has the best ra­tio of in­ter­est to com­plex­ity, Check­ers and Dots and Boxes might be sim­pler while re­main­ing suffi­ciently in­ter­est­ing. [1] But is Check­ers ac­tu­ally sim­pler than Go? If so, how much? How would we de­cide this?

Ini­tially you might ap­proach this by writ­ing out rules. There’s an el­e­gant set for Go and I wrote some for Check­ers, but English is a very flex­ible lan­guage. Per­haps my rules are un­der­speci­fied? Per­haps they’re overly ver­bose? It’s hard to say.

A more ob­jec­tive test is to write a com­puter pro­gram that im­ple­ments the rules. It needs to de­ter­mine whether moves are valid, and iden­tify a win­ner. The shorter the com­puter pro­gram, the sim­pler the rules of the game. This only gives you an up­per bound on the com­plex­ity, be­cause some­one could come along and write a shorter one, but in gen­eral we ex­pect that shorter pro­grams im­ply shorter pos­si­ble pro­grams.

To in­ves­ti­gate this, I wrote ones for each of the three games. I wrote them quickly, and they’re kind of terse, but they rep­re­sent the rules as effi­ciently as I could figure out. The one for Go is based off Tromp’s defi­ni­tion of the rules while the other two im­ple­ment the rules as they are in my head. This prob­a­bly gives an ad­van­tage to Go be­cause those rules had a lot of care go into them, but I’m not sure how much of one.

The pro­grams as writ­ten have some ex­cess in­for­ma­tion, such as com­ments, vaguely friendly er­ror mes­sages, whites­pace, and mean­ingful vari­able names. I took a js­com­piler-like pass over them to re­move as much of this as pos­si­ble, and mak­ing them nearly un­read­able in the pro­cess. Then I ran them through a lossless com­pres­sor, gzip, and com­puted their sizes:

  • Check­ers: 648 bytes

  • Dots and Boxes: 505 bytes

  • Go: 596 bytes

(The pro­grams are on github. If you have sug­ges­tions for sim­plify­ing them fur­ther, send me a pull re­quest.)


[1] Go is the most in­ter­est­ing of the three, and has stood up to cen­turies of anal­y­sis and play, but Dots and Boxes is sur­pris­ingly com­plex (pdf) and there used to be pro­fes­sional Check­ers play­ers. (I’m hav­ing a re­mark­ably hard time de­ter­min­ing if there are still Check­ers pro­fes­sion­als.)

I also posted this on my blog.