Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

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

tromp.github.io

Post reply on HN
Print view View original

51–60 of 116 posts

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

#51

Post by e12e »

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]?

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

#52

Post by thinkpad20 »

Orangeair wrote: post #34
motbob wrote: post #26

Earlier quoted context omitted.

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 th…

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.)

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

#53

Post by cevn »

e12e wrote: post #51

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 emula…

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

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

#54

Post by yuubi »

e12e wrote: post #51

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 emula…

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

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

#55

Post by kazagistar »

darkmighty wrote: post #27
everyone wrote: post #11

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…

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 d…

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.

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

#56

Post by JamesSwift »

Orangeair wrote: post #34
motbob wrote: post #26

Earlier quoted context omitted.

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 th…

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.

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

#57

Post by chongli »

e12e wrote: post #51

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 emula…

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.

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

#58

Post by Padding »

darkmighty wrote: post #27
everyone wrote: post #11

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…

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 d…

> '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

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

#59

Post by userbinator »

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...

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

#60

Post by pathikrit »

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?
Post reply on HN