Kuro5hin.org: technology and culture, from the trenches
create account | help/FAQ | contact | links | search | IRC | site news
[ Everything | Diaries | Technology | Science | Culture | Politics | Media | News | Internet | Op-Ed | Fiction | Meta | MLP ]
We need your support: buy an ad | premium membership

[P]
Go: Life Itself

By GoStone in Culture
Thu Jul 11, 2002 at 09:36:19 AM EST
Tags: Culture (all tags)
Culture

Saying 'just one game'
they began to play...
That was yesterday
Japanese senryu poem

There is one board game that stands above all others. The most beautiful, most ancient, most strategic, most subtle. The king of games. A game which teaches as much as it entertains, whose enthusiasts number tens of millions and which has often been compared to life itself.


Curiously in our little multicultural global village, the game is only faintly detectable on the periphery of the western cultural vision; mentioned in passing in novels, and seen briefly in movies (Pi, A Beautiful Mind), where it tends to symbolise an esoteric intellectualism. Geeks may know it only for its resistance to computer attack. Mathematicians may know it provided the inspiration for Combinatorial Game Theory, and the Surreal numbers. But despite an estimated 100,000 players in Europe, and a similar number in the USA, it is fair to say that most people have never even heard of the game. On this basis, l'd like to introduce Kuro5hin to the game of go.

"The Master said, 'Hard is it to deal with him who will stuff himself with food the whole day without applying his mind to anything good. Are there not gamesters and go players? To be one of these would still be better than doing nothing at all.' "
Confucius (who had better things to do)

Go is thought to be 3,000 to 4,000 years old, making it contemporary with Stonehenge. It began in China, where it is now known as Wei'Qi, possibly growing out of the same framework as acupuncture, shiatsu and feng shui. About 1,300 years ago it spread to Japan, where it blossomed, being sponsored by the medieval state and becoming an essential samurai art. Most recently the best players have come from Korea, where it is known as Baduk and an estimated one person in ten plays the game regularly. In total there are 25 to 50 million go players in the Far East.

Through these long millennia and cultural wanderings there has been little alteration to the rules. No other game can make a similar claim to longevity and stability. And for good reason. The rules of go are so simple, yet so perfect, that it cannot be tinkered with without destroying it. Like a mathematical truth, go appears to have always been there, beyond time and space. It has been conjectured that if there are sentient beings on other planets they may also be playing go.

Traditionally go is played on a polished wooden board (known as a Goban), marked with a square grid in thin black lines. Nineteen lines in each direction by convention, though sometimes smaller boards are used for a quicker game. Each player has a bowl of lens-shaped 'stones', actually made of slate for the black and shell for the white stones; 180 stones each, effectively an unlimited supply.

"That play of black upon white, white upon black, has the intent and takes the form of creative art. It has in it a flow of the spirit and a harmony of music. Everything is lost when suddenly a false note is struck, or one party in a duet suddenly launches forth on an eccentric flight of his own. A masterpiece of a game can be ruined by insensitivity to the feelings of an adversary."
The Master of Go, by Yasunari Kawabata, winner of the Nobel Prize for Literature

A game starts with an empty board, like a bare canvas before two painters. Starting with Black, the players alternately place single stones on the intersections of the lines, gradually filling the board. Once played, the stones do not move, unless captured and removed. With time the image of the game reveals itself like a landscape through a mist, now this detail, now that, where what seems clear now may later be revealed as illusion.

For a while a sequence of stones may be played close to one another like the cut and thrust of a sword-fight. But suddenly, seemingly unpredictably, play jumps about the board to distant, unconnected regions. To some extent you can tell how good a player is by the fractal quality of his play; a poorer player will spend too long detailing an idea, where a master will sketch it lightly before moving on. By the end of the game the stones press closely against each other forming "a map of the contest of two minds".

"Lose your first fifty games as fast as possible"
Go proverb

There are only three rules in go. But that is only the beginning. These rules have implications, and the implications have implications and so it goes on, until after ten years of playing it still feels like you are learning the game. There is often a period of frustration between learning the rules and working out what you are trying to achieve. So, on the understanding that these rules alone leave much unsaid, let me explain.

The first rule says that when you're surrounded, you come off. As stones sit on the intersections they generally have four lines radiating out from under them to neighbouring intersections (except on the edge where there may be three or even just two neighbours). If a neighbour is empty it is called a 'liberty', or a 'life'. If all its lives are taken by the enemy a stone is captured and removed. Captured stones count one point, and are usually stored in the lid of the same bowl a player stores his own stones in.

. o . .
o x . .
. o . .

the black stone at x has one liberty

. o . .
o x A .
. o . .

if white plays at A he captures the black stone

. o . .
o . o .
. o . .

now the board looks like this

If two stones are adjacent they both live or die together. To capture them, you must occupy all their liberties. A group of stones like this can be any size.

. o . .
o x x .
. o . .

this group of black stones still has three liberties

. o A .
o x x B
. o C .

if white gets to play A, B and C he captures two stones

. o o .
o . . o
. o o .

like this

Using this principle it is often possible to evade capture by 'running away', i.e. building a bigger group with more liberties. But a bigger group doesn't necessarily mean more liberties, and it is quite possible to run into trouble rather than away from it.

. . . . .
. x x x .
. . . . .
. x x . .
. x x . .
. . . . .

two black groups, each with eight liberties, though one is bigger than the other

A further complication is that while White is surrounding Black, Black might be surrounding White in a life or death struggle. Whoever gets there first will remove the captures, freeing up liberties for his own stones. Certain common formations are actually impossible to capture.

"The game of go is a vast territory for which the map will never be complete"

All in all, capturing stones is not easy. They tend not to lie still and accept their fate. And this is where the second rule comes in. Surrounded empty intersections also count one point each, called territory.

. x x . .
x . . x .
x . . x .
. x x . .
. . . . .

four intersections surrounded by black

Now territory is much easier to surround because it doesn't run away or fight back, and there are huge swathes of it to go for right from the start. So go is a game of territorial acquisition, often described as like two races settling a new land, or even two companies trying to capture a market. The emphasis is upon speed, efficiency and lightness, dropping stones into empty spaces to stake a claim, then leaving them to prove themselves.

So you play your stones, but paradoxically it is not your stones which matter. You don't want them captured because they allow you to surround territory etc., but they have little worth of their own. During the course of a game many stones will be sacrificed deliberately by both sides. This may offend modern notions of justice, and it certainly confuses play. The stones can blind, swarming like flies. You know you can kill some, and some will have to live, but which? Beginners will often, from pity, try to rescue stones that were serving more effectively in sacrifice. The temptation to become 'attached' to your stones, in the Buddhist sense, increases as the groups become larger.

"The board has to be square, for it signifies the Earth, and its right angles signify uprightness. The pieces of the two sides are yellow and black; this difference signifies the Yin and the Yang; scattered in groups all over the board, they represent the heavenly bodies. These significances being manifest, it is up to the players to make the moves, and this is connected with kingship. Following what the rules permit, both opponents are subject to them; this is the rigor of the Tao."
Pan Ku, 1st century historian

One verse of the great Tao Te Ching asserts the value of nonexistence, showing that the utility of a cup is the emptiness inside it, and the utility of a wheel comes from the inner hole on which it turns. These deep metaphors are found reflected in go. At a simple level, it is not the number of stones connected into a group that determines whether it lives, but the number of empty liberties you haven't played on. Similarly your stones do not add to your score in any way, only the empty territory they surround. Playing additional stones in your territory actually deducts from your score.

"Yield, and maintain integrity.
To bend is to be upright;
to be empty is to be full"
Tao Te Ching

Taoism stresses that flexibility and change are vital. This is fundamental to go, as is the Tao's emphasis on harmony and balance. Enthusiasts of Judo, Tae Kwan Do and other eastern martial arts will understand these ideas. Go, too, was considered a martial art by the samurai, and the more you understand go the greater becomes your appreciation of these Taoist principles.

"If this were go
I'd start a ko fight
and surely live,
but on the road to death
there's no move left at all."
Poem attributed to Sansa, the first Honinbo (leader of a prestigious Japanese go school) and founder of that line. He is said to have composed it on his deathbed in 1623.

There is a certain formation of black and white stones whereby one player can capture a stone, but is then liable to immediate recapture, returning the board exactly to its previous position. The captures could therefore repeat indefinitely. This formation is not unreasonably called 'ko', the Japanese for eternity. It occurs frequently, usually many times in a game. Even worse, ko situations can arise where it is worth a lot of points to be the last person to capture. Given the choice each player might repeat indefinitely.

The third rule provides an orderly escape. It says that after player A captures a stone in a ko, player B cannot take back immediately. He must play at least one move elsewhere first. This gives A an opportunity to destroy the ko formation. If he doesn't do so, and the ko still exists on B's subsequent turn, the roles may reverse. B may take back, forcing A to 'play away' for a turn.

It is not all bad for the person who has to play away from a big ko. If he can find somewhere on the board where two consecutive moves would be worth even more than winning the ko, the other player will be forced to respond, leaving the ko intact and available. Good players deliberately leave situations unresolved across the board to be used like this as 'ko threats' later, and a ko can develop into a complex fight. Or if a situation is resolving adversely for a player he may abandon it early, aiming to rescue it later with the two free moves that a ko fight offers.

"Go is to Western chess what philosophy is to double entry accounting"
Shibumi, bestseller by Trevanian

To many go players chess is the 'c' word, but the main reason to mention chess in a go article is not to disrespect it, but to provide a reference point. The two certainly seem like diametrical opposites. Chess has complex rules, go simple ones. Chess eliminates, go accumulates. Chess pieces are hierarchical, go pieces are equal. Chess is a battle, go is a war of many battles. Someone famously wrote a PhD thesis on the theme that in the Vietnam war, the Vietcong were using go strategy while the US military were playing chess. Personally I like chess, but I think go is in a different league.

My favourite theory is that chess is a variant of go. Despite the received wisdom that chess was invented in India or, even less likely, Persia, there is evidence to suggest its origin may actually have been China. There are more chess-variants in the Far East than anywhere else, and there is controversial documentary evidence in China that precedes anything in India. As it happens, Chinese chess, called "Xiangqi", is the only variant played with small round medallions inscribed with the name of the piece. It is also the only variant played on the intersections of the grid rather than inside the squares. The board has 9 x 9 intersections, like many small go boards, which corresponds to 8 x 8 squares. I'm not sure if anyone believes this but me (and you?), but it is such a neat idea I would be disappointed if it were disproved. It may be that go, chess, backgammon and playing cards were all invented in China.

"A bad plan is better than no plan at all"
Go proverb

"In the beginning, have no plan"
Go Proverb

Emanuel Lasker, an early chess grandmaster and one of the first western go enthusiasts, wrote "Chess is 99% tactics". He, like many others since, was impressed by the contrasting strategic depth of go. Now go, like chess, provides situations where the ability to read ahead is of paramount importance. It even has a vast body of TsumeGo problems, equivalent to the chess problems found in newspapers, and equally mindblowing. But in go the tactics are nothing without a separate strategic vision, which must be revised continually through a match.

Go is often referred to as "intuitive"; not because it is obvious to one and all, but because it is often not easy to explain rationally why one move is better than another. It is simply impossible to follow through all the continuations, so it comes down to experience. To help the task, Go has developed a large vocabulary of esoteric terms such as influence, aji - literally 'flavour', thickness, sabaki - 'lightness', and a folkloric list of proverbs, many of them conflicting, but nonetheless true for that.

"Studying go is a wonderful way to develop both the creative as well as the logical abilities of children because to play it both sides of the brain are necessary."
Cho Chikun, among the world's strongest players and one of the three great prodigies in go history

It is the intuitive nature of the game that makes it so hard to program. Currently the best programs on the fastest computers play little better than beginners, though the financial rewards for improving on this are huge. For twenty odd years (until the recent death of the donor) there was prize of $1 million for a program which could beat a professional player. This goal is still unlikely in our lifetimes.

The basis for computers playing games is the Minimax algorithm invented by Claude Shannon, which examines the tree of possible moves and counter-moves up to the limits of allowed time and computer resources. It evaluates all the positions reachable at the outer edge of the tree, and then uses the algorithm to prune the tree back down to the best first move.

The problems with computer go start with the size of the tree, due to the large number of potential moves. Chess has an average 30 or so legal moves per turn, generating of the order of a million possible positions within 5 moves. But go has an average of about 250 legal moves per turn, generating of the order of a thousand billion positions. The real problems begin, though, with the evaluation function. Computers have great difficulty deciding which is the better of two go positions, and cannot even reliably say who is the winner when the game is over.

Nevertheless, there are a number of programs available for beginners to practice against. Gnugo for Unix is the open-source choice (join the development team!). Igowin for Windows has an excellent built-in tutorial for beginners, and is free in the beery sense (burp).

"Often times at my go club, enraged old men will take the Goban and hurl it against the wall. This not only causes loud noises and distractions but also many injuries due to the flying stones. The old man then uppercuts his opponent and storms out of the room. If the man is seriously injured, he must wait until a member of the club is not playing a game before he can receive help. This is one of the worst habits in my opinion. Main Reasons:
  • Death or serious injury may be caused to your opponent.
  • Rushes all other games because the players are hurrying to finish in order to give the injured opponent proper medical treatment.
  • Less boards to play with in the club.
  • Less appealing club location due to dent in wall."
Posting to the brilliant Sensei's Library, under the section "Bad Habits"

Internet go servers are the safest way to play! They are bringing go to a new audience. The Kiseido Go Server (KGS) is friendly to beginners and has the best client and protocol. Log on as a guest and just watch some games. Be baffled! IGS is where the pros hang out. The Dragon go server is good for games at email speed. Most servers will even calculate your rating automatically after you've played a few games.

"There are nine mental levels into which players are distinguished. The first is called 'being in the spirit', the second 'seated in enlightenment', the third 'concreteness', the fourth 'understanding changes', the fifth 'applying wisdom', the sixth 'ability', the seventh 'strength', the eighth 'being quite inept', and the ninth and last 'being truly stupid'."
The Classic of Weiqi in Thirteen Chapters, c.1054 AD

The rating system was developed originally by the old Japanese go schools and is now used universally despite differences in calibration between countries. It allows players of different strength to play even games by giving the weaker player free moves ("handicap stones") at the beginning; the number being determined by the difference in grade between the two players. Traditionally there is a formal placement for these stones, to a maximum of nine.

Experts are assigned a "dan" rating, rising from 1 to 9-dan. A 9-dan player should therefore give a 1-dan player eight free handicap stones for an even game. There are not many 9-dan amateurs, but professionals have a separate, stronger dan scale, where a 1-dan professional is about the same strength as a 7-dan amateur. There are many great 9-dan professionals, though the professional scale doesn't really relate to handicap stones.

The rest of us get to play on the nursery slopes. We have our own "kyu" scale which runs in reverse from a complete beginner at 30-kyu up to 1-kyu, which is one point weaker than 1-dan. Again, every point on the scale corresponds to a free handicap stone. As a 5-kyu player with many years experience, I could start with twelve free moves against a top professional and still probably lose.

"Monks who have a talent for it play go with women and become their lovers."
Yamaoka Genrin (1631 - 1672), Edo-period essayist

To buy your own lover-board, try Kiseido, Samarkand or Yutopian.

For further reading, download The Way to Go by Karl Baker. A more in depth introduction is given in Go for Beginners by Kaoru Iwamoto, but there are dozens of other beginner's books to choose from.

The British Go Association and the American Go Association also sell equipment at a discount to members, as well as providing lots of other real and virtual resources, including downloads. The European Go Association can help you locate your nearest european club.

Jan van der Steen's go site is encyclopaedic, up-to-the-minute and very well presented. Play through the latest tournament games one move at a time.

Other interesting sites include the Mind Sports Olympiad, Milton Bradley's go pages, Harry Fearnley's go pages, and the rec.games.go newsgroup.

The Go Teaching Ladder is an neat way to improve. Send in your game records and the contributors here will review them for free. Also try the online Interactive Go Tutorial.

If you are prepared to pay for tuition, Guo Juan is the real thing. A 5-dan chinese professional living in Holland, who runs an internet based go-school. She sometimes gives demonstration games on the Kiseido Go Server too.

Sponsors

Voxel dot net
o Managed Hosting
o VoxCAST Content Delivery
o Raw Infrastructure

Login

Poll
K5 and go
o I already play go 33%
o I knew the rules but never played much 31%
o I'd heard of/ seen the game but didn't know much about it 27%
o I'd never heard of the game 2%
o I read the article and still don't know what you're talking about 0%
o Is that the same as Othello? 2%
o How do you spell that? 1%

Votes: 233
Results | Other Polls

Related Links
o Kuro5hin
o Combinator ial Game Theory
o Surreal numbers
o Confucius
o The Master of Go
o Tao Te Ching
o Shibumi
o TsumeGo
o list
o proverbs
o program
o Gnugo
o Igowin
o Sensei's Library
o Kiseido Go Server
o IGS
o Dragon go server
o The Classic of Weiqi in Thirteen Chapters
o Kiseido
o Samarkand
o Yutopian
o The Way to Go
o Go for Beginners
o British Go Association
o American Go Association
o European Go Association
o Jan van der Steen's go site
o Mind Sports Olympiad
o Milton Bradley's
o Harry Fearnley's
o rec.games. go
o Go Teaching Ladder
o Interactiv e Go Tutorial
o Guo Juan
o Also by GoStone


