Computer Cracks 5x5 Go

gustgr writes "The American Go Association is reporting that Go for the 5x5 board has been solved by the computer program MIGOS, reports the program's creator, Erik Van Der Werk, a professor at the University of Maastricht in Holland. At about a quarter of the full-board version, 5x5 go is miniscule, similar in scale to "solving" 2X2 chess. The fact that a programmer would even consider this a noteworthy challenge is itself a remarkable testament to the game's complexity. Van Der Werk's approach is described in detail in an article at the Netherlands Organization for Scientific Research (NOSR)."

Comments

October 2002

[fembots]

From the friendly article:

Subject: computer-go: 5x5 Go is solved
Date: Sun, 20 Oct 2002 15:27:04 -0100
From: Erik van der Werf
To: COMPUTER GO MAILING LIST

The fact that an editor would even consider this a newsworthy article is itself a remarkable testament to the site's simplicity.

Funny how the stock market crashed the day before 5X5 Go is solved.

Re:October 2002

[Anonymous Coward]

The doctoral thesis was defended on 27 January 2005

Maybe the results came out just now.

Re:October 2002

[Xzzy]

Sometimes I wonder if there's some secret society of geeks that scour geekly websites for neat stuff, who's only flaw is being several years old.

They make a contest of it.. whoever gets an old geek story posted on slashdot, wins the round.

It's such an obvious sport to invent, considering all the heckling slashdot editors recieve. I'm not quite prepared to accept that so many old stories get submitted out of ignorance.

Someone, somewhere, is toasting themselves to a beer right about now.

Re:October 2002

[torpor]

Funny how the stock market crashed the day [19 oct 1987] before 5X5 Go is solved [20 oct 2002].


"Time Fractally" in a Push kind of way ... ?

Re:October 2002

[Anonymous Coward]

Before trolling read the full fucking article

And as one had already stated, the thesis was defended just a few days ago...

Re:October 2002

[Anonymous Coward]

Well, the "editor" is Timmy Piquepaille, so we should lower our expectations of quality.

Re:October 2002

[onash]

from the website;The solution was found at 22 ply deep (23 for the empty board).(searching 4.472.000.000 nodes in about 4 hours on a P4 2.0Ghz)

4-hours is on a single p4 machine is just a joke.. but good point though, solving a game takes alot of time. University of Alberta (Canada) have been working on solving checkers (which is a much simpler game) for years. I think they are about half done with that. They are just using search, as checkers has low branching factor compared to Go

Van der Werf also investigated learning techniques, which are used in games such as backgammon

I belivie this is the way to be able to create a decent Go program, by learning (Reinforcement Learning, because Backgammon techniques). Brute force search gets boring, no matter how advanced it is!

Re:October 2002

[Xzzy]

Obviously their control extends deeper than any of us can imagine, for they conspired to mod my post insightful instead of the coveted +5 funny.

Re:October 2002

[shaitand]

Who told you about us? How did this leak after so long!!!!

Where did you say you lived again?

Re:October 2002

[Anonymous Coward]

I'm drinking, but it has very little to do with slashdot.

Re:October 2002

[hdparm]

Can you imagine the level of hilarity (this is the correct word?) produced tomorrow after dupe of this story appears on Slashdot front page?

Re:October 2002

[Anonymous Coward]

Maybe they should become patent examiners.

Re:October 2002

[Domini]

He-he...

Funny how it was the American Go Association who reported this...

They were always a bit slow compared to the Dutch in mathematics. ;)

I've read about this and 6x6 being solved a *long* time ago already here:

http://senseis.xmp.net/?SmallBoardGo

Re:October 2002

[zero_offset]

(searching 4.472.000.000 nodes in about 4 hours on a P4 2.0Ghz)

4-hours is on a single p4 machine is just a joke

More than 310000 nodes per second is quite a lot of work.

Re:October 2002

[donothingsuccessfull]

whoever gets an old geek story posted on slashdot, wins the round.

Go solved for 1x1 board.

Re:October 2002

[dtfinch]

I'm sure he could have put a few idle loops in there and made it take several weeks to impress you, but really, faster is better, and it's not always obvious how long something will take until you try it.

Re:October 2002

[JanneM]

Reinforcement learning type methods are not very good for problems like Go, since the credit assignment problem becomes very difficult.

Re:October 2002

[Anonymous Coward]

And in the case of proper Go [19x19 board] brute search is impossible.

Some slashdot lore.

[Eunuch]

Slashdot has a longstanding joke that with every chess article, some wide-eyed enthusiast will blurt out a quick description of Go like he's first to discover it in all the West. Speed is essential! There may be some pasty white guy who does not know the wonder that is Go.

I fully expect someone to breathlessly explain the Great Goodness that is Chess.

Chess is fun. Go is fun. People have generally heard of both. That is all.

Re:Some slashdot lore.

[Ayaress]

People on Slashdot probably fall into a different demographic, but I've found that people generally haven't heard of Go. They'll recognize a chess set by site, but they see Go and if you're lucky they assume Reversi or Othello. I was in the student lounge with a friend who was teaching me how to play Go, and somebody asked what game we were playing. When we told him, his reply was, "Go? I thought that was a card game."

Re:Some slashdot lore.

[Anonymous Coward]

I find it most amusing that they describe a 5x5 Go board as a quarter of the size of a full-sized go board... a full size go board is 20x20, so 5x5 is a sixteenth-sized go board. It's only a quarter sized if you only measure linearally, rather than spacially.

Re:Some slashdot lore.

[usefool]

When we told him, his reply was, "Go? I thought that was a card game."

I had a similar experience except that guy said "Go? I thought that was the monkey from outerspace."

Re:Some slashdot lore.

[PetWolverine]

A full-size Go board is 19x19, but you're right in your main point.

Re:Some slashdot lore.

[St. Arbirix]

Obviously I'm not posting enough.

The sig says it all.

Re:Some slashdot lore.

[IWannaBeAnAC]

But for practical purposes, its exponentially smaller ...

Re:Some slashdot lore.

[Deadstick]

It's only a quarter sized if you only measure linearally, rather than spacially.

Arm yourself against spelling flames first, Grasshopper. Only then will your math flames stand up to the foe.

rj

Re:Some slashdot lore.

[Anonymous Coward]

Chess is fun. Go is fun. People have generally heard of both.

(edit:) Neither have been solved.

That is all.

Re:Some slashdot lore.

[ChatHuant]

Chess is fun

Bah, chess...

Re:Some slashdot lore.

[rsilvergun]

What's this 'Go' you're talking about? Is it anything like chess? I typed the name into google, but all I could find was go.com, and it didn't look like a boardgame to me.... TIA.

Re:Some slashdot lore.

[iabervon]

I don't think you're all that lucky if they guess Reversi. The most casual observation is sufficient to realize that Go stone are the same color on both sides. I wouldn't be too surprised if the average American didn't know how to play Go or even recognize it, but Othello is pretty common as something people had growing up. They should really be guessing Pente, which you could play with a Go set if you wanted.

Now I want to know whether he was thinking of Go Fish or Cribbage.

Re:Some slashdot lore.

[gl4ss]

still, saying that something is equivalent to solving 2x2 board of chess where you can't really do anything is mighty stupid.

but it helps go's popularity that it is just under mainstream radar, it's still nerdy and 'cool' like rpg's and whatever...

but the complexity of go is really a waste, makes the starting(and keeping on playing) hard too, if you're playing it as a timewasting game. in competition it doesn't really matter that much if it's that much complex or not - there's still just one guy that is better than the rest and if it's settled with go or chess... it's just matter of taste(neither test 'true' intelligence on total pro level anyways).

