{"items": [{"author": "Danner", "source_link": "https://www.facebook.com/jefftk/posts/624094766962?comment_id=624096189112", "anchor": "fb-624096189112", "service": "fb", "text": "Was darts/target shooting a contender? There's a lot of skill games that could have very terse rules but have complicated physical issues.", "timestamp": "1376359884"}, {"author": "Jeff Kaufman", "source_link": "https://www.facebook.com/jefftk/posts/624094766962?comment_id=624096303882", "anchor": "fb-624096303882", "service": "fb", "text": "@Danner: I'm looking just at abstract games.", "timestamp": "1376359922"}, {"author": "Ozzie", "source_link": "https://www.facebook.com/jefftk/posts/624094766962?comment_id=624102646172", "anchor": "fb-624102646172", "service": "fb", "text": "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)", "timestamp": "1376362300"}, {"author": "Ozzie", "source_link": "https://www.facebook.com/jefftk/posts/624094766962?comment_id=624102696072", "anchor": "fb-624102696072", "service": "fb", "text": "For instance, Python may have a \"Checkers\" module, making Checkers take 2 lines of code, while GO may be 50 in comparison", "timestamp": "1376362340"}, {"author": "Jonathan", "source_link": "https://www.facebook.com/jefftk/posts/624094766962?comment_id=624103309842", "anchor": "fb-624103309842", "service": "fb", "text": "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.", "timestamp": "1376362784"}, {"author": "Ozzie", "source_link": "https://www.facebook.com/jefftk/posts/624094766962?comment_id=624104816822", "anchor": "fb-624104816822", "service": "fb", "text": "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.", "timestamp": "1376363755"}, {"author": "Bryce", "source_link": "https://plus.google.com/110073329443149494347", "anchor": "gp-1376375034535", "service": "gp", "text": "I bet you could beat that with hex:\u00a0\nhttp://gcrhoads.byethost4.com/GamesPuzzles/Basic.html\n. Note that the \"swap rule\" should be left out unless you also include it in go.", "timestamp": 1376375034}, {"author": "Jeff Kaufman", "source_link": "https://plus.google.com/103013777355236494008", "anchor": "gp-1376393274724", "service": "gp", "text": "@Bryce\n\u00a0It 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. \u00a0Go doesn't need a swap rule to be interesting.", "timestamp": 1376393274}, {"author": "Jeff Kaufman", "source_link": "https://www.facebook.com/jefftk/posts/624094766962?comment_id=624139497322", "anchor": "fb-624139497322", "service": "fb", "text": "@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?", "timestamp": "1376393877"}, {"author": "Jud", "source_link": "https://plus.google.com/116326897086485394386", "anchor": "gp-1376394864574", "service": "gp", "text": "I just lost The Game.", "timestamp": 1376394864}, {"author": "Bryce", "source_link": "https://plus.google.com/110073329443149494347", "anchor": "gp-1376404852593", "service": "gp", "text": "@Jeff Kaufman\n\u00a0Not 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).", "timestamp": 1376404852}, {"author": "Jeff Kaufman", "source_link": "https://plus.google.com/103013777355236494008", "anchor": "gp-1376405066901", "service": "gp", "text": "@Bryce\n\u00a0Are you saying that there could be professionals playing interesting Hex games very often on large boards without the swap rule?", "timestamp": 1376405066}, {"author": "Bryce", "source_link": "https://plus.google.com/110073329443149494347", "anchor": "gp-1376408902286", "service": "gp", "text": "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:\u00a0\n
\n
\nhttp://www.sciencedirect.com/science/article/pii/S0004370201001527\n
\n
\nA couple of particularly good quotes:\n
\n
\n\"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.\"\n
\n
\nand\n
\n
\n\"Experienced human players can probably play perfectly in any 5\u00d75 position, but likely not in every 6\u00d76 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\u00d76 board, but in fact it loses.\"", "timestamp": 1376408902}, {"author": "Jeff Kaufman", "source_link": "https://plus.google.com/103013777355236494008", "anchor": "gp-1376424767040", "service": "gp", "text": "I coded it up without the swap rule: \nhttps://github.com/jeffkaufman/game-complexity/blob/master/hex.py\n
\n
\n377 bytes gzipped, the simplest of the lot.", "timestamp": 1376424767}, {"author": "Jeff Kaufman", "source_link": "https://plus.google.com/103013777355236494008", "anchor": "gp-1376428856046", "service": "gp", "text": "@Bryce\n\u00a0\"with the swap rule, the game is a 2nd-player win by a very similar proof\"\n
\n
\nThe 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.", "timestamp": 1376428856}, {"author": "Bryce", "source_link": "https://plus.google.com/110073329443149494347", "anchor": "gp-1376432580053", "service": "gp", "text": "@Jeff Kaufman\n\u00a0Interesting 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\u00a0a 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.\"\n
\n
\nI'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.\"", "timestamp": 1376432580}, {"author": "Michael", "source_link": "https://www.facebook.com/jefftk/posts/624094766962?comment_id=745671037142", "anchor": "fb-745671037142", "service": "fb", "text": "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.", "timestamp": "1440598303"}, {"author": "Jeff Kaufman", "source_link": "https://www.facebook.com/jefftk/posts/624094766962?comment_id=745678008172", "anchor": "fb-745678008172", "service": "fb", "text": "@Michael: The 593 byte program I wrote implements the Tromp rules: http://senseis.xmp.net/?LogicalRules", "timestamp": "1440599998"}, {"author": "Michael", "source_link": "https://www.facebook.com/jefftk/posts/624094766962?comment_id=745679100982", "anchor": "fb-745679100982", "service": "fb", "text": "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.", "timestamp": "1440600564"}, {"author": "Kenneth", "source_link": "https://www.facebook.com/jefftk/posts/624094766962?comment_id=745680278622", "anchor": "fb-745680278622", "service": "fb", "text": "There are language-agnostic metrics to measure software complexity: https://en.wikipedia.org/wiki/Cyclomatic_complexity", "timestamp": "1440601277"}, {"author": "Jeff Kaufman", "source_link": "https://www.facebook.com/jefftk/posts/624094766962?comment_id=745680822532", "anchor": "fb-745680822532", "service": "fb", "text": "@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.", "timestamp": "1440601841"}, {"author": "Jeff Kaufman", "source_link": "https://www.facebook.com/jefftk/posts/624094766962?comment_id=745681072032", "anchor": "fb-745681072032", "service": "fb", "text": "@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.", "timestamp": "1440601947"}, {"author": "Michael", "source_link": "https://www.facebook.com/jefftk/posts/624094766962?comment_id=745681126922", "anchor": "fb-745681126922", "service": "fb", "text": "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.", "timestamp": "1440602031"}, {"author": "Kenneth", "source_link": "https://www.facebook.com/jefftk/posts/624094766962?comment_id=745681371432", "anchor": "fb-745681371432", "service": "fb", "text": "Jeff Kaufman But surely it's a better proxy in practice than file size?", "timestamp": "1440602271"}, {"author": "Jeff Kaufman", "source_link": "https://www.facebook.com/jefftk/posts/624094766962?comment_id=745681640892", "anchor": "fb-745681640892", "service": "fb", "text": "@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.", "timestamp": "1440602505"}, {"author": "Paul", "source_link": "https://www.facebook.com/jefftk/posts/624094766962?comment_id=745681670832", "anchor": "fb-745681670832", "service": "fb", "text": "Binary lambda calculus seems a reasonable metric", "timestamp": "1440602518"}, {"author": "Jeff Kaufman", "source_link": "https://www.facebook.com/jefftk/posts/624094766962?comment_id=745681720732", "anchor": "fb-745681720732", "service": "fb", "text": "For example, unrolling loops decreases branching and increases bytes, and I think it makes code more complex.", "timestamp": "1440602554"}, {"author": "Jeff Kaufman", "source_link": "https://www.facebook.com/jefftk/posts/624094766962?comment_id=745681780612", "anchor": "fb-745681780612", "service": "fb", "text": "@Paul: Do you expect that to differ much in the relative numbers of bytes from what I did?", "timestamp": "1440602616"}, {"author": "Paul", "source_link": "https://www.facebook.com/jefftk/posts/624094766962?comment_id=745683242682", "anchor": "fb-745683242682", "service": "fb", "text": "No!", "timestamp": "1440602852"}, {"author": "Kim", "source_link": "https://www.facebook.com/jefftk/posts/624094766962?comment_id=745688272602", "anchor": "fb-745688272602", "service": "fb", "text": "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.", "timestamp": "1440603700"}]}