Number of legal 18x18 Go positions computed. One more to go(tromp.github.io)
tromp.github.io
Number of legal 18x18 Go positions computed. One more to go
http://tromp.github.io/go/legal.html
115 comments
Anyone here play? It is pretty much the ultimate boardgame. Its like game-theory the game. From the very start you are embroiled in interesting risk/reward and provoking you opponent to overextending type stuff.
Great place to play is gokgs.com
I actually cant play many strategy games anymore because I realize this is like go with a load of crap thrown on it. My friend and I call this 'false complexity' the game isnt really complex it just has loads of rules and random stuff to familiarise yourself with before getting into the game proper. Its not a great a comparison but I would say something like magic the gathering or Dota would be good contenders for most 'false complexity' attained in a game.
In Dota for example the false complexity is what allows someone with not so great analytical thinking but great knowledge of the complexity (items and hero combinations) to fare pretty well. It helps level the field. Although comparing go to RTS is extremely misleading. RTS's have pretty deep of what I call 'continuous tactics' where you need to plan an optimal control of your character with a continuum rather than discrete set of plays. It presents incredibly rich situations which you cannot explain with the kind of strategy you see in go or chess, for instance. The same goes for games like counter-strike, once you take into account limited aiming capability. I think it's beautiful how those games can hide this richness into a very fun game at low levels, and how they don't seem so hard just because we're so good at spatial reasoning and planning.
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.
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.
It doesn't have the richness of Go but I believe https://www.gnu.org/software/liquidwar6/ captures the essence of the "action/micro" side of RTSs.
I prefer the old http://www.ufoot.org/liquidwar/v5 .
I didn't get the counter strike example. It is an example of a non-obvious mechanic, but I didn't see where the "rich strategy" was coming from.
In a single round, perhaps not. In a best of 30 rounds on three different maps with asymmetrical teams and a team economy, you can see the elements of what the original comment was talking about, "interesting risk/reward and provoking you opponent to overextending type stuff."
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.
[0] http://www.esl-one.com/csgo/katowice-2015/
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.
[0] http://www.esl-one.com/csgo/katowice-2015/
I'm not sure that kind of mechanical parts level the field. I'm terribly bad at learning repeatable, dumb, tasks - like checking your base at the beginning of SC2 for stray drones. For me, it's the lamest gameplay decision not to have the base fully covered with visibility at the beginning. It favors a different kind of player.
I'm playing a lot of CoH because it cuts all the base building ceremony down to minimum.
I'm playing a lot of CoH because it cuts all the base building ceremony down to minimum.
For a number of years, the common belief was that RTS Go = Starcraft Broodwar, especially in Asia.
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).
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).
> 'continuous tactics'
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
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
Twitch reactions are what make it real-time. You might be more interested in a turn-based strategy game where you can plan out your moves before striking.
I'm not super familiar with Dota, but I have thought a fair amount about game theory as it applies to RTS games, and Dota (being a MOBA) has many similarities.
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.
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.
Well go is often played online with a very tight time limit. Giving only a matter of seconds for each move. I wouldbt say its a matter of coordination, but, pattern recognition from noisy jumbled data at speed.
I play and love both Go and MtG, and I think your assessment of MtG is not fair. The thing about MtG is that the real fun is not as much in playing the game itself but in the deck building. When I'm playing a game of MtG, I'm not thinking only about the current game or how to win it, but rather which cards/combos are working well, which are not working, what cards I should use instead, etc. to improve my deck for the next game.
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.
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.
A lot of the "false complexity" in MtG comes from the wide variety of trivial differences between cards. Deckbuilding becomes an exercise in, depending on format, sifting through some 10,000 (probably more by now) cards to determine which are synergistic.
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 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.
But, but... sifting through 10,000 cards to determine which are synergistic is half of the fun!
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.
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.
I never said false complex game werent fun! :)
Go can be make you feel bad. Because it is so completely based on skill and judgement, the better player will invariably annihilate the worse one. So you either get annihilated and feel stupid, or annihilate your opponent and feel sadistic. Though a certain percentage of the time you have very close match which is really amazing.
> "What I dislike about the evolution of MtG is the placeholder words that they constantly add to the rules"
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.
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.
I love Go. But from a game-theoretic view it is theoretically rather trivial, as are chess, checkers, and any other game in which players with perfect information alternate moves.
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.
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.
Actually, it's interesting in the sense of combinatorial game theory (https://en.wikipedia.org/wiki/Combinatorial_game_theory) not the branch of decision theory for interactive rational agents known as game theory (https://en.wikipedia.org/wiki/Game_theory). Two only very distantly related subjects which unfortunately have confusingly similar names.
Got it. That said, I use "game theory" in the sense in which it's defined, not least because my thesis was in the subject. :)
Yes, that is the meaning of plain old "game theory", and I also think that's the meaning that the person you were replying to meant; I just wanted to point out that there is something with "game theory" in its name which is much more applicable to Go.
Actually, go has some deep complexity that chess and checkers do not have, primarily from the idea of "ko".
Read "Mathematical Go".
https://math.berkeley.edu/~berlek/cgt/gobook.html
Read "Mathematical Go".
https://math.berkeley.edu/~berlek/cgt/gobook.html
(I do. If anyone's interested, I made a little site you can play a casual game of Go; no complexity to getting started, since play is by email correspondence:
http://go.davepeck.org/
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.)
http://go.davepeck.org/
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.)
Cool, thanks for providing the option to change the board size. A good way to start is to play short games on a 9x9 board (19x19 is the official size, but games take a very long time to play out at that massive size). Just find a friend (or against yourself), and play out a bunch of games as quickly as you can, without overthinking every move. Doing this, you'll discover strategies much quicker on a small board than you could playing out games on large board.
Have you tried any other strategic board games out there? There are a fair few relatively recent games that involve deep strategy that come to mind. Since board games require the players to enforce the rules of the game themselves, there's an intrinsic limit to how complicated the game can be before it becomes tedious.
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.
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.
...'false complexity' the game isnt really complex it just has loads of rules and random stuff...
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.
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.
[deleted](1)
What makes complexity "false"? Is it "complexity I don't find interesting"?
I think 'artificial' would be a better word here. For example, in Magic the Gathering, there is a very basic turn structure and set of rules that define the game (draw a card, play some cards, attack, play some more cards, done) that is convoluted by several factors, including an increasingly large dictionary of terms relating to abilities and powers of the cards, and a correspondingly dense set of rules to handle the inevitable complexity of all those things.
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.
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.
I'm not quite sure why the comparison is being made here at all. Go has an incredibly simple rule set and is a game played with perfect information. That such deep complexity emerges from those things is part of what makes the game so beautiful. In Magic, randomness and limited information are integral elements of the game, as are the myriad rules and their interactions. That "so many rules have been piled on over time" is not some sort of accident; it's been the intention from the beginning and it's a huge part of what makes the game fun. It's simply a completely different beast from a game like Go. Labeling one game's complexity "artificial" in some arbitrary manner is not meaningful. What's rather clear is that creating a rigorous mathematical model of Go is fairly straightforward, while doing the same for Magic would seem to be a few orders of magnitude more complex.
(Also, that a creature's power and toughness might change has been part of the game since the very beginning: see Giant Growth.)
(Also, that a creature's power and toughness might change has been part of the game since the very beginning: see Giant Growth.)
The golden rule of Magic is that a card's text trumps all else. In other words, the entire premise of the game is that the rules are malleable.
I read "false complexity" as "complexity as imposed by a set of rules", as opposes to "complexity as an emergent behavior from very simple rules and interaction". Of course, adding any rule will add more complexity of the former, and probably the latter too. Whether one is more interesting than another is a matter of taste.
Also: arbitrary rules.
Concrete example: castling[0] in chess
[0]: http://en.wikipedia.org/wiki/Castling
Concrete example: castling[0] in chess
[0]: http://en.wikipedia.org/wiki/Castling
Reading that article, isn't that what Rich Hickey would call "incidental" (and thus bad) complexity?
Been playing for many years (I'm around 5k.) I also enjoy a game of backgammon (I picked it up last August) and still play casual, artificially-complex games with my friends, since they are not big go fans
Curious, what "artificially-complex" games do you play with your friends?
The ones they like, I don't care that much. Lately, Battlestar Galactica and a couple I don't remember the names.
I've been playing for a couple years now. Easily one of the most enjoyable games I've ever played. The amount of complexity that's hidden in something seemingly so simple so really rewarding to me. I've only managed to get to around 14-11k so far, but I'm looking forward to progressing as I get older in life!
Just wanted to add that if you don't regularly have the free-time to commit to a full game of Go, or if you simply prefer to play at a slower pace, you might also check out http://www.dragongoserver.net .
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
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
OGS (https://online-go.com/) is pretty good as well. It's web based and supports both correspondence and real time games. It's also pretty close to KGS in terms of features.
Generally the most important move is the first move, a common 'zen' go problem is an empty board with 'black to play to win'.
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)
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)
I'm about 7k on kgs. I'm at that stage where to get better I reckon I would have to actually study joseki and tsumego. Which seems wrong for a game. I will just keep playing at this level.
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.
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.
In my experience, the gap from 7k to 3k actually is mostly about the sense of the game, rather than skill and technique. To be precise, I don't think reading skill is that much difference, but 3k know better what to read, what constitutes weak or strong group. Joseki definitely isn't an issue well into dan level.
> Knowing how much komi should be is equivalent to knowing how to play the best game.
I think komi should be chosen so that black and white stand even chances when humans - not optimal players - play.
I think komi should be chosen so that black and white stand even chances when humans - not optimal players - play.
I've been playing on and off for a few years. I got to around 1 dan, and hit a wall because I need to actually study regularly in order to improve now, but I'm too lazy. I've been taking a break and planning on creating some sort of routine for doing tsumego every day and pro game reviews.
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).
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).
I really enjoy playing go. I found the online platforms burdensome and poor at matching me with beginners of similar experience. For years I've imagined Go bringing the world closer together through a platform that combines use of a physical board with Internet connectivity. Playing in person is so much more gratifying.
if anyone would like to simulate this experience together we can Skype play
if anyone would like to simulate this experience together we can Skype play
>poor at matching me with beginners of similar experience
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.
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.
[deleted]
I like Diplomacy (even no-press) because it adds a kind of complexity that you don't have in Go: multi-party considerations.
Gokgs is a great resource, but it requires a Java browser plugin to play. That's seriously messed up.
yes, love to play, and love to teach.
play mostly on KGS (4k), teach in person, whoever will sit still ;)
similarly, i find it hard to play other games because they seem silly by comparison.
similarly, i find it hard to play other games because they seem silly by comparison.
Just because the number of legal positions is computed doesn't mean we're anywhere close to "solving" 18x18 Go, right? What's the utility of computing the number of legal positions?
As George Mallory said when asked "Why did you want to climb Mount Everest?"
"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).
"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).
No, nowhere remotely close. This is just a matter of trying to precisely characterize the state space; there are upper and lower bounds that have been established, but it's an interesting computational problem to precisely characterize exactly how many legal positions there are.
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."
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](1)
It's just an open problem in combinatorics. Plenty of math doesn't have a specific utility associated with the problems.
Techniques developed to figure out this problem can be used in other fields. Developing them against a 'fact-checkable' issue can help troubleshoot issues, as opposed to using them on a dataset where we don't know what it's supposed to look like.
One example that just occurred to me: The base 2 log of the number of legal positions of a 9x9 go game is about 126.3, which means if I use a good hash of board positions yielding twice that number of bits, I have a better than 50/50 chance of having no collisions. That is very good to know if you've got anything like a transposition table in a Go playing program.
You don't really need that precise an estimate.
81 * 2log3 ~= 128.38
Generally, a Zobrist hashing system is used (which is a specific type of transpositon table) for Go. It's also probably used for chess, but I don't follow chess AIs as closely.
Well, it would be interesting problem in combinatorics if you calculated the result in an interesting fashion.
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.
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.
something something top-down dynamic programming
shuffles on, muttering
shuffles on, muttering
I wonder if this sort of thing might be appropriate for grid computing, e.g. BOINC? There are plenty of mathematically minded projects.
http://boinc.berkeley.edu/
http://boinc.berkeley.edu/
[deleted]
I don't understand this quote: "[determining the number of valid positions is] sadly unattainable for Chess, where determining if a given position is legal is the essence of a class problems known as Retrograde analysis.".
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]?
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]?
It seems that in chess, the (current) "best" way to figure out whether a move was legal is through retrograde analysis (1). As you can imagine, this becomes very expensive, very fast. Not only that, but the current position may be legal in chess given some previous conditions, but illegal given others (consider Castling). Therefore, given no extra information, you may not be able to tell whether a given chessboard is legal without being given the entire history of the board as well.
Disclaimer: I don't know what I'm talking about, just googled retrograde analysis
1. http://en.wikipedia.org/wiki/Retrograde_analysis
Disclaimer: I don't know what I'm talking about, just googled retrograde analysis
1. http://en.wikipedia.org/wiki/Retrograde_analysis
Right. So unattainable means "not feasible", not impossible - or that it's not possible to enumerate all legal positions. I of course realize that simulating all possible games (ignoring cycles) would be very demanding.
I'm not sure what ruleset OP is using for their analysis, but with superko in place you would also need the entire history of the board to know if a move is valid.
Although rulesets might differ on what is considered a legal move, they all agree on what is a legal position: one where every connected group of stones has liberties (empty adjacent point). Furthermore, in all rulesets you can reach any legal position by playing legal moves (and passes) from the empty starting position.
Chess has state; it is not a simple function of board layouts. Whether or not it is valid to make moves such as castling or en passant pawn capture is dependent on the move order, not on the current board position.
A position is valid iff there is a squence of legal moves that leads to it. In go, a legal turn consists of putting a stone on nearly any vacant point (some rule sets prohibit suicide moves, and all prohibit exactly repeating the position at the end of your previous turn) or passing (not putting a stone, which normally happens only near the end of the game), so the only illegal board configurations are those that have groups with no adjacent vacant points ("liberties"). In chess, these moves are more constrained: each piece may move only certain directions, sometimes depending on the locations of opposing pieces.
http://senseis.xmp.net/?Liberty
http://senseis.xmp.net/?Suicide
http://senseis.xmp.net/?Liberty
http://senseis.xmp.net/?Suicide
Following 9 months of computation and 4 petabyte of disk IO on a Dell PowerEdge R280 server
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...
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...
Most time is spent normalizing, encoding, decoding, and sorting so-called border states, compact 18*3-bit descriptions of all information needed about a partial board position to determine its legal full-board completions.
This code is fairly optimized, but it's possible that a small factor could be gained by expert analysis.
Even so, there's little to no room for reducing the amount of disk-IO, so the end-result might be that the problem becomes more IO bound than CPU bound.
So, given all the positions, can you tell which one(s) are possible results of another position after another turn?
// did not know you couldn't do this for chess (paper even pointed to why)
// did not know you couldn't do this for chess (paper even pointed to why)
Are you asking whether it's possible to determine all possible 1-move predecessors of a given position?
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.
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.
Yeah, that what I'm asking (in a really bad way). I wonder, given a list of positions, how long it would take to build the transitions between them. I would imagine 19x19 would be a "practically forever" type thing.
It would take at least a nanosecond for each position. Given that 6x6 already has 62567386502084877, it would take at
least 724 days. To take "practically forever", 7x7 more than suffices:)
Another great resource about Go combinatory: http://ps.waltheri.net/
I want to learn Go. I would like to practice against a bot first before I get on KGS. What is a good Go program I can run on my Mac to practice against? The AI does not need to be very good at all since I am novice. Once I get familiar with rules, I will play online against players. What is a good Go client to play online on the Mac?
There is a way to compile GoGui so it is a mac app. Through it you can play against GnuGo (brew install gnugo), fuego (brew install fuego), or pachi (compile yourself). With it, you can also learn a lot by making an AI play starting at a certain move, or making AI's play against each other.
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.
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.
Not the answer you are looking for, but get on KGS even if you are a novice. There are many folks starting out as well, and you can always play more advanced players there and ask for teaching games.
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.
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.
GnuGo is easy enough for beginners I think. I also used a bot called Aya when learning, but I don't know if that is available for OSX.
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.
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 you just want software to play against, without the client aspect, I'd recommend an older version of Sen:te's Goban (version 3.2). Unlike the latest version, it's free (the latest version is $10). It's quite old, but it seems to still work. It uses an older version of the Gnu GO engine. It used to be able to connect to the Pandas server. I don't know if that part still works. You should be able to find download links.
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.
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.
GnuGo is good enough to get started but you should not play many games with it. Just a handful to get acquainted with the rules.
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.
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.
Pachi and fuego are open source engines you can make work on Mac. To play online, IGS is quite nice-looking on Mac, and the most western-populated server is KGS. Ogs is a browser based turn & real time server, too.
KGS: Kiseido Go Server IGS: Internet Go Server OGS: Online Go Server
KGS: Kiseido Go Server IGS: Internet Go Server OGS: Online Go Server
Be aware that practicing against AI lead to poor play and very few improvement, playing weak or strong human is far better. Especially with handicap.
i recommend crazystone over gnugo (it's mobile)
For fun I did a search for approximations to the function with Eureqa. I get exp(0.0319x(naturalLogOfLastValue) + 1.056xn^2 - 0.184).
Some other approximations here: http://i.imgur.com/w84aPWs.png?1
Note they are all in the log domain.
Some other approximations here: http://i.imgur.com/w84aPWs.png?1
Note they are all in the log domain.
> we need from 10 to 13 servers, each with at least 8 cores, 512GB RAM, and ample disk space (10-15TB), running for about 5-9 months.
Is he sure about 512GB of RAM? That's a lot of memory. Even the 32-core memory-optimized AWS instances only have 244GB.
Is he sure about 512GB of RAM? That's a lot of memory. Even the 32-core memory-optimized AWS instances only have 244GB.
Where I'm currently working (computational neuroscience / data analysis) we've just had to upgrade our servers and 512GB is only just enough for some datasets. A couple of the labs nearby (genomics) share a cluster of ~10 machines with 1.5TB RAM each. So no, 512GB isn't stupidly high (though it's still uncommon!).
(Large SQL servers, etc, often have this much RAM)
(Large SQL servers, etc, often have this much RAM)
I once used over 500GB on a university research server simply using MATLABs backslash (linesr system solver) operator when processing a single image. I accidentally forgot to scale the image down from original resolution of 5MP. I woke up to an email from a very alarmed sys admin. Anyway it's super easy to use that amount of RAM.
Admittedly, the 512GB in one server is mostly for convenience. In each round, I run 8 processes each using 63GB, which could in principle also be farmed out to other machines with some more administrative and monitoring overhead.
Hello, we provide jobs for ESL teachers through http://preply.com/en/skype/english-tutoring-jobs
They got 57 legal position for a 2x2 game of go.
They're counting all the symmetries.
They're not pruning anything.
facepalm
Of course they are taking symmetries into account. They are including symmetries in their definition of what the different states are, and thus accounting for them in the count, but they absolutely are pruning symmetries in their implementation. Read the draft of the paper (https://tromp.github.io/go/gostate.ps) if you're interested in the techniques.
I'm not pruning any board symmetries. So, yes, the 4x4 position with only one Black stone adjacent to a corner
would be counted 8 times (with the Black stone at A2 or A3 or B1 or B4 or C1 or C4 or D2 or D3).
The only symmetry that the algorithm takes advantage of is color symmetry; but even there nothing is pruned; the count for a color-normalized state is simply doubled.
I apologize. I had skimmed the paper, but not read it in depth, and it was clear that you had considered symmetries (such as Figure 4 in the paper); I assumed, then, that your algorithm would prune symmetries and simply account for them by multiplying the results in each class by the number of symmetries. I hadn't yet finished reading the paper, however.
Few people can believe that there are as many as 386,356,909,593 games on the tiny 2x2 board. Needless to say, nothing is pruned there either. A game could visit as many as 48 of the legal positions and have dozens of passes (but only 2 consecutive ones, which ends the game).
That...is ridiculously intriguing.
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?"
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?"
Well it "ends" the game but play can resume. Plus, there's the crazy hypothetical play in the way-over-complicated Japanese rules. I think, in theory, you can play multiple almost-compete games after the game is "over". Each hypothetical play is just to resolve one group, as I understand.
Indeed, the Japanese rules are not suitable for mathematical analysis of the game;
see https://en.wikipedia.org/wiki/Rules_of_go#Counting_phase
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.
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.
I would also like to point out, for the benefit of anyone else here (just replying to you to clarify your point), that the Logical Rules referred to are commonly referred to as the Tromp-Taylor Rules, after John Tromp (the submitter and parent commenter) and Bill Taylor, who wrote them up as a simplified version of the New Zealand rules; and that these, in turn, are in the branch of Chinese-style, or area-scoring rules (counting the sum of stones on the board and territory surrounded for score), to contrast with Japanese and Korean style, or territory-scoring rules (counting the sum of territory surrounded minus captured stones for the score).
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).
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).
Rotation and mirroring only buy you a factor of 8, and that's for positions that aren't already symmetric.
exactly, spatial symmetries occupy a vanishingly small proportion of the state space that its not worth the added complexity and runtime cost (unlike the color symmetry).
Well no, they occupy around 7/8 of the state space (if the symmetries buy you a factor of 8). But I guess the point is that the state space is so large that the factor of 8 still doesn't do a lot to make things tractable..