so i present: Go is needlessly complex to start up playing on reasonable level and as consequence you're going to be having a lot of uneven matches between random players, making it quite frustrating hobby to continue, making for quite a large number of nerds that know the game and basic rules but who don't really care enough of it to really dig into it. it being quite unlikely that they could have a good match against their grandfather for example, where they could have a intresting match with chess with any random person(here it helps to NOT train chess too, that way you get more intresting matches. but to get them in go you'd need to train it yourself and find another player of the same level, for which they have the level system, which would be very improbable on a cabin trip or in a train or plane or wherever).

but if you're a nerd and read slashdot and say those things with a straight face and continue to say that you don't know what go is.. then you obviously haven't been reading.

and btw.. empires deluxe is more complex than go(and a bunch of other games, in which it is still easier to actually see if you're doing badly or not).

Re:Some slashdot lore.

[0x20]

RPGs are 'cool?' Where are YOU from, Finland or something? ...Oh.

Re:Some slashdot lore.

[OldAndSlow]

Go is needlessly complex to start up playing on reasonable level and as consequence you're going to be having a lot of uneven matches between random players

It seems you know next to nothing about go. Stronger players give weaker players a handicap. The handicap is a number of stones placed on the board before as the game begins. The number of stones is simply the difference is ranking. Beginners start at around 13 Kyu, progressing to 1 Kyu. From 1 Kyu, progress is to 1 Dan up to 9 Dan. When a 4 Dan plays a 1 Kyu, the 1 Kyu should get a 4 stone handicap. (I know about the professional Dan scale, and I'm ignoring it).

If two folks who do not know their ratings play, the handicap can be determined after the first game by dividing the winning margin by 10. Now was that hard?

A handicap game of go is a lot more interesting than a game of chess between a master and a class A player.

All this assumes that you are serious about your games and are willing to work on getting good. If all you want to do is kill time, go still has simpler rules, and you can use the set to play gomoku.

Re:Some slashdot lore.

[hunterx11]

Many chess endgames have seen solved, however: all five piece and many six piece endings IIRC.

Re:Some slashdot lore.

[cgenman]

A Go board is 19x19. This solution was for 5x5. Saying that it is a quarter of the size of the full board is incorrect, it's actually one fourteenth the size.

A Chess board is 8x8. One sixteenth of that is 2x2. It's a reasonable comparison, at least mathematically. The difference is that while Go at 5x5 is still strategic, if predictable, Chess at 2x2 is meaningless. One could say that Go happens to hold up well under that type of minimalist circumstance. One could also say that Go is just a physically larger game than Chess, and achieves a deeper degree of strategy through sheer insane volume.

But overall mathematically, it's a fair comparison.

Re:Some slashdot lore.

[hunterx11]

More people play Chess than Go. More people play Xiangqi than Go. More people in Japan play Shogi than Go. More people in Thailand and Cambodia play Makruk than Go.

Okay, so more people in Korea play Go than Janggi. Nonetheless, Go seems to have a reputation for being more cerebral and less popular. I play and enjoy Go and Chess and Shogi and Xiangqi and Makruk, but the different chesses (especially Shogi) are more exciting and immediately engaging than Go. Go is a better game to play more leisurely.

Re:Some slashdot lore.

[igrek]

I disagree completely. Completely.

I'm playing Go for long long time, and currently I'm about 1 dan. However, even when I was a novice of 20 kyu, and all these years in between, the game was always equally interesting to me. In fact, this is one of the main advantage of Go over chess. Until you're relatively good at chess, your game is very limited and there's no place for real creativity. In Go, you have planty of reasonable choices on every move, on every level.

Speaking of levels, Go has the great system of handicaps, which makes it interesting to play for players of really different strength.

Go is as complex as you want it to be. You can start playing meaningfully in 20 minutes, and you can master it all your life. It might sound like a cliche, but this is true.

Re:Some slashdot lore.

[msaulters]

"I fully expect someone to breathlessly explain the Great Goodness that is Chess."

You asked for it...

Each game of chess means there's one less variation left to be played. Each day got through means one, or two, less mistakes remain to be made.

Not much is known of early days of chess beyond a fairly vague report, that 1500 years ago two princes fought though brothers for a Hindu throne. Their mother cried, for noone really likes her offspring fighting to the death. She begged them stop the slaughter with her every breath, but sure enough one brother died.

Sad beyond belief, she told the winning son "You have caused such grief, I can't forgive this evil thing you've done." He tried to explain how things had really been, but he tried in vain; no words of his would satisfy the queen.

And so he asked the wisest men he knew the way to lessen her distress. They told him he'd be pretty certain to impress by using model soldiers on a checkered board to show it was his brother's fault.

They thus invented... Chess!

(now there's some REAL Slashdot lore for ya)

Re:Some slashdot lore.

[Deliveranc3]

But um against a newb a good go player can just clean the board regardless of handicap... It only takes one big mistake to lose....

Plus you can't really learn go from a beginner... it takes a while to even understand what's really going on... I mean grasping the eating of pieces is easy but trying to capture territory takes years...

Re:Some slashdot lore.

[Asmodai]

Of course, kyu is the rating from Japan. If using Korean rules you use gup.

Re:Some slashdot lore.

[Anonymous Coward]

beginners start between 30-kyu to 20-kyu

Re:Some slashdot lore.

[Anonymous Coward]

You need 5 in a row to win at Go. With a 4 stone head start, why not place them all in a row? If they cap one end, play on the other... You win!

Hmm... must be some other rule to it (I hope! Unless you move up a rank just for realizing that strategy... :)

Re:Some slashdot lore.

[memco]

You're thinking of Gomoku, which is very different. They use the same board and pieces, but in Go, the object is to capture as much territory of the board as possible. In the process, you may threaten, and take pieces from your opponent. Can't recommend a good place to read the rules, but I can recommend Kiseido Go Server if you want to play. They're good about teaching newbz to play, and often, players will go back through a game afterward and give advice on how to improve your game. They do have a section on how to play, but I haven't read it, I learned at school.

Re:Some slashdot lore.

[Anonymous Coward]

in 4+ years I've made at most 2 posts on slashdot.. this is my third.

awesome, awesome reference. i'm dying here! good stuff, really!

Re:Some slashdot lore.

[Anonymous Coward]

Get over it dude.

The joke will still be there in the future, but as more and more people start to play go and realise just how boring chess is, more and more articles like this one will appear, and it will be the chess people who will pipe up and post silly comments like yours. :P

I've recently converted a friend of mine... he has been playing club chess since a young age and currently plays for his university. He admits the game is more addictive than chess, but will not stop playing chess only because of all the effort over the years that would be wasted otherwise.

Re:Some slashdot lore.

[m50d]

You still need to be reasonably close though, because the handicaps only go up to 9. My brother, of similar strength to me, lost by 180 not so long ago, on a 13x13 board.

Re:Some slashdot lore.

[WillerZ]

Then your brother doesn't know when to resign. FFS there are only 169 points on a 13/13 board, so to lose by 180 means he was wiped out and played 11 more stones back into your territory which you subsequently captured.

Re:Some slashdot lore.

[91degrees]

I don't see what all the hype is about. While Go may be a decent strategy game, I don't see how it compares to Ludo.

Ludo is an ancient western board game, so sophisiticated that even the best computer implementations can only win against a human player 50% of the time.

Re:Some slashdot lore.

[0zymandias]

>>I was in the student lounge with a friend who was teaching me how to play Go, and somebody asked what game we were playing. When we told him, his reply was, "Go? I thought that was a card game."

Similar thing happended to me. When I told him what we we playing though, he left.

Re:Some slashdot lore.

[Anonymous Coward]

Linearly doesn't have much influence on the complexity, I would guess. Prolly, solving Go with raw power would be exponential in surface. So if the current need is, say, 2^(5*5), the full game would be 2^(19*19) or 2^361-2^25 = 2^336 times as difficult as this one to compute. I read somewhere that Go can't be solved with today's computing tech, citing the usual computer bigger than the universe.

Re:Some slashdot lore.

[Domini]

Then why, if both are equally fun, does Slashdot articles like this even exist? The significance of the 5x5 solution was great when it happened years ago... so why is it newsworthy now? Is it because an American finally discovered it? Does it not point to the general lack of knowledge?

Then you ask why do Go players bemoan the lack of knowledge in the west about this mathematical wonder! Perhaps because Americans are slow? (It was the American Go Association reporting this after all...) The Dutch person who did this proof did it in 2002.

I've seen this on
http://senseis.xmp.net/?SmallBoardGo

for some time now.

Re:Some slashdot lore.

[-brazil-]

> But um against a newb a good go player can just clean the board regardless of handicap...

If by "newb" you mean someone who's just been explained the rules, then yes. But any good player who plays to win in such a game is an asshole. OTOH, to anyone with even very little experience, a 9 stone handicap really is a HUGE headstart, too big to lose by one mistake, even a big one. It basically gives you tentative control over the entire board.

Re:Some slashdot lore.

[zero_offset]

Can't recommend a good place to read the rules

Requires Java, but with a relatively small investment of time, you can learn the rules fairly easily here, along with a nice assortment of problems to solve at the end of the tutorial:

http://playgo.to/interactive/

Re:Some slashdot lore.

[gl4ss]

handicap doesn't solve the fact that you still lose as you can't see the game developing. good go players can play 10 simultaneous games with those handicaps against weaker players and STILL win.

Re:Some slashdot lore.

[-kertrats-]

They stole the rankings from Virtua Fighter 4!

Re:Some slashdot lore.

[hyphz]

I think more the problem is that playing Go actually requires you to look ahead.

What's the aim of the game? To take more territory than the opponent. So, what makes an area "territory"? Basically, if an opponent's stone would inevitably be captured eventually if played there, that area is your territory.

So as a beginner it's terribly frustrating. You don't know which areas are your enemy's territory, so you waste moves playing into them. Even if the other player warns you, which most good players will do, to be really good you need to know when a given area is NOT the enemy's territory now, but will become it if they place one more stone there - and THAT'S damn hard to spot and I've yet to met a teacher who could point it out.

Worse yet, you can't count your own territory, because even if you learn the standard territory counting rules, they don't apply to you because as a novice you might screw up and fail to capture the enemy's stones before they trash your territory even though, by all rights, you should have been able to. Aaaarrgh!

Although I don't think that the "Chess vs. Go" argument is useful, I do agree with the first poster on the basic point - Go is a very steep uphill struggle when you're starting, and doesn't obviously offer any extra entertainment over any other board game, so unless you want to play competitively you're liable to drop out.

Re:Some slashdot lore.

[jgerman]

Then why, if both are equally fun, does Slashdot articles like this even exist?


Who knows. Why do you post the same thing over and over? Who knows.

Re:Some slashdot lore.

[yodhe]

Can't completely agree with you about "the deeper degree of strategy" in Go. Larger number of playable positions perhaps, but only one type type of piece. With six different pieces, Chess has its own depths.

As other posts have observed, both games are great, as is backgammon.

Re:Some slashdot lore.

[atlacatl]

You are wrong! Everyone knows it It originated in China.

Re:Some slashdot lore.

[Anonymous Coward]

I've been playing go for about two years.

1) It is super rare that any random person I meet knows anything about Go. I think Go is super awsome, so I have badgered my friends into basic knowledge of it - but someone I randomly meet who hasn't picked up on my intellectual geography? Unlikely to know anything about go.

Perhaps the /. community is the exception. Perhaps /. knows about Go only because some Go nerd is forever posting and submitting about it.

2) On the occation that I have tried to teach interested parties to play go, it seems to be difficult to convey the basic concepts. The total newb is not fun to play and is not likely to develop far enough to have much fun themselves in a short amount of time.

I know that when I was teaching myself I played against various free go computer opponents for a couple of months and read an intro book before my reaction was able to advance beyond "Huh?" Certainly if I had had a teacher that time would have decreased, but I think that "WTF is going on here?" is a common reaction for at least 10 games. 10 games of demonstration that you don't know what is going on is enough to discourage most people. Even once players have learned some tactical moves, motivating non-emergency play is difficult.

I think that chess is easier to learn here because the goal of "kill the king" is simpler than "capture the most territory" (which must include "what is territory?"). I think the learning curve of chess is shallower also because a player can loose themselves for a while in learning how the chess pieces move, and how to use them. But the actual Go rules are so simple that a player must more quickly move into higher level strategic thinking in order to develop in Go.

Personally I think that that "Huh?" is part of what makes Go neat to learn / play. The fact that Go so solidly confused me early on indicates that it struck an underdeveloped section in my brain. I was not prepared to play Go - I didn't have the cognitive tools in place. I believe that one (or the average westerner, at least) needs to wire up some neurons in order to see what is happening on the go board. I think that expanding one's mind in this fasion can only be good.

I'm sorry if people are bored by the stories about Go. I like them personally. I like to read through all the comments as well. But it's just because I'm a big fan of Go. Evidently I have company among the geeks. But, uh, if you don't like or care about Go, why are you reading these comments?

Adam

Re:Some slashdot lore.

[m50d]

He was playing someone quite a bit better than me. He was playing sensibly, just managed to get all of his stones captured. Yes, he deserved to lose, but amatuers playing chess grandmasters don't normally lose anywhere near that quickly and comprehensively.

Re:Some slashdot lore.

[Phishcast]

You people with your kyu and your gup. My car gets forty rods to the hogshead and that's the way I likes it!

Re:Some slashdot lore.

[_UnderTow_]

Go boards can be many sizes, depending on the desired length of the game. I play regularly with a guy at work, we use a 13x13 board and it takes about one lunch hour to complete a game. When we use a 19x19 board it takes almost three lunch hours.

Re:Some slashdot lore.

[Anonymous Coward]

You totally missed his point, which was hilarious. I will grant that the reference was a little obscure :-)

Re:Some slashdot lore.

[Anonymous Coward]

Ludo is an ancient western board game, so sophisiticated that even the best computer implementations can only win against a human player 50% of the time.

Exaclty. And Go is so sophisiticated that even the best computer implementations can only win against a human player 0% of the time. Get it now, smart boy?

Re:Some slashdot lore.

[91degrees]

I've been beaten by a computer simulation of Go dozens of times.

Re:Some slashdot lore.

[Anonymous Coward]

"I wouldn't be too surprised if the average American didn't know how to play Go or even recognize it, but Othello is pretty common as something people had growing up" As opposed to the average Swedish Fellow who is much more cultured than those dumb Americans. All they know is hot dogs and hamburgers. Stupid Americans. Not knowing what go is.

Re:Some slashdot lore.

[msaulters]

I wish I knew who you were. Good to know there's a few people out there who appreciate my kind of music. It's follow-ups like yours that make it worth posting.

Re:Some slashdot lore.

[Synbiosis]

Depends on your definition of 'deeper level of strategy'. They are both deep games in their own ways- Go depends more on subtle pattern recognition, while Chess is more straightforward.

Re:Some slashdot lore.

[Domini]

I guess for the same reason you read it all over and over... for it to sink in.

Re:Some slashdot lore.

[Anonymous Coward]

The parent poster was startingly ignorant, but you hardly appear to know a lot either. Beginners start at 50-30kyu in handicap (30k is the lowest "official" rating you can have, but when you've just started out, you're much worse than 30k). 13k is the rank of an average club player, not the rank you start with.

Re:Some slashdot lore.

[Anonymous Coward]

Sorry, I should have said: "Go is so sophisiticated that even the best computer implementations can only win against a human player 0% of the time, unless said human player is an idiot." Better now, smart boy?

Re:Some slashdot lore.

[barawn]

Well, you could also restrict chess by removing pieces, thus making it "non-meaningless", but still pruning the tree down to a solvable size. You start off with 16 pieces on each side, so a total of 32 pieces - naively, you could imagine cutting the pieces by 8 and the board by 2, so 4 pieces to a side, on an 4x8 board (or doing something like 6x6 rather than 8x8 - gets you close enough).

That's just as pruned as the 5x5 Go example, but still strategic.

Go's main advantage isn't in the available number of states, but measuring how "good" each configuration is.

2x2 chess?

[Anonymous Coward]

What is that? King/Queen * 2 on a 2x2 board? Double checkmate every time.

Re:2X2 Chess?

[nacturation]

But what if it's 2x2 chess with all knights?

Re:2x2 chess?

[Anonymous Coward]

There is a neat leaning variant called Quic k Chess.

Re:2X2 Chess?

[_Pablo]

In my opinion, for it to be chess, it would have to have two kings otherwise no one could win. Therefore 2x2 chess would start with checkmate and is absurd.

Re:2X2 Chess?

[tritone]

That would be one of the absurd possibilities!

Re:2X2 Chess?

[Anonymous Coward]

That 2x2 Chess is trivial is the point. If you scale the chess board down by a factor of four on each side you get a trivial game. If you scale the go board down by roughly a factor of four on each side, you get a game that was only just soluble. It just speaks to how difficult go is.

Re:2x2 chess?

[crummynz]

I call white!

Re:2X2 Chess?

[CastrTroy]

2 kings wouldn't work, it would be a constant stalemate.

Re:2X2 Chess?

[AvitarX]

Shouldn't the sig be 0x2b OR NOT 0x2b??

In anything I've used $2b would be a variable with that name.

0x2B | ~0x2B == 0xFF

$2B OR NOT $2B = $FF
Would return true or false depending on the value of $FF.

$2B = $FF should return as true (the assignment, the NOT makes it false, so the $2B would equal $FF and return as true for non-zero values (as a condition to an if).

I am not criticizing to be an asshole, I really liked the sig and it made me think, you were just a sensless victum who is forced to listen (after my girlfriend rolled her eyes and left the room).

Who wins 2x2 chess Black or White?

It starts with a checkmate, but in Chess you cannot take the king, so what happens?

Re:2X2 Chess?

[Anonymous Coward]

...of maybe it just speaks that Go's board has a substantially bigger area, to the point dividing each side by four does not make it trivial.

I'm not saying that Go is easier, just that it does not prove anything but that Chess' board is too small to reduce it so much.

Re:2X2 Chess?

[slickepott]

As can be read here some languages actually do use $ as prefix for hexadecimal.

Then there are languages who use single = for comparison too. So if you are friendly enough it might make sense. :)

Re:2X2 Chess?

[Zeinfeld]

2 kings wouldn't work, it would be a constant stalemate.

Actually no, it would be a mutual checkmate. The king can never place itself in check though so the game would start in an illegal state.

Re:2X2 Chess?

[Anonymous Coward]

2x2 chess with kings is just as absurd.

Re:2X2 Chess?

[shish]

And you need brackets somewhere or something, as something takes priority over something else; enough people've pointed out tweaks to my version that I can't even remember any more (and it's 4am, which is never a good time for thought...)

Re:2X2 Chess?

[Anonymous Coward]

White wins!!

Re:2X2 Chess?

[Anonymous Coward]

Black wins, because White is unable to move out of check on its turn.

Re:2X2 Chess?

[cbr2702]

The king can never be placed in check, but if through legal means he finds himself in check, there's no reason he can't take the other king and end the game.

Re:2X2 Chess?

[Infinityis]

I think I saw that in a movie...isn't that where the horse runs up to the edge of the cliff (or board in this case), stops just short of falling off, and the rider is unceremoniously thrown forward over mighty steed's head, over the edge of no return.

On a more serious note, that might be interesting if the chessboard had a "wraparound" feature, so if you move beyond the edge, you actually start back at the other side.

Re:2X2 Chess?

[AvitarX]

But can You take the King?

There is no rule saying you can't, in chess it is impossinle to be able to take the king.

Re:2X2 Chess?

[AvitarX]

I didn't expect to be taken seriously there,

I truly think it reads better the way you had it, I was just board and as I said, I liked it and thought too much.

Re:2x2 chess?

[hunterx11]

Actually, there was a cut down 6x6 variant of chess designed so that it would run on MANIAC.

Re:2X2 Chess?

[hunterx11]

The king can't approach the other king ever because that would place him in check. A king can never take a king.

Re:2X2 Chess?

[mmkkbb]

Shouldn't the sig be 0x2b OR NOT 0x2b??

In anything I've used $2b would be a variable with that name.

some assemblers use $ as the prefix for a hexadecimal literal. # or something is used for decimal literals. still others use $ to denote a particular register.

Re:2X2 Chess?

[Anonymous Coward]

But that's only because the game has never started from such a position..

Re:2X2 Chess?

[pluggo]

some assemblers use $ as the prefix for a hexadecimal literal.

Pascal does, too.

Re:2X2 Chess?

[Anonymous Coward]

That wrap-around feature you mentioned has been done in different styles by different enthusiasts of chess variations. Most feature a longitudinally cylindrical board (ie, pieces falling off sideways get to the opposite file on the same rank, but pieces going to the last rank don't come back to the first, otherwise queening would be impossible). From what I know about professional chess players' personal interests, Vishwanathan Anand likes this cylindrical version, while Kasparov apparently likes an outrigger version with two extra files added on to the sides.

Re:2X2 Chess?

[Anonymous Coward]

1. 2x2 Board
2. Knights, black and white
3. ??
4. Profit!!

Re:2X2 Chess?

[Anonymous Coward]

You mean you were BORED.

B O R E D.

Board is the thing you play the 2x2 chess on.

Re:2X2 Chess?

[Alsee]

there's no reason he can't take the other king and end the game

What makes you think that would end the game? No such rule! The only rules are the ones defining stalemate and the ones dealing with check/checkmate. If you *do* capture his king (and remove it from the board) then he's obviously not in check, much less in checkmate. Chuckle.

I depends on what peices you start with, but I figure the most likely outcome is that white captures black's second peice on turn 2. This leaves black not in check and with no legal moves - and there *is* a specific rule declaring that a stalemate. Another option would be white starting in checkmate and the game ending with no move at all. That would be true if for example if each player starts with a rook covering their king - you are in check and can't capture his king because that would be an illegal move into check.

It is impossible for white to win unless the starting configuration has a black king and no white king. Just a weeee bit unfair, chuckle.

-

Re:2X2 Chess?

[cbr2702]

I depends on what peices you start with, but I figure the most likely outcome is that white captures black's second peice on turn 2. This leaves black not in check and with no legal moves

How can this happen? On a 2x2 board with two kings, each king can move to any square they're not on, and as such will always be in checkmate by your definintion.

Re:2X2 Chess?

[Anonymous Coward]

Solved: Stalemate. 1/2-1/2.

Re:2X2 Chess?

[Alsee]

as such will always be in checkmate by your definintion.

No, on the first trun white was presumable in check. It is perfectly normal to escape check by simply capturing the peice causing the check. (So long as that move does not itself place you into check from some other peice.) So turn 1 white captures the black kinkg that was causing check. On turn two he captures the second black peice (if any). One of the stalemates rules then activates - black is not in chack and black has no legal moves. Game over, draw.

Chess actually has no rule against capturing a king. It is simply an move that is normally unreachable from the standard starting postion. If we change the starting position and leave all other rules intact ...well... there's still no rule against it and it's no longer unreachable.

There is also no rule stating that capturing the king wins the game. The game only ends by (1) loss by being in check with no legal move, (2) stalemate by triple board repetition, or (3) stalemate by non-check with no legal moves.

In fact someone who somehow has no king on the board could no longer be checkmated, and thus could never lose. We would either win by checkmating the other king, or at worst draw.

If you're going to make up a new reasonable game where someone can somehow capture a king then you'd probably want to add a rule that doing so wins the game. But the assuption was that no rules (other than starting setup) were changed or added.

-

That means

[Anonymous Coward]

That chess is much more complex, right?

Re:That means

[theguywhosaid]

solving a board a quarter of the size only solves one sixteenth of the problem. thats what i read.

Re:That means

[Anonymous Coward]

Can't you split the full board up into all possible 5x5 squares and solve for each?

Re:That means

[hunterx11]

Computationally, Go is far more complex. A good Go player can consistently beat the best Go computers. At the moment, the very best human players are only breaking even against the best Chess computers.

Re:That means

[Jim_Callahan]

Maybe go scales differently than chess, but i'm pretty sure the possibilities go up a lot faster than that.

GREAT SCOTT!

[agildehaus]

Marty, this story once mattered, back in 2002, when it happened.

Re:GREAT SCOTT!

[EnsilZah]

Slashdot - News for historians. Stuff that mattered?

What the hell?

[Anonymous Coward]

If someone bothered to read the linked article you would find that it was solved in October 2002. Just a tad out of date, wouldn't you say?

You would expect 20x20 to be solved by now...

Re:What the hell?

[mikael]

I heard rumours that there was a solution for "Tic-Tac-Toe" very close to being announced. The only hold up is finding a large enough
distributed network to explore all paths in real-time.

Re:What the hell?

[TapTapTheChisler]

If you had bothered to read the first comment you would have found this was posted as the first comment

Re:What the hell?

[prockcore]

I heard rumours that there was a solution for "Tic-Tac-Toe" very close to being announced.

Duh, the only solution is not to play.

Re:What the hell?

[hunterx11]

Ah yes, but can you solve Fractal Tic-Tac-Toe?

Seriously though, I wonder. I suspect that it might be rather easy to solve, but I'm to lazy to find out.

Re:What the hell?

[piltdownman84]

Old news

There was a documentary released twenty-two years ago about the trying to find a solution for Tic-Tac-Toe. Information can be found here: http://www.imdb.com/title/tt0086567/

Re:What the hell?

[space_in_your_face]

Authorization Required... Thank you google cache! -> fractal tic-tac-toe

Re:What the hell?

[hunterx11]

Thanks for pointing that out--I guess I really borked the site.

Re:What the hell?

[mikael]

If two experts are playing, every sub-game will become a draw, leading to the main grid becoming a draw.

Space Lines is much more fun.

How is this surprising?

[idono]

If computers can beat chess grandmasters and similar feats, how is this anything special?

Re:How is this surprising?

[lcrypt]

The combinations of possible Go games is much bigger.

Re:How is this surprising?

[Rakishi]

Because computers can't beat 10 year olds in Go. It's kinda amusing really.

Re:How is this surprising?

[Haydn Fenton]

Because Go is incalcuably more complex to design a computer program for, there are only two pieces, but they can go anywhere at any time (Ok, not *anywhere at any time* but pretty much), and the number of combinations there are to a simple move is much more difficult than the moves are in chess.
Or so I would assume, I've never actually tried to make a program for either, but it would appear so to anyone who has played more than a few games of each.

Re:How is this surprising?

[legLess]

If computers can beat chess grandmasters and similar feats, how is this anything special?

It's special for two reasons. For one thing, even though computer programs can beat most humans, chess itself has not been solved. That's a very different proposition.

For another thing, go is spectacularly more complex than chess. The very best go programs are competition only for weak amateurs. There's an archived NYT article that summarizes the problems reasonably well.

Although the standard go board is 19x19 intersections, the game scales, unlike chess. Things you learn on a small board are sometimes applicable to larger ones. A 5x5 is usually not interesting for human play; most consider 9x9 the minimum size for a worthwhile game. This means that a computer has been programmed to force a guaranteed win at a smaller size, and hopefully paves the way for further development and understanding.

Re:How is this surprising?

[STrinity]

In chess, there are approximately 71,000 possible board possitions after four moves, compared to over 16.7 billion in full board Go. Even on a simplified 5x5 board, there are more than 300,000 combos after four moves.

Re:How is this surprising?

[St. Arbirix]

Because computers don't have two sides of their brains to use. Chess only uses the left side of your brain, go uses both.

If this were comparable computers would be critiquing art and robots would never run into walls.

Re:How is this surprising?

[greppling]

If computers can beat chess grandmasters and similar feats, how is this anything special?

Well, on the one hand go is much harder, etc. etc., other people have explained this already. On the other hand, I don't think it surprised anyone seriously interested in computer go, that 5x5 can be done by brute force. Every serious go player can read out quickly that it is a full-board win for black. If Black's starting move is restricted, it takes a little more care to read it out, but I would be confident to read the out the correct play for both sides in a couple of minutes. Further, the essential key algorithm (position evaluation according to so-called "unconditional territory") used by Erik has long been known.

This is not to belittle Erik van der Werf's achievements. In fact to the contrary. His more interesting program is MAGOG, which plays 9x9 go. AFAIK, in the end of the game, it uses the same algorithm as MIGOS, and thus plays perfectly (given enough time, and not too complicated a position). Before that, it combines traditional goal-directed search (tactical search, "life-and-death-search") with a lot of brute force global search. Although his program is pretty young by computer go standards (ALL the top programs started to get developed in the 80's), it has shown to be a serious competitor in recent computer go tournaments.

Re:How is this surprising?

[PetWolverine]

Yay for ridiculously over-simplified neuroscience.

FYI, both games use both sides of your brain. The differences between the hemispheres are much subtler than any of the popular dichotomies, like "analytical v. synthetic" or "logic v. creativity".

Re:How is this surprising?

[Twinbee]

But couldn't one turn chess into a 'spectacularly complex' game by increasing the number of squares say... to 16*16? Or even into 3D :-)

A question. For chess to be 'solved', would a computer have to know definite answers to the best moves (something that would take a computer lots of processing time to figure out)? Or is it that some kind of 'mega-formula' is needed - one that uses relatively little processor time (but instead requiring tremendous human insight). If it's the former, then what is the term for the 'formula' type of solving.

Has even tic-tac-toe been solved using a neat formula (insert positions of pieces and x & y position, who's move it is, and out pops the answer) ?

Re:How is this surprising?

[legLess]

But couldn't one turn chess into a 'spectacularly complex' game by increasing the number of squares say... to 16*16? Or even into 3D :-)

Yes, but then it wouldn't be chess anymore. You'd need more pieces, for one thing. Go, on the other hand, requires no rule changes at all to scale to any size. There are only four rules, none of which depend on board size.

The other issue is that, regardless of search space size, go is inherently more difficult to evaluate. In chess, if the king is captured the game's over. In go, you have to count territory to determine a winner, and territory is space surrounded by stones. So to get an accurate territory count you have to know the life or death status of every stone on the board. Unless you have strong judgement this is very difficult. I'm a weak amateur myself, but I can trivially solve life/death problems that the very bext computer programs cannot.

For chess to be 'solved', would a computer have to know definite answers to the best moves...

My understanding of it is that "solved" means, "one player can always force a win." IOW, you don't need to calculate moves anymore, just look up positions on a chart. Of course, given (for go) 361! positions, that's far from trivial. Even for chess the search space is enormous.

Re:How is this surprising?

[Drako2]

For a great deal of time even the most powerful go programs were very weak compared to their human counterparts. The the fact that a simplified version of Go was solved by a computer speaks volumes for the program/programmer as well as the hardware.

Re:How is this surprising?

[cbr2702]

Perhaps you meant two kinds of pieces, but imagining a game of Go with two constantly moving pieces is making my head hurt.

Re:How is this surprising?

[Anonymous Coward]

In chess, there are approximately 71,000 possible board possitions after four moves, compared to over 16.7 billion in full board Go. Even on a simplified 5x5 board, there are more than 300,000 combos after four moves.

And current PC's (off the shelf) can perform operations at 3,000,000,000 cycles per second. That seems more than enough to loow at a measly 300,000 possible combinations.

Re:How is this surprising?

[eidechse]

The main issue is distiguishing between shapes that are "alive" and shapes that are "dead" (a shape that is alive can't be captured). This is difficult for humans to do, sometimes even for skilled players.

Due to this, it can be much more difficult to tell when a game is over in Go. All this makes for a set of problems that don't submit well to brute force analysis and are very difficult to develop other types of algorithms for.

Lastly, the above problems can/do occur in multiple areas of the board. Unlike chess where a single material or structural advantage typically ends up deciding the game, a single Go game can produce multiple smaller "battles" that in themselves won't be enough to decide the overall game.

Re:How is this surprising?

[Concerned Onlooker]

The very best go programs are competition only for weak amateurs.

OK, I'm going to pop off and shoot myself now. On Goban with the smallest board and the easiest setting I still cannot figure out how to win a game. Perhaps I should start considering that tying my own shoes is quite an achievement.

Re:How is this surprising?

[Fjornir]

So to get an accurate territory count you have to know the life or death status of every stone on the board. Unless you have strong judgement this is very difficult. I'm a weak amateur myself, but I can trivially solve life/death problems that the very bext computer programs cannot.

Your point is well made, however I do want to shill my favorite Go program for just a second. TurboGo and I very rarely disagree about the alive/dead status of a group. But I'm also one of the weakest players on the planet.

Re:How is this surprising?

[legLess]

It sounds to me like you need to read more about the game. For one thing, understand the handicap system. A stronger player (in this case the computer) should give a weaker player a number of handicap stones to compensate. This isn't a computer thing -- go players have been doing it for centuries, and it's one of the best things about the game.

Play Goban (or, more accurately, GNU go, which is what Goban uses) on a 9x9 board and have it give you 5 stones. Concentrate on keeping your groups alive. If 5 isn't enough, increase it. There's no shame in a handicap, only in not improving it over time.

More importantly, find another human. People all over play the game, and it's much more enjoyable to play with a friend than a machine. Get online and play on one of the go servers. Got questions? Visit Sensei's Library.

Re:How is this surprising?

[Anonymous Coward]

Every serious go player can read out quickly that it is a full-board win for black. If Black's starting move is restricted, it takes a little more care to read it out, but I would be confident to read the out the correct play for both sides in a couple of minutes.

Bull. Shit.

Cho Chikun himself couldn't, and neither can you.

2002?

[porcupine8]

What is this, Classic Slashdot? Next do we get a story on the impending end of the dot-com bubble?

Re:2002?

[Tablizer]

You mean my petfood.com stock is going to be worthless? I sunk my life savings into that. Go OS/2!

Re:2002?

[MillionthMonkey]

And I had just reprogrammed all my security algorithms to use Go instead of chess! Guess I'll have to convert back to chess, now that Go is "broken".

Re:2002?

[Anonymous Coward]

All your base are belong to old stories.

The future called

[Anonymous Coward]

It said 6x6 go is solved.

Re:The future called

[bcmm]

IIRC, go doesn't work well on even-number sized boards. I can't remember why though...
Can someone fill me in on this?

Re:The future called

[c=sixty4]

On an even-number sized board, it's very hard to do something against an opponent that simply mirrors your moves.

2X2 Chess?

[tritone]

Go scales downwards in a logical way, but 2X2 chess is either absurd or trivial depending on what pieces you decide to place there. The "equivalent" chess problem is probably more along the lines of 4x4 or 5x5.

In Other News

[froodiantherapy]

Sony has released a new devixe, tentatively dubbed the "CD Burner," capable of burning the first second of any of your music CDs! Programmers hope some day to move to the entire first track.

Re:In Other News

[Anonymous Coward]

now that one was really nice and funny in contrast to some other comments moderated as funny

thanks

Size?

[Anonymous Coward]

5x5 is 1/4 the size of 19x19??? More like 1/14th.

Re:Size?

[Ayaress]

It's 20x20. 19 squares, but Go is played on the vertecies, not the tiles, so it's 20x20.

Re:Size?

[Doctor Ian]

No, 18 by 18 squares, the game is played on the vertices which is 19 by 19. There's a centre vertex, see?

Re:Size?

[wmshub]

Uh, no.

It's 19x19. There are 18 squares on a side when you look at the board, but as you point out, the stones are placed on the vertices, so the playable positions form a 19x19 grid.

Re:Size?

[cameldrv]

You've never played go. There are 19x19 intersections.

Re:Size?

[PetWolverine]

No, it's 19x19. If you're counting squares instead of vertices it's 18x18, but that wouldn't make sense, since, as you say, it's played on the vertices.

Re:Size?

[Ayaress]

Yeah, I checked after the replies, you're right. I just assumed the dozen posts that said 20x20 were right without bothering to look it up. I suck at the game, even worse than I do with chess, so I never pay attention to it anymore.

Re:Size?

[teknomage1]

I think your math is faulty, in terms of board area 5x5 is 17% of the board, while 1/14 would be closer to 7%, and anyway as it's probably game theory trees 5x5 is likely a drop in bucket.

Re:Size?

[smoondog]

IIRC, traditionally computer approaches to solving Go have used a 10x10 board. Maybe that is what the poster was thinking about.

Re:Size?

[Dogun]

My god you're a dumbass.

Re:Size?

[Anonymous Coward]

(5x5)/(19x19)=0.06925... ~ 7% What was your point again?

Re:Size?

[teknomage1]

Damn it, guess my point was that I can't multiply...

Re:Size?

[Anonymous Coward]

I believe it is a mistake to automatically give members with high karma an +2 rating.
Clearly, we can't expect intelligence from all of them. I'm disappointed that this appeared at my browsing threshold.

Re:Size?

[lakeland]

And if you want to be really pedantic, there aren't 18x18 squares either since they are rectangles. At least under the japanese conventions, each 'square' is 1/8 longer than it is wide. A fun little question is, how many squares are there on a go board?

Re:Size?

[mlyle]

(5*5)/(19*19) .0692520775

I think your math is faulty, in terms of board area 5x5 is 17% of the board, while 1/14 would be closer to 7%

Looks pretty close to 7% to me.

Re:Size?

[Anonymous Coward]

Good luck on pushing a 5x5 goboard through a slit 1/14 of the width of a 19x19 goboard!

Re:Size?

[PetWolverine]

90, I think...

Each one has to be 8x9, if the specs you give are right. So along one side there are 18-8=10 squares, along the other side 18-9=9.

Re:Size?

[Anonymous Coward]

If you're going to compute a solution, it will be a first order solution (5/19, not 25/361), since you can just rotate/flip your solution on the square board by 45 deg, 90 deg or 135 deg. Why waste all those computations?

Re:Size?

[lakeland]

Sounds right. I might have got the ratio wrong, but obviously the technique is the same

Re:Size?

[cbr2702]

Do you count the intersections when you play? 1...2...3...4.........359...360...361

Re:Size?

[Anonymous Coward]

ust turn off the karmo boost in your options.

which moron were you referring to? Looking at they're post history, the grandparent actually knows what he's talking about in every other post he's made lately, and most are at least +3. Only one besides this one is 0, and no -1s, and that one wasn't fair. the parent has only two that are over his karmo boost, and both of them have overrated and troll points too. he also has several troll and flamebait posts and the rest all being unmoderated, but posted late in topics that don't get much moderation anymore, and all three that i clicked were blatant trolls

Re:Size?

[Anonymous Coward]

A fun little question is, how many squares are there on a go board?

Fourty-two of course. It's the answer to Life, the Universe, and Everyhting. Duh.

Re:Size?

[Alsee]

90, I think...

Your logic was good as far as it went, but I think you missed :)
Take another stab at it before you give up decode my answer:
Avargl guerr. Lbh zvffrq gur guerr qbhoyr-fvmrq fdhnerf.

-

Re:Size?

[Anonymous Coward]

Avargl guerr. Lbh zvffrq gur guerr qbhoyr-fvmrq fdhnerf.

Actually you are both wrong since the ratio of the lengths is incorrect. The correct ratio is 13:12 and hence there are

(19 - 13) * (19 - 12) = 42

squares in the goban.

Re:Size?

[p3d0]

19*19=361

5*5=25

361/25=14.44

QED

Re:Size?

[Alsee]

Actually you are both wrong since the ratio of the lengths is incorrect.

Is so then it was Lakeland who was wrong. PetWolverine explicitly said his calculations were under the assumption "if the specs you give are right", and my calculations were commenting on his calculations. However I just spotted a second error in his calculations which I blindly carried into my own. But I'll comment on that in a reply to PetWolverine.

-

Re:Size?

[Alsee]

Whoops, I spotted a second error in your calculations which I had carried into my calculation in my other reply to you. So my other reply has the wrong answer :(

The correct answer (I hope!):
Vg fubhyq or (AVARGRRA-avar) gvzrf (AVARGRRA-rvtug) rdhnyf bar uhaqerq naq gra, cyhf gur guerr qbhoyr fvmr fdhnerf. Svany gbgny bar uhaqerq naq guvegrra.

Decoding link.

-

Go...

[BicycloHexane]

The way that chess games work is they check n ammount of moves into the future. With each iteration into the next move it splits off into a massive tree of moves. As an example, the first iteration has 10 potential moves, the next has 100 and the next has 1,000 With Go as an example there may be 100 potential moves on the first iteration and then 10,000 and then 10,000,000 The number of potential moves grows way faster then in chess.

Re:Go...

[Sir_Real]

An initial dig brings up terms like "EXPTIME-complete" which doesn't match anything I remember from my undergrad algo class. Apparently, there is a rule modification that makes EXPTIME-complete games EXPSPACE-complete. This makes even less sense to me. Explanations in lay speak are appreciated.

Re:Go...

[Dogun]

I would also like to point out the increased computational challenge for RANKING a move.

A Go player has a significantly harder time judging whether groups of pieces are alive or dead than a chess player has deciding if he has killed a queen or not.

Similarly, Go is very much about more abstract qualities like territory and influence, thickness and lightness of play, good shape and bad. Although similarly abstract concepts exist in chess, my understanding is that at least in chess ai's aimed more at defeating the average player, these concepts don't even need to be explored. Those crazy machines they use to play against grandmasters are another story, I imagine.

I ramble. But suffice it to say the problem isn't entirely the exponentiality. There are significant challenges unrelated to alpha-beta pruning the search space before picking a decent move.

Re:Go...

[daveo0331]

That explains why it would be more challenging to program an AI to play Go, but it doesn't have anything to do with solving the game. Things like territory, influence, etc. are just heuristics that are used by humans (or computers) to find a good strategy for playing the game without having to completely solve the game. Actually solving the game is still just a matter of going through all the combinations.

Re:Go...

[WalksOnDirt]

Speaking of the difficulty of telling if a group is alive or dead, there seems to be an obvious (possible) mistake in the 5x5 result.

If black is able to control the entire board, white shouldn't move after black makes his first move in the center. This leads to a black win by 24, instead of the 25 stated in the paper.

I believe there is a rule though about black not having to move to prove that a position is dead, so perhaps the true result is that black declares he has won before making any moves, and getting the entire 25 points on the board!

Re:Go...

[piggity]

Not true. The board itself only has 361 places in which to place a move. Ergo, at any given time there are at most (361-n) moves possible, where n is the number of stones already placed on the board.

Re:Go...

[thefirelane]

True... the author wasn't 100% correct, but they were correct in magnitude. This would be 361! (factorial) moves. This is, of course, assuming no pieces are captured, in which case it grows larger than the insanely large number already given.

Re:Go...

[Jim_Callahan]

Plus, chess hasn't been solved either. We just have programs that are better at guessing outcomes than most people.

Re:Go...

[Cryogenes]

The number of potential moves grows way faster then in chess

Which is a problem, but not the main one. The real advantage of computer chess over computer go is the relative ease with which the leaves of the search tree (e.g. all positions after n moves) can be evaluated statically. In chess you can perform excellent static evaluation by counting material, mobility, king safety and maybe a few other features. In Go, static evaluation is considered difficult for an expert, let alone a computer.

Re:Go...

[hobbicik]

How did the parent get moderated "Informative"?!?
There are 20 potential moves in the first iteration for chess, and exactly 361 (19*19) for Go.
There are around 10^120 possible chess games, and around 10^760 possible Go games. That's why the milion-dollar prize for the first program to beat 1-dan Go player is still not taken.

Re:Go...

[Anonymous Coward]

The grandparent was refering to a typical search during play, not solving the game from the first move. In any case, there are 55 opening moves in Go. Of course the number increases once symmetry is broken, then decreases as the board fills up.

Re:Go...

[Anonymous Coward]

Number of moves doesn't necessarily mean more complex. If I were to play tic-tac-toe on a billion by billion board, there would be way more possible moves than in go. Yet the game would remain trivial. Now I won't claim that go isn't more complex than chess, but just number of moves doesn't explain it for me. Other things to consider are the number of states a field, or section of the board can be in, and how localized actions are. For instance, when playing tic-tac-toe on a large board, playing on one side of the board has little significance on the other side of the board. But that's different in go and chess (explaing why go and chess are far more complex than tic-tac-toe), and it's also different between go and chess. That also influences their relative complexiness.

Re:Go...

[Dogun]

Actually, yes it does have everything to do with solving the game. A good move heuristic is needed if you want to find a solution 150 ply deep, now isn't it?

Re:Go...

[Dogun]

You might be referring to this game.

http://jhubert.club.fr/Go/Parties/Takagawa_GoSei ge n_1959/Takagawa_GoSeigen_1959_0.htm

I'm not sure what you're saying about the result is correct. I advise you to read the page i've linked above and google around for other information related to the situation.

Re:Go...

[WalksOnDirt]

This is the sort of thing that makes me roll my eyes when I read that the rules of go are so simple. The issues discussed in your link seem much more difficult than equivalent chess arcana, such as ep pawn capture and the fifty move rule.

I make no claim of being a go expert; I haven't played in many years. I was implicitly asking a not very important question: Why is the optimal result for the 5x5 board given as a 25 point win and not a 24 point win? I guess your response is that a rule change in 1958 requires the game to be played out to the end. The books I learned from (Lasker, for one) were published before that date, but I never fully understood such subtleties anyway.

yep

[St. Arbirix]

Check out this for a decent comparison between chess and go for those of you who have been missing out.

Also, dig my sig biotches.

Re:yep

[falzer]

> Also, dig my sig biotches.

You aren't fooling anyone with your hip urban lingo. Slashdot is not the place to spout zealous remarks.

Re:yep

[mav[LAG]]

For those chess players who want a game that can be played on a normal chessboard with a normal chess set but is as difficult for computers to play as Go, I suggest they look at Arimaa. Like Go, the rules are incredibly simple and take minutes to learn, but the game is far from being well understood.

Re:yep

[HeghmoH]

Slashdot is not the place to spout zealous remarks.

You must be new here.

Re:yep

[PDAllen]

Slightly biased comparison, IMO.

I'd point out that in fact pattern recognition is a major component to chess play. But because the patterns are so simple, all the pattern recognition is done in the first second or so of your turn. The rest of the turn is analytic thinking. Good example of this is when you play 1 or 2 minute chess - you never have time to think about it, all your time is spent recognising patterns and responding. You can get in about 1 move a second like that, but the level of game play only drops to what you'd expect in a normal game between players ranked about 100-150 points lower.

Whereas with go (note: my play is poor) you can only get away with auto-responding to patterns when you're in a very restricted situation; trying it when you're playing in a large area will lose you the game.

Re:yep

[duggy_92127]

Also, dig my sig biotches.

It's times like these that browsing with sigs turned off is deeply, deeply satisfying. And somewhat amusing. :)

...biotch.

Doug

Um, who wins?

[endersdouble]

Am I the only one ***OUT OF THE PEOPLE HERE WHO KNOW HOW TO PLAY*** who is slightly confused after a cursory glance at that site as to who exactly *wins* in 5x5 go? Obviously if it's solved, it's either a black win, a tie, or a white win (as I said, I'm not sure, though I'd guess one of the first two.)

Re:Um, who wins?

[ricewind]

From TFA

As was expected it is a win for the first player with 25 points (the whole board belongs to black).

It's Go. Black plays first. Just like in that other board game, which I can't remember the name of, white goes first.

Re:Um, who wins?

[Anonymous Coward]

There are animated GIFs on the article's page showing the optimal moves in a 5x5 game. Black win in all cases, assuming optimal moves (once you consider the captures).

Re:Um, who wins?

[PetWolverine]

It has to be a black win or a tie. If White has an advantage, Black can just pass the first turn, effectively trading places and giving him White's advantage.

Re:Um, who wins?

[jrumney]

It's Go. Black plays first. Just like in that other board game, which I can't remember the name of, white goes first.

It's called "Nine Men's Morris". I thought everyone knew that. Or are you talking about that other game with the horses and castles and stuff?

Re:Um, who wins?

[Anonymous Coward]

Sorry, it is not what you think. Black is *not* allowed to pass the first move.

Re:Um, who wins?

[PetWolverine]

I wasn't aware of that rule, but regardless--as long as passing is allowed in general, black has the (theoretical) advantage.

Re:Um, who wins?

[Anonymous Coward]

That is not true. But if he does, white could then also pass, and the game would be a draw.

Re:Um, who wins?

[Anonymous Coward]

No. The first move is indeed an advantage, so white is given extra 2.5 points for compensation.

Oh a fanatic

[Eunuch]

You notice there's no chess players proclaiming its superiority to Go. What is this, frustration from the fact that Go doesn't help with getting an Asian girlfriend?

Re:Oh a fanatic

[Anonymous Coward]

What is this, frustration from the fact that Go doesn't help with getting an Asian girlfriend?

Hey, that's every Geek's concern---except you, obviously, since you are Eunuch.

Re:Oh a fanatic

[shish]

You notice there's no dirt lovers proclaiming it's superiority to pie. Must be a problem with the pie lovers :P

And does chess help me get an asian girlfriend?

(I don't play enough of either to take sides, but it annoys me to see people who's arguments are entirely logically falicious getting modded insightful...)

Re:Oh a fanatic

[Anonymous Coward]

It was just a jab at wankers who post about Go vs. Chess in every Go or Chess article.

He doesn't suggest or imply Chess would get him an asian girlfriend. He doesn't imply there is a problem with Go lovers.

Your attitude towards correct spelling offends me.

Re:Oh a fanatic

[shish]

On a topic of A vs B, saying A doesn't do something implies that B does, that's how implication works...

Your attitude towards correct spelling offends me.
Is that just a troll, or is there some meaning? I see nothing wrong with my attitude to spelling :/

Oh Please...

[_Potter_PLNU_]

5x5..pfft. I wrote a program that solves 1x1. I win every time.

Re:Oh Please...

[flatface]

No, a move by either player would be considered illegal self-capture.

Re:Oh Please...

[Anonymous Coward]

but white get 5.5 points, so white wins ;)

Re:Oh Please...

[Anonymous Coward]

Actually no, you lose.

Your first placed stone is surrounded, and thus taken from the board.

Re:Oh Please...

[PetWolverine]

Maybe he plays as White.

Re:Oh Please...

[_Potter_PLNU_]

wow...you all don't see a sarcastic joke when it stares you in the face...sheesh. 1x1, c'mon, you think I was serious?

Uh...

[Anonymous Coward]

(16x16 / 2x2) / (19x19/ 5x5)

8/3.8

Even taking into account that there's only 2 different sorts of pieces in Go, I'm sure that 5x5 Go is WAY more complex than 2x2 Chess. Way.

Hm, 4x4 or 5x5 seem closer for Chess...

Re:Uh...

[Ayaress]

Actually, the fact that Go only has two pieces is why it's so much more complex. Chess pieces individual behavior is what usually limits the number of moves in Chess. Also, since Chess doesn't easily scale down, 2x2 chess doesn't work: QK QK Neither side can move, since any move they make still leaves their king in check. I guess that means that White looses by default, since White goes first and can't make a legal move. Unless you play by rules like with blitz and don't count check, only actually capturing the king, in which case White always wins (unless he's REALLY dumb).

Re:Uh...

[Bradmont]

isn't it a stalemate if it's a player's turn and he can't move?

Re:Uh...

[Anonymous Coward]

Since when is orthodox Chess played on a 16x16 board?

Re:Uh...

[Anonymous Coward]

what if it's a she?

Re:Uh...

[Anonymous Coward]

Actually, the fact that Go only has two pieces is why it's so much more complex.

Well no, it's mostly due to the fact that the chessboard starts significatly full and the congestion of pieces prevents the search tree from fanning out significantly until a bunch of moves are made and maybe a few captures. It starts fairly narrow in chess, then gets wider at midgame (though never as wide as go), then gets narrow again at the end. In go, it starts incredibly wide (wider than chess ever is), and narrows very slowly (roughly 1 possibility per turn) until the end. this is an oversimplification that doesn't take into account ko and suicide and captures, but it's a good estimate of the shape and if you take a moment to sum the exponential math at each turn for both games and compare them, you'll realize why go is such a brutal problem for computers. (And why the human brain is such an amazing pattern-recognizing and intuitive machine.)

Chess
oo
oooo
ooooooo
oooo
oo

Go
oooooooo ooooooo
oooooooooooooo
ooooooooooooo
oooooooooo oo
ooooooooooo
oooooooooo
ooooooooo
oooooooo
ooooooo
oooooo
ooooo
oooo
ooo

Re:Uh...

[Ayaress]

It's stalemate if the player is currently not in check, but any move will put him into check. In the 2x2 chess setup, white starts in check, and any move he makes results in him still being in check, and is thus illegal. My diagrams broke last time because I had it on HTML, so here it is in plain text:

Start:
QK
QK

White at the bottom, first move, he can do four things: He can use either his king or queen to capture one of the other two pieces. However, both the black king and queen check the white king currently.
Whichever one he captures, his king is still in check, and thus the move is illegal in standard rules, and the game ends in checkmate. White can't finish their turn, so black wins:

Queen takes queen:

QK
K
Black king still checks white king, so this move is illegal.

King takes queen:
KK
Q
Same as above, black king checks white king, this move is also illegal.

Queen takes king:
QQ
K
Black queen checks white, so you can't do this.

King takes king:
QK
Q
White is still in check by the black queen here.

Any way you play it, white is in checkmate. So is black, but by the rules, since white can't get out of check before ending his turn, he looses.

If you're going by blitz rules, then you have the same four options, but they're all legal, since you don't call check in blitz anyway. I've had situations where I've had somebody in check for several turns in a blitz game and not realized it until afterwards, and even more where I've been in check and not been able to immediately counter it and spent a couple turns in sheer agony hoping they don't notice it.. If you capture the black king, you win. If you make a serious mistake and capture the queen for some stupid reason, black king takes black king next turn and white looses.

Then we come to the unbelievably unlikly reason that, having just seen such a stupid mistake made, black then proceeds to capture the white queen, thus putting the ball back into white's court to pave the way for even more stupid mistakes. I suppose it could take nine turns to win a 2x2 chess game, but you'd have to be very drunk to accomplish that.

Re:Uh...

[Getzen]

2x2 chess is impossible. There is no legal starting position possible since opposing kings cannot be adjacent to each other -- they must be at least one space apart, which would require at least a 2x3 board.

Getzen

"a quarter of a full scale board"?

[Speare]

A 5x5 go board is not a quarter of a full scale board. It is only roughly a quarter in each dimension. A full go board, if I recall, at the size most people play, is 19 by 19 intersections. That's 361 positions. A 5x5 only has 25 positions. Each intersection can theoretically contain three states.

In the past couple days, people have been talking about "cracking" an 80 bit hash with a 69 bit effort. It's logarithmic, people. 69 bits is not three-quarters of 80 bits, it's a factor of 0.000488 in terms of the workload to crack it.

SHA-1 is now 0.000488 (4.88*10-4) as strong as it was. And by my calculator, 5x5 go is 4.866*10-161 as hard as a brute-force solution as a 19x19 board would be.

Re:"a quarter of a full scale board"?

[Cyn]

So what you're saying is that we should switch to a new go based hashing standard?

Re:"a quarter of a full scale board"?

[Anonymous Coward]

While the board needs to be stored with three possible states for each of 361 intersections, there aren't 3^361 possible moves. For example, white's first move can't be to remove black's one stone.

Comment removed

[account_deleted]

Comment removed based on user account deletion

Can there be a tie?

[Eunuch]

I don't think so.

Re:Can there be a tie?

[endersdouble]

Well, I can imagine a tied position (though it's never happened in my play, and with optimal play, I doubt it's likely...) Just think of any board position where each side controls (undisutably) equal amounts of territory.

Re:Can there be a tie?

[k8to]

That is correct, if komi is included.

Komi are the extra points given to white (who plays second) in an even, 19 by 19 full game.

In smaller games, there is no official komi valuation, because it is not really the full game of go, just an amusing diversion, learning exercise, or what have you. In learning and handicap games, komi is not usually worried about, and the game is often scored "as-is", thus making ties possible. However, as these types of games are not often close, and as the victor is genearlly less important than the learning, it is not worried about.

How long till they solve chess?

[jaylee7877]

I've always believed within my lifetime, chess would be solved. In other words, a computer would come up with the perfect solution to chess so that no matter what moves you possible make, out of the, i dunno, billions, trillions, or higher number of possible moves, the computer knows how to beat you. The simplest comparison I can think of is tic-tac-toe. If you've played tic-tac-toe enough, you've learned that no matter who goes first, someone can always force a cat (tie game). I wonder, is it possible to always force a draw in chess or might it be that whoever goes first can always win? Sure the computing power to figure this out is beyond anything we have now, but with quantum computing and other advancements, I expect to see chess solved in my lifetime.

Re:How long till they solve chess?

[cnettel]

Yeah, you have to rely on quantum computing to do that. Alternatively, you have to prove that lots of "possible" chess positions don't actually appear, no matter how the other player plays, on the way to the optimal win.

The number of chess positions is, very naively and as a significant underestimation, something like C(8, 64) * C(8,56) * C(8, 48) * C(8,40).

Even this severe underestimation gives 1.8E35, or about 2^117.

Let's say that 2^80 problems are crackable today and that we wouldn't have the non-locality problems of chess (a move consists of computing another position and then you have to see if that is already in the database of computed moves, not as parallel as just trying encryption keys 'til it works). The added 2^37 is on the scale of 13 billions. If 2^80 is done in a year now, this would require the age of the universe.

We can guess that we, if lucky, get to trust Moore for our lifetimes. Hoping that it will get better than that is a long shot, in my mind. The development of computing speed for computing machines in the Turing sense will probably rather slow down. Even if the current speed of increasing computation capacity was maintained and chess would be as simple as encryption testing (calculating moves is simpler, coordinating the effort and addressing the memory isn't), it would taket 56 years to get to the point where a run would take a year -- based on extremely optimistic assumptions.

Finally, we haven't even got to the point about how to store all that information. 6E23 hydrogen atoms weigh about a gram (Avogadro and all that). Let's say we store one bit for each atom. We would need one billion kilograms of storage to store one bit for each of the possible chess positions. To reach less than 1 bit/position seems quite hard...

Re:How long till they solve chess?

[smallfries]

Congratulations on a quality troll. Too bad you didn't get any bites. Has the makings of a classic slashdot flamefest.

Re:How long till they solve chess?

[frank_adrian314159]

I've always believed within my lifetime, chess would be solved.

For all practical purposes, it already has. Opening books are dozens of moves deep and many endgames have been completely solved and loaded into databases. I doubt that more than a couple dozen of the best Grandmasters could beat the best computer program out there - Kasparov had a heck of a time with Deep Blue.

The days when an average person could walk up to a chess program and beat it are long in the past. For me, that's close enough to call solved. Solution: the computer wins.

Re:How long till they solve chess?

[Anonymous Coward]

If you look up "Deep Blue" you will discover the best AI chess player beat the best human chess player. Thus, chess in the AI field is being replaced by GO, which is far more complex as a few have pointed out. To just look up every move possible, is possible but takes an incredible amount of time. GO has becmoe more interestnig because the amount of time to do this (look up every move) in GO is almost exponential compared to chess, so even the fastest computers can't test every possible move from the beginning - They have to make moves that resemble intelligence.

Re:How long till they solve chess?

[dvdeug]

Yeah, you have to rely on quantum computing to do that. Alternatively, you have to prove that lots of "possible" chess positions don't actually appear, no matter how the other player plays, on the way to the optimal win.

Not necessarily either. Connect-4, for example, was solved not by brute force, but by finding simple rules to find a quick path to victory in certain situations. Chess would be a lot more complex, but it is concievable that we could discover "simple" rules that could tell the computer how to win a particular position without searching the complete game tree.

Re:How long till they solve chess?

[Anonymous Coward]

This is exactly how it would work. Every move your opponent makes limits the results.

Plus he is thinking in normal terms of how we store data and such. A quantum computer could just solve the problem from any state. It would just calculate the answer right then and there, you wouldn't need to store all possible answers.

Re:How long till they solve chess?

[Deanalator]

Oke, so in chess we have how many possible positions per square? blank, pawn, castle, horsey, bishop, queen, and king for each color. This would be 13 ways for any given square on the board. Just for the fun of it, lets add three more garbage spots to take us up to 16. This means we can represent each square on the board with a 4 level atom (2^4=16). So we gather up 64 of these 4 level atoms, and hit them all with a funky-do haddamard. They all assume an even superposition, and we now have an entire chess board with 64 qudits, a proposition well within my lifetime.

Ofcourse the rough part is still going to be how the heck you find an algorithm to get a good move, but the point is you have all possible chess board positions (not to mention the three magic pieces) represented with 64 atoms. I might be wrong, ive only been looking at this stuff for a few months, but you can see how nicely quantum computers scale :-)

Re:How long till they solve chess?

[Anonymous Coward]

"This is exactly how it would work. Every move your opponent makes limits the results."

Um. That only works in connect 4 and other systems which decrease the possible number of states the board is in. Chess does not require each play to decrease the possible number of sucessive plays.

" A quantum computer could just solve the problem from any state. It would just calculate the answer right then and there, you wouldn't need to store all possible answers."

Er.. that's more of what we'd call a "magic computer". A quantum computer still would need to calculate the data and store the data that it is calculating.

Re:How long till they solve chess?

[Cryogenes]

All these calculations about the number of possible positions don't mean a thing. Towers of Hanoi has 3^64 positions and yet it can be solved in about 5 lines of code.

A chess player may know how to mate with knight+bishop+king vs. king. That does not mean he has remembered the roughly 10 million different positions in which the four pieces can be arranged on the board.

Many, many games have been solved. The solution nearly always comes from better insights and improved methods, not from Moore's law.

Re:How long till they solve chess?

[Anonymous Coward]

A quantum computer could just solve the problem from any state.

Because quantum computers are, you know, magic.

Re:How long till they solve chess?

[Anonymous Coward]

This calculation is "irrelevant", since you only need to find one winning path to solve it. (If that is the usual meaning of "solve") Therefore, if you found one on 1F3, you can disregard all others. I don't know how much that chops off, but still...

(Is there something like an "algebra nazi"? ;))

Re:How long till they solve chess?

[p3d0]

Alternatively, you have to prove that lots of "possible" chess positions don't actually appear, no matter how the other player plays, on the way to the optimal win.

This statement is correct, and renders the rest of your post moot. It makes no sense to claim a problem is impossible to solve based on analysis of only the most naive possible solution.

Re:How long till they solve chess?

[Anonymous Coward]

I've always believed within my lifetime, chess would be solved. In other words, a computer would come up with the perfect solution to chess so that no matter what moves you possible make, out of the, i dunno, billions, trillions, or higher number of possible moves

You have "always believed" this, and yet you have absolutely no idea of how many moves would be in that game tree? "billions, trillions"? You got to be kidding. It's above 10^120.

The simplest comparison I can think of is tic-tac-toe. If you've played tic-tac-toe enough, you've learned that no matter who goes first, someone can always force a cat (tie game).

Actually, for any non-completely retarded person it suffices with one or two games of tic-tac-toe to notice that property...

Sure the computing power to figure this out is beyond anything we have now, but with quantum computing and other advancements, I expect to see chess solved in my lifetime.

The game tree of chess can't be stored with all the energy in the universe. It won't happen. Revise your beliefs.

Chess vs Go

[Anonymous Coward]

Go is orders of magnitude more complex than chess (although chess is the more interesting game for us mere mortals, imo).

The reason this is noteworthy is that Go (which is played on a 19x19 board) is notoriously difficult for computers; the best programs cannot defeat a competent amateur. To have a program which has solved Go (unlike the best chess programs, which are merely at the strength of Grandmasters), even at a miniscule 5x5 scale, is a sign of progress.

Re:Chess vs Go

[Transcendent]

To have a program which has solved Go (unlike the best chess programs, which are merely at the strength of Grandmasters)

It should be noted that even on a 9x9 board (let alone 19x19), competent amateurs can beat any computer program.

19x19, 13x13, and 9x9 (the "standard" sizes, though 7x7 is fun sometimes), require totally different strategies. 9x9 is pure life and death, 13x13 is mostly fighting, and 19x19 requires a good understanding of balancing influence for defined territory (don't spread your stones too thin while not letting them get bunched up).

For all who don't play go or are new to go, the biggest problem with the 19x19 and even 9x9 computer programs is that the computer can't see the dual threat someone might play with a sequence of moves. For example, you can start to attack a specific section of the board, and use what you played to grab hold of an even larger section of territory, or even kill a large portion of their stones. It's easy to fool the computer in Go.

In the interest of fairness...

[Theatetus]

It's nice that AI and computer science research is going into popular and well-known games like go, but a lot more complexity and interesting research can be found in a less-known game called chess

Re:In the interest of fairness...

[malfunct]

No, not complexity, that is if you measure the number of possible outcomes given a particular configuration of the board as compexity. For any given configuration of the board there are far more possible outcomes for go so it is MUCH harder to min/max because of the size of the search space.

Re:In the interest of fairness...

[Anonymous Coward]

Fairness? You forgot backgammon.

Re:In the interest of fairness...

[eobanb]

You are mistaken, sir. The game of Go is fantastically more complex than Chess can ever hope to be.

Re:In the interest of fairness...

[Anonymous Coward]

Only in the number of combinations of different moves that can be played. I've always found it to be a dull game.

Chess, on the other hand, is far more interesting.

Re:In the interest of fairness...

[maino82]

Go may have simpler rules than chess, but it by no means a simple game. When I tell my friends about Go they laugh at me, but after explaining the game to them and giving them a 9 stone handicap and thoroughly trouncing them (I'm only around 12kyu... practically a beginner) they begin to see the game is much more complex and subtle than they anticipated. A computer program playing Go would have to be much more adaptive than a program playing chess, or have a much quicker algorithm to process the insane number of possible moves and responses. In either case, research into a computer that can play Go and can beat a human is something that is extremely worthwhile and applicable not just in Go, but in other AI applications as well. Don't get me wrong, research into chess playing programs is just as worthwhile, but any advance in Go will be orders of magnitude more impressive than any advance in playing chess.

Re:In the interest of fairness...

[cnettel]

His humor is fantastically more complex than you can ever hope to be. (Or maybe you just carried it on...)

Re:In the interest of fairness...

[Anonymous Coward]

He was joking; it's a slashdot cliche to say that about Go when someone posts about chess.

Re:In the interest of fairness...

[Council]

He was joking; it's a slashdot cliche to say what you just said about Go when someone posts about chess.

Re:In the interest of fairness...

[MegaFur]

Actually, I think most of the popular two player strategy games other than chess (like checkers, othello, mancalla, go) are harder to become good at than chess. Reason: In Chess, different pieces look different and are worth different amounts, strategically speaking. In all the other strategy games, all the pieces are worth the same, in and of themselves--so it's the position and the patterns that mean *everything* in those strategy games.

But even if the above line of reasoning is flawed, standard 19x19 Go is uber-crazy-hard compared to 8x8 Chess. If you don't believe me, go study it and find out for yourself. :-)

Re:In the interest of fairness...

[maino82]

You'll have to forgive me :) I'm fairly new to the slashdot community.

Re:In the interest of fairness...

[STrinity]

Actually, I think most of the popular two player strategy games other than chess (like checkers, othello, mancalla, go) are harder to become good at than chess. Reason: In Chess, different pieces look different and are worth different amounts, strategically speaking.

Is there some reason why Stratego doesn't count as a strategy game?

Re:In the interest of fairness...

[Theatetus]

You are forgiven. Now go forth and bite at trolls no more.

Re:In the interest of fairness...

[Anonymous Coward]

Only if your game is in tactical rigour and not strategical beauty.

Re:In the interest of fairness...

[Domini]

A typical tree-hugging, Mac-using statement.
Go draw something! ;)

Re:In the interest of fairness...

[Anonymous Coward]

In all the other strategy games, all the pieces are worth the same, in and of themselves--so it's the position and the patterns that mean *everything* in those strategy games

Well, duh. If you have just one type of piece, it's hard to argue that one of it is worth more than the other. And since in go, pieces don't move, obviously position and pattern means everything. It means everything, because that's all there is.

In chess, position is far more important than the strength of the pieces. However, in chess, unlike in go, pieces move, and, just as in go, position is build using the pieces. So in chess, strength of the pieces matter - but position matters too. In chess, a well placed knight is worth a lot more than a locked in rook. Two bishops working in unison are more powerful than two lone bishops combined.

But even if the above line of reasoning is flawed, standard 19x19 Go is uber-crazy-hard compared to 8x8 Chess. If you don't believe me, go study it and find out for yourself. :-)

I've been playing chess for over thirty years. A lot longer than I know how to play go. I've studied chess books, never any go books. But I get trashed as hard by computers or strong players in chess as in go - so in my experience, chess is harder. Because with all the extra amount of time I spend playing and studying chess, I'm as far as I am with go. ;-)

But neither is my favourite game. I prefer other board games, and for "traditional" "thinking games", I prefer bridge over both chess and go.

Re:In the interest of fairness...

[stanmann]

Because unlike the others you don't have perfect knowledge of your position.

Re:In the interest of fairness...

[stanmann]

Stratego is like poker, you are playing against a person, not a board. The completely random and unknown layout of the board makes for a very complex and entertaining, but not very strategic, game.

Re:In the interest of fairness...

[STrinity]

Stratego is like poker, you are playing against a person, not a board. The completely random

But a Stratego board isn't laid out randomly -- or if it is, you're playing against a fool. In fact, how you array your pieces in Stratego is itself a strategic decision since it determines how much defensive and offensive power you're going to have; and how you probe your opponent's forces is also a matter of strategy.

and unknown layout of the board makes for a very complex and entertaining, but not very strategic, game.

I don't see how imperfect knowledge of your opponent means the game doesn't require strategy -- certainly real-world strategians don't always know what pieces the other side has where.

Re:In the interest of fairness...

[stanmann]

In the real world, you can tell the difference between a squad(4-8 people) aka an 8 and a field battallion(4-5k people) aka a 1 without much difficulty. Determining if the 8 people are a supply convoy or a special forces team is a different story, but a field battalion will still squash a special forces squad.

Re:In the interest of fairness...

[STrinity]

I didn't claim that Stratego was a perfect mapping of a real-world battlefield, just that imperfect knowledge is a factor in real-world strategy, and Stratego can't be discounted as a strategy game for including it.

Re:In the interest of fairness...

[MegaFur]

It does count as a strategy game, but I wasn't including it because it involves hidden information. (I.e. you don't know how your oppoenent's pieces are laid out.)

The games I was counting are all public information (in a Game Theory sense).

Posted AC to avoid karma whoring

[Anonymous Coward]

Seeing as so many karma whores are saying that this was solved 3 years ago, here's a hint: RTFFA (Read The Full Fucking Article). If you do you'll realise that it was just solved recently.

Re:Posted AC to avoid karma whoring

[Anonymous Coward]

Seeing as so many karma whores are saying that this was solved 3 years ago, here's a hint: RTFFA (Read The Full Fucking Article). If you do you'll realise that it was just solved recently.

Speaking as a karma pimp, don't you be talkin' about my ho's.

Re:Posted AC to avoid karma whoring

[Kippesoep]

The other posters are correct. If you really RTFFA, you'll find that it was solved October 20th 2002, well over two years ago. Even the link you provide only mentions the corresponding doctoral thesis beind defended recently (January 27th 2005). Perhaps you should RYOFL (Read Your Own Frelling Links).

Re:Posted AC to avoid karma whoring

[Hecatonchires]

Calm down, count to ten. 1 mippi-pippi, 2 mippi-pippi...

"Cracks" defined

[Anonymous Coward]

/Anon because I'm not in a whoring mood, and Wiki is getting so slow these days the link may not load for you...

But what the headline means is that 5x5 Go has become a Closed Game.

Re:"Cracks" defined

[Anonymous Coward]

Anon because I'm not in a whoring mood...

What makes you think you would get points for your "post", such as it is?

Re:What the fuck?

[castrox]

Although put in a silly language, the parent does have a point. :-\

The mathematical rules

[Eunuch]

Note that a liberty is an empty spot on the board that is either next to your stone or can be reached by moving across your stones horizontally or vertically. This is great for computer scientists who don't know the game yet, http://brooklyngoclub.org/jc/rulesgo.html:

The Alternating Rule:
Two players, called Black and white, keep alternating moves till the end of the game. Black plays first. A move by a player begins by his placing a stone on an empty intersection of the go board. The first player who cannot put down a stone without breaking a rule loses the game.
The Rule of Capture:
After a stone is placed on the board, all enemy stones which have no liberties are removed. A player's move is not finished until this phase has been completed.

The Rule for Suicide:
Suicide is illegal. Precisely, after a stone has been played, and after the rule of capture has been applied to his enemy stones, if the stone has no liberty, then the move was illegal.

The SuperKo Rule:
A player is not allowed to place down a stone if, after the rule of capture has been applied, the resulting Board position has appeared previously in the game.

Re:The mathematical rules

[Ken Broadfoot]

There is one more rule being missed:

You can choose not to move during your turn.
i.e. You can "pass"

Can you do that in chess?

*wink*

-ken

Re:The mathematical rules

[k8to]

Some comments:

The rule for suicide applies in japanese rules (americans generally play under slightly modified japanese rules, AGA rules), but not Ing or Chinese rules. Suiciding a single stone would never be a good idea (you give away a point and a turn), but suiciding a group can be advantageous. It's always struck me as dumb to disallow this.

The SuperKo rule I believe is incorporated into Ing rules? But most broadly used rulesets do not have this rule. A game which enters into a stalemate via 3 simultaneous equally valuable kos is considered differently in different game rules sets. In american go it is considered a draw, and so a winning player should allow it to end. In a japanese game it is considered a null game, is stricken from the record, and the game is started again. I've found this practice very strange as well.

So, for correct computer play, it is necessary to describe the rule of Ko in a more complex fashion. A player is not allowed to place down a stone if, after the rule of capture has been applied, the resulting Board position is the same as that two positions prior (on the previous last turn of the opposing player).

Re:Oh noes!

[Abreu]

Hilarious! Too bad you posted AC

Sheeshkabob

[Anonymous Coward]

A marathon.. pfft. I run a centimeter-long track. I finish every time.

arthur c clarke story

[Sark666]

Everytime chess gets mentioned on /. (ok I know it's a go story but you know the comparisons will start) I like to post a link to this short story written by Arthur C. Clarke. I originally found the story through someone else's /. post http://www.research.ibm.com/deepblue/learn/html/e. 8.2.shtml

Re:arthur c clarke story

[Anonymous Coward]

Thats a great story, thanks for sharing.

What, are you crazy!?

[ucblockhead]

It's not going to end! It's the new economy, dude! (I can't wait until Salon.com goes public so I can buy a new house!)

Could I get that in binary or hexadecimal?

[Eunuch]

I don't see why decimal needs to be used here.

Checkers

[Skraut]

Isn't this in the realm of possibility for Checkers now. I know checkers has been solved with up to like 9 pieces a side. But with the limited moves, it should be able to create a database of all moves in only a couple terrabytes or so. Yeah I know "only" is relative, but it should be in the realm of possibilities.

The actual details

[Anonymous Coward]

The actual details are available at Erik van der Werf's homepage at the Universiteit Maastricht, and in particular on his publication list.

And the solution is.......

[Anonymous Coward]

here.

Just as exciting as...

[Anonymous Coward]

This is nearly as exciting as the release of HappyKitchenGames first game Click-a-Block. Anyone want to write a program to play that game?

If we solve Go, will it still be fun?

[Eunuch]

I think it will. We still have weightlifting competitions even though we have forklifts at our disposal.

Re:If we solve Go, will it still be fun?

[colmore]

We also aren't going to solve Go. We'll solve Chess first, and we aren't going to solve Chess either.

19x19 is exponentially more complicated than 5x5, and it's a really big exponent.

Re:If we solve Go, will it still be fun?

[m50d]

OTOH, chess has had a big decline since Deep Blue won.

Re:If we solve Go, will it still be fun?

[WillerZ]

Is that because there was a bug surge of interest while IBM were building (and marketing) Deep Blue, or are whatever numbers you use to measure this kind of thing down compared to before Deep Blue was announced?

Phil

Re:If we solve Go, will it still be fun?

[huge colin]

It shouldn't be surprising that there wouldn't be a lot of interest in a game if the best human player in the world can't beat the best computer player in the world. It's only a matter of time before a similar thing happens with Go, and then we can all move on to something important.

Re:If we solve Go, will it still be fun?

[m50d]

I'm just using numbers at my local tournaments, not very scientific, but they are down by as much as 80% on numbers from before there was anything about Deep Blue. Correlation does not imply causation, of course, but Deep Blue seems the most likely candidate for having caused it.

GNU Go and future AI research

[__aaijsn7246]

AFAIK, the current state of the art of Go on computers is Goemate and Go4++.

GNU Go is actively developed, but it still does not match commercial Go software, ranking 1-2 stones weaker. It is rated from 8 to 9 kru, which is a weak amateur.

Computers have thus far not been too great at cracking go via the usual searching algorithms, as it has a high branching factor - starting at 361, much higher than chess! It is only recently that Go programs have even begun to achieve low levels of competence. Besides the limited searching and pattern recognition of current software, future programs may improve by decomposing Go into 'subgames', allowing it to be more readily attacked.

Re:GNU Go and future AI research

[__aaijsn7246]

Sorry, that should read *peaking* at 361 (which is of course 19^2).

Re:GNU Go and future AI research

[latroM]

GNU Go is actively developed, but it still does not match commercialGo software, ranking 1-2 stones weaker. It is rated from 8 to 9 kru, which is a weak amateur.

You probably mean proprietary software. For example MySQL is Free Software and commercial.

Re:GNU Go and future AI research

[__aaijsn7246]

Well, Go++ sells for $39.95 at http://www.goplusplus.com/ and Goemate is $60.00 from http://www.wulu.com/sale.htm - so, indeed, they are selling their software as a business, with the goal of profit. I agree the distinction between proprietary and commercial software is important, but these programs are both commercial.

Re:GNU Go and future AI research

[Alsee]

Actually it peaks at 360 on the second move. On the first move you have 8-fold-symmetry which yeilds 55 distinct openings.

-

Re:GNU Go and future AI research

[latroM]

I could sell you GNU Go for 5$ with some special patches and that would make it also commercial :>.

Re:GNU Go and future AI research

[__aaijsn7246]

Ahh, I see your point now :) So would that make Go++ software proprietary and commercial?

Re:GNU Go and future AI research

[latroM]

Commercial. It would be illegal to make it proprietary because it is licensed under the GPL.

Re:GNU Go and future AI research

[__aaijsn7246]

I mean Go++, not Gnu Go. :)

What??

[Transcendent]

5x5 go is miniscule, similar in scale to "solving" 2X2 chess

Sorry, but that's like a full chess board with the pawns removed (if even that much).

5x5 Go is still fairly complex. Although the article is old (2002), I'd still like to see a caltulation time comparison.

2x2 chess can be solved in a manner of seconds/microseconds. 5x5 Go might take a few days to brute force it.

Re:What??

[gl4ss]

2x2 chess can't need solving.

if you want to do the "go is SOOO COMPLEX MATES!!!" post how about you put your brain into solving WHY 2x2 chess would be pointless(let's assume there to be at least the two kings there).

Re:What??

[Transcendent]

Hence the timing. A minute to write the program ("hello world" replaced with "This violates the rules of chess"), and a vew microseconds to run it.

What I was really referring to is the possibility of changing the rules. Put 4 pawns on it (or 2), and see who wins. Well... it should be obvious... more obvious than tic tac toe. Thus, I was really referring to the possible combinations of a board position in some sort of game. Just like 1x1 go. You can't even place a stone, but white will win anyway (under a certian komi).

I guess I forgot the quotes around "solved".

Re:What the fuck?

[dcclark]

And on the other hand, while it may be old news, it IS interesting. I certainly didn't hear about it when it happened. News like this tends to be less visible than news about chess computers or other projects that are more in the public eye.

Versus people or computers?

[Eunuch]

It would seem that it could be very different. There are a lot of these computer-only competitions and tuning for that will be very different from tuning for humans online.

Want to play?

[Champaign]

A variant of Go (Atari or first capture Go) can be played at:

http://swag.uwaterloo.ca/~jchampaign/goapplet.html

Re:Want to play?

[UserGoogol]

And real Go can be played at KGS.

Re:Want to play?

[WillerZ]

Or at Dragon Go Server which is a web-based non-real-time Go server.

Re:Want to play?

[BlueYoshi]

or IGS

Connect 4 Solvable As Well

[Comatose51]

My friends and I once made a connect 4 game but the AI wasn't very good against other AIs. It occured to me that perhaps Connect 4 is solvable. Each hole has 3 possible states and there are 42 holes. So it's 3^42 possible board states. However, there is a very large number of board states that cannot happen, such as having a piece in row 2 but not row 1, etc. Someone with better math skills can calculate what the actual number of possible board states. My intuition is that it should greatly reduces the number of states enough that we can solve the entire game. The rules are simple and the AI for it is simple as well. We used a tree to represent moves and applied alpha-beta pruning to it.

Re:Connect 4 Solvable As Well

[emurphy42]

The canonical game (7 columns, 6 rows) has been solved.

Re:Connect 4 Solvable As Well

[mako1138]

One of my CS class projects involved alpha-beta pruning and game trees. You might find it interesting: Network.

Re:Connect 4 Solvable As Well

[Anonymous Coward]

It has been solved,about ten years ago. IIRC by a team of the same university.

Re:Connect 4 Solvable As Well

[Anonymous Coward]

If you have N columns of height M, there are (2^(M + 1) - 1)^N positions - including positions that contain 4 stones of the same colour.

Re:Connect 4 Solvable As Well

[SamSim]

I programmed my graphing calculator to play Connect 4. It is amazingly primitive - if it can make a winning move, it will; failing that, if you are about to win, it will block you; failing that, it moves randomly.

It beats me about 25% of the time.

I'm REALLY bad at strategy games.

Re:Connect 4 Solvable As Well

[Anonymous Coward]

My laymans attempt at cutting that number down.

Each column can be described with 7 bits. One bit determining the top color, the other 6 describing the pattern.

Examples:
1.001111 = 4 x red
0.000110 = black, black, red
1.010101 = red, black, red, black, red
1.111111 = all red
0.111111 = all black

Note that 1.000000 is the same state as 0.000000

This means there are 127^7 (~2^49) physically possible board states, many of which already contain a 4-in-a-row.

The number of possible states for a column without 4-in-a-row is 103, discarding:
{0,1}.001111
{0,1}.010000
{0,1}.011 11{0,1}
{0,1}.10000{0,1}
{0,1}.101111
{0,1}.110 000
{0,1}.1111{00,01,10,10}

That leaves 103^7 (~2^47) gamestates without 4-in-a-row vertically. This is quite manageable.

Ridiculous.

[stonecypher]

A 5x5 go board has only 847,288,609,443 possible game states, even including impossible boards. Assuming the relatively tame pace of scoring 100,000 boards per second towards completion, which on a board of that size is trivial, this solution takes a simple brute-force time of 98 days. That solution space can be cut down by almost two orders of magnitude with simple reflection and rotation tricks, implying a realtime tree search space of about a day and a half.

Given that my full board scorer moves faster than that, and given that the university probably has more than one PC to work with, I wonder how it is that anyone can justify this as something larger than a publicity stunt, especially given that none of go's emergent structures even fit onto a 5x5 board.

This is horseshit, in short. Mod story down.

Re:Ridiculous.

[sillybilly]

"Scoring 100,000 boards per second" is the catch - there is no good way to score. How do you know what a move is worth without knowing its effect? A move that looks seemingly awful, and suicidal, might be a brilliant move whose effect develops 25 moves later, or 50 moves later. The only true way to "solve" is not to consider all game states, but to consider all possible paths, or sequence of states to a state where no more moves are made. (note: the board never gets completely full, game stops before, when no more territory can be made, and playing into enemy territory would be suicide inviting a pass from the opponent while the invasion stones still being dead, increasing the enemies points.) Now take those 847,288,609,443 possible states, and consider all the sequences through which you can travel because you can't just look at a position and "evaluate it" without knowing the "future" it holds (don't forget captures that give you back empty spots that can be played again.) Actually, knowing all the possible "reasonable" end states, then tree searching backwards on how you can arrive at them might be a better way than starting forward from an empty board. Basically knowing the "future" of a position, or all the "futures" that you get to from a given position, could be a better way to go about things.

Re:Ridiculous.

[tradervik]

You assume that scoring a game state is easy in go. It isn't and it remains the reason why go playing computer programmes still cannot defeat even relatively weak amateurs (at least not the last time I checked, which was a few years ago). Try learning the rules and reading a few books on "life and death" problems and you'll see what I mean.

Re:Ridiculous.

[stonecypher]

When you're dealing with a ply tree, it's relatively straightforward: the score is positive infinity if the board wins, negative infinity if the board loses, 0 if no path to a win is possible (tie boards or unknown boards,) and +-inf +-epsilon/ply for any board whose path towards a solution/solutions are known.

How do you know what a move is worth without knowing its effect?

Uh, when you're solving a game, there's no such thing as a move. You consider only board states, not the moves which lead to them, except in determining in which order to evaluate states. In this way it's trivial to understand how the value of a board in an infinite cycle between two paired positions - say, two kings moving back and forth between their same two cells each turn on a chess board - have up to four board scores through which they oscillate (unless there's a terminate-at-N-moves rule like in chess, but whatever.)

The only true way to "solve" is not to consider all game states, but to consider all possible paths

Game theory 101: the board states are the only thing there is. There are no "paths" - there is no difference between a board which has had a cyclic move applied to it ten thousand times than one which hasn't gone through them at all.

Solve has a very specific mathematical definition here - that the perfect response is known for every move. For games of no chance and perfect information such as go, chess and so forth, the traditional way to handle this is to create the entire move ply tree and then follow through the paths of least risk. When that tree is completed, you know for every possible board state every possible result of every move, and therefore know what exactly the best move is.

In this way you can find out that some games are balanced (tic tac toe, for example, is always a tie with perfect play with both sides) whereas other games are unbalanced (with perfect play by both sides, the second player will always win at connect-4; there is nothing player 1 can do.)

The reason chess remains unsolved is that its solution tree is so preposterously huge that even by modern computing standards it's just an absurd thing to want to attack, even given twenty years and positing 20 years' hardware development.

By the way, what I described above is not the only way to sove a game; if you'd like to find out how the branch of mathematics called Game Theory works, I recommend the primers "The Compleat Strategyst" (yes, it's spelled like that) and "Game Theory: a Nontechnical Introduction."

Common sense as what you're saying may seem, John von Neumann proved you quite wrong in the early 50s. I suggest you read up before challenging these terms; they're very well defined.

(note: the board never gets completely full, game stops before, when no more territory can be made, and playing into enemy territory would be suicide inviting a pass from the opponent while the invasion stones still being dead, increasing the enemies points.)

Er, yes, I know how Go works, and that's what I was referring to when mentioning that I was counting impossible boards. The number I quoted is the mathematically-derived high end cap on possible board definitions as a simple string of radix-3 digits. Observing that you can reduce the solution space here does you no good: you're only making my job easier.

Now take those 847,288,609,443 possible states, and consider all the sequences through which you can travel

That's a giant waste of time. Watching the ko cycle doesn't change the board, and since Go is scored not on held piece count but rather difference in held piece counts, the scores aren't changing either. It really doesn't matter how you got to a board - if you play squares a,b,c,d,e,f in order then the next game you play f,a,b,e,c,d, nothing has changed; your opportunities are still exactly the same.

because you can't just look at a position and "evaluate it" without knowing the "future" it holds

Re:Ridiculous.

[stonecypher]

You're trying to apply too much emotional content here. In the context of solving a game, the notion of scoring applies to exactly one thing: a board's proximity to a winning or losing state, as measured by the risk and reward ratio between possible end states over the gamut of the ply tree.

That has nothing to do with the reason computer programs are still bad go players. The reason that computer go players suck is that the ply tree for Go is awesomely large, and that short of currently-unknown geometric attacks on the board, the only way to reduce the size of the ply tree short of an incomplete principal variation search is to do simple reflections and rotations, which is woefully inadequate. Furthermore, the number of potential go states following any initial or leader state prevents strong knowledge of the strength of a leading position, and the number of closure states is fantastically large, so closure systems like chess' and draughts' dictionary play isn't realistic.

There are a number of approaches which are showing new promise on the front of computer go; I have a neural network playing at what I estimate to be about 8 kyu against american professional Dan. Most active go playters will scoff and insist that's impossible, as the best known computer go players play at 1 dan 1 kyu and because I'm a total nobody. What's really going on is that I know what the guy behind Negascout did, and I applied it to Go, and it works really well.

Oh, and I'm not the first one to do it. Things are about to change.

Anyway, computers have been able to defeat weak amateurs (Try learning the rules

I play at one dan six, and at 9 kyu against american professional rank, meaning I probably play at around 8 kyu against Japanese professional rank. Don't tell me to learn the rules until you know whether I'm familiar with the game, please. I'm a professional game developer. I'm not speaking out of ignorance of either the game or the math underlying attacking a game. Your tone is unwarranted and insulting.

Re:Ridiculous.

[greppling]

A 5x5 go board has only 847,288,609,443 possible game states, even including impossible boards. Assuming the relatively tame pace of scoring 100,000 boards per second towards completion, which on a board of that size is trivial, this solution takes a simple brute-force time of 98 days.

Ok, the position evaluation needs Benson's algorithm to identify unconditionally alive stones, for which 100,000 positions per second is a realistic pace. So you are right that it is not so surprising that it is doable. Still it is interesting to see how it is done optimally. So for me, the interesting part is not that it got done, but which search optimizations turned out to be useful to cut it down to 4 hours on a single desktop processor.

I wonder how it is that anyone can justify this as something larger than a publicity stunt

Well I am not sure Erik van der Werf claimed it was worth slashdotting :P But it's certainly worth an e-mail to the computer-go mailing list, and a paper in some journal.

Re:Ridiculous.

[bhima]

Since you sound like you know what you talking about how about answering a simple question. Why, if they're able to solve a 5X5 and 6X6 boards, can't they solve a 9X9 board albeit in a significantly longer timeframe. TFA states "searching techniques alone are not enough to play Go well on larger playing boards" but it doesn't say why.

Re:Ridiculous.

[HeghmoH]

In theory, they could be solved with the exact same techniques.

In practice, the universe is not large enough to hold a computer that could accomplish it before the heat death or big crunch, whichever it turns out to be.

Re:Ridiculous.

[tumbaumba]

Uh, when you're solving a game, there's no such thing as a move. You consider only board states, not the moves which lead to them, except in determining in which order to evaluate states.

Very interesting. Does any one know if there is a game where next possible state depends on a whole history of the states of the board? For example, if in chess Knight on a white square should move like a bishop, along diagonals, but on a black squares like Knight.

Re:Ridiculous.

[Alsee]

Why, if they're able to solve a 5X5 and 6X6 boards, can't they solve a 9X9 board albeit in a significantly longer timeframe.

Just going from 6x6 to 7x7 means a "significantly longer timeframe" multiplier of something like a million. If it took a day to solve 6x6, well... that's over 2000 years to solve 7x7.

-

Re:Ridiculous.

[Alsee]

Does any one know if there is a game where next possible state depends on a whole history of the states of the board?

From a game-theory point of view the question is meaningless. The "state of the board" is considered to include anything which affects the current game poisition.

For example I assume you are aware of the chess rule that if you move your king you can no longer castle. If you move your king then move it back (history), that is considered part of the board state. Boards that look identical can be different. A king that has moved is a different state than one that has not.

I just thought of an amusing example of the sort of game you were attempting to ask about. We can define a game that plays exactly identical to chess, but it looks like the kind of game you mean. You have an empty chess board. Each player has their 8 pawns and their 8 peices in their lap(*). On your first turn you can place a pawn on the board in any of the 16 squares you could move a pawn in a normal chess opening, or you can place a knight on one of the 4 legal knight opening squares. On my turn I can place a pawn or knight on any of the squares I could legally go to in normal chess, and in the process "capture" your peice and drop it in your lap again. We continue playing an exactly normal game of chess like this, but at any time there's only ever a single peice on the board. It's really normal chess with the bizzare rule that all the peices are invisible except for the last peice that was moved. The legal moves at any given time complexly depend on the entire history of moves.

*Footnote:Technically we need to be able to tell the pawns apart, maybe number them 1 through 8, and we need to be able to tell the left rook and knight from the right rook and knight.

-

Re:Ridiculous.

[stonecypher]

The article is basically misled. Yes, you can apply searching techniques to a larger board, and no, there isn't a practical limit to board size for searching techniques.

The issue here is the positively spectacular rate at which Go ply trees expand. Even in the case of a go game in which no stones are taken by move 5 - three by player A and two by player B, only five stones on the board - there are already 5,962,870,725,840 distinct possible boards (well, almost - about 0.001% aren't legal possibilities, but I don't feel like doing the underlying math.)

The problem here is that modern machines crap out on the solution space without reduction techniques around move 6, and even with reduction techniques around move 20. Furthermore, moves in Go are smaller than they are in Chess - one chess move is far more significant on average than one Go move. As a result, those 20 moves turn out to not be very far looked ahead at all.

They could in fact solve 9*9; it'd just take a shocking amount of processor time. You're well into the multiple decades with a good advanced PVS or MTD(f) implementation on a high-end home machine. 9*9 might be tractable with a Seti@HOME sized effort, given modern computing, but single or small-cluster setups are just totally outclassed by the massive size of a Go board's move space.

Re:Ridiculous.

[stonecypher]

Ok, the position evaluation needs Benson's algorithm to identify unconditionally alive stones, for which 100,000 positions per second is a realistic pace.

No, it doesn't. Ply trees are only concerned with boards which are won, boards which are lost, and the distance to either. Because a solution is a complete expansion, one need not be concerned with the actual score during evaluation; only with finding all achievable states and state loops. The hell with scoring the tree; the building of the tree is the difficult part, and the scoring of the board - which you correctly point out is expensive - need not be considered during the tree solution.

Once the tree and loops are identified, then one can begin evaluating the solution with something like Benson's. Still, that's not nessecary for a solution; a solution just means you know every possible consequence, not that you have an opiunion on which consequences are superior. (This is a critical distinction when one gets into games where the needs of the two players are not matched, where there are multiple possible game states, or when information is imperfect.)

To solve the game simply construct the tree. Don't worry about scoring the boards; just know what boards are reachable.

Re:Ridiculous.

[stonecypher]

This is entirely a matter of perspective. By and on the whole the person which already replied to you is correct; I intend to provide contrast in the hopes that this can be made more visible.

In the most literal sense, Alsee is correct to point out that the game state includes literally everything of value to the game. So, the question is in effect tautological: if the history of the states of the board matters, then that history is part of the current state.

Another viewpoint which is popular is to answer that in terms of its reverse observation as cyclics: if the game cannot cycle, and if there is no chance, then the history of board states is the sole determinant of the current board state, and therefore in such a game an understanding of the history is effectively an understanding of the current state. Games where tokens are added with no mechanic for removal, such as pente, tic tac toe and connect-4 would fall well within these boundaries.

That said, I choose to answer your question from a different viewpoint, because I believe you're asking something else based on slightly flawed understanding of the game theory terms in play. This is a guess; I could be wrong about what you mean.

As I see it, what I suspect you're asking is whether current board states can be interfered with by how those board states were achieved. The answer to that question is a resounding no for every game, but a strong yes for agents. Remember please that the rules of the game are usually less important than the behavioral characteristics of the people playing the game. For example, Connect-4 solves to a second player's win, guaranteed; still, the way most people play, player 1 appears to have a large advantage for first play.

The game state is oftentimes more than just a board. By comparison, the game state for poker includes not only the cards on the table and in people's hands, but also the amount of money held by each player and in the pot, the size of the current raise, the check position, where any blinds are, whether wilds or special rules are in play, et cetera. Therefore, it really doesn't matter how we got to our current position: if I have cards a..e and you have cards f..j, if I have X money and you have Y money, and it's your turn to bet on such-and-such a raise, then there's no real variance based on how we played earlier in vantage or available opportunity.

That said, I chose poker carefully for this example because the notion of a card shark is prominent and easily associated with, and there are movies to which I can refer to give a sense of method. One common tactic for a poker shark is to lose for the first 45m-1h of a game, not horridly but measurably. This has two effects: one, the other players are (sometimes) fooled into thinking there's a mark on hand to be bled, and two, the player has a chance to inspect his/her opponent's tells.

There's a good example of this behavior in the Mel Gibson movie Maverick, in which the main character openly promises to lose for the first hour in order to gain access to a table. The proposition was in essence to pay for the privelege of playing, but what the character was up to was learning his opponent's poker faces so as to better read them, and to ditch any appearance he might have had of skill in order to sweeten that speculative big pot. There are similar examples where players who inspected early chess algorithms made bad moves to poison the algorithm's impression of the player, leading the algorithm to respond wrongly thereafter.

So in the technical sense, if it affects the current game it's not history, it's part of the game state, so no. In the literal sense, the history is the creator of the state, so yes. In the realistic sense, the game state no, but the players yes, oftentimes very importantly so.

I'll try to enlighten you...

[hummassa]

exp-time-complete: the time to solve one particular problem for an input of size N is no less than O(2^N) time units.
exp-space-complete: you can solve one particular problem in less then O(2^N) if you calculate all the solutions and try to keep all the O(2^N) results around, wasting an enormous amount of storage.

Re:I'll try to enlighten you...

[NoMercy]

Might be worth noting to the layman that O(2^N) in both time, or space are almost totally impractical for large N (100 is huge to O(2^N), just concider how many places you can go in a 19-19 go game...)

The practical impossibility to use the same methods applyed to chess for a go board any decent sized go board draws AI programmers to the game, in particular using things like neural networks in combination with other tricks to focus on areas, spot possibilities without relying on precise calclation of moves.

Somewhat exciting, but hey, even the simple computer go players beat me hands down :/

I looked it up, no.

[Eunuch]

Look at the mathematical rules I wrote. If you have equal amounts, whoever goes first will lose because that person will have no move left.

Re:I looked it up, no.

[endersdouble]

OK. Think of this, in 4x4 Go. Yes, it's uberly trivial. Yes, this'll never happen. yet, it is a tied game--move passing or no. X is black, O is white, - is nothing. -O-O 0000 XXXX -X-X Assume equal captures. Each side has two points of territory. Any move in this state is instantly captured. No matter what, the game is over and tied. And while it's not *likely* to occur, it is *legal.*

Re:I looked it up, no.

[endersdouble]

Hmm, I'm an idiot who didn't think to *preview.*

Try that again. X is black, O is white, - is nothing.

-O-O
OOOO
XXXX
X-X-

Assume equal captures. Each side has two points of territory. Any move in this state is instantly captured. No matter what, the game is over and tied. And while it's not *likely* to occur, it is *legal.*

Re:I looked it up, no.

[Shai-kun]

White wins in this case: because black begins, white gets a certain amount of points added to their score (5 moku on a 19x19 if i'm not mistaken).

Re:I looked it up, no.

[endersdouble]

This is true... OK...I have no idea what the correct score bonus is on a 6x6 board is. Let's say it's 1.

O-O-OO
OOOOOO
OOOOOO
XXXXXX
XXXXXX
X-X-X-

Happy? Now black has three territory, white has two...and the bonus equalizes it. I don't claim ties are likely. BUT THEY ARE POSSIBLE.

Re:I looked it up, no.

[Chundra]

Usually the bonus is an odd multiple of 0.5 so ties don't occur.

To put this in perspective for non-go players...

[GrpA]

Since computers have started to beat strong chess players, it *is* taken for granted by many that computers can beat reasonably strong people with today's processing power.

Presently, if a typical geek started playing Go, they would get their ass kicked by the weakest computer for a week or two.

After a month, they would be winning the odd game, if the computer gave them a 3-stone headstart. (Like 3 free moves to start in chess).

After three months, they would win some games in an even match against the weaker programs (Turbo-go)

After six months, they would be winning against a 3-stone or higher handicap for the computer.

Then they find a stronger Go program.

They start to lose every match again.

After another month or so, they start to win on the weaker levels.

Take it six months ahead, and they are smashing the computer in an even match with no handicap, playing white (white moves second) or at lower levels against a 3 or 4 stone handicap.

The only thing that makes the game playable against a computer is that Go has an incredible handicapping system that lets uneven players play against each other.

So what makes this story interesting? Aside from the brute strength issue?

The first moves of the game, often in the corners in roughly a five-by-five area (Joseki) are only recently being evaluated for best move potential...

That can affect the outcome of professional matches played for big $$$$.

But more importantly for people like me, I can't play humans much... Kids, wife and home environment mean I can't spend 30 minutes undisturbed, so playing against human opponents is out for me.

Any technology that makes computer programs stronger, improves algorythms or makes me play harder will keep my morning bus trips interesting.

Because Go programs have got a long way to go if they are easily defeated against a human opponent with just 1 year experience.... Who would be easily classed as a novice let alone just a weak player.

GrpA

Isn't Go solveable?

[Qrlx]

I don't mean in terms of computation power, I mean in a theoretical way. As in, it can be shown that Go can be solved, even if we cant='t solve it.

I don't know much about these sorts of things... practically nothing in fact. Now, we all learned as kids that tic-tac-toe (or Naughts and Crosses if you prefer) is closed or solved or whatever the right term is... whoever goes first always wins, so long as they go right in the middle.

It seems pretty clear to me that if the solution in the 5x5 case is to put the first stone right in the middle of the board, then my money's on the same move on a full-size board. Because of the way Go works, the center square has the highest "potential" for liberty in that it's equally capable of finding that liberty in any direction. (Conversely, the worst first move is the corner.) I have a hunch that going anywhere else is more of a dead-end move... just like in Tic-Tac-Toe, only we don't learn this, brute force, from the older kids on the schoolyard.

(Wait... Did I miss something? I thought the solution presented in the 5x5 game had black's first move at the center. If that's not the case, consider this an exercize in rationalization, facts notwithstanding)

Re:Isn't Go solveable?

[Anonymous Coward]

[...] tic-tac-toe [...] whoever goes first always wins, so long as they go right in the middle.

Alright, you played "O" in the middle. Here's my move:

X . .
. O .
. . .

Go ahead and beat me in a tic-tac-toe correspondence game through slashdot.

Re:Isn't Go solveable?

[Anonymous Coward]

it doesnt matter where u make the first move on tic-tac-toe, it should never be won..
if u think for one second before you mark next you would see that...
only a fool would lose at tic-tac-toe..

Re:Isn't Go solveable?

[isometrick]

What if you are motivated by political reasons? :-p

Re:Isn't Go solveable?

[gordo3000]

you missed a couple of other things, namely that tic tac toe has a completely different solution, guaranteed draw if both players make correct moves. you should go back to your Tic Tac Toe games. If you were always winning by playing center, it was because your opponents were making major mistakes. And if you lost because your opponent led with the center square, well, you need to go back and study your "brute force" method.

btw, if I remember correctly, the proper response to a center move is to take a corner. That way no matter X's repsonse, you can always block while setting up a 2 in a row. This forces x to make certain moves and the game ends. slightly more interesting is to actually take a corner as your starting move. It leads to a slightly more complex board that can fool people in the beginning.

Re:Isn't Go solveable?

[Anonymous Coward]

Now, we all learned as kids that tic-tac-toe (or Naughts and Crosses if you prefer) is closed or solved or whatever the right term is... whoever goes first always wins, so long as they go right in the middle.

Didn't you learn anything from WarGames?

Re:Isn't Go solveable?

[Anonymous Coward]

If player 1 starts in the corner and player 2 does not take centre square, player 1 can always win by taking the position for which player 2 cannot create a potential winning line.

Re:Isn't Go solveable?

[Nrlll9]

eh of course it can be solved. there are a finite number of states.

Re:Isn't Go solveable?

[Anonymous Coward]

Unfortunately, just having liberties isn't enough, eventually your opponent will surround you. So how do you stay alive? If you have a single liberty completely surrounded by your own stones (called an eye), your opponent cannot play there without capturing your stones, because his stone will be captured. So in order to capture your group of stones, he will have to remove every other liberty, then play the eye last. Now imagine if you had two eyes. Making eyes is the key to living.

It takes less stones to create an eye at the corner or edge of the board than in the centre (try it!). So on a full-sized board, a stone more than about four lines from the edge will find it hard to make eyes. For that reason, the centre is not a common opening move, although it is seen from time to time.

Re:Isn't Go solveable?

[Anonymous Coward]

Good starting points on a full size board are not the center, but between 3 and 4, sometimes 5 lines from the corner.
This is because it's easier to live in the corner.
Actually the 3-3 point is guaranteed life in the corner (if continued correctly), but if you start with the higher points you get a greater area if you can defend it.
Now the center point of the 5x5 board is the 3-3 point for every corner... That means that white, playing second, will not get a living group.

Re:Isn't Go solveable?

[Shai-kun]

This of course ends in a tie when both players play perfectly. The move to at least not lose:

X . .
. 0 .
. . 0

Nope

[Eunuch]

Passing need not be mentioned. The page mentions that.

Re:Nope

[Anonymous Coward]

It clearly needed to be mentioned, because your loss condition is false.

Re:Not "one quarter"

[Dogun]

You don't, it's 19x19.
but yes, 1/16th is reasonably close.

2 x 2 Chess?

[rutabagaman]

I don't know where that 2x2 chess comparison came from, but heck..I can solve that: take the guy's king with your king. Done.

Re:2 x 2 Chess?

[eboot]

Actually you can't take a king with a king, a king cannot even exist in the adjoing spaces. In fact if you attempted to set up such a game Chess itself would be destroyed!

OLD news

[UlfGabe]

I definitely heard about this a long time ago, i think the same guy is working on a 9X9 version working up to the 13X13 and eventually to the 19x19? version.

its a goodo accomplishment, but only if they could crack ARIMAI (spelling mistake.) it is much harder to beat, even on the most difficult setting i can still beat the computer easily with funky tactics.

2x2 chess?

[slavemowgli]

2x2 chess... the new reform chess variant?

GOTI@Home?

[buckhead_buddy]

My fascination with solutions to these games is not really what they are, but how they developed. Of course the verification is boring since its simply brute force, but I do like strategies that have some clever evolution or a clever implementation.

A multi-user network client to "solve" Chess or Go might produce some fascinating results or verifications. Is there a way we can contribute our space CPU cycles to the end of these game as we know it?

Re:GOTI@Home?

[ryancerium]

Probably not. The amount of computational power necessary to solve go likely doesn't exist in the world today. You can only add millions of computers to a GOTI network, which cuts the time needed to solve from trillions of trillions of years to billions of trillions of years. Not much help there in any realistic sense.

Reading skills??

[Anonymous Coward]

He said "similar in scale" not "similar in solving time".

Pattern recognition

[Anonymous Coward]

Eventually we may have the horsepower to brute-force win every game at 19x19 but I wonder if it might be more economical to program computers to play the same way that people do. (The father of one of my friends seemed to have all of Alekhein's games memorized. We couldn't do anything that he hadn't seen before.) By using pattern recognition we might be able to get a more capable game sooner. You wouldn't have to store all possible games; only the good ones. If someone blunders while playing the computer and produces a game it hasn't seen before then it could probably win by brute-force calculation. If someone does something different and wins then the computer has another game for the database. The game is symmetrical in a way that chess isn't and that would reduce the number of games stored by a factor of at least four.

Seems kinda obvious so there must be something wrong with it but I'm not sure what it is.

Re:Pattern recognition

[Anonymous Coward]

The game of chess is much simpler than go - there are less places, less pieces (even if the complexity is bigger as the pieces have different capabilities). However, the "store space" would be quite a lot larger, and it might be too much even for a gifted individual.
However, even if the memorization works against beginners and advanced, it won't work against expert players.
I read a story some time ago, about a chess player (a junior chess player, at like 16-17 years) that won a tournament in Hungary as the game was drawn into a position that he and his trainer developed three years ago. Even if then he lost, at the tournament he managed to win.
So memorization is good for chess played at quite high levels. It might help at go also, but I wouldn't bet on this

I find it rather illogical

[Dr. Max E. Ville]

So if I solve 3x3 chess it's greater achievement than this? OK, I SOLVED IT! Solution is: you have to be a fuckin moron to play 3x3 chess! Mod me as genius.

Re:To put this in perspective for non-go players..

[Anonymous Coward]

Hi

Sorry to hear you can't really play undisturbed as much as you like. I'm in a similar position at times and hence I've started playing go at http://www.dragongoserver.net wich is a sort of korespondance go. You play long lasting games at perhpas as little as one move per day or less (logging on and off in between).

I tend to play a few moves at breaks or inbetween idleing on the net.

Hope to see you there... :)

You can pass

[kulpinator]

http://gobase.org/studying/rules/?id=2&ln=uk

hypertext

[morcheeba]

I hear they are working on a "hypertext" transfer protocol -- it's kindof like Apple's hypercard where you can "link" to various media in a free-form manner. A "mouse" is used to select which links to follow, and the transport protocol sends the appropriate network packets to retrieve the data.

Re:hypertext

[TLSPRWR]

Using this technology, I've created the "one-click shopping" technique to create webstores!
I should probably patent it before someone else does...Nah, I'll wait and see if it takes off.

Um...

[brsmith4]

I don't know whats worse: a dupe or a story thats almost 3 years old... I certainly hope the editors aren't paid to do what they do. You subscription holders should really rethink your purchase.

You can pass at any time - this is important!

[damm0]

It does need to be mentioned. I've never seen the rule that if you can't put a piece down eithout breaking the rules, you lose. You can always pass.

5x5 is way too small

[Anonymous Coward]

A 5x5 board has 25 tiles, each of which has three possible states: empty, taken by black, or taken by white. Thus, in total there are 3^25 = 847,288,609,443 states. At 1 billion operations per second even the brute force solution would take only several hours. What exactly does this article prove?

Re:5x5 is way too small

[mikera]

The ko rule means that you can't just solve for all possible board positions, you also have to consider previous states of the game.

This makes things quite a lot more complicated....

Improved Rule for Suicide

[Anonymous Coward]

The Rule for Suicide: Suicide is illegal. Attempt to suicide shall be punished with immediate execution.

They needed a news posting to show life

[EmbeddedJanitor]

The last news was probably "go invented" dated 2500BC or whenever.

Go is to scheme...

[Anonymous Coward]

as chess is to perl.

Go and scheme have very few operators and therefore allow more creative freedom of expression.

Re:Go is to scheme...

[WillerZ]

Your post is to insightful what this story is to news.

Yes, there can be a tie.

[Anonymous Coward]

The number of spaces each player occupies are integers, so there can be a tie. BUT! In order to forbid that, modern go gives 5 and 1/2 points (or 6 and 1/2) to white, so that the black has to have occupied six (or seven) more spaces to win -- that should compensate for having the second hand in starting the game (with 6 1/2, the black is known to win in 52% among the pros, so that is gaining more support). So in effect, a tie is made further more unlikely. I say unlikely because still there is another possibility for a tie: it's called jang-saeng in Korean (I don't know the name for it in Japanese and Chinese) which is a repetition of a pattern that is actually allowed (more strictly, not disallowed) by the rule of go. It is so unlikely that among the millions records of go games accumulated in those countries during several millenia (yes, millenia!), there is only ONE game that ended in a tie by jang-saeng.

And to answer some of you guys, just keep passing to tie intentionally is a stupid thing to do and is not allowed anyway. I would happily win.

OMFG

[mcc]

Therefore 2x2 chess would start with checkmate and is absurd.

YOU'VE SOLVED IT!

An Idea

[spud603]

I have been interested in computerized Go for a while now, but have never actually gotten my feet wet in the subject.
One approach I have always wanted to try is this:
set up a massive neural net that takes the state of the entire board as input, goes through way too many intermediate layers, and spits out a preference for spots to play. The state of the neural net could be exhaustively described with a few tens of thousands of [0,1] doubles.
Then set up "breeding" algorithm, make a few hundred instances of the program, each with its own neural net, and then have them pretend to be users on an internet Go site. Don't try to understand how they play, just let them figure it out. You could even, on occasion, let them play eachother...
I don't know if this would produce a good genome ever, but I'd be interested to see where it went regardless.
Does anybody know if this sort of thing has been tried before?

Re:An Idea

[jrtom]

Something like this has been tried; Pierre Baldi has worked on neural network approaches to playing Go. I don't know how much progress his group has made on the problem, though.

Re:An Idea

[Flyboy Connor]

Markus Enzenberger's NeuroGo implements a neural network to play 9x9 Go. The program is reasonably strong, but no match for the more traditionally designed programs.

Re:An Idea

[Anonymous Coward]

Dunno about for Go, but this has been done for checkers and produced a very good opponent. Obviously Checkers isn't in the same league as Go when it comes to complexity. An interesting read anyways...

http://www.cs.nott.ac.uk/~gxk/courses/g5baim/paper s/checkers-002/TNNKChellapillaAndDBFogelText.pdf

Re:An Idea

[dh5fbr]

Not to forget SapioGo http://www.ryanflannery.org/works/go/.

My personal opinion is that the way you describe is the correct solution. My personal experience is, that there are still a number of problems in there.

You are right as you wonder if it EVER will breed a good genome, especially as even a good attempt of genome will be equally crushed as a real bad genome. So a good rating function is the first necessary step.

I guess you have to do some sort of learning, input simplification with breeding in controlled surrounding (playing on the server like using KGSGTP is probably only at the end of the road, like after it doesn't emberrass itself by playing stones on top of existing ones or putting onself into atari).

Write me if you want to team up...

Re:An Idea

[Anonymous Coward]

My first impression is that this would be really bad at go, for any size neural net you'll be able to run in the next 20 years. That is, if you used only a few layers, it'd run fast enough to try, but it would be really weak; if you used enough layers to make it conceivably good at go, it'd take years to do the simplest thing.

Based on what I've seen neural nets do, my guess is it could get good at identifying rough shapes (walls, loose shape, bamboo joints, tigers mouths), but still lack skill.

Imagine a player who knew only the rules, and some general shapes. He'd get beaten by anybody who knew joseki, or go problems, or any trick plays. Heck, take white and play mirror go -- a neural net would have to be *huge* to figure that one out.

Neural nets are good for some things, but to encode enough smarts to play go well would take a mind-bogglingly huge net. There are much more efficient ways to encode go-playing ability.

Sorry. Interesting idea, but I don't see it panning out. (Which means: If you believe in it, convince me!)

Re:An Idea

[Anonymous Coward]

Your idea has been used on checkers, and more recently on chess as well. Google "Blondie24" to read about the full story.

AI

[Anonymous Coward]

Actually (all joking aside), I would question if programming a computer to play chess (or go for that matter) is actually heading towards AI.

In essence, it isn't much different than a computer playing pong. Only the level of complexity has changed. In a very real sense the computer isn't playing chess; it is regurgitating moves.

And suppose a perfect solution to chess had been found. Would it still be a game? At that point, it has become one-dimensional. Not to detract from the inventiveness of the algorithm, but the computer didn't devise the algorithm. It is still executing code without a means to not execute the program (as I can choose not to play).

Just musing on the nature of AI.

Re:AI

[Theatetus]

First, I'm glad to see at least a few people got the joke.

Secondly, I definitely agree with you. I think both go and chess programs are taking the less interesting route by doing dictionary / exhaustion algorithms, since that's not how humans play either game (in most circumstances -- openings and endgames are another matter).

Sticking with chess (since I know it better, and I think the lesson carries over), I think Kasparov really exposed this flaw in his second game against Fritz. If you completely seize the initiative from an algorithm based on exhaustive move analysis, it is helpless until you make a mistake. Even the most amateur human player would have said "he's making me look stupid; I have to do something". People play games like go and chess by setting out objectives and performing a basic analysis on the moves that further those objectives, calculating risks based on that analysis, and choosing the next move. I would love to see a go- or chess-playing program based on that model.

Also Posted AC to avoid karma whoring

[Anonymous Coward]

Seeing as you're stupid, um, well, that's all.

I wrote the first commercial Go playing program

[MarkWatson]

Honinbo Warrior was coded in UCSD Pascal and really did not play that well, but my boss and a few friends talked me into running ads in some Apple II magazines and marketing it. Working on that program was a fun obsession that lasted about 1 1/2 years.

Go is such a great game. In the 1970s, I got to play exhibition games with Miss Kobyoshi (women's world champion) and Mr. Lee (national champion of South Korea). The high level of their play really blew me away - getting slaughtered was a surprisingly great experience.

The Gnu Go program plays a good game, BTW. It is best to play against human opponents, but give Gnu Go a try also. Just like studying chess, if you get into playing Go, make sure you study complete master games: studying opening, middle game, and end games in isolation just does not cut it.

Even more perspective.

[cwills]

To put this into even more perspective

In go, players can be given a rank on how strong they are compared to others. It's a fairly simple method.

Everyone starts out at about 30 kyu. As they get stronger, their kyu number decreases till it gets to 1 kyu. At which point starts a new number system that goes upward, starting at 1 dan and goes to 9 dan.

So..

30 Kyu, is weaker then a 29 kyu,... 2 kyu, 1 kyu, 1 dan, 2 dan, ..., 9 dan.

Now that is for amateur rankings. There is a professional ranking system that starts at 1 dan pro and goes to 9 dan pro. I have heard that a 1 dan pro is roughly the same strength as a 7 dan amateur.

There is a handicap system where if you take the rankings of two players and subtract them, it determines the number of handicap stones given to the weaker player. Thus a 10 kyu playing against an 8 kyu, the 10 kyu player gets to play first by placing 2 stones on the board (one set of rules allows black to place the stones anywhere on the board, another set of rules, the stones must be played at specific spots). The rule of thumb is that each handicap stone is worth about 10 points. Another rule of thumb is that each handicap stone "erases" one mistake by the weaker player.

Normally one doesn't play with more then a 9 stone handicap. Mainly because beyond 9 stones, black really isn't "learning" much

To prevent ties, a half point is awarded to white in handicap games, in an even game (where both players are of equal strength), white is given 6.5 points (this has been changing around some -- depending on the rules you are playing with).

Usually after the 1st game or so a 30 kyu player learns enough to drop to around 28 kyu or there abouts.

I have heard that the amount of time and study to go from a 10 kyu to a 1 kyu rank is about the same as going from a 1 dan to a 2 dan.

A game between two weaker players can result in scores of anywhere from just a few points to 100's of points going to the winner. As one gets stronger, the wins are usually only a few points, or someone resigns.

I have seen strong dan and pro players when playing weaker players their goal is to try to get the score within a half point (always in their favor).

In Go, the game really doesn't start to get interesting till about 30 to 50 moves into the game (in chess, the game is usually over at that point).

Currently on one of the online go playing servers, GNU Go (among the top go playing programs -- though not the strongest) is roughly around 11 kyu in strength, A weak dan player can give gnugo a 9 stone handicap and the dan player will still win.

Several years ago, Janice Kim gave the top go playing program a 28 stone handicap and she still won the game (I believe it was a 28 stone game).

To get to a professional level player, it is best to start playing when you are very young. Expect to dedicate your life to the game. To get to a strong amateur dan level, also expect to dedicate a good chunk of your life to the game.

Comparison between Chess and Go

[J_Omega]

I'll admit that I'm a wide eyed enthusiast, but I'll also delimit that with acknowledgement of the fact that I'm one of the last pasty white guys in the West to have discovered it.

I wish I had been introduced to Go as a child. I've only been learning for a month now, and I'm obsessed already. I've completely given up traditional computer games, unintentionally... its friggin' GO. I like chess, and play when I've free time... but Go is making me make time for it!

That being said, I'll let someone else descirbe the virtues of go with a comparison to chess:
http://users.eniinternet.com/bradleym/Compare.html

Mod Parent as "funny"

[J_Omega]

There is no computer program that is able to beat a high-ranked amatuer, let alone a professional go player.

Aside, you meant 19x19, I hope...

2x2 Chess

[gnovos]

Not QUITE that scale...

Two by two chess:

White: Checkmate in 0, would you like to play agin?
White: Checkmate in 0, would you like to play agin?
White: Checkmate in 0, would you like to play agin?
White: Checkmate in 0, would you like to play agin?

Re:2x2 Chess

[Kehvarl]

wouldn't that be:
White: Checkmate in 0, average moves per game: ERR!
Play Again? [Y/n] Y
White: Checkmate in 0, average moves per game: ERR!
Play Again? [Y/n] Y
White: Checkmate in 0, average moves per game: ERR!
Play Again? [Y/n] Y ...

Roshita Go

[gnovos]

Roshita Go is similar to Go, but done in the Roshita Style:

Both players have a supply of "stones" which are actually compressed sugar. One of them is posioned.

Each player takes turn placing pieces on the intersections on the board.

Any player may "capture" an opponents piece by eating it.

There is no draw. Each player must place pieces on the board, anwhere on the board, when it's thier turn, even if all the spaces are filled up.

The first player to die loses.

Death does not have to be by posioning.

Re:To put this in perspective for non-go players..

[Sinner]

I can't help thinking that if you spend 18 months learning to beat a computer at Go you're still gonna get your ass handed to you the first time you play an actual human being. Even if the computer players are strong, don't they lack "personality"?

I suppose I have a hard time understanding why someone would devote that much time to learning to play against humans, much less a computer. Not that I'm claiming I spend my time any better (which would be absurd, seeing as I'm posting on Slashdot!), but what is it that you get from playing Go?

Strength ref : Gnugo is within a 6 month reach

[tototitui]

I started to play from scratch 5 months ago dedicating around 1 hour per day for go.

Now I beat gnugo with no handicap more then 50% of the time.

On KGS (http://kgs.kiseido.com/) I'm 14 kyus only.
Gnogo is around 12-11kyus on the same scale but I think the last stones are compensated by the fact I subconsciouly know which patterns gnugo are unable to handle.

clarification

[Deternal]

Now that is for amateur rankings. There is a professional ranking system that starts at 1 dan pro and goes to 9 dan pro. I have heard that a 1 dan pro is roughly the same strength as a 7 dan amateur.

Actually the amateur rankings only goes to 7 dan - however since the pro's goes up to 9 dan some systems use that for amateur rating too. Anyway a toplevel amateur is regarded as a little below a shodan (1 dan) pro player.

Go 6x6 was solved some time ago already...

[Domini]

...or am I mistaken?

http://senseis.xmp.net/?SmallBoardGo

Also, 19x19's complexity is in the order of 10^500 and chess about 10^54.

But chess has more rigour as the unnecessary (debatable) obfuscation build into the game through the arbitrary complexity of the moving pieces, thus making it more difficult to get past the tactics to the strategy. Go, on the other hand, has a very simple rule-set similar to finite automata which lends itself easily to the human thought process, making it easy even for a beginner to be able to see dozens of moves ahead and get caught in it's rich strategy.

I am not debating 'which is better' here. If your into rigour and tactics, chess is your game.

Chess is the battle, go is the war.

A couple of errors

[Flyboy Connor]

The American Go Association is reporting that Go for the 5x5 board has been solved by the computer program MIGOS, reports the program's creator, Erik Van Der Werk,

His name is Eric van der Werf.

a professor at the University of Maastricht

He is not a professor. He was a Ph.D. student. He received his Ph.D. title January 27 of this year.

in Holland.

That should be "The Netherlands". Holland is part of The Netherlands, but Maastricht is not located in Holland.

At about a quarter of the full-board version, 5x5 go

That's about 1/14th of a full board (25 points as opposed to 361 points).

is miniscule, similar in scale to "solving" 2X2 chess.

It is similar to solving 5x5 or 6x6 chess.

The fact that a programmer

Calling Van der Werf a "professor" is a bit too much, but calling him a "programmer" is not enough.

would even consider this a noteworthy challenge is itself a remarkable testament to the game's complexity.

Basically, it was not done before, and could be done with a couple of weeks computation time. That's not to belittle Eric's work; it is only a small part of his work. Read his thesis to see what he has done for the field of Go research.

Van Der Werk's

Again, it is "Van der Werf".

approach is described in detail in an article at the Netherlands Organization for Scientific Research (NOSR).

That should be NWO, not NOSR, and the approach is not described in detail in the article. For details, visit Eric's website.

Re:A couple of errors

[ControlFreal]

His name is Eric van der Werf

That would be Erik van der Werf, but ok ;) It's amazing how our puny Windows department webserver stood up to the slashdotting...

Re:A couple of errors

[Anonymous Coward]

I agree with the size. I'm a 1 dan Go player (been playing for 18 months) and a real go board is over 14 times larger than a 5x5 size board.

The good thing bout Go is that computers cant brute force it so it takes some talent and Go knowledge to even get to the level of 5x5 through programming as opposed to chess where the bigger the computer the better the AI :p

Re:A couple of errors

[Anonymous Coward]

After all those errors, the conclusion can only be that either the article submitter is a retard, or he's playing the "fool the slashdot editor" game, as proposed earlier in the discussion. I wonder how many points those errors are worth?

Yeah, but

[WillerZ]

Real players don't play with the super-ko rule.

Re:2x2 chess is...

[0zymandias]

Actualy, 2x2 tic-tac-toe is rather hard.

It took me *hours* to get three in a row.

So, how to begin playing go?

[GozzoMan]

Some time ago I tried to pick up go, basing on the faq of a dedicated usenet group (sorry, I don't remember which one right now).

I found it all rather confusing, since it went immediately through the different sets of rules (some rather complex), while I had made the opinion that the power of Go is that it can be played with a very small rule set but still offering a lot of possibilities during play (which imho is what make great games, well, great). Am I wrong?

So, how (I mean basing on which document, tool or else), oh sage ./ers-goers, do you suggest I begin again?

Thank you.

Re:So, how to begin playing go?

[dh5fbr]

Hi,

try to be able to count liberties (remember you are sitting on the stone with your bicycle and only can leave it along the lines). Then finding out what a group is and when it has 0 liberties should be doable. After that you are basically set and can play.

There is, however, one "confusing" additional rule, the ko-rule, which basically states that I can not do a move so that the whole board (meaning every spot of it!) looks the same like two moves ahead. If there would be no ko-rule a (ko-)fight over one important spot would go on forever. (One would take out a stone, the other back, etc.).

People will want to explain you about Josekis, Empty triangle (DO NOT PLAY THEM!), Influence, Aggressive, Defensive play, Ladders etc. Listen (to be polite) but don't worry about not understanding.

Keep on playing your game by counting liberties and trying to figure out your personal strategy. It is proven, that all the other "rule-sets" can be discovered naturally. (Better start playing on a 9x9 board!)

Well, the previous said, I have to speak about he rule set as how to decide, who won the game. On a 19x19 board the one moving first (black) has an advantage, with makes a komi (points added to whites score at the end,6.5 is a good value). The amount of komi differs in the different countries rules, so does if only the empty spaces or also the stones itself are counted. BTW in 99% the cases neither difference matters for your (beginner) games - the same person would win. By the time it matters you will understand it easily ;)

The opligatory link: http://gobase.org/

Re:So, how to begin playing go?

[DrJimbo]

The Interactive Way To Go is a great place to learn the basics. You can learn more here and here. The Sensei's Library is a wiki with a lot of interesting but scattered information.

At some point you should probably buy some books. There is a very complete Go Bibliography that will help you pick out books to start with. I suggest the Learn to Play Go series along with the Graded Go Problems for Beginners series.

From the Sensei's Library you can get links to find Go playing programs and also Go servers that will let you play go on the internet with people from around to globe.

Re:So, how to begin playing go?

[Anonymous Coward]

Ooo! As a go fan I love to hear questions like that.

I have been playing "go" for about 2 years now. I taught myself. I was confused about what was going on and how to motivate play for a while, so don't expect it to be easily grasped immediately if you are trying to pick it up without someone to show you.

The approach I took was two-pronged:
1) download a free opponent off the web.
a. The one I use currently is GnuGo. It has 10 difficulty settings (10 hardest). I started on '3'. GnuGo is a back-end, you also need a GUI - I use JAGO. I run them on my windows box. I use cygwin to do it. Getting them installed can be kinda tough, but you can figure it out with online resources. If you install cygwin there is a checkbox to include GnuGo somewhere.
b. When I first started to play, however, I used an easier opponent than GnuGo (just for a week or 10 days). I forget what it was called, however. It was a free demo for a commercial program. I initially found it after scant moments of searching, so I am unconcerned about your ability to pick one up for free.

2) Read a book.
a) I bought one at Barnes and Noble for $8. Sometimes it is hard to find them in stock, but there are 3 or 4 that show up in stores from time to time.
b) Free downloadable book here: http://www.usgo.org/usa/waytogo/index.asp
It is short, however, and I would expect one to want more. Other intro books I have seen had a bit more to them.