Display: Sort:
Go: Life Itself | 310 comments (294 topical, 16 editorial, 0 hidden)
Alright (2.22 / 18) (#1)
by psychologist on Thu Jul 11, 2002 at 06:34:10 AM EST

I learnt this game when I was six, together with chess. I played these games with my father all day, because I lived in a country where television did not show interesting stuff.

I don't advice you edit it, but I really dislike chinese and japanese wise sayings when they are spouted by people who call themselves "geeks". They seem to think it makes them cooler

I'm confused... (4.66 / 6) (#37)
by Stick on Thu Jul 11, 2002 at 11:20:30 AM EST

because I lived in a country where television did not show interesting stuff.

You lived in America?


---
Stick, thine posts bring light to mine eyes, tingles to my loins. Yea, each moment I sit, my monitor before me, waiting, yearning, needing your prose to make the moment complete. - Joh3n
[ Parent ]

No... (5.00 / 3) (#97)
by rusty on Thu Jul 11, 2002 at 01:56:17 PM EST

...just Earth. :-)

____
Not the real rusty
[ Parent ]
My television shows interesting stuff. (1.50 / 2) (#124)
by Shren on Thu Jul 11, 2002 at 03:42:55 PM EST

...because my playstation 2 is plugged into it...

[ Parent ]
Can't...help...myself...must...slap... (5.00 / 2) (#170)
by freebird on Thu Jul 11, 2002 at 06:22:50 PM EST

I've been ignoring this all day, but it just got under my skin and I have to regulate:
I don't advice you edit it, but I really dislike chinese and japanese wise sayings when they are spouted by people who call themselves "geeks".

OK, so really they shouldn't talk about Go either, right? After all, it's not their culture either (as you seem to assume the author must not actually be Japanese or something...) so they have no business dabbling in it. Can we talk about chess? Well, that probably came from India, so that's out. I guess western geeks really can't talk about much but the kind of rocks their anscestors liked to hit each other with, eh? Um, is it OK if I don't identify as 'geek'? Or is it cross-cultural reference in general you disapprove of?

More to the point, since I don't think you actually mean you can't talk about stuff from other cultures, is that there is a tremendous body of philosophical and literary material relating to Go, and ignoring it is both robbing yourself of some beautiful things, and ensuring that you'll never be very good at Go.

So I don't really know what your concern is. Judging from the quality of the article, do you really think the author just wanted to throw something in to "make them[selves] cooler"? Or did he just do an excellent job showing the deep and rich traditions and culture associated with this deep and rich game?

What's the problem here?

...TAGGATC...(etc)
[ Parent ]

Go, Chess, and the Real World (3.71 / 7) (#18)
by zenofchai on Thu Jul 11, 2002 at 10:00:42 AM EST

I'd love to play go. It has fascinated me as an observer -- but I'm afraid I would be "quite stupid" at playing the game. I have enough trouble with chess.

What I like most about chess, is that most people (at least in my circles) have at least a passing affinity for chess, or at least know most of the basic rules. I have an "open chess" match in my office, where basically I leave a board and all the pieces, and players make a move and record their move on a whiteboard. Basically, you walk by, take a look at the board, and make a move. You probably play both sides in the same game, and you don't really even know who is making some of the moves.

If I tried the same with 'go', the board would probably sit mostly empty, most of the time.
--
as gold which he cannot spend will make no man rich, so knowledge which he cannot apply will make no man wise.

Learn! (4.00 / 4) (#21)
by codemonkey_uk on Thu Jul 11, 2002 at 10:21:11 AM EST

Go really is a wondeful game, and not to hard to learn. Don't be afraid of defeat - go has a good handicap system, and you can start on a 9x9 board so it's not so intimidating. I used to play Go on my lunch breaks at work. You can play me on Richards PBeM server as well.
---
Thad
"The most savage controversies are those about matters as to which there is no good evidence either way." - Bertrand Russell
[ Parent ]
I like the idea (5.00 / 2) (#56)
by GoStone on Thu Jul 11, 2002 at 11:47:32 AM EST

this might be a neat way to teach go in an office


Cut first, ask questions later
[ Parent ]
Different skillset (5.00 / 2) (#164)
by sabaki on Thu Jul 11, 2002 at 05:43:40 PM EST

I'm afraid I would be "quite stupid" at playing the game.

You might be quite surprised. There's a different skillset involved with Go, and different strategies and tactics.

Chess is, at its essense, a cutthroat game where the purpose is to kill your opponent. But you can win a Go game without capturing a single stone -- it's about getting more territory (even just by a tiny bit) than your opponent.

Also, skills like counting and shape/pattern recognition come in handy. I'm not good at the former, (which my mathematician opponents can never believe) but I excell at the latter (which frustrates them when I capture a critical group). Even if you lose a group, it's possible to turn that into a victory -- sacrifice is a big part of strategy.

So give it a shot -- play some other beginners for a while, or one of the 9x9 starter programs. You could be pleasantly surprised. (And then, hopefully, hooked.)



[ Parent ]
whoa (3.00 / 4) (#19)
by VoxLobster on Thu Jul 11, 2002 at 10:13:40 AM EST

I saw the movie Pi just the other day...the Max and Saul play Go almost every time they meet...that's freaky that there's a story about it now.

VoxLobster
I was raised by a cup of coffee! -- Homsar

Purdy GUIs. (3.83 / 6) (#20)
by evilpenguin on Thu Jul 11, 2002 at 10:15:59 AM EST

For those that want a nice looking GUI to play gnugo with, there's Cgoban. It also acts as a client for Go servers. I recommed it to anyone using gnugo, especailly beginners. Personally, I find it hard to visualize strategies without some sembalence of a goban, and I haven't found a better one than cgoban (that is, for free).
--
# nohup cat /dev/dsp > /dev/hda & killall -9 getty
Cgoban/Gnugo will run under Windows/Cygwin, also (none / 0) (#68)
by graal on Thu Jul 11, 2002 at 12:25:22 PM EST

Just fired it up, but had to shut it down, as I'm at work. :(

--
For Thou hast commanded, and so it is, that every
inordinate affection should be its own punishment.
-- St. Augustine (Confessions, i)
[ Parent ]

CGoBan (none / 0) (#157)
by sabaki on Thu Jul 11, 2002 at 05:15:35 PM EST

CGoBan is actually the client for the Kiseido Go Server (mentioned in the article) -- the author started out writing his ideal client, then decided to write a server to test it on, and at some point he partnered with Kiseido.

It's my favorite server -- it's got great editing tools, community AND it's hosted down the street. (Your relative location may vary.)



[ Parent ]
Uhhh (2.77 / 9) (#22)
by jmzero on Thu Jul 11, 2002 at 10:40:30 AM EST

For twenty odd years (until the recent death of the donor) there was prize of $1 million for a program which could beat a professional player. This goal is still unlikely in our lifetimes.

Maybe if you're 70.....  

In the 80 more years I intend to live, computers are scheduled to get about 2^60 times faster (depending on what you think Moore's law should be now).  And likely all it will take is a novel algorithm or a determined good player to radically advance computer play.

Current software cannot "reliably say who is the winner when the game is over"?  If true, this demonstrates considerable lack of interest among programmers.  This shouldn't be at all a taxing challenge.
.
"Let's not stir that bag of worms." - my lovely wife

Hes right you know.. (1.85 / 7) (#25)
by tonyenkiducx on Thu Jul 11, 2002 at 10:55:17 AM EST

There isnt any computing problem you cant solve. Theres now hardware/software that can extrapolate 3D environment maps from a 2D view, down to almost microscopic level(Obviously depending on the camera). So programming a system to score go shouldnt be that difficult. I just learnt the rules for go about ten minutes ago, but the scoring system doesnt seem that complicated. Id program a system for it myself, but I'm incredibly lazy.

Tony.
I see a planet where love is foremost, where war is none existant. A planet of peace, and a planet of understanding. I see a planet called utopia. And I see us invading that planet, because they'd never expect it
[ Parent ]
mighty presumptuous (5.00 / 6) (#36)
by mikeliu on Thu Jul 11, 2002 at 11:17:19 AM EST

That's mighty presumptuous of you two to believe that you've suddenly made some great insight into a well known Very Difficult Problem after only being introduced to it.  Even more than that, as you have no real insight or solution, to believe that you two know better than people for whom this domain is their area of expertise in life.

"In the 80 more years I intend to live, computers are scheduled to get about 2^60 times faster (depending on what you think Moore's law should be now)."

To the contrary, Go is a well known problem in computer science, and it is well known for being a problem that cannot possibly be brute forced.  You seem very impressed by the amount of expected increase in computing power, along the lines of 2^60 times, and admittedly it is a very impressive number.  However, let's throw into the mix another number.  The estimated search space for go is something on the order of 10^170.  Really brings that 2^60 into perspective doesn't it?

"Current software cannot "reliably say who is the winner when the game is over"?  If true, this demonstrates considerable lack of interest among programmers.  This shouldn't be at all a taxing challenge."
"So programming a system to score go shouldnt be that difficult. I just learnt the rules for go about ten minutes ago, but the scoring system doesnt seem that complicated. Id program a system for it myself, but I'm incredibly lazy."

The author failed to point out the difficulty in scoring himself, which is perhaps a fault in the article.  The difficulty lies in the fact that a game of go is not over when every piece has been played, or when the king has been captured.  A go game ends (between two skilled players) when both players acknowledge that the game has ended.  The game will reach a point such that both players (if they are skilled) know exactly how it will end, and then the game is over.  So there's more to this problem than just (sum(pieces captured, area surrounded)).

Want to learn more so that you can at least be informed before you shoot off your mouth?  Here's a place to start that I found after a second of googling:
http://ai-depot.com/LogicGames/Go.html

"And likely all it will take is a novel algorithm or a determined good player to radically advance computer play."

Granted.  A novel algorithm can work wonders  (Though frankly I dunno what you're getting at with the determined good player bit).

And likely all it will take is a novel algorithm to radically advance the cause of true human-level machine AI as well.  Now figuring out the algorithm, there's the trick isn't it.....

[ Parent ]

I didnt say it would be easy.. (3.00 / 2) (#38)
by tonyenkiducx on Thu Jul 11, 2002 at 11:20:44 AM EST

..but it will be done. If your brain can do it, then a piece of AI can too. My comment about thinking I can do it was a joke. I obviously couldnt as I dont fully understand it myself yet, hence the "I've only been playing for ten minutes" comment. Sorry for the misunderstanding :)

Tony.
I see a planet where love is foremost, where war is none existant. A planet of peace, and a planet of understanding. I see a planet called utopia. And I see us invading that planet, because they'd never expect it
[ Parent ]
heh (3.00 / 2) (#44)
by mikeliu on Thu Jul 11, 2002 at 11:30:28 AM EST

Sorry for jumping all over you.

"I didnt say it would be easy.."
Heh, I guess I overreacted.  It's just that I misinterpreted the part where you said "so programming a system to score go shouldnt be that difficult" to mean "it would be easy".  My bad =P

[ Parent ]

AI and brains (1.00 / 1) (#197)
by Thinkit on Fri Jul 12, 2002 at 02:27:38 AM EST

What is AI? The term makes no sense. We'll progress by hooking up concious entities directly to computers, which is a lot more interesting than this AI (which is usually just applied to deterministic systems that are too complicated to understand quickly).

[ Parent ]
Of course it makes sense.. (3.00 / 1) (#210)
by tonyenkiducx on Fri Jul 12, 2002 at 05:11:41 AM EST

Its currently one of the most researched areas of computing. AI can provide solutions to problems that only humans can currently solve, and they can usually do it much faster. For example, AI is available that can scan video footage of hundreds of people, match them up to a database, and pick certain people out in real-time. You would need several dozen human brains to handle that, no matter how well there hooked up to a computer system.

Tony.
I see a planet where love is foremost, where war is none existant. A planet of peace, and a planet of understanding. I see a planet called utopia. And I see us invading that planet, because they'd never expect it
[ Parent ]
Intelligence (1.00 / 1) (#215)
by bloat on Fri Jul 12, 2002 at 06:29:47 AM EST

That's not intelligence - it's just digital signal processing and pattern recognition.

And guess what - it's done by Turing complete machines which are completely subject to the laws of maths which produce the Halting Problem.

CheersAndrewC.
--
There are no PanAsian supermarkets down in Hell, so you can't buy Golden Boy peanuts there.
[ Parent ]

You dont even know what your talking about (4.00 / 1) (#217)
by tonyenkiducx on Fri Jul 12, 2002 at 06:59:20 AM EST

And I dont mean that in a bad way ;) Nobody can/has defined what intelligence is, so you cant say its not intelligent. If you compair your brain to a neural net used in artificial intelligence, they are very similair, and modern AI is getting very close to producing an exact copy of the human mind(Albeit on a smaller scale). I give these links as evidence.

Nitrous Oxide & Neural Nets

Creativity Machine

Tony.
I see a planet where love is foremost, where war is none existant. A planet of peace, and a planet of understanding. I see a planet called utopia. And I see us invading that planet, because they'd never expect it
[ Parent ]
It's pretty simple (none / 0) (#234)
by Thinkit on Fri Jul 12, 2002 at 12:58:43 PM EST

Consciousness is an entity that constantly processes waveforms.  Hook up a computer directly to the input and output of this, and you'll have all the intelligence you could want.

If your really like this issue, try to get an article about it to the frontpage, so I can explain.

[ Parent ]

Blah, blah, blah (4.00 / 2) (#41)
by jmzero on Thu Jul 11, 2002 at 11:24:11 AM EST

I misunderstood what was meant by "reliably say who is the winner when the game is over".  I'm very sorry.  I know I shouldn't be doing awful things like "posing questions" here on K5. I have played the game before (although according to slightly different rules), and I thought the author meant something he didn't.

I'm not saying that the game of Go is going to be easy to figure out.  All I was suggesting is that a lifetime is an awful long time in terms of progress, and that perhaps that it would be an overstatement of the problem's difficulty (and human's capacity for the game) to suggest that there won't be a challenge in "our" lifetime.

Suggesting that humans have this sort of mystical gift for playing a game is a good way to set yourself up for disappointment - no matter how much trouble current programs are having with the problem.

.
"Let's not stir that bag of worms." - my lovely wife
[ Parent ]

well... (5.00 / 2) (#51)
by mikeliu on Thu Jul 11, 2002 at 11:39:59 AM EST

I misunderstood what was meant by "reliably say who is the winner when the game is over".  I'm very sorry.  I know I shouldn't be doing awful things like "posing questions" here on K5."

Heh, I don't think it was the posting of questions that made everyone rate you so harshly and made me snap out a reply.  I think it was more your statements that accompanied your questions, which gave off the reek of arrogance (like the parts where you comment that the problem is difficult just because it "demonstrates considerable lack of interest among programmers" or that it "shouldn't be at all a taxing challenge").

I'm not saying that the game of Go is going to be easy to figure out.  All I was suggesting is that a lifetime is an awful long time in terms of progress, and that perhaps that it would be an overstatement of the problem's difficulty (and human's capacity for the game) to suggest that there won't be a challenge in "our" lifetime.

Suggesting that humans have this sort of mystical gift for playing a game is a good way to set yourself up for disappointment - no matter how much trouble current programs are having with the problem.

Now here I agree with you.  I do believe strongly in the potential of AI in the future, despite our rather lackluster history with it.  This isn't nearly as "easy" a problem as chess was though, and we will have to formulate whole new approaches for attacking this problem, probably a whole lot more akin to the way that people do it than the way computers have played games in the past.  But then again, people have also been known in the past to make overstatements about the speed of progress as well....shouldn't we have flying cars by now or something?

[ Parent ]

Yeah... I'm dumb. (3.00 / 2) (#55)
by jmzero on Thu Jul 11, 2002 at 11:45:59 AM EST

Heh, I don't think it was the posting of questions that made everyone rate you so harshly and made me snap out a reply.  I think it was more your statements that accompanied your questions, which gave off the reek of arrogance (like the parts where you comment that the problem is difficult just because it "demonstrates considerable lack of interest among programmers" or that it "shouldn't be at all a taxing challenge").

My intent was sarcasm - I wanted someone to explain how scoring the game (after it was over, as I initially misunderstood) was going to be a hard thing.  I see how this would have sounded offensive if you didn't figure out what part I was misunderstanding.  Have a good day.

.
"Let's not stir that bag of worms." - my lovely wife
[ Parent ]

thanks, just getting there myself (3.00 / 1) (#47)
by GoStone on Thu Jul 11, 2002 at 11:33:51 AM EST

but I couldn't have said it better.

fair criticism of the article, I knew there was something I forgot. Just about everything actually :-)


Cut first, ask questions later
[ Parent ]

Oh really? (4.33 / 3) (#43)
by lb008d on Thu Jul 11, 2002 at 11:27:14 AM EST

There isnt any computing problem you cant solve

"tonyenkiducx meet the Halting Problem. Halting Problem, tonyenkiducx. I'm sure you two will get along just fine."

[ Parent ]

Gimmie.. (3.00 / 1) (#46)
by tonyenkiducx on Thu Jul 11, 2002 at 11:33:35 AM EST

..a bit to read about it ;) I love a challenge.

Tony.
I see a planet where love is foremost, where war is none existant. A planet of peace, and a planet of understanding. I see a planet called utopia. And I see us invading that planet, because they'd never expect it
[ Parent ]
Ok, read it.. (2.00 / 1) (#52)
by tonyenkiducx on Thu Jul 11, 2002 at 11:41:34 AM EST

And from what I can see its a problem with current programming methods of the whole IF-THEN methodology. Wait till you get computer systems that no longer run on binary and YES-NO data, and your problem dissapears. Or am I mis-understanding? I'll read up a bit more on this, its intrigues me..

Tony.
I see a planet where love is foremost, where war is none existant. A planet of peace, and a planet of understanding. I see a planet called utopia. And I see us invading that planet, because they'd never expect it
[ Parent ]
also of interest (none / 0) (#66)
by speek on Thu Jul 11, 2002 at 12:21:31 PM EST

You might find Goedel's Incompleteness theorem of interest. It's related to the halting problem. Penrose's "The Emperor's New Mind" might be informative as well on the subjective on non-computable problems.

--
what would be cool, is if there was like a bat signal for tombuck - [ Parent ]

How the halting problem works (none / 0) (#78)
by prolefeed on Thu Jul 11, 2002 at 01:06:37 PM EST

What the halting problem, and other incompleteness theorems, tell us is that _one cannot write a program that can take *any* other program (in a turing-complete system) and *always* correctly determine some specific functionality of that program_.  

This theorem (Rice's Theorem) is usally proven by contradiction (http://www.wikipedia.com/wiki/Rices+theorem) -- essentially, if you had some program that was able to solve the halting problem, I could always take that solution and make a program that halts if and only if it doesn't halt.  This is impossible, thus you could never write a solution to the halting problem.

This has nothing whatsoever to do with *how* the formal system is constructed ("the whole IF-THEN methodology"), it has to do with fundamental properties of formal systems.

[ Parent ]

*ahem* (4.00 / 1) (#209)
by tonyenkiducx on Fri Jul 12, 2002 at 05:03:52 AM EST

My point was, the halting problem is one of those theoretical problems, like not being able to go past the speed of light. We know we cant go past the speed of light, but until we can explore that theory(And it is only a theory) fully, I will remain open to the possibilities. The turing machine is the same, its a theoretical machine(In mass computing terms), and the halting problem is also theoretical. I've been programming since I was 8, and Ive never come up against a situation were the halting problem may come into play. So until you can prove that the problem exists, or that there is definately no solution, I'll stick by my original statement. Every computing problem can be solved.

And on the point of formal systems, If-Then is a formal system. And you havent considered that computers dont need to be based on a formal system, think of your brain. It doesnt consist of much formal structure, its a lot of if-then-possibly-ormaybenot's. Your holding problem would apply to a computing system that was restricted to simple loops, but not a human brain, which for all intents and purposes is a very advanced computer. For example, You wouldnt get stuck in a holding loop, because You'd realise it was happening and take steps to prevent it, as would a half-decently intelligent computer system.

Tony.
I see a planet where love is foremost, where war is none existant. A planet of peace, and a planet of understanding. I see a planet called utopia. And I see us invading that planet, because they'd never expect it
[ Parent ]
theories (4.00 / 1) (#214)
by bloat on Fri Jul 12, 2002 at 06:25:31 AM EST

The halting problem is a provable mathematical fact. It is not an attempt to model the universe like the Theory of Relativity.

The fact that you can not build a real Turing Machine does not imply that it's not proven. You don't need to (and in fact you can't) have 2 * pi * r bottle caps to work out the circumference of a circle.

CheersAndrewC.
--
There are no PanAsian supermarkets down in Hell, so you can't buy Golden Boy peanuts there.
[ Parent ]

Erm, thats what I said.. (4.00 / 1) (#216)
by tonyenkiducx on Fri Jul 12, 2002 at 06:48:23 AM EST

But until you actually do it, IT IS NOT A FACT. A hundred years ago we knew that, mathematically, nature was so random that there was simply no way of calculating how certain things work(Fluid dynamics, biological population systems). Now with the latest in chaos theory and common attractors, we can work out how a particle of water moves through the sea with almost perfect accuracy. So what was a mathematical impossibility, isnt now that the proper solution has been found, and the necessary people convinced.

Even if you have the maths to prove it, you cant have explored all the maths that says you can prove the opposite. Even famous mathematicians have remained blind to new advances because there so convinced that there ideas are right. But a lot of basic assumptions about maths have been utterly destroyed in recent years, so who's to say your halting problem isnt one of those problems?

Tony.
I see a planet where love is foremost, where war is none existant. A planet of peace, and a planet of understanding. I see a planet called utopia. And I see us invading that planet, because they'd never expect it
[ Parent ]
Sure you can... (3.50 / 2) (#281)
by mattbelcher on Sat Jul 13, 2002 at 03:43:48 AM EST

just make sure that r = i/pi (where i is some integer). :)

[ Parent ]
The halting problem (4.00 / 2) (#246)
by Steeltoe on Fri Jul 12, 2002 at 02:09:40 PM EST

The halting problem cannot be solved by brute-force approaches, and a general algorithm quite impossible to implement. However, this is primarily due to a too general a problem.

It is easy to disprove and be negative. More constructive is to push the limits regardless of the naysayers. You shouldn't use these theorems to stomp on others' enthusiasm, that is misuse of such valuable resources. You were even the one to mention it in the first place just to set him up!

Of course a solution to the halting problem shouldn't halt! For it to somehow inspect itself and take action, would need a non-deterministic evolving system that most probably would take over the Internet and enslave us all! ;)

Despite such difficulties, we should proceed at full speed. There are algorithms developed to reverse-engineer Turing-complete algoritms into mathematical and logical knowledge. Then you don't NEED to waste cycles simulating any calculations, as the system will have access to proofs and theorems to use in determining a function.

Specialized solutions to the halting problem already exists, especially in us humans. However, we are not guaranteed anything in life. Humanity MAY halt before we solve a specific problem.

And that's just life man! ;-)
Explore the Art of Living

[ Parent ]

Yes, please (none / 0) (#64)
by mattbelcher on Thu Jul 11, 2002 at 12:09:08 PM EST

I'd love to see a Halting problem algorithm. Then I can finish that automated proof checker and universal program correctness solver I've had on the back-burner for a while now.

[ Parent ]
trivial (5.00 / 2) (#84)
by Ubiq on Thu Jul 11, 2002 at 01:20:37 PM EST

If you assume a finite amount of memory, it's trivial. Interestingly, 100% of the computers that can be bought today fall into this category.



[ Parent ]
No, it's not (5.00 / 1) (#144)
by fluffy grue on Thu Jul 11, 2002 at 04:51:55 PM EST

Given a finite amount of memory, the disproof by contradiction still holds.

For example, let's say you have a function, willHalt(char *program, char *input), which solves the halting problem.  Then you have this quite trivial program:

int main(int argc, char **argv) {
    if (willHalt(argv[0], argv[0]))
        for(;;);
    else
        return 0;
}

So you have here a program which takes the mythical "will this program halt?" function and runs it on itself.  If the function says that it will halt, then it goes into an infinite loop (and thus never halts), and if the function says that it won't halt, it immediately halts.

There is NO WAY that any implementation of willHalt() could POSSIBLY give the correct answer!
--
[ Hug Your Trikuare ]
[ Parent ]

For linear-bound automata, halting prob's decidabo (none / 0) (#161)
by prolefeed on Thu Jul 11, 2002 at 05:36:21 PM EST

Look it up for a decent proof.  IIRC, since the set of states is finite, and the set of strings on the tape is finite, it can only run infinitely if it comes back to the same state with the same string.  Indeed, you can compute the upper bound on the number of steps a terminating linear-bound automaton can take.  (So if it runs longer than that it must run infinitely.)

[ Parent ]
Oh yeah (none / 0) (#162)
by fluffy grue on Thu Jul 11, 2002 at 05:41:31 PM EST

I forgot about that one. Though you also have to assume that the system is totally deterministic (and if you're dealing with, say, any sort of I/O, it won't be). Though that does expand the problem outside of "finite memory" since you can consider the external states to just be part of the memory and so on, yadda yadda.
--
[ Hug Your Trikuare ]
[ Parent ]
IO would fork the problem space (none / 0) (#251)
by Steeltoe on Fri Jul 12, 2002 at 02:20:45 PM EST

The problem with your first post, was that you didn't specify arguments. Thus, how are one supposed to solve a partial problem like that?

A brute-force solution is to fork the process for each unaccounted value from either IO or initial arguments. This is both time-consuming and slow, but not infinite.

The answer could be represented as a multi-dimensional matrix ripping through spacetime itself! ;-)
Explore the Art of Living

[ Parent ]

halting problem solution (none / 0) (#65)
by speek on Thu Jul 11, 2002 at 12:19:15 PM EST

I can write a program that can solve the halting problem. In constant time even!

Tester: Will this program ever end (inputs program code)?

My program: Yes (response immediate).

--
what would be cool, is if there was like a bat signal for tombuck - [ Parent ]

That's not correct though (none / 0) (#141)
by fluffy grue on Thu Jul 11, 2002 at 04:38:17 PM EST

Given infinite computing resources (which is the premise of the halting problem - the entropic heat death of the universe doesn't count), your program will give the wrong answer for main(){for(;;);}.
--
[ Hug Your Trikuare ]
[ Parent ]
And if the system has one of a billion conflicts (none / 0) (#166)
by Xeriar on Thu Jul 11, 2002 at 06:00:23 PM EST

Like say, the system does not have enough memory to stop the program, it will not halt. If it cannot access the resource needed to respond 'yes' it will not halt.

If if your program did work, it's not solving the halting problem anyway. It is merely saying that it is sure that -it- will not halt, not some other program.

I realize you were being semi-sarcastic, but this is a far more hideous problem than you may guess.

----
When I'm feeling blue, I start breathing again.
[ Parent ]

really? (none / 0) (#177)
by rantweasel on Thu Jul 11, 2002 at 07:39:31 PM EST

Just to be pedantic,

while true {
   i++
   print i
}

will halt when?

mathias

[ Parent ]

when you have a power outage (nt) (3.00 / 2) (#221)
by speek on Fri Jul 12, 2002 at 09:47:43 AM EST


--
what would be cool, is if there was like a bat signal for tombuck - [ Parent ]

Winners (4.50 / 6) (#27)
by Happy Monkey on Thu Jul 11, 2002 at 10:59:37 AM EST

Current software cannot "reliably say who is the winner when the game is over"? If true, this demonstrates considerable lack of interest among programmers. This shouldn't be at all a taxing challenge.

I think this is because Go games don't always go down to the bitter end - at some point it is obvious to good players who the winner is certain to be. What this means is that a computer player wouldn't know when to resign, thus making games against computers longer and more tedious.
___
Length 17, Width 3
[ Parent ]
That makes more sense.. (n/t) (3.33 / 3) (#28)
by jmzero on Thu Jul 11, 2002 at 11:00:56 AM EST

But instead of explaining it, why didn't you just mod me down?
.
"Let's not stir that bag of worms." - my lovely wife
[ Parent ]
I wasn't certain I was right. (4.00 / 3) (#31)
by Happy Monkey on Thu Jul 11, 2002 at 11:10:23 AM EST

And therefore didn't have the righteous indignation that it wasn't obvious to you.
___
Length 17, Width 3
[ Parent ]
Well.. (3.00 / 1) (#35)
by tonyenkiducx on Thu Jul 11, 2002 at 11:17:08 AM EST

Chess computers can decide when they are in a no-win situation by scoring the board and considering available moves. But you must'nt forget that chess computers/programs have been evolving for a long time. They were among some of the first artificially intelligent game playing systems built. Go software may just need more work on it to develop better algorythms for "understanding" the board and the scoring system.

Tony.
I see a planet where love is foremost, where war is none existant. A planet of peace, and a planet of understanding. I see a planet called utopia. And I see us invading that planet, because they'd never expect it
[ Parent ]
lifetimes... (4.66 / 3) (#48)
by GoStone on Thu Jul 11, 2002 at 11:35:14 AM EST

As I understand it, go programming has been around almost as long as chess programming. Remember, go is much more popular in the East than chess is in the west.

Even if computers became 2^60 times faster that would only allow the tree to look ahead about 8 more moves.

In go, stones are often played and then 'ignored' for twenty or thirty moves. They have made their point, so play moves on elsewhere. Looking ahead 10 or even twenty moves would not allow the computer to decide if the stone was worth playing in the first place.

mikeliu answers this better than me, thanks


Cut first, ask questions later
[ Parent ]

Indeed (4.50 / 2) (#59)
by jmzero on Thu Jul 11, 2002 at 11:53:37 AM EST

Go is certainly a different challenge than chess, and you've given good reasons why it will be less vulnerable to brute force, "tactical" assault.  Perhaps the problem will remain intractable.

All I'm suggesting is that a lifetime is a long time, especially in computer science - and especially if the problem is as important to as many people as you suggest.  
.
"Let's not stir that bag of worms." - my lovely wife
[ Parent ]

8 moves more (4.00 / 1) (#72)
by gazbo on Thu Jul 11, 2002 at 12:39:42 PM EST

Yes, but how many moves do humans look ahead? Just because the complete minimax tree is huge doesn't mean that a computer has to analyse the whole thing in order to beat a human. Humans can only look ahead a small number of moves as well.

As for your example of positions being left for 20 moves - that is the job of the static evaluator function that takes a board and scores it. It need only (hah!) make note of these positions matched against generic patterns in order to take note of them in the scoring. These static evaluators are where the 'intelligence' goes.

Less analytically, compare this with chess. Chess also has the problem where players will resign when a game is logically over. Chess also has a vast tree of moves "But go's tree is even bigger!" So? That's where the 2^60 improvement comes in. Also, remember that this bigger decision tree adversely affects the human player as well.

Finally, when computing was in its infancy, and chess programs were crappy little toys, everybody (in the world of chess) claimed that it would be impossible for a computer to beat a professional, for all of the same reasons as are being spouted now.


-----
Topless, revealing, nude pics and vids of Zora Suleman! Upskirt and down blouse! Cleavage!
Hardcore ZORA SULEMAN pics!

[ Parent ]

Korean Go Masters (5.00 / 2) (#86)
by Kintanon on Thu Jul 11, 2002 at 01:24:35 PM EST

The Korean 9th dan looks in around 220 moves ahead according to the accounts of his games that I have read. I can see around 17 moves ahead but I'm getting better at planning overall strategy now, so I work on building situations where my lack of foresight won't damage my chances of winning an area. I'm an 11 kyu player right now.

Kintanon

[ Parent ]

Hmm (none / 0) (#98)
by gazbo on Thu Jul 11, 2002 at 01:57:23 PM EST

220 moves considered in total, maybe. 220 moves ahead (i.e. deep), even when paths are pruned by past experience, I do not believe for a second. We are talking billions* of possibilities. In terms of moves examined a human couldn't even beat a 286** in the same timeframe.

*Give or take a dozen orders of magnitude.
**In terms of speed; I don't even want to think about memory addressing requirements, but I doubt it'd be a problem.

-----
Topless, revealing, nude pics and vids of Zora Suleman! Upskirt and down blouse! Cleavage!
Hardcore ZORA SULEMAN pics!

[ Parent ]

That paths will be heavily pruned (5.00 / 3) (#104)
by bgalehouse on Thu Jul 11, 2002 at 02:41:20 PM EST

The paths will be pruned very heavily by a go master, as he can recognize lots of moves that the opponent would never do. Also, if you have a fight, often the number of moves which affect it are limited, though recognizing how limited can be a real art.

I've heard a story in which Kitani (famous modern go player) said after the game 'I would have played here, but I didn't like the Ko'. "Ko?" his opponent asked. Kitani then proceded to show on the demonstration board a 100+ move fight going all the way accros the board and leading to a Ko. It perhaps wasn't the only continuation, but his opponent could certainly agree it was likely. At this point, his opponent basically gave up any chance of ever beating Kitani.

[ Parent ]

100+ moves (none / 0) (#130)
by Osiris on Thu Jul 11, 2002 at 04:09:24 PM EST

He probably just grabbed the demo board and played as many moves as it took to find a ko he could call the one he "didn't like".  And never told anybody he was faking it.

After all, if you can fake sincerity, you've got it made ;)

[ Parent ]

Sure Koreans are good at Go... (5.00 / 2) (#156)
by jmzero on Thu Jul 11, 2002 at 05:13:57 PM EST

But the Japanese whoop them at Eating Hotdogs.
.
"Let's not stir that bag of worms." - my lovely wife
[ Parent ]
2^60 (5.00 / 1) (#88)
by Dolohov on Thu Jul 11, 2002 at 01:29:12 PM EST

The problem is that the sheer number of possible games exceeds (19x19)! (That's a factorial). I say exceeds because every capture of stones makes for more possible moves, and thus more possible games.

No, sheer computing power will not make a good computer Go player any time in the next hundred years or so. What will, however, is the application of pattern-recognition techniques. Human players can manage to use their past experience to a point, as well as knowledge of certain patterns and a general awareness of the state of the board. Many are also familiar with their opponents' weaknesses, strengths, and styles, and can predict where an opponent is focusing his efforts. Programming a computer to do this and still play well is a considerable challenge.

[ Parent ]

[ns] (4.00 / 2) (#96)
by gazbo on Thu Jul 11, 2002 at 01:51:44 PM EST

Recognising players' weaknesses from previous games is pretty novel, but not impossible. I forget if Deep Blue used this technique, but I have a vague memory there was a certain amount of tuning to his opponent.

As for pattern recognition/awareness of board, that is what I was talking about when I mentioned static evaluators - it is their job to do exactly that. It is of course the programmers job (or, I guess, some sort of evolutionary algorithm) to configure these evaluators in the first place though.


-----
Topless, revealing, nude pics and vids of Zora Suleman! Upskirt and down blouse! Cleavage!
Hardcore ZORA SULEMAN pics!

[ Parent ]

Exceeds? Or not? (4.33 / 3) (#200)
by sjl on Fri Jul 12, 2002 at 03:00:37 AM EST

Just an observation. A starting move on the edge is universally recognised as a bad idea -- the stone is far too easily captured. On the first row in from the edge similarly. Second row in from the edge is usually pretty good, though. So to say that there are (19x19) possible moves at the start is true, but misleading: no sane Go player would ever start on the sides.

On a slightly related note -- what about symmetry? For each position other than the centre, there are at least three other positions that are effectively the same; usually there are seven (rotations and mirrors).

Certainly, though, the scope within Go is far too large to be brute forced with any known, or envisaged, technology. In my opinion, it will never be completely solved (in the sense of knowing whether Black or White wins, assuming perfect play on both parts.)

Great game, though -- I'm hooked. :) (and have been for a couple of months now.)

[ Parent ]

Symmetry (none / 0) (#231)
by Dolohov on Fri Jul 12, 2002 at 12:28:13 PM EST

That's true, I hadn't considered symmetries. Still, the number of possible games will exceed 2^60 pretty easily, I think.

[ Parent ]
Just like chess (3.20 / 10) (#23)
by Yellowbeard on Thu Jul 11, 2002 at 10:52:27 AM EST

It's a game that people think, because it's been around a long time and they find it difficult that mastering it is somehow the key to life or being good at it proves you're smart. I have news for you: mastering it only proves that you are good at a game.

"Whenever there is any doubt, there is no doubt." - Deniro in Ronin


philosophy in games (5.00 / 4) (#81)
by Phelan on Thu Jul 11, 2002 at 01:15:11 PM EST

It's a game that people think, because it's been around a long time and they find it difficult that mastering it is somehow the key to life or being good at it proves you're smart. I have news for you: mastering it only proves that you are good at a game.

There's a reason that people attribute intelligence and philosophical insights to games like Go and Chess, and not games like Tic Tac Toe.

Go and Chess exercise parts of the brain that deal with creativity and analytical thinking. Go, in particular, is far more dynamic and creative, where chess is far more analytical. Both have fundamental philosophical lessons that they can teach those who study them. Both are fundamentally games of war, teaching the values of sacrifice, feints, and territory.

Masters of these kinds of games are more than "just good at a game". They also show that they have an incredible grasp of certain kinds of thought processes: strategic thinking, logic, abstraction, combination, and mathematics. In 1893, Professor Binet found that 90% of chess players he questioned were good at math. The Venezuela "Learning to Think Project" reached the conclusion (involving a sample of 4200 elementary school kids) that learning chess accellerated an increase in IQ. Getting good at these kinds of games generally does mean you're smarter.

[ Parent ]

Throughout life (4.00 / 2) (#87)
by thebrix on Thu Jul 11, 2002 at 01:26:47 PM EST

I wonder what basis there is in this ... but I've never known any board game or card players fall apart after retirement as, sadly, so many people do. These games seem to be good for the mind throughout life.

As does bingo, which appears to exercise slightly different mental processes. Bingo is often unfairly caricatured, but keeping N cards going at high speed is phenomenally difficult to start with!

[ Parent ]

Correllation does not mean cause and effect (4.00 / 2) (#93)
by Yellowbeard on Thu Jul 11, 2002 at 01:47:14 PM EST

Here's an alernate theory: People who are good at math and smart tend to like these games because they know that people who are smart are supposed to play these games. It does not prove that they are smarter. I admit that it may prove that they are good at particular things associated with the games, but not necessarily that they are smarter in general.

"Whenever there is any doubt, there is no doubt." - Deniro in Ronin


[ Parent ]
mental exercise (none / 0) (#118)
by speek on Thu Jul 11, 2002 at 03:30:26 PM EST

What if I were to suggest that playing games like Go or Chess increases your intelligence, similar to the way lifting weights increases your strength. I've always thought we'd be better off if as children we were taught games like Go and Chess rather than math and science - at least till around 6th or 7th grade.

--
what would be cool, is if there was like a bat signal for tombuck - [ Parent ]

not in the 2nd case I cite (4.50 / 4) (#142)
by Phelan on Thu Jul 11, 2002 at 04:47:24 PM EST

While I do not have conclusive proof that Binet's study shows a non-causal link, this is not the case in the second case I cited.

In the second case, Venezuela specifically found that chess practice accellerated an increase in IQ compared to those who did not practice. In other words: chess made you smarter, faster.

Based upon this, I'd strongly suspect that Binet's study showed both a causal and correlating relationship (smart people tend to like chess, and chess makes them smarter).

[ Parent ]

Heh (3.00 / 1) (#186)
by phybre187 on Thu Jul 11, 2002 at 11:33:39 PM EST

I find it interesting that you accuse others of being obsessed with who is "smarter", when so far, you're the only person doing that. How do you quantify being "smart" ? Arbitrarily so that it benefits your trolling, I'm sure. If being "smarter in general" has nothing to do with "being good at particular things", then what does it have to do with?

[ Parent ]
What? (none / 0) (#305)
by Yellowbeard on Wed Jul 17, 2002 at 02:06:56 PM EST

1. By what cause do you call me a troll?

2. I never claimed to be smarter than anyone else. I just said that just because someone plays chess or go well does not mean they are.


"Whenever there is any doubt, there is no doubt." - Deniro in Ronin


[ Parent ]
Well, (none / 0) (#241)
by MoonVine on Fri Jul 12, 2002 at 01:50:31 PM EST


I 'm not smart and yet not only do I throughly get my rockers off playing chess, I am really good at it, and always have been. I have picked up a little of Go and find it fascinating to play, and feel it is only a matter of time before I become a really skilled Go player as well. I guess I like challenges. And I prefer poker over spades. Any correlation? Hmmmm, and no, I am not being sarcastic.

"If you are not in danger, do not fight."
Sun Tzu

[ Parent ]
Philosophical observations come with the furniture (5.00 / 1) (#83)
by thebrix on Thu Jul 11, 2002 at 01:20:20 PM EST

Alas, the admonition won't work. I'm not so sure about Go, but chess has had such analogies and metaphors by the shedload. There seems to be a compulsion to equate the struggle on the board to larger concepts:

Famous Chess Quotations

Exeter Chess Club: Chess Quotes

[ Parent ]

A nice way to get started (5.00 / 8) (#24)
by thebrix on Thu Jul 11, 2002 at 10:54:30 AM EST

If you have a PalmOS handheld I found the following combination very useful to get started:

AIGO (Go program, allows 9x9, 13x13 and 19x19 boards and is disconcertingly strong given the feeble performance of the platform, rather like Chess Genius or Chess Tiger);

Learn to Play Go: A Master's Guide to the Ultimate Game by Janice Kim.

At about £17 this pair is a steal and the perfect combination for train journeys or similar. Before now Go books tended to be rather dowdy and down-at-heel, as though they were turned out in a back bedroom, but Janice Kim's are superbly written and presented. (As implied the book is one of a series ... of four; the title is a little misleading as the 'master level' comes towards the end of the series).

Actually, it's not misleading... (4.00 / 1) (#159)
by sabaki on Thu Jul 11, 2002 at 05:27:04 PM EST

The title "A Master's Guide" is not misleading because she is the master, not the reader. It's a good book, but no one's going to become a master after reading one book.

I've had the good fortune to play Ms. Kim twice, and you understand how powerful a professional player when you make an attack and she declares it "a strong attack -- but ultimately futile!" and you both play a sequence over the next twenty stones where she gets exactly what she wants, regardless of how inescapable your attack seemed.

The professionals are the masters, and don't you forget it.



[ Parent ]
Go Rules (4.28 / 7) (#26)
by jmzero on Thu Jul 11, 2002 at 10:57:28 AM EST

The scoring rules as outlined in this article seem different. What's up?

Similarly your stones do not add to your score in any way, only the empty territory they surround

Maybe that's why computers are having such a hard time deciding who won (which I still think is ludicrous, even though codemonkey will probably mod me 2 again for saying so)...
.
"Let's not stir that bag of worms." - my lovely wife

Rule sets (4.50 / 4) (#34)
by GoStone on Thu Jul 11, 2002 at 11:14:20 AM EST

As you point out, there are a number of different formulations of the rules. They all play pretty much the same, however. In some, rarish, circumstances there may be a slight difference in the score.

The rule sets are not different enough that players think of them as different games.

You will also find that the rule sets have many more than 3 rules in them. Its partly a question of how you state them, partly a matter of trying to cover exceptional events that can happen.

My aim was to show the simplicity which underlies all versions of the rules, and to give beginners enough to know what the game is about.


Cut first, ask questions later
[ Parent ]

Scoring... (5.00 / 1) (#73)
by Chakotay on Thu Jul 11, 2002 at 12:40:17 PM EST

I knew the scoring where the stones plus territory surrounded counted. I think that's a good scoring system for beginners, as me. I've known the rules now for some 10 years, but have only had very few chances to play the game, unfortunately. But the scoring system you describe, where only surrounded territory counts, and not the stones themselves, seems extremely interesting to me. You then get interesting dilemmas when you have a large piece of territory with one or two loose "enemy" stones in them. Capture them and actually lose points, or leave them sitting there, glaring, in your turf? Interesting...

--
Linux like wigwam. No windows, no gates, Apache inside.

[ Parent ]
chinese rules (none / 0) (#115)
by GoStone on Thu Jul 11, 2002 at 03:16:57 PM EST

The scoring system you were using was probably based on the chinese rules. A lot of people think these are the best rules for beginners because they do make the issue of dead stones clearer.

In practice, there isn't usually much difference in the result whatever rules you use, strangely enough. I am told the main difference is in seki situations, which aren't all that common.

Its easy to get a game on the internet now. Just put up your invitation and wait for someone about the same strength as you to take you up. On the Kiseido server you can play whatever rules you want :-)


Cut first, ask questions later
[ Parent ]

seki difference (none / 0) (#257)
by nusuth on Fri Jul 12, 2002 at 02:53:05 PM EST

Actually the differenc is very simple. If you are counting empty territory, noone gets points from a seki, if you are counting territory+stones, both sides gets points from a seki. Usually one side will have less stones in a seki, so the net result would be non-zero. That is all there is to it as far as I know.

[ Parent ]
Actually,,, (none / 0) (#273)
by bgalehouse on Fri Jul 12, 2002 at 08:40:11 PM EST

Seki doesn't have a serious effect. The reason that Chinese counting (counting stones and territory) results in such a similar game to Japanese counting (counting just stones) is that, more or less, both people have made the same number of moves.

Since in Japanese counting, prisoners are placed back into the board, there will be a white stone on the board for every move white made. Similarly for black. So, in an even game, if nobody gratitously passed, and if white makes the last move (and some Japanese type rule sets use pass stones and/or require white to make the last move), then the two counting methods obviously give the same difference in score. Having a seki on the board doesn't change this.

Where things are different are things like the triple-ko rule and the bent four in the corner special rule. The triple ko rule comes from the fact that the Japanese don't use 'no repeating previous board positions' as a ko rule, but use something more complex, presumably hoping for something formally easier to 'implement' when playing face to face.

The bent four tries to match Chinese counting by not requiring the attacker to fill her ko threats first. (which costs points in Japanese counting, but not in Chinese) The problem this causes is that sometimes there is an unussual structure which gives an infinite supply of ko threats. So sometimes a bent-four wouldn't be dead under Chinese counting, wheras it is under Japanese.

And of course, the reason that most people, in this country at least, play by the Japanese rules is that it is easier to count. There are fewer spaces to count, so it takes less time. I daresay that is the primary reason for it's popularity. Though now through clever equipment and a rich recently deceased Chinese philatropist, (the same who came up in the computer Go discussion) a variation of Chinese counting which is easy to count is common at tournaments.

[ Parent ]

Computer Scoring. (4.66 / 3) (#42)
by thefirelane on Thu Jul 11, 2002 at 11:27:11 AM EST

Maybe that's why computers are having such a hard time deciding who won

The reason computers have such trouble scoring go games is because:
  1. When you score, you remove your opponents "dead" stones from your territory.
  2. To tell if stones are dead, you have to be good at Go
  3. To make a Go AI that is good, they really need to be set up to play each other in large test groups (like Genetic Algorithms for example)
  4. This makes a catch-22, as we can't make a good Go AI, unless we have a good Go AI. Until we do so, we are stuck with one of the following two options
    • Train Go AIs from recorded sets of human games, or against human players
    • Make Go AIs kill off all opponents stones (wasting their points) until the board has "settled" and there are no opponents stones in eachother's territory.


It should be noted however, that there are actually very strong life-and-death solvers out there. I have heard of one ranked at the 9-dan level, just for life and death problems. I'm not sure how practical it is to integrate this one into scoring, or how long it takes to compute.


---Lane

-
Prube.com: Like K5, but with less point.
[ Parent ]
Thanks, I misunderstood (dbr) (3.00 / 1) (#49)
by jmzero on Thu Jul 11, 2002 at 11:35:25 AM EST

I had thought the author was suggesting that it was hard to tell who had won after the game had been decided "over".  I figured it out a little after I posted, and somebody cleared it up later in the thread. Sorry.
.
"Let's not stir that bag of worms." - my lovely wife
[ Parent ]
PERFECT! (4.64 / 17) (#29)
by jabber on Thu Jul 11, 2002 at 11:01:26 AM EST

  1. You have sold me on the game of Go. I will be getting a board and stones this week. I'm really looking forward to it. Thank you.
  2. This is one of the greatest articles EVER on K5. Definite Hall-of-Fame material. Thank you.
  3. I need clarification on just one or two points, regarding scoring (no pun intended) and play. A captured stone is worth a point, as is each surrounded intersection. Does this imply that territories surrounded by capturing enemy stones, as opposed to the chaining of your own stones, count for the sum of captures AND the spaces they occupied?
Also, this implies my second play question. Captured territories are still considered in play, yes? So once A captures and area, B may play into it still to take away from A's points?

Fascinating game, and you've done it a great service with your article. Thank you.

[TINK5C] |"Is K5 my kapusta intellectual teddy bear?"| "Yes"

hey thanks! (4.50 / 4) (#40)
by GoStone on Thu Jul 11, 2002 at 11:21:28 AM EST

Good luck in your go adventures!

Yes, when you capture a stone it is often effectively worth two points. One for the stone, and one for the territory it leaves behind.

And you are also right about playing inside someones territory. It is perfectly legal, and you may be able to steal the territory away from them.

The problem is that inside enemy territory there is not much room to run, so you are likely to be captured, unless the territory is very large.


Cut first, ask questions later
[ Parent ]

Yes, I see (4.00 / 3) (#50)
by jabber on Thu Jul 11, 2002 at 11:38:06 AM EST

But once inside the territory, you are working to steal the space away, and any action your opponent takes to fight you, also takes away from their territory. Truly fascinating.

[TINK5C] |"Is K5 my kapusta intellectual teddy bear?"| "Yes"
[ Parent ]

Unless... (5.00 / 4) (#58)
by codemonkey_uk on Thu Jul 11, 2002 at 11:51:28 AM EST

For each stone you play, that forces him to play a defensive stone, there is no change in score in the case that your attack fails. Where your attack is futile and he does not play defensive stones, you are loosing points. Where you attack is a success, you can only gain points!

But it is impolite to launch an attack that must be defended against, but is trivial to repel - it implies you think you opponent is a fool.
---
Thad
"The most savage controversies are those about matters as to which there is no good evidence either way." - Bertrand Russell
[ Parent ]

So wait (4.00 / 1) (#70)
by jabber on Thu Jul 11, 2002 at 12:27:49 PM EST

A placed stone costs you a point?

[TINK5C] |"Is K5 my kapusta intellectual teddy bear?"| "Yes"
[ Parent ]

If it is captured... (4.00 / 2) (#74)
by codemonkey_uk on Thu Jul 11, 2002 at 12:40:28 PM EST

Your enemys gain is your loss.
---
Thad
"The most savage controversies are those about matters as to which there is no good evidence either way." - Bertrand Russell
[ Parent ]
What? (none / 0) (#287)
by brunes69 on Sun Jul 14, 2002 at 03:11:37 PM EST

When is your enemys gain NOT your loss???

---There is no Spoon---
[ Parent ]
no (5.00 / 1) (#76)
by GoStone on Thu Jul 11, 2002 at 12:47:56 PM EST

a stone played on your own territory costs you a point because that is no longer territory.

a stone played inside enemy territory may well cost you a point if your opponent decides to ignore it because he judges it would be dead even if you played more stones to help it

by a dead stone I mean it could be taken if necessary

this determines the end of the game. when neither player can make a move without actually losing points.

as I say, better to start playing, then these things become clearer!

there are sets of rules that explain these things, if you really want to take that route. Jan Van Steen or Harry Fearnley's site should point you in the right direction.


Cut first, ask questions later
[ Parent ]

Last question (4.00 / 1) (#95)
by jabber on Thu Jul 11, 2002 at 01:49:52 PM EST

In a single (A) stone surround situation, where the stone is taken off the board (by B), a) does it make sense (for A) to put a stone back in that now empty space to take away that piece of territory from B? or b) does that A stone, if placed, get taken off by B immediately?

I guess what I'm asking is this: Are stones removed upon being surrounded, or whenever they are surrounded?

[TINK5C] |"Is K5 my kapusta intellectual teddy bear?"| "Yes"
[ Parent ]

Whenever surrounded, with an exception (5.00 / 3) (#103)
by vorfeed on Thu Jul 11, 2002 at 02:37:16 PM EST

Sorry to jump in on the conversation... hope you don't mind ^_^

You mean like when this:

. . . . .
. . x . .
. x o x .
. . x . .
. . . . .

Becomes this, right?

. . . . .
. . x . .
. x . x .
. . x . .
. . . . .

In this case, o cannot replace a stone inside the x's without losing the stone. At all times, any stone without any liberties is captured. In your words, a stone is taken away whenever surrounded.

There's one exception, and that is that you may place a stone that has no liberties, if by capturing, it will gain at least one liberty.

. . . . .
o o . . .
x x o . .
. x o . .
x x o . .
o o . . .
. . . . .

Here, o may place in the center of x's stones, because then he would capture, and the board would look like

. . . . .
o o . . .
. . o . .
o . o . .
. . o . .
o o . . .
. . . . .

I hope this helps. This is one of the more confusing aspects of Go, for beginners. It took me a while to get a feel for it. In fact, when I started, a friend and I tried playing "without any suicides", so that capturing moves similar to the above were disallowed. Unfortunately for us, the game is essentially unplayable that way -_-;;

I agree with a previous poster - the way to learn the particulars of Go is to play a lot of games, either with an experienced player, or with a computer program which will count score and enforce the rules for you. Try starting on a 9x9 board, it's a great way to learn localised tactics without worrying about the higher-level strategy involved with the 13x13 and 19x19 boards. Computer Go is also dirt cheap, though a decent board and some cheap glass stones can cost you less than $40, if you decide to upgrade.

Good luck with Go!

Vorfeed's Black Metal review page
[ Parent ]

my best tip... (4.66 / 3) (#60)
by GoStone on Thu Jul 11, 2002 at 11:59:47 AM EST

...is to start playing, on a small board. 9x9 gives a great short game, especially for beginners.

It all becomes clear after a while! Do download "The Way to Go" too. It helps.

I deliberately didn't give too much away in the article. Its more fun to find out by yourself.


Cut first, ask questions later
[ Parent ]

Points for capture (5.00 / 3) (#54)
by codemonkey_uk on Thu Jul 11, 2002 at 11:45:55 AM EST

But don't forget that to capture a stone, you have to play a stone, and the stone you play may occupy a point in your territory, so when you are happy that your enemy cannot create a "living" group (cannot make two eyes) there is no point in actually playing the stones to make the capture! They will be automatically captured at the end of the game!

Thus here:

  123456789
1 o.o......
2 .oo......
3 oo.......
4 .o.......
5 xo.......
6 .o.......
7 oo.......
8 .........
9 .........
There is no point in 'o' playing stones to capture the 'x' at 1,5 - it is aready dead.
---
Thad
"The most savage controversies are those about matters as to which there is no good evidence either way." - Bertrand Russell
[ Parent ]
What it also means (5.00 / 6) (#57)
by thefirelane on Thu Jul 11, 2002 at 11:48:21 AM EST

Is that, if you opponent has a large territory, you have to invade.

You loose nothing doing this though. As long as when you put down a stone, you opponent matches it with a counter stone. Therefore, your opponent is gaining a point by having you place down the stone (if it dies in the end) but also looses a point because he plays "inside" his territory. If you die, you have lost nothing by trying. You do however, still have to make intelligent play, because if you die, you signifigantly streangthen your opponents position. Furthermore, if you make moves during your invasion that your opponent does not need to respond to, then you have effectivly given him a point each move.


---Lane

-
Prube.com: Like K5, but with less point.
[ Parent ]
Go in movies (4.87 / 8) (#30)
by dipierro on Thu Jul 11, 2002 at 11:01:39 AM EST

seen briefly in movies (Pi, A Beautiful Mind), where it tends to symbolise an esoteric intellectualism.

It's actually probably more than that. John Nash and especially Max Cohen were obsessed with the concept that everything was deterministic, that there was a mathematical structure underlying nature. And while that's technically true with Go (and perhaps with life), there are far too many possibilities to play the game from a purely mathematical standpoint. This is the reason that both John and Nash lose at Go. They aren't able to let go of the thinking and start feeling.

It's kind of like the opposite of the point of the chess game in 2001, where Hal beats Frank.



Nash's other game (4.00 / 1) (#90)
by thebrix on Thu Jul 11, 2002 at 01:37:59 PM EST

Hex is another simple and profound game.

Mazeworks Java applet (the rest of the site has many other excellently-presented Java puzzles and games)

Hexy Windows client

[ Parent ]

Great article! (3.80 / 5) (#32)
by jseverin on Thu Jul 11, 2002 at 11:10:57 AM EST

You cover the subject completely, you write well, and you keep it interesting. Thank you!

Thank you very kindly :-) (none / 0) (#61)
by GoStone on Thu Jul 11, 2002 at 12:02:13 PM EST

An easy subject to keep interesting


Cut first, ask questions later
[ Parent ]
A nice java client (3.80 / 5) (#33)
by zer0 moon on Thu Jul 11, 2002 at 11:13:57 AM EST

My brother and I play Go on a very nice looking java Go program Jago

http://www.rene-grothmann.de/jago/

it looks nice, can connect to go servers, you can direct connect with someone else, or play against a cpu GNUgo opponent, as well as some other stuff.

and ofcourse being java.. you can enjoy it on any operating system that has java.

on the bounce!
-zer0

on the bounce!
【ゼロ ムーン】

game of life (2.80 / 5) (#39)
by anon868 on Thu Jul 11, 2002 at 11:21:06 AM EST

It's interesting the similarities that Go has to the Game of Life (try searching for it in google if you don't know what I mean). It seems that Go is a much mor organic, fluid game than most. I can't wait to get home to try it out!
Open a window. No, not that one! One made from actual glass, set in an acual wall, you dork.
i never thought of that! (none / 0) (#105)
by elderogue on Thu Jul 11, 2002 at 02:43:12 PM EST

wow. i've been playing go for many months and never noticed the similarity.

maybe it would be possible to use the Life rules as a go variation. this would make fuseki rather difficult ;) but on the upside, it would explicitly punish me for making overconcentrated shapes.

yeah.
yeah!
i'm very intrigued by the possibilities now...

each player would have to start with a stable shape of some sort and build off of that. heh. and you could attack by firing gliders into enemy territory =) what fun!

anybody know if this has been tried before?


-e
[ Parent ]

A bit OT: Science fiction book (none / 0) (#114)
by Happy Monkey on Thu Jul 11, 2002 at 03:16:36 PM EST

A few years back, I read a book in which the primary game of the culture was Life. Each tile was a clockwork device, and players took turns laying down a row on their side of the board. Anyone remember reading that one?
___
Length 17, Width 3
[ Parent ]
The book was... (none / 0) (#131)
by Polverone on Thu Jul 11, 2002 at 04:15:39 PM EST

...Glory Season, by David Brin. It was a nice change to read this after the never-ever-gonna-be-resolved Uplift series.
--
It's not a just, good idea; it's the law.
[ Parent ]
Iain M. Banks (none / 0) (#134)
by KnightStalker on Thu Jul 11, 2002 at 04:20:12 PM EST

The author is probably Iain M. Banks... Player of Games maybe? I haven't read that one, just guessing based on the title.

[ Parent ]
Beginning with Go (4.57 / 7) (#45)
by lb008d on Thu Jul 11, 2002 at 11:32:24 AM EST

When my wife and I first started playing Go we started by reducing the board to 13x13 and by not thinking too hard about opening moves.  We just plunked stones down until the board got filled up. The opening moves seem really vague until you've had a chance to get a feel for the opening of a game.

Once you get more advanced at the game you can start thinking more and playing slower, but I'd suggest keeping the pace up as a beginner to keep from getting frustrated!

true too (5.00 / 2) (#53)
by GoStone on Thu Jul 11, 2002 at 11:41:46 AM EST

actually I recommend the 9x9 board for beginners. Its a good little game and doesn't take too long.

and definitely keep it moving along! Its better to play lots of games and lose, than play a few and win. You'll learn quicker that way.


Cut first, ask questions later
[ Parent ]

Thanks for renewing my interest! (4.75 / 4) (#62)
by graal on Thu Jul 11, 2002 at 12:05:32 PM EST

I've had an ongoing occasional fascination with Go for awhile now - I've read The Way To Go and played with CGoban quite a bit...then other things come along and it sort of gets the back-burner. You've renewed my interest again! A very well-written essay. I hope it soon appears alongside other "Go For Beginners" reference materials. Just in case it doesn't, I'm probably going to save it locally. Thanks again!

--
For Thou hast commanded, and so it is, that every
inordinate affection should be its own punishment.
-- St. Augustine (Confessions, i)

Job done! (none / 0) (#63)
by GoStone on Thu Jul 11, 2002 at 12:08:33 PM EST

thanks


Cut first, ask questions later
[ Parent ]
Quick plug: Cgoban and Gnugo run under Cygwin (none / 0) (#67)
by graal on Thu Jul 11, 2002 at 12:23:07 PM EST

Just wanted to let folks know that Cgoban and Gnugo will run correctly under the Cygwin X environment...just downloaded both and started up a quick 9x9 game. ...For all those other Windows folks out there.

--
For Thou hast commanded, and so it is, that every
inordinate affection should be its own punishment.
-- St. Augustine (Confessions, i)
[ Parent ]

Great, GREAT article (3.00 / 4) (#69)
by alvarete on Thu Jul 11, 2002 at 12:26:19 PM EST

Well written, cleverly quoted, and it definitely sparked my interest in the game (and I use the term loosely here). While I think that, eventually, somebody will be able to make a computer play a decent game of go, I find the nature of the game fascinating, and I'm already taking my baby steps with GNUgo.
Able to come in contact with reality upon request. Inquire within.
Chess/Go type game from Africa (3.33 / 3) (#71)
by buglord on Thu Jul 11, 2002 at 12:29:47 PM EST

A game with similarly simple rules but deep strategy is mancala, also called Awale, originating from Africa. The board consists of 12 depressions, six on each side, in which seeds are placed clockwise. The object is to capture your opponent's seed by getting a certain number of seeds in a depression. There are numerous differences in the rules depending on the region in Africa.

It's quite different from many european/asian games and seems simple at first, but there are many "standard" situations which reappear and you quickly have to think up a strategy that works well with your opponent. I played it with my g/f for a while and was surprised at the depth of the game. It has distinct opening, mid-game and end-game phases that require different playing style.

I found a playable applet (the page is in french), and another online-playable version. Oh, and some general information about it.

I'm happy so much now I know how to use a gun!
Die Technik bereit und stabil... wir wollen zurück ins Telespiel!
welle:erdball - telespiel

Oualé (none / 0) (#77)
by Chakotay on Thu Jul 11, 2002 at 12:55:24 PM EST

My girlfriend is from Burkina Faso, where they call that game Oualé, but it's the same thing. It is indeed a quite interesting game, but I find it does not have too much depth...

--
Linux like wigwam. No windows, no gates, Apache inside.

[ Parent ]
Also Omweso (none / 0) (#155)
by Eric Henry on Thu Jul 11, 2002 at 05:13:54 PM EST

I'd also like to mention another African game called Omweso. It's quite fun, and much more complex than most of the other mancala variants. For those at all interested in the mathematics behind games, there is a pretty interesting paper about Omweso here. It includes some comparisons to Go and Chess, along with the other Mancala type games.

Eric Henry

[ Parent ]

Go is interesting... (4.40 / 5) (#75)
by anon0865 on Thu Jul 11, 2002 at 12:41:42 PM EST

I have played Chess and Chinese chess from a young age (I was familiar with Chinese chess before Chess, so although I love both forms, I prefer Chinese chess). Along with the usual assortments such as pawns, horses, and rooks, you get to play with interesting pieces like the "cannon"- a rook style piece that must jump over one piece X to capture piece Y. There are also "guard" pieces such as the elephant, which only moves in certain territorial spaces. Best of all, there is a river in the middle of the board :) If you like chess, I definitely recommend that you try Chinese chess.

I tried Go a few months ago. Go is...well, interesting. When I play Go, I feel like I am running a marathon rather than a sprint. It doesn't seem to have the same momentary tension in Chess (i.e. AH!!! He's about to capture my rook!) but the tension seems to be spread cumulatively over the entire game.

I think that maybe playing Go is more like an art- you develop an aptitude after observing and playing countless games, whereas Chess is more of an analytic game. Recommended, but can be frustrating :)

Japanese Chess... (5.00 / 1) (#82)
by dasunt on Thu Jul 11, 2002 at 01:17:22 PM EST

...is known as Shogi. Its similar to 'normal' chess, but most peices tend to move 'forward', pawns capture in the same direction they move, and captured peices can be dropped back onto the board by the player who captured them. In playing it, I find that the game tends to be more offensive and quicker then chess.

winshogi is a win32 GPL'ed implimentation for those of us who use Windows. Freshmeat.net has a few implimentations that you can try, I haven't used one so I can't recommend it.

Chinese 'chess', from what I recall, has a 'moat' in the center of the board, and is designed to be a slower, more defensive game. Unfortunately, I cannot find a free windows implimentation of the game with a decent AI and GUI.

And, of course, 'normal' chess is a heck of a game. Great game for learning strategy.



[ Parent ]
Chess vs. Chinese chess. (none / 0) (#108)
by claudius on Thu Jul 11, 2002 at 02:47:01 PM EST

Chinese chess plays alot more "open" than "normal" chess in the opening.  Chess typically has rooks playing a minor role until the endgame, whereas in Chinese chess rooks and cannons (an odd cross between rooks and a king in the game checkers) are sprite and lively from the get-go.  Horses (knights) are less mobile and easier to block than their chess equivalent, the pawns playing an altogether different role: I find they don't define the game so much in Chinese chess than they do in chess.  The pieces that act somewhat like bishops (the elephants) are very weak in comparison--they cannot cross the river, and they must move in increments of two along diagonals. The generals (kings) are much weaker and more docile, unlike chess, where kings become active players in the endgame.

To me chess is more tactically oriented than Chinese chess, but I must confess I don't have as much proficiency with the latter.  And, truth be told, as a King's Gambiteer I gravitate more towards tactical chess games anyhow.

Both are fun.  Especially so when played blitz over a bottle or two of wine.

[ Parent ]

Shogi (none / 0) (#223)
by ffrinch on Fri Jul 12, 2002 at 10:27:43 AM EST

Shogi is definitely faster than Western chess, and it's easy to see why - in Western chess the number of pieces on the board decreases, causing the game to slow down. In shogi you can place pieces you have captured, so the game speeds up in the endgame.

There isn't just one type of shogi either, as I understand it - accepted variants range from 3 pieces on the board to "Grand Shogi" with hundreds on each side.

-◊-
"I learned the hard way that rock music ... is a powerful demonic force controlled by Satan." — Jack Chick
[ Parent ]
Increasing your skills at Go (5.00 / 6) (#79)
by radghast on Thu Jul 11, 2002 at 01:07:38 PM EST

After playing for a while, you might find that you seem to plateau on Go. One way to increase your skills at that point is to tackle Go problems. Working through Go problems will increase your recognition of certain types of formations, and will allow you to make headway. An excellent site for this is http://www.goproblems.com. But be warned; this could be a lifetime study!

"It remains to be seen if the human brain is powerful enough to solve the problems it has created." -- Dr. Richard Wallace
Advice from a beginner to beginners (5.00 / 11) (#80)
by IvyMike on Thu Jul 11, 2002 at 01:09:51 PM EST

I've been playing go for about three years now, on and off, and here are a few pieces of advice.

First, don't bother going out and buying a board; download the kgs client and use it offline. This is important for a few reasons, including that it makes it impossible for you to make illegal moves, it helps you score at the end of the game (which can be tricky), it records your game so you can review it, it lets you "branch" the game so you can try variations, and pieces don't scatter every which way when the cat jumps on the board. There are other suitable clients, but the kgs client is one of the most polished so it's my personal favorite. Yeah, yeah, an expensive board and pieces have a style that can't be beat, but a good computer client will help you learn faster.

Second, when you first play, especially against other people, you're likely to get bogged down in tactics. You should buy the "Graded Go Problems for Beginners" series to help you learn to calculate quickly.

Third: My favorite beginning go books are probably the "Learn to Play Go" books by Janice Kim, and "The Second Book of Go" by Richard Bozulich. Your local Barnes & Noble or Borders might even have a copy. (At least the bookstores in Boise did have the Kim books. And Boise's not exactly a Go mecca.)

Fourth: After you've played a few games, play a LOT of games. You need to build up the intuition, and the only way to do that is to play many times. And you don't even want to think too hard while doing it; play where it "seems" right. Of course, you're going to lose a lot of games this way, which is embarassing (at least to me) so I bought "The Many Faces of Go" so I could have an opponent who wouldn't tire of those antics.

I would give more advice, but I don't know anything else. Good luck, and maybe we'll play soon.



Beginning Go starting points. (4.60 / 5) (#85)
by DuncanChud on Thu Jul 11, 2002 at 01:22:18 PM EST

2 months ago a heavy marketing materials type tube came into the office. No one else knew what it was so I claimed it. As a kind of weird metaphor for their product, Trend Micro sent out complete, very upper-end-for-free flexible cloth go sets w/ nice weighty plastic stones and an instructional book and site to back it up. It may be worthwhile talking to your purchasing manager to see if you can get them to send a freebie your way. Anyway, I became instantly obsessed.

As a beginner to other beginners I'd definitely recommend the Learn To Play Go series by Janice Kim as a good starting point. The books are enjoyable to read, and lay out a progressive foundation for learning the game, complete with example problems and answers at the end of each chapter.

Also, I've found internet play to be a great way to learn. Every Go server (even the Yahoo games Go section) allows you to watch games in progress as well as play. Watching matches a level or two beyond your current competency level is a great way to learn the tricks of the trade.

Even at my extreme novice level, I can easily see how most of the computer versions of go play nothing at all like the style of humans. They are useful in learning how to attack, but tend to allow you to make good amounts of territory completely unchecked.

Anyway, great article and I stongly encourage anyone who is intrigued with Go to check it out, even if its just a quick look on Yahoo games.

The first rule of GO... (3.00 / 4) (#89)
by DuncanChud on Thu Jul 11, 2002 at 01:33:27 PM EST

Is you don't talk about GO. --Tyler Durden

Golden Rule in golden ages (none / 0) (#122)
by sye on Thu Jul 11, 2002 at 03:40:39 PM EST

I abide by this way of playing

~~~~~~~~~~~~~~~~~~~~~~~
commentary - For a better sye@K5
~~~~~~~~~~~~~~~~~~~~~~~
ripple me ~~> ~allthingsgo: gateway to Garden of Perfect Brightess in CNY/BTC/LTC/DRK
rubbing u ~~> ~procrasti: getaway to HE'LL
Hey! at least he was in a stable relationship. - procrasti
enter K5 via Blastar.in
[ Parent ]

Othello (3.33 / 3) (#91)
by nutate on Thu Jul 11, 2002 at 01:38:17 PM EST

I remember a long long time ago playing othello (the pressman board game) with a friend of mine. Later on, after hearing about go, I just assumed that othello and go were the same exact thing (perhaps my friend told me that :). Now after skirting the issue mentally for some time, this article opened up my eyes to why people seem to go crazy over go. As it turns out, othello is just a version of go, (many other rule variations can be found here.)

Wow. Now I want to head to chinatown and grab a cheap beginners set as soon as I can. Thanks for a neat article that cleared up some assumptions I had made.

Othello is more like Go-moku (5.00 / 2) (#286)
by czolgosz on Sun Jul 14, 2002 at 11:31:51 AM EST

Go-moku is a children's game that uses a go board but which doesn't have go strategy. Just get five in a row and you win.I don't recall it having capture rules like Othello, though.

It's quite fun, but lacks the depth of Go.

Incidentally, I once got a job because of Go. During the interview, I noticed the two pots of go stones in the interviewer's bookshelf and I mentioned that I played a little too, so we played a game over a (long) lunch. He was a good player, but I was having one of my good days too. I won decisively, and was hired on the spot.

I asked a very competent go-playing friend of mine once why he preferred go to chess. His answer: "Chess is too mercantile."


Why should I let the toad work squat on my life? --Larkin
[ Parent ]
Nice little story (none / 0) (#291)
by nutate on Mon Jul 15, 2002 at 11:27:38 AM EST

Like I said I was going to, I went to Chinatown and grabbed a cheap Go set at Pearl River. Such fun. Sadly I was playing in a situation where I didn't have a ruleset that dealt with some of the intricacies of capture, but we figured it out mostly. Othello is really boring in comparison.

Now to get a real set :)

[ Parent ]

You make it all worthwhile :) (none / 0) (#292)
by GoStone on Mon Jul 15, 2002 at 11:54:36 AM EST

Download "the way to go". Have fun!


Cut first, ask questions later
[ Parent ]
Oh, man. (none / 0) (#295)
by sabaki on Mon Jul 15, 2002 at 07:26:08 PM EST

Where is this place? I need a new job.



[ Parent ]
Online, quick and simple... (4.00 / 4) (#92)
by Meatbomb on Thu Jul 11, 2002 at 01:42:42 PM EST

...at www.itsyourturn.com

You only play a turn at a time, so you do need patience (and a patient opponent).

I have been playing for years, but have never had the privelege of sitting face to face with a person more experienced than myself, so I remain an informed newbie. If anyone out there would like to play me, I am Meatbomb at the above site.

_______________

Good News for Liberal Democracy!

Wow. (3.83 / 6) (#94)
by gblues on Thu Jul 11, 2002 at 01:49:38 PM EST

This is the best story I've seen posted on K5.. ever. Have you considered a career as a writer or journalist?

On the subject of Go, a friend of mine at work got me into it. I laughed out loud at the "lose your first 50 games as fast as possible" proverb, because it is so true. Starting out, you will lose. A lot.  The best way to learn is to find a good teacher who will explain your mistakes without making you feel stupid.  The next best way would be to get some books and a free or inexpensive Go computer program.

But seriously, this is one of those stories that make you feel sad that you can only vote once. ;)

Nathan
... although in retrospect, having sex to the news was probably doomed to fail from the get-go. --squinky

Hear Hear (none / 0) (#212)
by jeep on Fri Jul 12, 2002 at 05:38:49 AM EST

I second that. Fab article... really shows the beauty and power of K5.

And thanks for re-invigorating my interest in GO.


--
The FREE e-democracy Project
Promoting Free Software in Government

[ Parent ]
Go is great (3.00 / 3) (#99)
by mujo on Thu Jul 11, 2002 at 02:04:50 PM EST

I play go with at friend at work everyday at lunch and breaks while some other employees play Warcraft III or Wolfenstein.

I always think and say to the others that with the simplicity of lines and two colors of rocks go is deeper than any computer games such as those they play.

Its a great game and it helps us program afterwards, so much that our boss asked people to stop playing computer games but he always encouraged us to go.

Mindgames (none / 0) (#256)
by Steeltoe on Fri Jul 12, 2002 at 02:42:51 PM EST

Taking a break from mind-consuming programming with mind-consuming games, isn't generally such a good idea. I know from my own experiences how engrossed you can become in mind-activities. So much that you don't notice it's not really making you happy. It becomes an addict and an obsession.

A balance between physical and mental activity is best. This is just a friendly advice IMHO however.

The trick is to convince your boss that exercise during work-hours is good. :)
Explore the Art of Living

[ Parent ]

Chess Complexity and Go Complexity (5.00 / 6) (#100)
by freebird on Thu Jul 11, 2002 at 02:18:08 PM EST

Chess and Go provide one of my most often used models for different types of complexity, particularly that arising from rule-based or algorithmic systems.

Chess has a fair amount of complexity built in explicitly - there are lots of different rules and special cases for different pieces and situations, so the structure and pattern that makes the game fun develops out of this overt complexity.

Go, on the other hand, has (depending on how you count) somewhere between 2 and 5 rules. That's it, and everything develops by implication from this axiomatic foundation. The structure and pattern (and implications strong enough to be rules) develops or grows out from this simple core.

This is not to place one over the other - I just find it a useful model in many circumstances. I find many systems tend to evolve from one to the other over time, and most have elements of both in their various aspects. Some examples off the tip of my head, all of which can of course be debated:

  • perl is chess-complex, lisp and scheme are go-complex.
  • legos used to be go-complex when they had a few very general pieces, now they tend to be more chess-complex (lots of specialized pieces).
  • science tends to be a motion from chess-complexity (lots of descriptive special cases) to go-complexity (general rules that imply the special cases).
  • feudalism and hierarchical power systems are chess-complex, democracy a bit more go-complex, though this is complex (heh).
  • free-markets are go-complex, managed markets chess-complex.
And so forth. Drink enough coffee and everything starts to fit into place...

...TAGGATC...(etc)

ANKOS (1.50 / 2) (#196)
by medham on Fri Jul 12, 2002 at 02:24:43 AM EST

Is a dangerous thing when ingested alone. Remember that, grasshopper.

The real 'medham' has userid 6831.
[ Parent ]

ANKOS - SHMANKOS (3.00 / 1) (#236)
by freebird on Fri Jul 12, 2002 at 01:22:20 PM EST

What does Wolfram's book have to do with anything, other than that he mentions the word 'complexity'?

Maybe he talks about more neat stuff than I realized and I should go read his book, but honestly I got over Cellular Automata about a decade ago.

But I guess I'd rather be a Grasshopper than a Troll...

...TAGGATC...(etc)
[ Parent ]

Thank You!! (4.50 / 6) (#101)
by Empty_One on Thu Jul 11, 2002 at 02:26:38 PM EST

I've just spent the last few hours reading this article, comments, and many wonderful links you provided, and I am facinated.  I seem to recall hearing about this game a few years ago, and passing it off as a kids game, since I new nothing about it.  Man, was I wrong.  

I'm starting to get back into board games again, after burning out on computer games like everquest and quake, games where you don't have to think.  With all the strategy and learning tools for checkers, chess, and now go, how could I possibly have time for all that junk.  :)

Now, to get my girlfriend interested, so I have a human to practice against.

Again, thank you.
--
"Barney sucks! Best Buy sucks! Sony Sucks! Microsoft sucks, Bill Gates is the anti-Christ and John Ashcroft can kiss my ass!" Wil Wheaton

when playing your girlfriend... (3.25 / 4) (#195)
by Thinkit on Fri Jul 12, 2002 at 02:21:29 AM EST

Try making penis and nutsack patterns. Then "go" have sex.

[ Parent ]
Thanks! (4.00 / 1) (#275)
by Empty_One on Fri Jul 12, 2002 at 11:34:52 PM EST

Hey, that worked. Thanks for the advice, now she's exausted and sleeping, and I'm up reading kuro5hin.
--
"Barney sucks! Best Buy sucks! Sony Sucks! Microsoft sucks, Bill Gates is the anti-Christ and John Ashcroft can kiss my ass!" Wil Wheaton
[ Parent ]
good luck (3.00 / 1) (#207)
by GoStone on Fri Jul 12, 2002 at 04:44:16 AM EST

do read up articles like "The Way to Go" first. I deliberately didn't cover everything because booklets like this have already done it very well, and I was trying to provide a background and 'reason' to play first.




Cut first, ask questions later
[ Parent ]

Be careful (3.00 / 1) (#225)
by Dolohov on Fri Jul 12, 2002 at 10:54:18 AM EST

I taught my ex-girlfriend to play, and she skunked me twice in a row, first-off. (The second time I was really trying, too!)

[ Parent ]
Don't forget... (3.00 / 1) (#227)
by sabaki on Fri Jul 12, 2002 at 11:22:27 AM EST

...to let her win some games

Or, if she's stronger than you, accept your losses gracefully.



[ Parent ]
Minimax it--no more interesting than 1+2=3 (1.00 / 11) (#102)
by Thinkit on Thu Jul 11, 2002 at 02:34:54 PM EST

I worked on something like this (pente). Like chess, it's easily solvable by a computer. In the end, the only thing that may matter is who goes first--or perfect players may end up tieing every time (like tic-tac-toe).

Pente != Go (4.00 / 1) (#106)
by chipuni on Thu Jul 11, 2002 at 02:43:58 PM EST

Pente (and Go-moku) and Go may be played on the same board, with the same equipment, but they are not the same game. Pente's goal is to get five stones in a row or make five captures of pairs of stones. Go is... entirely different.
--
Perfection is not reached when nothing more can be added, but only when nothing more can be taken away.
Wisdom for short attention spans.
[ Parent ]
pente=tic-tac-toe=go=chess (1.40 / 5) (#110)
by Thinkit on Thu Jul 11, 2002 at 03:04:30 PM EST

Who cares about any of these? Like I said, it's like 1+2=3, but our brains can't wrap around the solution as easily. If we could hook up our brains directly to a fast computer, 1+2=3 is as interesting as chess--not very.

[ Parent ]
Quite the computer you have there (4.00 / 3) (#119)
by spcmanspiff on Thu Jul 11, 2002 at 03:33:10 PM EST

Assume the article is correct when it says there's about 250 potential moves per position. There are about 10^69 atoms in the universe. Suppose you can store one game position per atom. That would give you a horizon of, oh, twenty-nine or so moves before the universe ran out of atoms. I'd appreciate it if you would please stop spouting about things you know nothing about. Thanks in advance.

[ Parent ]
Oops. (Formatted version) (3.00 / 3) (#120)
by spcmanspiff on Thu Jul 11, 2002 at 03:34:35 PM EST

Assume the article is correct when it says there's about 250 potential moves per position.

There are about 10^69 atoms in the universe.

Suppose you can store one game position per atom. That would give you a horizon of, oh, twenty-nine or so moves before the universe ran out of atoms.

I'd appreciate it if you would please stop spouting about things you know nothing about. Thanks in advance.

 

[ Parent ]

finite versus infinite states (1.60 / 5) (#123)
by Thinkit on Thu Jul 11, 2002 at 03:41:35 PM EST

The point is that all these games are fundamentally no different than 1+2=3. Now a more interesting game would be one with an infinite state count. Like pente with an infinite board. Solving this would require human intelligence to give a proof by symmetry. Chess, pente, go, whatever, all have finite states--and are only interesting to stupid people who can't comprehend abstract math.

[ Parent ]
oh my (4.66 / 3) (#127)
by elderogue on Thu Jul 11, 2002 at 04:02:34 PM EST

that must suck being so smart that finite state games are no fun for you =(

how do you get any pleasure out of life? i suggest you kill off some of your brain cells, kick back, and play a few games of Go

cheers!
-e
[ Parent ]

Thanks for this comment (3.00 / 2) (#136)
by Thinkit on Thu Jul 11, 2002 at 04:31:15 PM EST

It's one of the most insightful comments on my way of thought.

[ Parent ]
It's all about you, thinkit! (1.25 / 4) (#158)
by Meatbomb on Thu Jul 11, 2002 at 05:15:54 PM EST

That's why we're all here. Just for you. Go get laid.

_______________

Good News for Liberal Democracy!

[ Parent ]
Wow, you really are pretentious (4.00 / 2) (#138)
by fluffy grue on Thu Jul 11, 2002 at 04:35:01 PM EST

Sure, there's a finite number of game states, but it's a pretty large value of "finite" - on a 15x15 board, there are 53919893334301279589334030174039261347274288845081144962207220498432 game states (2225), and that doesn't even consider points for captures. Assuming a maximum game length of 180 moves (since there's 180 stones per player), there's a maximum of 180 captures, so that brings the total number of game states up to 4313591466744102367146722413923140907781943107606491596976577639874560 (80*2225).

Just because the rules are simple doesn't mean the game is.

Also, pente is far from "infinite." Even on an infinite board, you only have a finite number of actual games - if the two players develop on opposite ends of the board, the game gets real boring real quick.
--
[ Hug Your Trikuare ]
[ Parent ]

infinte states and conscious beings (2.66 / 3) (#143)
by Thinkit on Thu Jul 11, 2002 at 04:50:13 PM EST

Realizing that an infinite game can still be solved perfectly requires human intelligence--and that is the point of using a conscious being. Any finite state game can be solved by brute force--why would a conscious being want to bother with it?

[ Parent ]
Uh, hello? (4.00 / 2) (#148)
by fluffy grue on Thu Jul 11, 2002 at 04:55:41 PM EST

There are far more states in a simple game of Go than could possibly be brute-forced with all of the energy in the universe!

And there's more to life than solving problems.

No wonder you're a solipsist. You can't understand the motivation behind anyone else's actions, and so therefore it must not exist.

Hey, reality itself has only a finite number of states. So why bother with it?
--
[ Hug Your Trikuare ]
[ Parent ]

reality is not determined (1.50 / 2) (#150)
by Thinkit on Thu Jul 11, 2002 at 04:59:01 PM EST

Reality may or may not have finite states (I think it has infinite states in order to organize the reincarnation of conscoius beings). But reality features free will and no method for winning, which makes it more interesting than a simple finite state game like go.

[ Parent ]
So? (3.00 / 1) (#152)
by fluffy grue on Thu Jul 11, 2002 at 05:02:01 PM EST

That doesn't make Go not worth doing. People do things because they want to, not because some solipsist who thinks he's the only conscious being in the universe which is really a computer simulation (and hey, if reality is a computer simulation, WHO BUILT THE COMPUTER?) thinks it's a worthless pursuit.
--
[ Hug Your Trikuare ]
[ Parent ]
Nothing to do with solipsism (2.00 / 2) (#154)
by Thinkit on Thu Jul 11, 2002 at 05:05:51 PM EST

Just think of my argument alone without regard to the author. I think we are all conscious beings in a world that is infinite. Taken together, that refutes what you assume I think.

[ Parent ]
Two flaws (4.00 / 2) (#163)
by fluffy grue on Thu Jul 11, 2002 at 05:42:32 PM EST

The universe is not infinite, and there's no special property of consciousness which gives it an infinite capability.
--
[ Hug Your Trikuare ]
[ Parent ]
infinite meaning not discrete (2.00 / 2) (#167)
by Thinkit on Thu Jul 11, 2002 at 06:03:15 PM EST

I believe the universe to be not discrete, and thus infinite in that way. The big bang/crunch still give way to a limited amount of space. Consciousness doesn't give way to infinity--it gives way to free will.

[ Parent ]
if you don't wan to bother with go... (4.00 / 2) (#203)
by florin on Fri Jul 12, 2002 at 03:19:15 AM EST

...then why bother writing all these messages? ;-)

[ Parent ]
As a mathematician... (4.66 / 3) (#185)
by kaibutsu on Thu Jul 11, 2002 at 11:32:16 PM EST

...I feel it my duty to defend my profession by stating that the Go problem is, in fact, incredibly interesting, and not only because it is unsolved. It is an open problem which has thus far been attacked using many branches of mathematics, from combinatorics to topology, and which will certainly provide some shattering new insights if we come up with anything resembling a 'simple' solution.

Yeah, sure, if we had an infinitely big, infinitely fast computer, we would have a solution. However, existence is not the end-all-be-all of a mathematical theory. Imagine how lame we'd be if we'd stopped with the existence of, say, mathematical groups. Interesting problems are often searches for a new KIND of solution to something that is already solved. For example, there was a huge search for an 'elementary' proof of the Prime Number Theorem, as the original proof relied heavily on mathematics that was outside the basic framework of number theory. In the present case, we have a problem which may be solved in the most superficial way imagineable, but which we would like to see a more interesting solution for.

-kaibutsu
[ Parent ]
infinitely big? (1.50 / 2) (#194)
by Thinkit on Fri Jul 12, 2002 at 01:58:30 AM EST

Um, what exactly do you mean by infinitely big? So it doesn't get destroyed by an infinitely big asteroid? I think under minimax, very little storage is required, and the bulk of the work is calculating which is easily parallelized. You either need an infinitely fast processor, or infinitely many processors. True about finding better (more elegant) proofs. I think a lot of work is still going on with FLT after Wiles to do this.

[ Parent ]
poor troll (4.50 / 2) (#230)
by majubma on Fri Jul 12, 2002 at 12:27:24 PM EST

Solving this would require human intelligence to give a proof by symmetry.

Nonsense, formal proofs are enumerable, so it only requires a computer to check.


--Thaddeus Q. Thaddelonium, the most crookedest octopus lawyer in the West.
[ Parent ]

Stupid people (4.00 / 2) (#249)
by ucblockhead on Fri Jul 12, 2002 at 02:16:38 PM EST

Smart people realize that the interesting thing about "solving go" is figuring out how to solve it in a reasonable timeframe.
-----------------------
This is k5. We're all tools - duxup
[ Parent ]
Not even almost (4.33 / 3) (#109)
by widoxm on Thu Jul 11, 2002 at 03:04:18 PM EST

As the author already said, mini-max'ing is not a practical solution. Not only does your search-tree expand at an obscene rate, but more importantly there is no way of scoring a particular position. In Chess you can simply score on peices taken and relative positions, and in Pente you can search for a win easily because the tree is easily pruned. But in Go the strength of a position is infinitely more abstract, and hence hard to teach a computer. The optimal strategy for Go is going to be so ridiculously long that human could win simply by going first.

[ Parent ]
computer limitation (2.00 / 3) (#125)
by Thinkit on Thu Jul 11, 2002 at 03:45:21 PM EST

This is just because Go requires one to go deeper down the search tree to do even a "best guess" analysis. Perhaps that makes it more interesting to humans and their limited brain capacity. But it's the same thing, different rules than even tic-tac-toe.

[ Parent ]
re: computer limitation (4.50 / 2) (#146)
by widoxm on Thu Jul 11, 2002 at 04:54:33 PM EST

No, it's nothing to do with depth. Mini-Max relies on the 'score' of a given configuration to decide which path to take up or down the tree. This method utterly fails with Go because no-one knows of any algorithm that can provide the score that Mini-max relies on. Minimax type methods also rely on assumptions about the opponent(s) always making the best long or short term moves, which in a game as open-ended as Go is exceptionally unlikely to happen.
Playing Go via a deterministic process such as Minimax is as futile as trying to predict next years weather, and for largely the same reasons.

[ Parent ]
min-max assuming optimal play (4.33 / 3) (#179)
by elderogue on Thu Jul 11, 2002 at 09:00:44 PM EST

the fact that minmax assumes the opponent will play optimally doesn't mean that it is useless against less-than-optimal opponents. the algorithm simply uses this information to determine its own best move. if a less-than-optimal play by its oponent defeats min-max's "strategy," then the move min-max chose wasn't really optimal. so i think (!) that unless you have a true rock-paper-scissors situation, min-max will win.

the real problem (as has been stated many times) is that the vast amount of computations required makes min-max impossible for all practical purposes.

but don't kill me if i'm wrong about all this.


-e
[ Parent ]

If it is 'so simple' (2.50 / 2) (#168)
by Xeriar on Thu Jul 11, 2002 at 06:11:27 PM EST

then do it without genetic programming or neural networks.

Hell, make a program that could do it (using a minimax algorithm) on a 9x9 - well enough that it could even beat your limited faculties, and I will believe you have an argument, and an IQ above two digits.

----
When I'm feeling blue, I start breathing again.
[ Parent ]

my IQ is infinite (2.00 / 4) (#169)
by Thinkit on Thu Jul 11, 2002 at 06:21:25 PM EST

Much like the digits of pi.

[ Parent ]
an IQ of 3.141 is not something i'd brag about ;) (3.80 / 5) (#180)
by elderogue on Thu Jul 11, 2002 at 09:03:12 PM EST

sorry. that was too easy. i really shouldn't have.


-e
[ Parent ]

You're wrong & why the universe exists... (5.00 / 2) (#112)
by freebird on Thu Jul 11, 2002 at 03:11:54 PM EST

Have you ever played go?

More to the point, have you had any experience with actual Go programs?

The fact is that the best Go programs in the world play at advanced amateur level. Period. I don't know what you think you are talking about, but it's not Go.

Having said all that, to the joy of a well-played troll I must admit, it is true that Go is probably a zero-sum game and who goes first determines who wins - in theory. In reality, since there are far too many states, and the interactions too subtle and long-reaching, it's one of those games that would require a computer the size of the galaxy or something to solve.

Hmmm...maybe that's why the universe exists. The answer isn't '42', it's all the Joseki and Opening games possible....

...TAGGATC...(etc)
[ Parent ]

cross purposes (4.50 / 2) (#128)
by GoStone on Thu Jul 11, 2002 at 04:08:46 PM EST

You are talking about a 'universal computing machine'; an abstract mathematical concept. You are correct that in that sense there is an algorithm to solve go.

I was talking about physical implementations of that machine, as I suppose you know full well.

troll on


Cut first, ask questions later
[ Parent ]

You must be the guy who collected the $million... (4.33 / 3) (#145)
by Phelan on Thu Jul 11, 2002 at 04:52:11 PM EST

for writing a master-level Go program.

What do you mean it hasn't been collected? I thought it was soooo easy? Oh yeah, I forget, it's easier to talk something up and try to sound competent than actually prove it.

But hey, don't feel bad. No one's collected the James Randi Paranormal Challenge [randi.org]prize money, either.

[ Parent ]

randi is different (1.66 / 3) (#147)
by Thinkit on Thu Jul 11, 2002 at 04:55:33 PM EST

I think Randi is doing a great service with that prize by weeding out all the crap people after money. As has been pointed out, Go is a finite state game, just with a huge amount of states. Like 16^32 or other obscene amount. I understand that it is hard to score moves unless you go to the bottom of the tree (nearly impossible). The only way I can imagine to do this is to hook up a conscious being directly up to a computer to combine intuition and computing power.

[ Parent ]
he is? (3.00 / 3) (#219)
by Phelan on Fri Jul 12, 2002 at 08:40:22 AM EST

The only way I can imagine to do this is to hook up a conscious being directly up to a computer to combine intuition and computing power.

Ah..and you think "hooking a concious being directly up to a computer" is somehow less far fetched that using precognition to psychically discern the outcome?

Interesting.

[ Parent ]

We already do this. (none / 0) (#232)
by Thinkit on Fri Jul 12, 2002 at 12:48:41 PM EST

It's just a matter of improving the interface from a QWERTY keyboard and screen.

[ Parent ]
what a piece of work. (4.33 / 3) (#250)
by Phelan on Fri Jul 12, 2002 at 02:20:23 PM EST

So, now a QWERTY keyboard and a monitor are somehow analagous to hooking up a concious brain directly to a machine?

Sorry, pal. Hooking up a brain to a machine implies that there's a direct data transfer (to and from) the machine to the brain in question. And that there's direct mental control over the machine in question. And that this would somehow magically solve the problems of the huge difference in the number of play position combinations possible in go as compared to chess.

Unless of course, you're back to the original premise: solving go with computer was easy. Implying that you could make a master-level go program with a keyboard and screen. In that case, I'm back to my original statement: The reason you haven't done so is the same reason that folks haven't claimed the Randi prize. While there are folks that may honestly believe that they are psychic, when push comes to shove, they can't produce. And, other than poorly played verbal word games, neither can you.

It's a simple concept really: If it's so easy, do it. If you can't, you've just proven it's not as easy as you think.

[ Parent ]

machine seat (1.00 / 1) (#258)
by Thinkit on Fri Jul 12, 2002 at 02:59:04 PM EST

A conscious entity would merely have to mearly have to be captured by a seat of consciousness hooked up directly to a computer.  But that doesn't guarantee this problem will be solved.  It will just increase the likelihood conscious intuition (free will) will stumble on something.

[ Parent ]
and I assume... (5.00 / 1) (#260)
by Phelan on Fri Jul 12, 2002 at 03:23:43 PM EST

capture this seat of conciousness in your spare time while you're writing the aforementioned Go master-level software?

When is the expected release date again?

[ Parent ]

Well, wait. Which is it? (5.00 / 1) (#184)
by phybre187 on Thu Jul 11, 2002 at 11:19:58 PM EST

I worked on something like this (pente). Like chess, it's easily solvable by a computer. In the end, the only thing that may matter is who goes first--or perfect players may end up tieing every time (like tic-tac-toe).

If it's so easily solvable, why can't you tell me if the game is an unfair game or a futile game? It should be a trivial matter for someone who has "worked on something like this".

[ Parent ]
in theory (2.50 / 2) (#191)
by Thinkit on Fri Jul 12, 2002 at 01:43:23 AM EST

I did short little minimax prog to show tic-tac-toe is a futile game. This is obviously quite easy and doable by hand even. I'm not sure the status of some of the others--I think most games end up being futile (at least well-designed ones do). Best guess for go is that is is unfair--isn't that why they have that handicap rule for who goes first?

[ Parent ]
Handicap rule (4.00 / 1) (#204)
by sjl on Fri Jul 12, 2002 at 03:27:08 AM EST

No, it isn't. The handicap rules are a recognition that players are of differing strengths. The handicap rules provide a way for the weaker player to take on the stronger player on a much more even basis. It doesn't unbalance the game, but it does make it more fun for both parties -- the weaker because he has a chance to beat the stronger, and the stronger, because she has to think harder to win the game.

It also means that you aren't discouraged from playing, because you won't be beaten as often as you might otherwise have been. Handicap go is an interesting study on its own.

The ultimate question is whether go, without any handicap, is fair, futile, or unfair. My instinct is to say that it's unfair, but by such a very fine margin that for all sane purposes, it can be treated as fair. There are just too many possibilities to try to figure out the "ultimate" game of go.

In the end, what matters is the enjoyment you gain from playing the game. If you have fun (in whatever sense that you define the word), it's worth playing, regardless of whether it is truly fair or not. If you don't have fun -- why are you playing?

[ Parent ]

Oh, I meant komi (3.00 / 1) (#211)
by Thinkit on Fri Jul 12, 2002 at 05:13:49 AM EST

I was reffering to the komi rule (5.5 I think) for subtracting points for going first. If one solved it, you would probably want to have a futile game to make things even.

[ Parent ]
My thought (4.00 / 1) (#284)
by phybre187 on Sun Jul 14, 2002 at 05:43:38 AM EST

The komi rule would suggest that the player that goes first has an advantage, but this doesn't necessarily make the game unfair. To be unfair, the first player must be capable of ALWAYS winning, given the correct strategy. I don't know that this is true. I only know that it's been observed that before komi was instituted, whoever went first tended to score slightly higher. This could very well have been a psychological advantage, rather than a material one. Maybe I don't know about some study of the game that shows otherwise.

Go differs from chess in that the winner is determined by a point total at the end, rather than by capturing a certain piece. There is no capturing objective in Go. In fact, excessive capturing will cause you to lose, because only vacant spaces you control are counted for points, and capturing fills spaces. This is important because a first-move advantage in chess would have a significant effect on being able to fulfill that capture objective. A chess player can sacrifice all the territory and material he wishes, so long as he mates the enemy king in the end, and he wins. Strictly speaking, to mate without unnecessarily loss is considered "better", but it won't affect the fact that you've won. Mating the king is the only way to win. So there is a clear advantage here.

In Go, there is no clear advantage. This is reinforced by the fact that komi exists. It shows that the first move only puts you up 5-ish points, which isn't exactly an unbalancing advantage. All other things being equal, this would lead to a consistent win by the first player, yes. But I think this falls under the Gambler's Ruin scenario: the player starting out with more value has the greatest chance of winning, but it's still chance. And a 5.5 point advantage is practically trivial. Komi just corrects a minor advantage that isn't itself overwhelmingly unbalancing. So IF Go is unfair, it's not because of komi or the lack of komi.

[ Parent ]
Addendum (none / 0) (#307)
by phybre187 on Thu Jul 18, 2002 at 06:29:07 AM EST

The existence of the komi rule itself isn't enought to make the game unfair as opposed to futile. However, the fact that the komi always has a half-point in it somewhere DOES make the game unfair, because the half-point makes a draw impossible. So it's a categorical game, and thus unfair.

[ Parent ]
Great article. (4.75 / 4) (#107)
by vorfeed on Thu Jul 11, 2002 at 02:45:10 PM EST

Genius article... as others have said, Hall of Fame material.

I've been playing Go for two years, now, though I stopped playing rigorously about a year ago. Your article has convinced me to start again - I dearly love the game, and maybe I can finally convince some of the people around here to play.

Thanks a lot, highest praise for this article!

Vorfeed's Black Metal review page

another funding solution? (3.50 / 2) (#117)
by Shren on Thu Jul 11, 2002 at 03:22:39 PM EST

Interesting. Since the Hall of Fame started, I see more *really* high quality articles. It's actually changed the way I vote - I'm a lot more picky.

Before the Hall of Fame, good articles and bad articles vanished into the depths of the archives at equal speed. Now, a really good story never vanishes. Will a time come when the article quality level is so high that dead tree kuro5hin becomes an economically feasible proposition?

Alternatively, you could put a higher ranking in above "front page", "Email List", and the best of the best of the best (sir) could get emailed out monthly (weekly? per article?), minus commentary, to those too busy to lurk K5, or to those who can use email but are confused by interactive web sites.

Laugh at the second if you like, but there are millions of people like this. Kuro5hin could break into a whole new market segment - and that could take a chunk out of that funding problem K5 has been having. Just like the pizza places, a little free delivery could change the face of things.

[ Parent ]

Here's a link to the Hall of Fame (4.33 / 3) (#181)
by sebpaquet on Thu Jul 11, 2002 at 09:52:38 PM EST

for those who want to have a look:

K5 Hall of Fame

----
Seb's Open Research - Pointers and thoughts on the evolution of knowledge sharing and scholarly communication.
[ Parent ]

Teaching kids/beginners (4.75 / 4) (#111)
by Meatbomb on Thu Jul 11, 2002 at 03:10:40 PM EST

This link will show you an organic step-by step process to learning go. It sounds like it works great for kids, and might be a gentle way to lure in girlfriends/family/friends etc who otherwise would be difficult to get involved.

I admit I have not used it myself, but I have a four year old that will be experimented on in a year or so.

_______________

Good News for Liberal Democracy!

Sorry, link here (4.50 / 2) (#113)
by Meatbomb on Thu Jul 11, 2002 at 03:14:22 PM EST

http://www.sentex.net/~mmcadams/teachgo/index.html learn to use the preview, moron

_______________

Good News for Liberal Democracy!

[ Parent ]
The rules of Go... (4.75 / 4) (#116)
by chipuni on Thu Jul 11, 2002 at 03:18:39 PM EST

Through these long millennia and cultural wanderings there has been little alteration to the rules. No other game can make a similar claim to longevity and stability. And for good reason. The rules of go are so simple, yet so perfect, that it cannot be tinkered with without destroying it. Like a mathematical truth, go appears to have always been there, beyond time and space. It has been conjectured that if there are sentient beings on other planets they may also be playing go.

I disagree; Chinese, Japanese, Korean, IGS (International), and ING variations on the rules all exist. Several sites link many different standard rules of Go. Other sites give more friendly comparisons among the rulesets.

Though some basic rules remain the same, enough variation exists that you should check which ruleset your opponent uses.
--
Perfection is not reached when nothing more can be added, but only when nothing more can be taken away.
Wisdom for short attention spans.

Like I said... (4.00 / 3) (#121)
by GoStone on Thu Jul 11, 2002 at 03:35:35 PM EST

...there has been little alteration to the rules. Not 'none' just 'little'. If you look at all the different rule sets they are largely different ways of saying the same thing.

To be sure you would want to establish which rules you were using beforehand, but it probably wouldn't make much difference to the actual game you ended up playing. I know there are exceptions.

Most go players would consider them all to be the same game.


Cut first, ask questions later
[ Parent ]

cannot be tinkered with without destroying it (4.00 / 2) (#126)
by elderogue on Thu Jul 11, 2002 at 03:46:37 PM EST

"The rules of go are so simple, yet so perfect, that it cannot be tinkered with without destroying it."

The Go Variants at Sensei's Library disagree with you on that one.

Or perhaps these variants DO classify as destroying it?
-e
[ Parent ]

Variants don't change strategy (4.50 / 2) (#253)
by b1t r0t on Fri Jul 12, 2002 at 02:29:54 PM EST

The thing about all the variant rules is that the strategy of where you place a stone esentially does not change with the rules variation. Even the matter of who wins the game will change by no more than a point between territory and area scoring, that being the effect of seki parity.

The only real exception is suicide-allowed variations, in which supposedly there are a very few situations that suicide moves can make a difference. I'd like to see a good article or book on the topic of suicide move tesuji in Go.

-- Indymedia: the fanfiction.net of journalism.
[ Parent ]

suicide (4.50 / 2) (#261)
by GoStone on Fri Jul 12, 2002 at 03:59:54 PM EST

As I understand it, there are only a very few peculiar cases where suicide might be a sensible idea, and I think it mostly involves variations of the super-ko rule. This is from memory. Super-ko being the modern idea that it should be illegal to repeat a board position.

I don't think there would be enough material to fill a book. I'd like to be proved wrong.

Most rule sets forbid suicide, but I've always thought that was unnecessary.


Cut first, ask questions later
[ Parent ]

suicide as ko threat (4.00 / 2) (#263)
by mattn on Fri Jul 12, 2002 at 04:44:11 PM EST

Essentially the only time suicide/no suicide makes a difference is in giving a player extra ko threats: for example, if a black group had a three-point eye, and there were white stones on both of the non-central points, white could use a suicide in the middle as a ko threat.

[ Parent ]
Also in case of some semeais (4.00 / 1) (#265)
by nusuth on Fri Jul 12, 2002 at 05:03:05 PM EST

Check here

[ Parent ]
Dead groups (3.66 / 3) (#129)
by sab39 on Thu Jul 11, 2002 at 04:08:49 PM EST

Your article led me to go (no pun intended) and eavesdrop on someone's game on KGS, and then to apt-get install cgoban and gnugo and attempt to play the computer.

Of course, it kicked my butt handily.

However, there was one aspect of playing in this way that I wasn't able to do correctly. At the end of the game, the program asked me to "select the dead groups". Since I only just barely understand the concept of a dead group, I didn't really have a clue which groups I should be selecting.

Can anybody either explain to me in simple terms how I can tell whether a group is dead (unlikely, because if it was that simple the computer could do it itself) or better yet, reassure me that the result will be the same even if I don't select any stones as "dead"?

Thanks,
Stuart.
--
"Forty-two" -- Deep Thought
"Quinze" -- Amélie

life and death (5.00 / 1) (#132)
by elderogue on Thu Jul 11, 2002 at 04:17:39 PM EST

the results will most likely NOT be the same if you don't mark dead groups.

any group of stones that can't make 2 eyes (or connect to a group than can) is dead.

read this stuff


-e
[ Parent ]

Dead groups (4.50 / 2) (#133)
by krek on Thu Jul 11, 2002 at 04:18:50 PM EST

Are those that have no chance of surviving a concerted attack.

. x . . . .
. x o o . .
. x o x x .
. x x x . .
. . . . . .

I am not an expert but I believe that even though those three o's are not surronded and have lives left, they are still dead, there is no way to save them if your opponent is paying attention.

One thing to keep in mind is that Go is a game of consensus, the game does not end untill both players agree that it is not worth playing further. Similarly, dead groups are usually decided by consensus, if a consensus cannot be reached that means the game is not yet over.

[ Parent ]
Concerted attack (4.00 / 1) (#137)
by sab39 on Thu Jul 11, 2002 at 04:33:36 PM EST

Hmm. That definition makes perfect sense but I'm still not at all confident that I could identify such situations in a game. And the computer player obviously can't either or it wouldn't need to ask me to do it for it.

It sounds to me like the ideal would be for both the computer and myself to continue making "concerted attacks" until we both feel we can't go on any further at all. Then any group remaining will be alive, simply because anything "vulnerable to concerted attack" will have been concertedly attacked. I wonder if there's a way to convince gnugo to do that...

Or perhaps I'm still not understanding well enough...

Stuart.
--
"Forty-two" -- Deep Thought
"Quinze" -- Amélie

[ Parent ]

Identifying dead groups (5.00 / 1) (#198)
by sjl on Fri Jul 12, 2002 at 02:49:37 AM EST

It's not always easy to tell what is and isn't dead. That's one of the reasons why you should play games, many times over. If you think something should die -- attack it, see how you go. If you think something is going to die, but you have a chance to save it -- try to save it.

This does run somewhat counter to the idea of leaving uncertain situations alone. If something is going to die anyway, don't force the issue -- it can be useful to you in forming threats (forcing your opponent to capture, giving you time to do something else -- eg, if there's a ko you want to take.)

I realise there's a contradiction here. It's one of those intangibles that's nearly impossible to understand. Maybe sit down at a board after the match and replay the situation, to try to understand why a given group is dead? Most high-level players will be happy to help you out in this regard.

Stuart (a different one :)

[ Parent ]

Argh! (4.00 / 1) (#202)
by sjl on Fri Jul 12, 2002 at 03:15:47 AM EST

"nearly impossible to explain [in plain text without a board]", not "nearly impossible to understand". Fingers, meet brain. Brain, meet fingers. You two need to work together in the future. (Twice in one day... sigh...)

[ Parent ]
Depends on ruleset (none / 0) (#235)
by nusuth on Fri Jul 12, 2002 at 01:09:30 PM EST

Under territory-based rules, any move into your territory is loss of one points (since your territory, not your stones, are counted), under Chinese variants it is a neutral move. Killing already dead groups may cost a lot under territory rules or may extend the game unnecessarily under Chinese rules. As soon as fate of every group of stones is decided and there is no empty space left, you should pass.

To convince gnugo, just play. If one more move of yours will convert a dead group to an alive one, gnugo will respond. Otherwise it won't respond at all. Notice that if you can change status of a group by just one move, it is neither dead nor alive yet. So you are not cheating.

[ Parent ]

I regret (none / 0) (#237)
by krek on Fri Jul 12, 2002 at 01:22:47 PM EST

using the term "concerted", a slightly poor choice of words, but not the point

You can play every day for the next 10 years and you will still have difficulty identifying dead groups, it is the nature of the game, just keep playing.

It is far more important though, in my opinion, to be able to preemptivly indentify, set up, prevent, and determine the likely winner of ladder situations. It is a bit difficult to explain here but check the net; The Net Knows Everything.

[ Parent ]
On the way to capture (5.00 / 1) (#135)
by thebrix on Thu Jul 11, 2002 at 04:29:15 PM EST

A dead group is a group of stones which is surrounded by enemy stones and can't be saved but which hasn't yet been formally captured.

The best pictorial description I've found so far is Life and death and the concept of 'eyes' (halfway down the page)

[ Parent ]

dead groups (4.00 / 2) (#139)
by GoStone on Thu Jul 11, 2002 at 04:36:02 PM EST

oh dear! This is one of the problems with computer go I mentioned. They can't reliably tell you who has won, so they often ask you to provide some help. You can use this to your advantage by clicking all his stones as dead, then you will always win :-)

Between human players it is rather simpler, depending on which exact rules you use. They all come up with much the same result, but some are easier to explain than others. Basically, if there is any doubt about whether a stone is dead, just keep playing until it obviously can be captured, or else obviously can not be captured.

A good place to learn about this is the booklet "The Way to Go" which you can download from here

I didn't want to explain all this in the article because there are plenty of resources out there that do it very well already.


Cut first, ask questions later
[ Parent ]

Which raises the question... (4.00 / 1) (#151)
by sab39 on Thu Jul 11, 2002 at 04:59:39 PM EST

Why can't they just program computer players to recognize "obviously" dead stones, then keep on playing until all the stones are "obviously" dead or alive? Why do computer players feel the need to pass (and thereby allow the game to end) if they aren't sure of the status?

And if they do already keep playing until everything's obvious, then there should be no need to redundantly ask me to remove dead stones, right? Sure, give me the option, but when I'm new at the game the computer will probably be better than me at it and I'd rather trust its judgement...
--
"Forty-two" -- Deep Thought
"Quinze" -- Amélie

[ Parent ]

Some computers do... (3.00 / 1) (#160)
by dipierro on Thu Jul 11, 2002 at 05:33:17 PM EST

There are two different scoring systems in Go. In one of the scoring systems (I think it's Japanese), you lose a point when you play a stone in your own territory, in order to remove dead stones. So by passing instead of playing you effectively gain a point. In the other scoring system (I think it's Chinese), you don't lose points for stones in your own territory, so it doesn't hurt to capture all the dead stones. Many (maybe most) computer systems use the second scoring method.

[ Parent ]
So this Yamaoka guy is saying... (4.75 / 4) (#140)
by Gord ca on Thu Jul 11, 2002 at 04:36:43 PM EST

Go is a good way to pick up girls? Sweet! That's the kewlest piece of ancient wisdom I've ever heard!

I'm from Canada. I played go in grade 3-5. I was in a gifted class at the time, a go player came to our school and held a go club. In grade 6 I moved to another school so haven't had go players to play against. Though I do think Go is more interesting and beautiful than Chess. Haven't bothered to get in on the internet go situation. This article should increase the number of players avail :)

If I'm attacking your idea, it's probably because I like it

Third Rule Clarification (4.75 / 4) (#149)
by nyri on Thu Jul 11, 2002 at 04:56:38 PM EST

The third rule provides an orderly escape. It says that after player A captures a stone in a ko, player B cannot take back immediately. He must play at least one move elsewhere first. This gives A an opportunity to destroy the ko formation. If he doesn't do so, and the ko still exists on B's subsequent turn, the roles may reverse. B may take back, forcing A to 'play away' for a turn.

This leaves multiple-ko fights in the twilight zone. Let me say the third rule in another words: Previous situation is not allowed to show up.

-- Jari Mustonen

Kolarification (5.00 / 1) (#165)
by sabaki on Thu Jul 11, 2002 at 05:58:11 PM EST

This leaves multiple-ko fights in the twilight zone. Let me say the third rule in another words: Previous situation is not allowed to show up.

This is referring, by the way, to the entire board, since the nature of a ko fight is that you have to make a threat somewhere before you can capture that one stone back. A ko, by its nature, is one stone from each that can immediately threaten to capture the other -- watch out for shapes where the opponent can simple connect... or you can't.

As mentioned, multiple kos are a special situation, but they're normally quite rare (although I had a triple ko last Tuesday) -- for the beginner, it's probably useful enough to remember "no next move take backs".

OK, I hope that was clarifying.



[ Parent ]
superko (3.00 / 1) (#233)
by nusuth on Fri Jul 12, 2002 at 12:54:45 PM EST

There is not a single rule defining ko. The one you refer to is called, IIRC, superko. Many ko rule variants allow for exact duplication of a previous board position. Also some rule sets forbid "ko like" situations as well as real kos.

[ Parent ]
Couldn't you prune the tree and solve go? (2.40 / 5) (#153)
by Thinkit on Thu Jul 11, 2002 at 05:02:57 PM EST

Isn't it possible to come up with some way to prune the minimax tree enough to completely solve go? This just takes a lot of intelligence to do. Hook up a conscious being directly to a computer and it could happen, right?

No (4.00 / 2) (#173)
by widoxm on Thu Jul 11, 2002 at 06:59:02 PM EST

You do not understand the complexity of Go. There is no optimal solution because a single unexpected move by the opponent completely changes the rest of the game, to a much greater extent than in games such as Chess. No amount of Minimaxing will work, because a single unexpected move from the opponent will screw up the rest of the tree. Brute force is not a solution here. Even if we did have computers that processed an infinite amount of moves in zero time, it would get us nowhere because Mini-max just does not work with this game.

[ Parent ]
Plain boot wrong (3.50 / 4) (#174)
by Thinkit on Thu Jul 11, 2002 at 07:00:37 PM EST

Mini-max works in EVERY finite state game, including go. Solving the tree to the bottom will ALWAYS work. Got it?

[ Parent ]
Going all the way down the tree... (4.50 / 2) (#175)
by spectecjr on Thu Jul 11, 2002 at 07:09:53 PM EST

Hey... when you get a computer that can hold a tree of that size in any kind of storage, and can process it within a few hours, can I borrow it? I promise I'll bring it back :)

[ Parent ]
storage isn't important (3.33 / 6) (#176)
by Thinkit on Thu Jul 11, 2002 at 07:17:50 PM EST

Storage isn't important in minimax--processing is the limiting factor.

[ Parent ]
stack space is storage (3.00 / 4) (#220)
by codemonkey_uk on Fri Jul 12, 2002 at 09:15:06 AM EST

But it's clear that you don't know what your talking about.
---
Thad
"The most savage controversies are those about matters as to which there is no good evidence either way." - Bertrand Russell
[ Parent ]
1000 moves == far too little (none / 0) (#289)
by leyssens on Mon Jul 15, 2002 at 05:13:47 AM EST

The problem is that it's very hard to implement a criterium for what is a good move, and what is a nonsense move. Even worse, even beginners can calculate up to 100 moves far, in some particular situations. And in order to store a go position (time-)efficiently, you need to store extra information about the groups, otherwise you have to run the grouping algorithm every time.

So, because a computer must evaluate just about any move, even after pruning the most stupid ones, there's about 100 left. Each of those can lead to an expansion of on average, say, 20 deep. So that's 100^20 boards. Pretty hard to calculate all of them, let alone store all of them, too.

Even if a program would manage to prune the number of possible moves to 20 (which is utterly impossible) and limit the average number of moves per variation to 10 (which is also a debilitating limitation), it would still be 20^10, which is 10^13. It just doesn't work that way.

[ Parent ]

Theoretical limits on depth (none / 0) (#290)
by Thinkit on Mon Jul 15, 2002 at 09:39:20 AM EST

In pure minimax, storage is linearly dependent on depth of tree.  I didn't know all of go's patterns, and it looks like the depth may exceed 2^128 or some other huge number (just have kos scattered across the board and it's like a binary system).  But some rule variants may place a move cap, right?  In that case, the breadth of the tree would still make solving it unfeasible, while the limited depth would limit storage needs.

[ Parent ]
depth (none / 0) (#299)
by codemonkey_uk on Tue Jul 16, 2002 at 06:35:22 AM EST

Even when you run out of stones, you still need to determine who won, which is basically a matter of saying if we played on, who would win? Which means a potentially infinite depth, once you realise that a game can theoretically cycle between multiple ko fights.
---
Thad
"The most savage controversies are those about matters as to which there is no good evidence either way." - Bertrand Russell
[ Parent ]
superko (none / 0) (#300)
by Thinkit on Tue Jul 16, 2002 at 11:17:15 AM EST

One, you can never run out of stones.  Two, the rule preventing board repetitions guarantees that minimax will find a solution.

[ Parent ]
In theory (none / 0) (#301)
by codemonkey_uk on Tue Jul 16, 2002 at 11:28:18 AM EST

In practice the depth of the tree can be equal to the number of configurations of a 3 bit 19x19 matrix (1.7408965065903192790718823807056e172) and viola! Stack space becomes an issue...
---
Thad
"The most savage controversies are those about matters as to which there is no good evidence either way." - Bertrand Russell
[ Parent ]
Capturing... (none / 0) (#298)
by Thinkit on Tue Jul 16, 2002 at 02:47:00 AM EST

The problem is, as I posted in rec.games.go, that captures are not limited and can greatly increase the depth of the tree (as if it wasn't wide enough already).

[ Parent ]
go position shall not be repeated (none / 0) (#303)
by codemonkey_uk on Wed Jul 17, 2002 at 08:24:46 AM EST

That is a rule. Trouble is, there are an awful lot of go positions ( 3^(19*19) )
---
Thad
"The most savage controversies are those about matters as to which there is no good evidence either way." - Bertrand Russell
[ Parent ]
reptition is not the issue (none / 0) (#306)
by Thinkit on Wed Jul 17, 2002 at 03:35:02 PM EST

Reptition of any amount in minimax is just a waste.  Now if you limit moves, you clearly have a limit to the depth of the tree and thus stack storage.

[ Parent ]
storage not important (4.00 / 1) (#244)
by ucblockhead on Fri Jul 12, 2002 at 01:57:07 PM EST

And where do you propose to store all the branches you are following?
-----------------------
This is k5. We're all tools - duxup
[ Parent ]
enumarate and use iterative deepening (3.50 / 2) (#248)
by nusuth on Fri Jul 12, 2002 at 02:12:22 PM EST

Minmax doesn't have to be a plain BFS. A move requires just 8.6 bits to be fully specified. A game of move# moves requires 8.6*move#, and that also identifies a unique board. To speed things up, you can also store board position and last move in 78 bytes :) Give me my infinite speed 16kB computer and I'll show you how to solve go.

[ Parent ]
ID-DFS (none / 0) (#270)
by jjayson on Fri Jul 12, 2002 at 07:07:22 PM EST

Rememer, you need to keep a fat hash of previously analysed boards for ID to work properly (i.e., without re-expanding too many positions visited during the last tree search). It does seem that in go, even though there is a huge branching factor greater than chess, that there is an much larger number of transpositions. Plus symetry can be used in go, where it is really useless in chess.

-j
"Even I can do poler co-ordinates and i can't even spell my own name." - nodsmasher
You better take care of me, Lord. If you don't
[ Parent ]
Combinatorial explosion (none / 0) (#243)
by ucblockhead on Fri Jul 12, 2002 at 01:56:54 PM EST

Yes, given infinite computing resources. However, in the real world, we don't have infinite computing resources, which is why chess has not been solved. Go is many times more complex than chess in terms of minimax, because each round allows more possible moves.
-----------------------
This is k5. We're all tools - duxup
[ Parent ]
Mixed techniques (5.00 / 1) (#213)
by thebrix on Fri Jul 12, 2002 at 06:11:18 AM EST

1. Minimax is used but, in 'pure' minimax, the tree rapidly becomes colossal as the number of valid (middlegame) moves is:

Chess: 30-45
Go: 200-300

(Even with chess the tree size has become a problem, because of Moore's Law allowing greater depth through quicker evaluation of nodes in the tree, and there is currently much work on pruning algorithms).

2. In Go moves are made largely by instinct; in chess they appear not to be although the mechanisms are not well understood (attempts to make chess programs which work on pattern-matching and other 'human-thought-like' processes have had poor results).

1 and 2 together make Go programming phenomenally difficult; from what I can pick up a combination of minimax and AI techniques (to cut down the tree size) seem to be commonly used ...

[ Parent ]

MTDT (5.00 / 1) (#271)
by jjayson on Fri Jul 12, 2002 at 07:13:00 PM EST

MTDT is merely a theoretical novelty that ties together many approaches into a common algorithm which has an input for how to expand the new nodes. It is not really new research, but a coalescing of current techniques. As far as I know, it is not used in any competitive system. They tend to opt for variants of the brutally micro-efficient nega-scout.

-j
"Even I can do poler co-ordinates and i can't even spell my own name." - nodsmasher
You better take care of me, Lord. If you don't
[ Parent ]
Wrong on two points (4.00 / 1) (#240)
by nusuth on Fri Jul 12, 2002 at 01:48:25 PM EST

1 - There is an optimal solution, we just can't find it. If we had the computers you are talking about, go would have been solved. You won't say exp(exp(exp(exp(exp(2))))) is a not number just because you can't calculate it, will you?

2 - Go is actually easier to minmax than tactical games such as chess because most groups are independent and can be analysed seperately. The only(!) problem is even after partitioning, there is just too many moves left to analyse.



[ Parent ]

Not really (4.00 / 1) (#245)
by ucblockhead on Fri Jul 12, 2002 at 01:59:41 PM EST

Chess is a bit easier because it is more structured, and therefore it is easier to tell a bad position from a good one. (Crucial in minimax if you can't follow the tree to the bottom, which, of course, is the case in nearly any interesting game.) This is easier in chess because bad things (getting a piece taken, getting your king in check, losing control of the center squares) are more obvious than in go.
-----------------------
This is k5. We're all tools - duxup
[ Parent ]
Yeah, bad wording (4.00 / 1) (#252)
by nusuth on Fri Jul 12, 2002 at 02:24:41 PM EST

I meant to point out there were easier aspects of go minmaxing too but went too far by claiming go is easier. I apologize.

Neurogo II and similar approaches may overcome difficulties with evaluating intermediate board positions in the future though. If that happens, minmaxing go would really be easy.

[ Parent ]

neurogo? (none / 0) (#259)
by Thinkit on Fri Jul 12, 2002 at 03:21:41 PM EST

I'm guessing that's neural networks.  Yeah, that seems like a perfect fit for something like go--neural nets even look like a go board.  I still consider that deterministic though.  Neural nets aren't very good at certainties, so they may be able to get really good at go, but not solve it.

[ Parent ]
I don't want to solve go (4.00 / 1) (#262)
by nusuth on Fri Jul 12, 2002 at 04:17:26 PM EST

And I don't think anyone else does either. We just want programs that can occasionally beat us, and nothing even comes close yet. I have been working on go programming on and off for about 6-7 years, with no results. Go is so mind-bogglingly difficult to program that one can usually prove futility of a suggested approach without even testing it. In fact, just one of my go engine designs ever left paper, proving its uselessness in its debut game...and it was playing 9x9 variant :)

If you are really obsessed with solving, 5x5 variant is easily solvable by hand. 7x7 variant should be solvable by a desktop computer but I'm not aware of any such solution. Try it, you will appreciate the game.

BTW NeuroGo II is go playing program with an interesting neural network architecture.

[ Parent ]

Board representation? (5.00 / 1) (#264)
by sab39 on Fri Jul 12, 2002 at 04:58:49 PM EST

I've been thinking about go programming since I read this article for the first time, and I'm curious about your experiences actually doing it. One of the things that occurred to me is that doing interesting things with the representation of the board in memory could be the basis of some interesting strategies.

It seems to me that a Go board isn't really so much a grid of squares as it is a network, or graph. Each square is a node, and most of them have 4 edges coming off them to adjoining squares. The directions associated with these edges make very little difference, really.

Expressing the board in this way lets you make interesting statements about the game play in terms of statements about flow through the network. For example, stones form a group if they are all directly connected in the graph. Territory is unambiguously captured by white if there is no path through the network to a black stone that doesn't involve passing through a white stone. A group is captured if there are no edges leading from it to empty space.

It seems to me that this might be an interesting way for a program to look at the board. For example, if you want to restrict your attention to a particular interesting area, you can determine that area by radiating out along the network in interesting directions. Also, pattern matching in general should be easier on the graph structure, because it's inherently non-directional and "flexible".

Perhaps this idea is obvious and every go program does it already, or perhaps it's been tried and ruled out for good reasons. But it seems like it might lend to more intelligent attacks on the problem space than the naive representation as just a two-dimensional array.

Stuart.
--
"Forty-two" -- Deep Thought
"Quinze" -- Amélie

[ Parent ]

My primary interest is automated learning (5.00 / 1) (#267)
by nusuth on Fri Jul 12, 2002 at 06:02:28 PM EST

I didn't delve too much into represntations at the very basic level. I guess it wouldn't matter much because you never spend much time on analysing primitive representations anyway. Although all strings share the same fate, reverse (stones that share the same fate are strings) is not true. A group of stones is a set of string of stone(s) which are connected to to each other in a functional way. It is crucial to identify such groups rather than just strings. A dumb example follows:

xxx..

.xx.C

A.xB.

Identity of stone at B is unimportant, but the stone at A is very important. The stone of color x at position C is alive or dead depending on color of A. Notice B would be member of the string if it is color x, while neither A nor C is. A graph representation of board would only help you to identify those 5 x's are indeed a string quickly, but won't be more helpful than a 2d representation after that level of analysis.

But representing groups of stones as a graph is useful. Each node encodes more than just location, it may encode liberty count, its territorial value, "dead as it stands/alive as it stands" information etc. If it is possible that two groups may influence each other, there should be an edge. They should also be directional; C is influenced by large string, but string isn't influenced by stone at C. During mid to late game most groups will not be connected at all, so they may be only tactically analysed (and results cached) or not analysed any further, saving considerable time. Computers are better than humans in end-game analysis and on par with experts on tseumo-go problems. If one doesn't use a graph representation for those, they are just as hard as midgame.

A 2d representation is not that useless, because you would have to encode "distance to nearest edges of board" information in the nodes anyway. Position relative to edges of the board are very important; most shapes cannot live elsewhere can survive if they are near an edge or a corner. So that information cannot be left out of pattern matching database. A graph representation would save you from considering symmetry of shapes explicitly, but not much more.

Partial pattern matching or selecting most closely resembling shape whould also be easier with graph-based templates, but again, it is better to use patterns consisting of groups definitions rather than explicit placements of stones is a better approach. The above shape (when B is empty) can be generalized as "L shaped, 3 points empty space at corner, surrounded by a string without additional enclosed liberties", all such strings are unconditionally alive if position B is occupied with the same color and unconditionally dead if B is occupied with the opposite color. The exact shape of surrounding string does not matter at all.

Anyway, there are plenty of people that can do a better job of explaining basics than me with my broken English and non-CS background. Here is a good start.. Also plenty of good links have been already posted to thread. GL.

[ Parent ]

Neural nets (3.00 / 1) (#266)
by ucblockhead on Fri Jul 12, 2002 at 05:24:51 PM EST

A neural net is apt to be lousy...on serial hardware they perform pretty poorly, your apt to have to train the damn thing for decades just to get it to learn the rules.

You could potentially use a neural net just for the piece that differentiates good and bad positions, though...that's the sort of pattern recognition neural nets are good at. It is still apt to be dog-slow, though.
-----------------------
This is k5. We're all tools - duxup
[ Parent ]

Regions aren't separate. (5.00 / 1) (#288)
by leyssens on Mon Jul 15, 2002 at 05:04:58 AM EST

Not really, until the end game.

Not really at all. Specially in current pro-level Korean games, one can easily see how each move influences the whole board situation. Some of them are currently so strong that they can interrupt a joseki (series of more-or-less fixed moves) when they feel a move on the other side of the board is bigger. Highly unstandard behaviour. Of course, everybody knows that picking the moves that influences the flow of the joseki should be done with the whole board position in mind, and preferably with the possible evolutions of the other regions of the board in mind as well.

Think about it. Each region is, e.g. 20x10 squares. Say that there's 6 of those regions, each of which heavily influences the direct neighbours. And each of which subtly influences all the non-neighbouring regions, too. Each of these regions should be calculated to get a feeling of the most likely evolution. Then, a move has to be picked that will a) generate the desired local effect and b) generate the desired global effect and c) keep the initiative to be able to influence the evolution of the other regions.

Multiply by about 300 moves, and you see that it's a bit of a nasty thing to calculate for machines. There's a lot of intuition involved in go. A typical professional go player will not be able to give a good reason why one move is slightly better than another. A typical answer will be: "It looks better..." After long, heavy calculations, it turns out the move gives an advantage of 3 points, or 2, or one (on a 361 point board).

[ Parent ]

Ok, let me clarify (none / 0) (#293)
by nusuth on Mon Jul 15, 2002 at 01:04:39 PM EST

You can partition the board, just not by giving fixed regions that are analysed seperately; partitioning is based on current stones and their relationships. You can discover a lot of regional facts which will not change thru the game unless someone plays in the neighbourhood of analysed stones. It is not about strategy, it is not holy grail of go programs. It is more like "Surrounding white group is unconditionally alive. So my stones here are dead unless I can make two eyes. That requires two moves in the region, so I have a ko threat here. And it is worth 19 points." What to do with that information is something else. Computers are capable of doing this kind of analysis; not on par with humans, but they can and they already do.

Try debug mode (or something named like that) of gnugo for a demo.

[ Parent ]

zero-sum (none / 0) (#269)
by jjayson on Fri Jul 12, 2002 at 06:58:00 PM EST

Go is a zero sum game, just like chess. Therefor there is an optimal play. Just like chess, we don't know if optimal leads to a win for white, a win for black, or a draw.

-j
"Even I can do poler co-ordinates and i can't even spell my own name." - nodsmasher
You better take care of me, Lord. If you don't
[ Parent ]
Not *that* indeterminate (5.00 / 2) (#282)
by nusuth on Sat Jul 13, 2002 at 05:15:26 AM EST

For 0 komi, it is either a black win or a draw. If for a non-pass first move, go is proved to be unfair white win game, every black player would start by passing. Then white would pass too, to avoid losing, and end the game in draw.

Also there is some reason to believe it is a black win for zero komi. Even with a 5.5 komi, black wins more games than white in the tournaments. It is unreasonable to think humans play something like an optimal game (immense variability between expert opinions show that) but human games are only data points avaliable now.

For the non-zero komi case, the komi value would be adjusted to always end an optimal game in draw. I tried to imagine where changing komi would change gameplay such that there is no such "always draw" komi value, but couldn't so far.

So all in all, Go is definetly not a white win game .It is most probably a black win game with zero komi.

[ Parent ]

No! (5.00 / 2) (#242)
by ucblockhead on Fri Jul 12, 2002 at 01:51:02 PM EST

In order to prune the tree effectively, you need to be able to classify particular board positions as "good" or "bad" without looking ahead. This is relatively easy in chess...you can do things like compare the point totals for the pieces on both sides, see who best controls the middle, stuff like that. Since go is a more holistic game, doing this is much, much harder, so not only does go have a tree with more branches, but it is much harder to create a heuristic to prune branches up without following it.

(Note that the ability to prune branches out of the tree without following them seems to be what separates the best human players from computers.)

I think perhaps you don't understand what "combinatorial explosion" is. It gobbles up more computing horsepower like mad.
-----------------------
This is k5. We're all tools - duxup
[ Parent ]

Forward pruning (4.00 / 1) (#268)
by jjayson on Fri Jul 12, 2002 at 06:55:59 PM EST

In order to prune the tree effectively, you need to be able to classify particular board positions as "good" or "bad" without looking ahead. This is relatively easy in chess...you can do things like compare the point totals for the pieces on both sides, see who best controls the middle, stuff like that.
I am unsure what you are trying to say, but whatever it is, it is a very stange way of saying things. What you really mean is that to you need a good evaluation function. This is irrelevant to pruning, since no good chess programs do forward pruning, they only do alpha-beta pruning.

-j
"Even I can do poler co-ordinates and i can't even spell my own name." - nodsmasher
You better take care of me, Lord. If you don't
[ Parent ]
Infinite for all intents and purposes (none / 0) (#309)
by glog on Mon Jul 22, 2002 at 06:36:42 PM EST

Ever wonder why there are so many chess programs and there are very few go programs? Well, because playing go is much harder, is why! Why is it harder you say? ucblockhead makes a valid point about heuristics but there is another very important one - there are much more possible moves allowed in go as compared to chess. Hence a lot more possible game outcomes. And it all becomes exponential. I am guessing all of that will take processing power that we don't have. Also, if you can solve go *completely* for the standard go board you should be able to solve it for 2x, 3x, ad infinitum. BUT *that* will mean solving the P=NP problem which is impossible for all intents and purposes.

[ Parent ]
As a Go addict, I must say... (4.00 / 1) (#171)
by artsygeek on Thu Jul 11, 2002 at 06:41:06 PM EST

As a Go addict, I must say that I wish there were more Go players where I live (Roanoke,VA). It's a game that I LOVE, but there's just so few people around here that I know that know it well enough for me to play(I'm still a bit of a beginner, so if I try teaching someone, they're getting both their "natural skill" plus some of mine through the process of teaching, and it adds up to them invariably beating me. So, I just wish there were folks that know enough of the rules to play against me and to both give me the opportunity to concentrate on play w/o having to teach. Electronic/cyber-play is fun, but it's not quite as fun as being able to kibbitz with someone face-to-face while slugging down gallons of coffee or tea or other beverages......

roanoke? (4.00 / 1) (#190)
by Kej on Fri Jul 12, 2002 at 01:08:58 AM EST

There aren't any Go clubs in Roanoke?

All I can say is that I know that there are players who meet to play at Va. Tech (where I go).  I guess at least resort, you could come down and hunt it down.  =)

[ Parent ]

This article has piqued my interest... (none / 0) (#296)
by amike on Mon Jul 15, 2002 at 11:25:13 PM EST

...and I am interested in seeing a game or two. I am also beginning school at Tech in the fall. Do you know when and where these Go players meet?

----------
In a mad world, only the mad are sane. -Akira Kurosawa
[ Parent ]
Lynchburg (4.00 / 1) (#218)
by sparkchaser on Fri Jul 12, 2002 at 08:09:34 AM EST

Heck, if you're willing to teach me then I'm willing to come over to Roanoke and play!

Rob in Lynchburg
"Radiation Shield Since 1998"
sparkchaser@adelphia.net
AOL IM: JavaJunkie2002
Visit my Collection of Collections site - A site by a collector for collectors
http://www.collectionofcollections.com

"Bacon makes it better."


[ Parent ]

Skills of a good chess/checkers/go etc. player (4.00 / 6) (#172)
by cliro on Thu Jul 11, 2002 at 06:50:20 PM EST

Even an experienced player, who knows many different strategies and techniques, relies mainly on the ability to see a large number of positions ahead. This skill is essentially the key to being good at any of these games. It is unclear to me why people see this particular ability as a sign of intelligence. Creating a mental image of future states in a very confined enviroment of rules is a skill that's rarely (if ever) practiced in real life. It doesn't involve a great deal of creativity or original thinking, but rather a machine-like combination of speed and memory. Of course, where the human mind can't analyze the situation deeply enough, a good player compensates with well learned strategies and techniques. The problem is that memorizing many different positions (even if slightly different) and their solutions is just another form of a machine-like memory. I have no idea why people think of board games so highly. Granted, humans find this kind of thinking difficult, but so is adding two 10 digit numbers. Hard, but not a true indication of intelligence.

I don't buy it...at least not all of it (5.00 / 1) (#178)
by freebird on Thu Jul 11, 2002 at 08:25:05 PM EST

Well, I do agree that being able to play any game really well is no sure sign of (any but a restricted) intelligence.

But there's a lot more to playing most games than seeing ahead. There's a quote by (I think) Dr. Lasker - when asked "How many moves ahead can you see?" He replied "One - the right move".

Probably not true, but cute.

There's alot of pattern recognition and structural reasoning involved in Go, and while certainly not defining intelligence, I think it is true that intelligence (of certain varieties) will often make for a better player.

...TAGGATC...(etc)
[ Parent ]

In my own experience... (4.66 / 3) (#182)
by phybre187 on Thu Jul 11, 2002 at 10:59:09 PM EST

...being good at Go isn't about predicting your opponent. Not the same way that chess prediction works, anyway.

The problem is that memorizing many different positions (even if slightly different) and their solutions is just another form of a machine-like memory.

I'm not comfortable with you treating Go and chess this similarly. That's how chess works, yes. Let's memorize some strategies that have been tested by players for the last 50 years, eh? That's not what Go is about. Go is about accomodating your opponent's playing style, not dominating it. Only opponents of hugely different skill levels playing without a handicap ever get into games like that. There are too many possible moves on a Go board to reliably predict your opponent's next few moves. Or even your own, many times. Even a skilled Go player, who will only regard the moves worth making cannot do that consistently (I don't know this from experience; I'm not a skilled Go player, but it's the impression I get from watching the games, and from the commentary of skilled players). Instead, Go strategy seems to deal with finding subtle ways to confront your opponent, generally losing or gaining materially the same amount, and trying to get yourself a superior position, that you can grow from. It's not supposed to be about taking advantage of the rules of the game, and that's why there aren't many. It's supposed to be about outwitting your opponent. Making him think he's gaining something just as you're getting ready to unleash your attack-sinister, which he never saw, because all your "main" moves were diversionary. Fuseki and joseki are SIMILAR to chess openings and strategies, but they're much different, too. Hell, the entire objective of joseki is an EQUAL outcome for both players. Chess strategies are meant to lead to a superior outcome for one player. Go forces you to be very clever. That's why people associate Go skill with intelligence. Only very rarely will you find yourself in positions where you'll be able to dictate the opponent's losses (forcing moves and shicho), which is the cornerstone of chess strategy.

It doesn't involve a great deal of creativity or original thinking, but rather a machine-like combination of speed and memory.

So explain to me why it's so hard to make a computer program that's good at playing Go. So far, none exist that can consistently beat neophyte players. Certainly none are going to win any championships for a long time to come.

Hard, but not a true indication of intelligence.

If that were true, humans wouldn't be so much better at it than machines.

Anyone who knows better than I do, please correct me.

[ Parent ]
Why computers can't beat humans at Go (3.00 / 2) (#239)
by cliro on Fri Jul 12, 2002 at 01:42:11 PM EST

The minimax algorithm can be used, theoretically, to win any game of Go or chess. Of course, no computer exists - and probably ever will - that can predict so many movements ahead, especially in the Go case.

Still, Deep Blue was able to defeat Kasparov at chess several times. It didn't do it using solely a minimax algorithm, but also by "learning" from mistakes and using situations it had seen before.

I stronly believe that the same method can be used with computerized Go opponents. It is only because Go isn't quite as popular as chess that a good Go machine has yet to be invented.

[ Parent ]

Popularity? wtf... (4.50 / 2) (#272)
by Spendocrat on Fri Jul 12, 2002 at 08:02:22 PM EST

That's not true at all. Are you trying to tell me that there's *no one* in Japan, Korea, or China working on CS game theory?

The problem is that the set of possible moves for go is magnitudes larger than that of chess. If - currently - a perfect chess game can't be played by a computer, how do you expect even a decent go game to be implemented programmatically?

I'm sure it'll happen, but I think you should be looking for advances in the physics side of computation before it becomes a reality.

[ Parent ]

that's true for chess, not for Go (4.00 / 2) (#201)
by florin on Fri Jul 12, 2002 at 03:01:59 AM EST

Re-read the article. It explains how in Go you have to use, besides logical thinking, some other mental tools.
Really, you can only realise this after you learn it. I had the same attitude, and i changed my mind after i learned the game.

[ Parent ]
n/s (4.00 / 2) (#222)
by majubma on Fri Jul 12, 2002 at 10:19:50 AM EST

If what you say were true, you'd think a computer would have beaten a Go master by now, no?


--Thaddeus Q. Thaddelonium, the most crookedest octopus lawyer in the West.
[ Parent ]
Such ability (4.00 / 2) (#226)
by Jman1 on Fri Jul 12, 2002 at 11:04:49 AM EST

correlates strongly with spatial and logical reasoning.  If you've ever met a computer programmer, a mathemetician, an architect, etc. you've probably met someone who is pretty good at those things.  It's not the only kind of intelligence, but it's definitely an important one.

[ Parent ]
My Point (3.33 / 3) (#228)
by cliro on Fri Jul 12, 2002 at 11:46:59 AM EST

This is exactly my point: a computer programmer and a mathematician are required to use inventive and creative thinking. The kind of thinking required in many board hames has nothing to do with any kind of intelligence.

Actually, the fact that children learn these games so quickly and can beat even moderately experienced adults serves as a proof. Surely their logic skills and abstract thinking cannot be compared to that of an adult (as all IQ tests will indicate). Yet somehow they are able to see future states of the board and are able to recognize recurring patterns in a way that eludes many adults.

I have met many good programmers that have very poor skills in this type of thinking (not to mention architects), yet they are very intelligent in any aspect of their profession.

People often confuse memory and machine-like thinking with intelligence. I guess this is just another case.

[ Parent ]

Go supplies online (3.50 / 2) (#183)
by phybre187 on Thu Jul 11, 2002 at 11:11:23 PM EST

I've never been able to find a good website for Go supplies, and there's nowhere around here (Northwest Chicagoland) to find any, either. I'd appreciate any links people think would help me. The only sites I currently know of are the ones listed here.

I'd love to know about better options.

Go supplies (none / 0) (#192)
by sabaki on Fri Jul 12, 2002 at 01:44:30 AM EST

Those are all good stores. I prefer Samarkand, but I've bought something from all of them.

What were you looking for? Or, perhaps, why don't you like those?



[ Parent ]
Heck, I'll play you... (none / 0) (#308)
by gatekeep on Thu Jul 18, 2002 at 12:08:46 PM EST

Sounds like we're in the same area. While I don't know of local stores or anything, there's an active go club in evanston, and the US Go Congress is in river forest this year. check out usgo.org for info. I'm in Wheeling, if you're ever up for a game.

[ Parent ]
Why go players always refer to chess? (4.00 / 2) (#187)
by Tezcatlipoca on Fri Jul 12, 2002 at 12:28:02 AM EST

I have not read a single article (yours is very good by the way) that talks about go without mentioning chess at least tangentialy (I can't read Chinese, Japanese or Vietnamese, places were most probably they don't care much about Western chess).

Let go stand on his own merits without, er, having  a go (ged it?) at the standing of chess, the most interesting game played by Western cultures.
---
_._ .....
... .._ _._. _._ ...
._.. ._ _ . ._.. _.__

Re: Why go players always refer to chess? (none / 0) (#193)
by sabaki on Fri Jul 12, 2002 at 01:50:59 AM EST

Hmm. Probably because we're trying to provide comparisons and contrasts in terms that Western people unfamiliar with Go can understand.

Also, I would argue that the most interesting game played by Western cultures... just not a very familiar one.



[ Parent ]
because... (4.00 / 2) (#199)
by florin on Fri Jul 12, 2002 at 02:58:38 AM EST

...chess is much more popular, and therefore offers a handy comparison for people who know nothing about Go.

[ Parent ]
For our Korean readers (4.50 / 2) (#188)
by KWillets on Fri Jul 12, 2002 at 12:33:19 AM EST

One reason perhaps that Korea is doing so well is that it has Paduk TV, the "Go Channel".  Endless games of Go, with commentary.

When I'm over there I usually switch between that and the Starcraft shows.  

Wow. (none / 0) (#229)
by Souhait on Fri Jul 12, 2002 at 12:17:41 PM EST

They have starcraft shows over in Korea? Broadcasts of the best starcraft games? I should have been Korean...

[ Parent ]
Korea and Starcraft (none / 0) (#255)
by b1t r0t on Fri Jul 12, 2002 at 02:42:34 PM EST

Maybe you should read the other site more often?

-- Indymedia: the fanfiction.net of journalism.
[ Parent ]
Go and Chinese Chess in Vietnam. (4.00 / 1) (#189)
by Tezcatlipoca on Fri Jul 12, 2002 at 12:35:36 AM EST

What you mention about Viet-Cong recruits playing go may be wishful thinking: I walked the streets of several towns in Vietnam (both North and South) and invariably the game people were playing in their house entrances, in the cofeeshops and restaurants was a variant of Chinese Chess.

It was so prevalent that it prompted me to buy a board and learn to play (after a few games one can recognize the pieces by their Chinese characters, although for us westerners, the pieces have easily recognizable western chess equivalents, with the addition of the cannon).
---
_._ .....
... .._ _._. _._ ...
._.. ._ _ . ._.. _.__

Interesting (none / 0) (#205)
by GoStone on Fri Jul 12, 2002 at 04:02:04 AM EST

I understand that by far the most popular game in China is Xiangqi, chinese chess. Same in Vietnam by the sound of things. I've heard it may be the most popular game on the planet.

But that doesn't mean there are not also lots of go players, or that go is not part of their culture.

I haven't seen seen the thesis I mentioned, but I have often heard it quoted.

I think it wasn't really referring to the recruits so much as the overall strategy of war they used.


Cut first, ask questions later
[ Parent ]

Mac OS X client (4.71 / 7) (#206)
by driph on Fri Jul 12, 2002 at 04:31:16 AM EST

First off, excellent article.. one of the best I've seen in some time, and it renewed my interest in the game. Thanks. :]

For those of you running Mac OS X and looking to play, check out Goban. A native cocoa client, it supports both solo(GNU Go) and internet play. I've checked out quite a few clients on multiple platforms tonight, and this is definitely one of the nicest.

--
Vegas isn't a liberal stronghold. It's the place where the rich and powerful gamble away their company's pension fund and strangle call girls in their hotel rooms. - Psycho Dave

Thanks for the link! (none / 0) (#238)
by MoonVine on Fri Jul 12, 2002 at 01:39:03 PM EST


I just found a twenty year old GO gameboard stashed in my father's billiards room. Too strange, and now I hear about it everywhere. I can't wait to play!


[ Parent ]
Go Anime (3.00 / 3) (#208)
by GoStone on Fri Jul 12, 2002 at 04:49:20 AM EST

a lot of people rave about the hikaru nogo anime

I forgot to put it in the article, duh




Cut first, ask questions later

You also forgot... (none / 0) (#224)
by codemonkey_uk on Fri Jul 12, 2002 at 10:50:11 AM EST

...to put a working link in your comment.
---
Thad
"The most savage controversies are those about matters as to which there is no good evidence either way." - Bertrand Russell
[ Parent ]
Brilliant. Try here... (4.50 / 2) (#247)
by GoStone on Fri Jul 12, 2002 at 02:09:55 PM EST

I wonder why I bother. I can't check the links at work because they've just installed a harsh new mistress firewall, designed by Thatcher.

These are tested at home, if there's anyone still out there. There is an English translation at: www.toriyamaworld.com/hikago/

Sensei's library says you can find the first 35 episodes using IRC, server irc.enterthegame.com, channel #elite-fansubs or #soldats.

You can also find them on alt.binaries.anime ,alt.binaries.multimedia.anime and alt.binaries.multimedia.anime.repost


Cut first, ask questions later
[ Parent ]

Thanks pal! (1.66 / 3) (#254)
by poopi on Fri Jul 12, 2002 at 02:36:32 PM EST

Now I found yet another thing which proves just how ordinary I am! As if golf, wasn't enough. Sheesh, if someone posts a story on bridge, or chess I may have to skip "Go" and go directly for the Prozac!

-----

"It's always nice to see USA set the edgy standards. First for freedom, then for the police state." - chimera

on a tangent... (3.50 / 2) (#274)
by blisspix on Fri Jul 12, 2002 at 08:56:54 PM EST

are there any versions of Mahjong available for Mac OSX? I once installed Linux on a PC just so I could play Mahjong on it. ahhh.

Go is such a great game. Thanks for the article, I'll check it out again after reading this.

Baduki (4.50 / 2) (#283)
by inode on Sat Jul 13, 2002 at 08:24:15 AM EST

No one has mentioned Baduki.

Baduki is a computer go game in the FreeBSD ports system. It routinely routs me.

The last time I played GnuGO, I routinely beat it. Does GnuGO still play in its own territory?

GnuGo (none / 0) (#285)
by b1t r0t on Sun Jul 14, 2002 at 10:06:38 AM EST

What crappy ancient version of GnuGo were you playing? 3.0 and 3.2 play quite decently.

-- Indymedia: the fanfiction.net of journalism.
[ Parent ]
Just wanted to say... (3.00 / 1) (#297)
by xaositec on Tue Jul 16, 2002 at 01:05:39 AM EST

... thanks. I don't frequent K5 quite as much as I used to. It was nice to log on and find something of this calibre posted on the front page. It certainly piqued my interest.

I recently became a practicioner of a Korean martial Art, Tang Soo Do, for anyone interested, and found the many proverbs in the article very apt and well-place.

Now I have to go find that Go board I used to have years ago. ;)



No Walls Go (none / 0) (#310)
by willelm on Mon May 26, 2003 at 08:16:53 PM EST

[white and black occupy the corners in equal proportion at the beginning of the game 2:2] I can't really call this Riemann Surface GO because I don't understand enough of the number theory. I would like to, however, because this type of game seems too complex for me to consider at present time. The way I envision this game is that the right side of the board is connected to the left. The top is connected to the bottom. Not so that the top and bottom vertices (or left and right) are actually the same thing, but so that the stones that lie on the left side of the board, are actually lying just to the right of the stones on the right side of the board (or top to bottom as the case may be), and take up their freedom. White and black occupy the corners in equal proportion at the beginning of the game and the most important part of this game is that this rule is adhered to. The reason why this game has been played on a two dimensional board is simple, gravity. But we can break this convention easily with our minds. The Riemann GO is played on a spherical board, with one layer of the board utilized `above' the other. Pictures of a (not so good, cause it's the first) game finished can be requested from willelm@ucla.edu, I hope to hear from you all. -Will
-VII
Go: Life Itself | 310 comments (294 topical, 16 editorial, 0 hidden)
Display: Sort:

kuro5hin.org

[XML]
All trademarks and copyrights on this page are owned by their respective companies. The Rest © 2000 - Present Kuro5hin.org Inc.
See our legalese page for copyright policies. Please also read our Privacy Policy.
Kuro5hin.org is powered by Free Software, including Apache, Perl, and Linux, The Scoop Engine that runs this site is freely available, under the terms of the GPL.
Need some help? Email help@kuro5hin.org.
My heart's the long stairs.

Powered by Scoop create account | help/FAQ | mission | links | search | IRC | YOU choose the stories!