Number of legal 18x18 Go positions computed. One more to go
tromp.github.io
tromp.github.io
Here's an illustration:
http://youtu.be/5e8HZqF3cyk?t=2m1s
I also like this quote by von Neumann:
"If people do not believe that mathematics is simple, it is only because they do not realize how complicated life is."
I confess I do wonder what would be the equivalent 'go of RTS games', where the minimal, essential dynamics are captured without all the bling.
If you haven't seen a Counter-Strike game played competitively, this weekend a "Major" tournament is being played in Katowice[0]. It's well worth watching a match to get a glimpse of the mechanics. It might also be fun.
I'm playing a lot of CoH because it cuts all the base building ceremony down to minimum.
You can maintain this belief until today if you measure "minimality/essentiality" by size (in MB).
Most probably there are other games out there that are even more minimalistic but for sure they're less popular and less known. You could make a case for DF (although there is no MP) or even C&C1 (just ignore the balance issues).
I think the words you're looking for are "micromanagement" (if it's about dealing with more than one unit) and "mechanical skill" if it's about having twitch reaction times (for last hitting, landing spell-combos, etc.)
I play DotA on and off, and thi is the part that irritates me the most :x
The main thing (from a game theoretical standpoint) that I believe sets RTS games apart from (most) strategy board games is not the real-time nature, but the fact that RTS games are not perfect information games.
Incorporating knowledge about your opponent's playing style is important in chess (and I presume Go), but I believe it is vastly more important in RTS games, so much so that in high-level competitive games it is a primary driver of both players' decisions in the game.
Of course, from a broader (not game theoretical) standpoint, the bigger and more obvious difference between strategy board games and RTS games is that the latter, being real-time, requires substantial physical speed and coordination, which is mostly not the case with the former.
Finding interesting combos among the thousands of existing MtG cards is also very fun and cannot be done in a minimalistic game with a very small number of components like Go. They are just games with different goals and scopes.
What I dislike about the evolution of MtG is the placeholder words that they constantly add to the rules, e.g. "lifelink" for "damage dealt by this creature also causes you to gain that much life". Cards with that ability existed before the word was introduced, so the word is unnecessary, it just makes the text of the cards shorter... but the constant extensions of the vocabulary make the rules harder to understand and remember. The actual rules are still mostly like in the nineties... in fact most, if not all, of the actual rule changes have been simplifications rather than complications (mana burn removed, meh). But they just like to make up unnecessary words, it's a pity.
I wish they would strip out the trivially different cards, particularly the ones that are strictly better or worse than another, such as two identical cards but one has a higher cost for no reason.
Some of the cruft is due to rebalancing as the game evolved, but some is just part of the artificial scarcity model of making many of the common cards worse than the best rare ones.
I agree, though, that MtG has a very broad and creative tree of possibilities. In the pure board game world, it is perhaps more similar to Arimaa.
I really love the feeling of seeing an interesting card in a new expansion, and thinking that it might go well with some obscure card that you remember from some obscure expansion from 15 years ago. And researching what that card actually did. It really feels like being a wizard and going to an ancient forgotten grimoire to see if you can find a use from a long-forgotten spell. I especially enjoy realizing that a card that was considered universally crappy and never saw serious use is suddenly useful.
I agree that the cards that are strictly worse than others could have been avoided. But they don't really do that much anymore (they seldom release commons that do nothing like Hill Giant or Grizzly Bear, for example). And they can still be fun in formats like Type III, or Limited as new players call it.
This is an odd criticism. It's the essence of DRY applied to a context with very limited space (the physical surface of the card). Would you really prefer to have something like this written out in 2pt font?
http://magiccards.info/bng/en/144.html
Having a named mechanic also enables rulings to apply to it, rather than just to individual cards with a particular wording. The keywords they introduce do create a learning curve for new players, but this is Magic we're talking about--not exactly a game for people afraid of learning curves.
The winner of a Go game is whoever more reliably predicts the ultimate result of various potential intermediate positions. The only interesting game theoretic aspects at all arise to the extent one can predict one's opponents' likely errors, or that one "knows what one doesn't know" in terms of one's own calculating ability.
Read "Mathematical Go".
The sources are at https://github.com/davepeck/game-of-go under the MIT license -- I have a long list of things I'd love to work on if I could find the time.)
Terra Mystica and Caylus are two examples that I would mention as having a decent amount of complexity and are deeply strategic games without being too complicated. However, whilst still being considered as strategy games, the mechanics and methods of thinking are very different to those used in Go, so it's difficult to compare them directly.
They also have very little randomness in them, so the players' decisions are much more impactful.
Another term I've seen for this concept is "complication". Then one may speak of simple, complex, or complicated systems. Complexity is (perhaps unexpected) behavior that arises from the interaction of relatively few basic behaviors. Complication comes instead from just heaping more and more crap on top of the existing system.
There is no accounting for taste. Many people appreciate complication more than complexity.
I have played go, but not enough to be any good at it.
For example, creature cards have power and toughness. Simple enough. But then at some point, cards were printed that allowed you to modify those values. Now you have to mentally keep track of the actual state of the card. Then consider what happens when you have two effects like "add two to toughness" and "switch power and toughness" applied at the same time. Which one happens first? Much as in software, each new feature of the game inevitably has interactions with other features that have to be analyzed and handled appropriately.
Going back to the main point, this complexity is 'artificial' because it is not an emergent property of the rules themselves, but rather a consequence of the fact that so many rules have been piled on over time.
(Also, that a creature's power and toughness might change has been part of the game since the very beginning: see Giant Growth.)
Concrete example: castling[0] in chess
They have a variety of board sizes, game types, and recently added tournaments. The average game will play 2-4 moves per day. I typically have 15-18 games going simultaneously, which overall gives me just enough to do while waiting for dependencies to download or the CI server to run.
One note of caution if you've played on other servers: DGS's rankings are shifted considerably higher than many other online servers (much closer in parity with the professional organizations). More info here: http://senseis.xmp.net/?RankWorldwideComparison
Komi(compensation given to the second player) is a recent invention(1900s) and has only gone up from 4.5 to the recent 6.5 or 7.5 in some tournaments, and yet black still wins over 50% of professional games. Knowing how much komi should be is equivalent to knowing how to play the best game.
As the board fills up tactics or 'tesuji' becomes increasingly important and many times there is only one correct move, computers have become better at this but they still can struggle over common life and death problems. End game is where computers really shine and can now play better than even the best players. Overall computers have taken a recent dramatic upturn in strength thanks to Monte Carlo probabilistic reasoning and are now within a few stones of professionals.
Seemingly, Go will become as chess is within our life times probably even within the next ten years, it will be another interesting moment in the advance of 'AI', but whether it will reveal anything deeper is an open question to me.
I find Go more interesting than chess because often, especially in the beginning, the analysis is less 'hard' or involves less reading of game tree possibilities but involves more 'soft' concepts like spacing, relative territory, trading territory for influence (whether to play on the third line or the fourth line), and is something more akin to art than science if I were to grasp for a metaphor.
Computers will likely enlarge the 'end game' that is be able to play better and better than humans the last part of the game and eventually play better middle game, and eventually only the opening will be where humans have an advantage until that too is taken by computation.
(I'm about an AGA 6 dan)
Also the rating system (while necessary to find a roughly match) sorta bothers me. I keeps making me want to get a higher rating! Normally I dont care about stuff like that.
I think komi should be chosen so that black and white stand even chances when humans - not optimal players - play.
I've always loved the way it becomes so complex through such seemingly minimal and simple rules (although superko rule and komi aren't particularly simple rules).
if anyone would like to simulate this experience together we can Skype play
I don't know what server(s) you tried, but unfortunately quite a few of them have a sandbagger problem at the lower ranks. Also the ranking system itself has its inconveniences. The difference between a 19 kyu and a 16 kyu might be nearly negligible, but the difference between a 3 kyu and a 1 kyu is usually not. Coupled with the fact that it takes servers a few games to get an accurate rank, it often makes for a frustrating experience for beginners.
similarly, i find it hard to play other games because they seem silly by comparison.
"Because it's there."
The number of legal Go positions is a simply defined number that is easily approximated but an enormous computational challenge to compute exactly. I've made it my Mount Everest:-)
I also want to see if the number, written as 19x19 trits in ternary, corresponds to a legal position, which would be totally awesome (but at 1.2% the odds are against it).
I think that there's not much utility in this work beyond "it's an interesting challenge," but, well, there's not much utility in any game beyond "it's an interesting challenge."
Deleted comment
81 * 2log3 ~= 128.38
Something like numberjack, which uses constraint programming for combinatorial optimization, would be useful and an article about how someone did this would be useful but alas the op is just a dull statement of a result and doesn't have much merit imho.
shuffles on, muttering
Is this due to some subtle distinction between valid moves/games and positions? Because since the starting position is given, and the rules are set, surely it's possible (in theory) to simply emulate all possible moves, and recording positions as one goes along, backtracking on cycles [ed: and on check mate]?
Disclaimer: I don't know what I'm talking about, just googled retrograde analysis
I wonder if the time could be improved by optimising the programs some more, since at this scale constants matter a lot. The amount of memory needed might not be reducible but optimising a tight loop and reordering it to take advantage of cache effects could yield nontrivial speedups.
Taking advantage of the very wide new instructions in recent CPUs might also be worth it, instructions which compilers often have difficulty figuring out how to use effectively:
http://davidad.github.io/blog/2014/02/25/overkilling-the-8-q...
// did not know you couldn't do this for chess (paper even pointed to why)
If so, then yes, that is pretty straightforward. E.g. the last move was either a pass, or a move by White, or a move by Black. For a move by White, it was either a suicide, so could be on any point in an empty region enclosed by Black, or it was no suicide and is one of the points occupied by White in the given position, possibly having captured a Black group in any of the adjacent empty regions enclosed by White.
You can also buy Goban from the app store to play GnuGo or Pachi (both bundled), but it is a bit buggy (and not really better than the older free version). They do respond to bug reports though so it sounds like they are actively working on it.
Start out playing 9x9 against GnuGo. Give yourself a 9-stone handicap, you should probably win. Take away handicap stones until you can win with a 3 stone handicap.
In general you don't want to play an AI at less than 3-stone handicap or you will learn bad habits.
At that point, play against GnuGo 19x19 with a 9-stone handicap. If you are a beginner around 20kyu, you will find it a challenge to win.
I've been practicing consistently for the past couple of months. I do problems on goproblems.com or from a few iPhone apps. I've played a couple of games against ranked bots on kgs and am ranked 15kyu there since I beat a popular 16kyu-ranked bot. KGS is inflated through so I'm probably around 20kyu, still a complete beginner. I beat GnuGo 19x19 at a 9-stone handicap but not quite yet at an 8-stone handicap.
Once you are able to beat GnuGo 19x19 at a lower handicap then you can start playing against Fuego or Pachi. But at that point you should also already be playing humans regularly - it's a very different playing style in that you'll come across clearly bad moves that you will have to learn to recognize and take advantage of.
I don't have much time now to play, but was around 4-5k in KGS and like me, there are always a bunch of folks ready to play with you while explaining the rules/strategy.
Regarding clients, there are a few options. CGoban2 is the only client you can use to access KGS, which is currently the biggest English-speaking server. You can also try online-go.com which is entirely browser-based so you don't need a client, and there's also IGS, a Japanese server which can be accessed through their own client called GoPanda2 or other clients like qGo2. There are also two servers called Tygem and WBaduk which are mostly Korean. They have proprietary clients you can run through Wine. I think they're supposed to be accessible through qGo2 as well, but I haven't been able to play through it, only observe others' games.
Also, if you're just learning, http://senseis.xmp.net/ is a great resource.
If the Mac version of SmartGO has features similar to the Windows version, it should be excellent. But, they've been focused on iPhone/iPad apps so it hasn't come out yet.
Playing against computers will teach you bad habits and will not be helpful past the very basics. If you want to do exercises, try e.g. Tsumego (for Android at least).
And the best way to get started is to find your local Go club, take a friend with similar level to you (ie. complete novice) and join their game night (my local go clubs meet in bars). Ask a more experienced player to over-the-shoulder for a few games. This is how I got started.
KGS: Kiseido Go Server IGS: Internet Go Server OGS: Online Go Server
Some other approximations here: http://i.imgur.com/w84aPWs.png?1
Note they are all in the log domain.
Is he sure about 512GB of RAM? That's a lot of memory. Even the 32-core memory-optimized AWS instances only have 244GB.
(Large SQL servers, etc, often have this much RAM)
I'm afraid to ask for pointers to understanding that statement, as it would mean spending hours pouring over the details (and likely writing & running software to analyze it) just to understand a ... 2x2 go board.
Seems to fall into the category of "grand unified theories" in any topic, where prolonged advanced study of complex systems tends to lead students thereof to develop zen-like simple-yet-profound expressions of the subject.
Now I want a 2x2 go board. "What's the point of that?" "There are a third of a trillion possible games that can be played on it. Care to try one?"
That's why our paper "Combinatorics of Go" assumes the so-called Logical Rules at http://tromp.github.io/go.html, which do end a game on consecutive passes.
The reason that rulesets in the Chinese style branch are more amenable to mathematical analysis are that you can play the game until you have an unambiguous result about the life or death of a group, and thus these rulesets usually involve simply resuming the game and playing it out if there is any dispute about whether a group is alive or dead (or, for the logical rules, don't involve resumption at all, you just play it out and score it as is after two passes, with all empty points that reach two colors being counted for no one; since in area scoring games, ending the game before that point is mainly a convention for human players who don't feel the need to play all the way to the point of killing obviously dead groups).
Under Japanese style rules, playing within your territory to kill a disputed group may reduce your own score, so rather than just playing it out to the end, there are an elaborate set of conventions for determining the life or death of particular shapes. This elaborate set of conventions is much more difficult to represent mathematically.
The American Go Association rules of Go have an interesting hack to allow you to use Japanese-style territory scoring, but wind up with the same result as Chinese-style area scoring would give you, by having you actually give your opponent a stone as a capture when you pass, plus making the game-ending passes be two or three passes such that each player has the same number of turns. This preserves the benefit of area scoring, that any dispute on life or death can be resolved by resuming the game and playing it out until the situation is completely unambiguous, while still allowing the somewhat easier method of counting that territory scoring provides (filling in liberties with captured stones, and then just counting the remaining territory, and thus having to actually count to a lower number).
The Tromp-Taylor rules do make some adjustments for the sake of making it even more amenable to analysis that most other rulesets do not, such as allowing suicide. This doesn't actually affect the strategy in very many games, as it's very rare to encounter a situation in which a suicidal move would be the best choice, but it tends to make analysis a bit simpler as there is one fewer constraint to worry about. I feel like allowing suicide is more elegant, but it is only allowed in a few rulesets.
It is unfortunate that for such a simple game, there is no one agreed upon worldwide rule set. There are a couple of different parameters that you can tweak in a ruleset that give you a game that is very similar, but different enough in a few corner cases to make them different games; territory vs. area scoring (and with territory, the large number of conventions on life and death you need to make it work), simple ko vs. situational superko vs. positional superko, suicide vs. no suicide, counting points in seki, and komi (number of extra points for the second player to make up for the first-move advantage).