Go here for more resources / info
www.usgo.org

Eventually you'll need a set. Games by James at the local mall has cheap ones ($12). More expensive ones can be ordered online - find merchants at the www.usgo.org resource.

Local Go clubs can be found through the usgo link as well.

When you have developed a bit the most accessable online play can be had at yahoo games. Cheating is rampant, however. More hardcore play can be had at KGS.

obligatory emacs link

[10am-bedtime]

i wrote some elisp to play GNU Go in an Emacs buffer. check it out! (fishing for bug reports; patches welcome.)

see also: GoMode (emacswiki)

"Go Blip"

[Anonymous Coward]

A variation on Go for players with vastly different skills is to play Go by all the regular rules except the following: The weaker player instead of placing enough stones on the board to make it an even game places enough stones on the board to prevent the better player from creating any viable territory whatsoever. So the strong player's first 20 moves or so are all around the board using his better sense of strategy, while the weaker player responds tacticly to each move and doesn't have a feeling of being overwhelmed. I played this "Go Blip" thousands of times, and it's unsymmetrical play helps the weaker player from being embarrassed at losing since he's trying to beat his own best score of how few initial handicap stones are needed to stop the other from ending up with any viable territory.

Go and Chess compared

[^DA]

http://users.eniinternet.com/bradleym/Compare.html

