top | item 9167781

Number of legal 18x18 Go positions computed. One more to go

229 points| tromp | 11 years ago |tromp.github.io | reply

109 comments

order
[+] everyone|11 years ago|reply
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.
[+] darkmighty|11 years ago|reply
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.

[+] baddox|11 years ago|reply
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.

[+] Al-Khwarizmi|11 years ago|reply
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.

[+] CurtMonash|11 years ago|reply
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.

[+] davepeck|11 years ago|reply
(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.)

[+] barbs|11 years ago|reply
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.

[+] jessaustin|11 years ago|reply
...'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.

[+] motbob|11 years ago|reply
What makes complexity "false"? Is it "complexity I don't find interesting"?
[+] RBerenguel|11 years ago|reply
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
[+] simpleblend|11 years ago|reply
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!
[+] jballanc|11 years ago|reply
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

[+] shit_parade|11 years ago|reply
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)

[+] esgoto|11 years ago|reply
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).

[+] Dowwie|11 years ago|reply
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

[+] eru|11 years ago|reply
I like Diplomacy (even no-press) because it adds a kind of complexity that you don't have in Go: multi-party considerations.
[+] Tharkun|11 years ago|reply
Gokgs is a great resource, but it requires a Java browser plugin to play. That's seriously messed up.
[+] spot|11 years ago|reply
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.

[+] tunesmith|11 years ago|reply
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?
[+] hemmer|11 years ago|reply
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/

[+] e12e|11 years ago|reply
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]?

[+] cevn|11 years ago|reply
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

[+] chongli|11 years ago|reply
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.
[+] yuubi|11 years ago|reply
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

[+] userbinator|11 years ago|reply
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...

[+] tromp|11 years ago|reply
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.
[+] protomyth|11 years ago|reply
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)

[+] tromp|11 years ago|reply
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.

[+] pathikrit|11 years ago|reply
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?
[+] tunesmith|11 years ago|reply
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.

[+] BSousa|11 years ago|reply
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.

[+] esgoto|11 years ago|reply
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.

[+] tjl|11 years ago|reply
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.

[+] exDM69|11 years ago|reply
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.

[+] RBerenguel|11 years ago|reply
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

[+] xcombelle|11 years ago|reply
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.
[+] spot|11 years ago|reply
i recommend crazystone over gnugo (it's mobile)
[+] Houshalter|11 years ago|reply
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.

[+] alexbecker|11 years ago|reply
> 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.

[+] nippoo|11 years ago|reply
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)

[+] sjtrny|11 years ago|reply
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.
[+] tromp|11 years ago|reply
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.
[+] chizthtor|11 years ago|reply
They got 57 legal position for a 2x2 game of go. They're counting all the symmetries. They're not pruning anything. facepalm
[+] lambda|11 years ago|reply
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.
[+] tromp|11 years ago|reply
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).
[+] DavidSJ|11 years ago|reply
Rotation and mirroring only buy you a factor of 8, and that's for positions that aren't already symmetric.