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

91–100 of 116 posts

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

#91

Post by eru »

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…

I like Diplomacy (even no-press) because it adds a kind of complexity that you don't have in Go: multi-party considerations.

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

#92

Post by im2w1l »

shit_parade wrote: post #63
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…

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…

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

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

#93

Post by sjtrny »

alexbecker wrote: post #81

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

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.

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

#94

Post by tromp »

b3n wrote: post #78
cevn wrote: post #53

Earlier quoted context omitted.

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…

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.

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

#95

Post by spot »

pathikrit wrote: post #60

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?

i recommend crazystone over gnugo (it's mobile)

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

#96

Post by spot »

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…

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.

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

#97

Post by tromp »

userbinator wrote: post #59

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

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.

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

#98

Post by tromp »

alexbecker wrote: post #81

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

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.

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

#99

Post by e12e »

cevn wrote: post #53
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…

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.

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

#100

Post by Tharkun »

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…

Gokgs is a great resource, but it requires a Java browser plugin to play. That's seriously messed up.
Post reply on HN