Scroll down to see a point by point comparation.

Re:To put this in perspective for non-go players..

[dh5fbr]

# but what is it that you get from playing Go?

Beside keeping your brain active (after all you need to continous learn), another property is worth spending the time. In Asia the "balance-of-things", which is tought by Go also highly tributes to the recognition of the game worth to be known by most of Japan's executive business men.

To give an example, and to comment on the real achievement of solving 5x5 Go, the smaller the Go board the more importance has your tactical skills. Like in chess the "reading moves ahead". I might say although the program used learning it might well be to have "just" found a good way of storing positions - never mind to do real strategy. Because on bigger boards (starting 13x13) strategy is another key issue. Finding the balance is the real key to mastering Go. Like in real life you can't get everything in one go, but sometimes allowing the other to win a tactical/local battle, will bring you forward in the big strategy. Hence Solving 5x5 Go misses out a most of the finer skills a real 1 Dan player needs to master.

You asked what it is worth, well, gaining real life experience will teach you that sometimes achieving a goal means holding the balance between different things. But it will so at costs, I like to put forward, that if you master Go, you will be able to skip some of the less pleasurable real life failures.

BTW these points are also made in The Way of Go (Senseis library review) Amazon page

Funny sort of quarter

[Anonymous Coward]

Right so they've solved go for a 5x5 board wonderful, nice to know it has a solution.

