Simplest Interesting Game |
August 12th, 2013 |
| games |
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
Was darts/target shooting a contender? There's a lot of skill games that could have very terse rules but have complicated physical issues.
@Danner: I'm looking just at abstract games.
Just a note: Simplicity is similar to "amount of information", which is very dependent on the medium/language. Game A may take fewer lines in Python, but that would just mean that the game is "simpler" in Python. I don't believe that there can be an objective language-independent value for complexity (or simplicity)
For instance, Python may have a "Checkers" module, making Checkers take 2 lines of code, while GO may be 50 in comparison
@Ozzie: " Python may have a Checkers module, making Checkers take 2 lines of code, while Go may be 50 in comparison"
While this is true at the extreme, I would expect that any general purpose programming language would give similar results to what I found here. Do you think that if I redid these programs in C I would get different relative sizes? Some other language?
But language is always going to be a complicating factor. Consider for instance the analogous story between metric and english systems, say you want to determine a distance in metric using the next smaller measurement - just add a zero, but trying to do the same step down in english is much more complicated, you have to multiply by 12. I would say the base question lies more in being able to lay out the rules in language that a computer could understand, regardless of the code being used. Maybe some programming languages have greater mathematical capabilities, or can do more advanced boolean logic - but that is not the point here, it is more about identifying the simple game in basic terms.
I'm not saying that finding the "simplest" game is completely impossible. Just that there will have to be a few assumptions / generalizations made to give a reasonable (likely not an exact) result.
I bet you could beat that with hex: http://gcrhoads.byethost4.com/GamesPuzzles/Basic.html . Note that the "swap rule" should be left out unless you also include it in go.
@Bryce It sounds like if you leave the "swap rule" out of Hex you get boring games where the first player wins, so it's required for Hex to be an interesting game. Go doesn't need a swap rule to be interesting.
I just lost The Game.
@Jeff Kaufman Not at all. Hex is only ultra-weakly solved, meaning there's a non-constructive proof that it's a first-player win. On boards of non-trivial size the swap rule is only relevant for players of roughly equal skill (rather like komi in go).
@Bryce Are you saying that there could be professionals playing interesting Hex games very often on large boards without the swap rule?
Yes. First of all, note that with the swap rule, the game is a 2nd-player win by a very similar proof. In practice these proofs don't help at all. This paper (from 2002) has a good subsection on Hex:
http://www.sciencedirect.com/science/article/pii/S0004370201001527
A couple of particularly good quotes:
"Hex has been proved to be PSPACE-complete [36,89]. The state-space and decision complexities are comparable to those of Go on equally-sized boards."
and
"Experienced human players can probably play perfectly in any 5×5 position, but likely not in every 6×6 position. One example is the opening move most frequently played by experts. The general consensus among top players was that this move would win the unrestricted game on a 6×6 board, but in fact it loses."
@Bryce "with the swap rule, the game is a 2nd-player win by a very similar proof"
The effect of the swap rule on a partially understood game is to focus play on the parts of the space that aren't well understood yet.
@Jeff Kaufman Interesting point. I'd like to quibble with the idea of "focusing play on the parts of the space that aren't well understood yet." If a game hasn't been (at least) weakly solved then even the strongest opening moves aren't well understood. I would say it as "focusing play on likely borderline cases between winning and losing first-moves."
I'd also describe this "an effect," rather than "the effect," which makes it seem like game-tree exploration is the rule's goal. I would describe the rule's goal as "achieving approximately balanced outcomes between equally-skilled opponents."
I coded it up without the swap rule: https://github.com/jeffkaufman/game-complexity/blob/master/hex.py
377 bytes gzipped, the simplest of the lot.
How could you write an accurate Go program in 593 bytes? At the end of the game the computer has to be able to identify dead stones (unless you have players do it manually), which is a highly nontrivial problem.
@Michael: The 593 byte program I wrote implements the Tromp rules: http://senseis.xmp.net/?LogicalRules
Jeff, don't those rules imply that if black has surrounded a territory with a group of white stones inside it, they have to manually capture the white stones for them to possess the territory? This seems pretty different from normal Go.
There are language-agnostic metrics to measure software complexity: https://en.wikipedia.org/wiki/Cyclomatic_complexity
@Michael: That's equivalent to normal Go in that it doesn't change the scoring. Players can choose to stop at any point where they can quickly see how it would turn out if they played to the end.
@Kenneth: We want information theoretic complexity not branching complexity. A program with only one path through it could still be very complex in a kolmogorov sense.
Okay, I think I get it. I was thinking that if black has to manually capture white's stones, black will fill in their own territory and lose points. But if the scoring rules give you a point for your own stones inside your territory (which isn't how I usually play (I use Japanese counting) but it's how Tromp-Taylor rules work) then it doesn't matter.
Jeff Kaufman But surely it's a better proxy in practice than file size?
@Kenneth: the size of losslessly compressed size-optimized code seems like a much better proxy for kolmogorov complexity than the number of unique paths through the program, since you could design some very strange rules that minimized branching without seeming at all simple to us.
Binary lambda calculus seems a reasonable metric
For example, unrolling loops decreases branching and increases bytes, and I think it makes code more complex.
@Paul: Do you expect that to differ much in the relative numbers of bytes from what I did?
No!
The ELO rating difference between the best players and beginners has been proposed and studied as a game complexity measure; see, for example, https://www.lri.fr/~teytaud/depth.pdf.