However it does make me wonder how good your maths is as if a 'standard' board is 19x19 then this small board is approximately 1/15 of the size (a 5x5 has 25 possible places where as a 19x19 has 361 possibilities which is clearly about 15 times bigger.

so if you are going to say its 4 times bigger be more specific as the area is not just 4 times...

enjoy

"Solving"

[Anonymous Coward]

Solving a game: calculating every possible sequence of moves and storing them in a database along with the optimum move at each stage of the game.

Why is this noteworthy? It's pretty straightforward, and known to be impossible for large games ( it has been calculated by 'some physics PhD in a popular book' that to 'solve' chess using a (hypothetical) maximally energy efficient cpu it would require one to convert the mass of Jupiter to pure energy just to power the cpu during the computation - Go is even worse. People do not play games by 'solving' them except maybe very simple ones like Tic Tac Toe. I'd be more impressed with a machine that could actually reason about games, forming powerful theorems and even unproved hypotheses which are improved upon when they don't pan out. For instance, you could state a theorem about chess that it is impossible for white to lose a piece in the first move, or a general unproven hypothesis like: it's good to control the board early in the game to restrict your opponent's movements and create opportunities for your self without knowing exactly what those oppertunities will be.

It's generally accepted among chess-heads that controlling the board early is a Good Thing, but maybe, in the space of chess games, more winning strategies are actually to be found where control of the board is not gained early. That has never actually been proven, it's only a hypothesis ( or maybe a theory since it seems pretty well accepted and seems to be borne out by actual chess games ) but if say, the actual 'solution to chess' were known and it happened to be a strategy that did not cease control of the board early for most sequences of opposing moves, and that player with the 'cheat sheet' for chess played some games, then that theory of chess would quickly fall out of favor to be replaced by the new stategem.

If life is a game, then maybe reasoning itself is rooted in the need for the ability to reason about games. Deception may not play much of a role in the lives of lions and tigers and bears, but for monkeys, the current battle is many times not the war. A male chimp may kowtow to the Bluto of the troop when he's around but then do the nasty with the lady chimps behind his back.

Among humans, goals are even more veiled. The road to X is rarely the direct route. You want a candy bar, you go to the store and buy it - seems direct, but it isn't. To get the 85 cents, you go to a job and earn your money. But to get that job you may have had to obtain college degrees, or certifications, and to do that you had to compete. To get hired you had to compete, and to get promoted you had to compete. The games you participated in probably had less to do with being valuable so as to make your paycheck a good deal for your employer than with gaming so as to appear that way - especially if you have been successful in getting anywhere - nobody ever got to be boss by being a good laborer, the games you have to play to be boss take too much time for someone who spends all their effort working to compete in. Some may find this amoral, but be assured that those who are successful most likely do not even know they are useless fucks who reap all the reward.

They probably assume everyone games as much as they do and when they are rewarded they are certain it is because they really *are* more valuable and they actually think they *deserve* it. To think otherwise would offend their own egos. In fact, if your desire to masturbate your own ego does not make you stupid enough to accept the top seat with a straight face, then you either accept being 'evil' to some extent and wear a poker face, or you put your nose to the grindstone to be an even more valuable resource to exploit ( a lot of currently technical people who didn't spend all their time 'gaming' for popularity in high school because they didn't enjoy it have taken this route. Then they find that labor is labor and that they can not charge more than the third world shmoe who will charge the leas

Re:To put this in perspective for non-go players..

[Abcd1234]

Beside keeping your brain active

Actually, this by itself is a great reason to play Go. After starting to play, I've found my visualization skills have improved significantly. Moreover, it's a great way to improve your overall focus and mental stamina. Plus, it's just damn fun. :)

frelling?

[Anonymous Coward]

People who say 'frelling' are funny. I can understand why you'd want to make up a swear word for a TV program, but even then it's a kludge.

If you need an alternative F-word, why not just use 'freakin'? It's well established.

Re:frelling?

[Kippesoep]

I just happen to like Farscape. (Aeryn and Crichton are making out aboard Talyn when the ship is attacked). Aeryn: "Frell!" Crichton: "Yes" Aeryn: "No, bad frell."

THAT IS STALEMATE

[Anonymous Coward]

THAT IS STALEMATE

No no no

[Eunuch]

The counting phase is just accomplished by filling in your own territory. The first won who has to pass loses.

It isn't really normal Go

[damm0]

I failed to understand, before posting my comment, that the rules described are not how people play Go but rather a mathematics curiosity.

Thanks

[Sinner]

Food for thought.

freaking amazing

[epine]

The fact that a programmer would even consider this a noteworthy challenge is itself a remarkable testament to the game's complexity.

Brilliant. We've discovered a new scaling effect. When you reduce a game where all the pieces begin on the board, it loses complexity more rapidly than a game which begins with an empty board where pieces can be added at will.

I get a stream of far more remarkable testaments in my spambox every day.

saved

[Doc Ruby]

Oops - fixed. Thanks for pointing that out. You almost exposed us, and then you would have been stuck searching for 3-year-old unreported geek stories too, according to the curse under which we live.

Single stones

[Eunuch]

The superko rule would cover single-stone suicides. An advantage from group suicide seems very rare to me. It would seem that this rule doesn't need to be in the mathematical rules. However, it would be an easy way to cut down on brute force checking.

Re:Single stones

[k8to]

But the superko rule doesn't actually describe real go. It's a simplification that's inaccurate.

Furthermore, it suggests that the "board state" is merely the stones on the board, when in actuality it is also the last stone played.

Math rules

[Eunuch]

Whoever moves has to. The opponent then captures and wins.